Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
Risk in network routing games
== Speaker ==
Evdokia Nikolova is an Assistant Professor at the Computer Science &
Engineering Department at Texas A&M University. Previously she was a
postdoctoral associate in the Computer Science and Artificial
Intelligence Laboratory at MIT. She graduated with a BA in Applied
Mathematics with Economics from Harvard University, MS in Mathematics
from Cambridge University (U.K.) and Ph.D. in Computer Science from
MIT. She is interested in risk analysis from an algorithmic
perspective arising in stochastic optimization, networks, economics
and complex systems. She has worked on applications to transportation
and is also interested in energy and other domains where her work may
apply.
== Abstract ==
Network routing games are instrumental in understanding
traffic patterns and improving congestion in networks. They have a
direct application in transportation and telecommunication networks
and extend to many other applications such as task planning, etc.
Theoretically, network games were one of the central examples in the
development of algorithmic game theory.
In these games, multiple users need to route between di fferent
source-destination pairs and links are congestible, namely, each link
delay is a non-decreasing function of the flow on the link. Many of
the fundamental game theoretic questions are now well understood for
these games, for example, does equilibrium exist, is it unique, can it
be computed e fficiently, does
it have a compact representation; the same questions can be asked of
the socially optimal solution that minimizes the total user delay.
So far, most research has focused on the classical models in which the
link delays are deterministic. In contrast, real world applications
contain a lot of uncertainty, which may stem from exogenous factors
such as weather, time of day, weekday versus weekend, etc. or
endogenous factors such as the network tra ffic. Furthermore, many
users are risk-averse in the presence of uncertainty, so that they do
not simply want to minimize expected delays and instead may need to
add a bu ffer to ensure a guaranteed arrival time to a destination.
I present my recent work on a new stochastic network game model with
risk-averse users. Risk-aversion poses a computational challenge and
it often fundamentally alters the mathematical structure of the game
compared to its deterministic counterpart, requiring new tools for
analysis. The talk will discuss best response and equilibrium
analysis, as well as equilibrium efficiency (price of anarchy) and a
new concept, the price of risk.
One relevant paper is here:
http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
A short summary of the paper is here:
http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf
Risk in network routing games
== Speaker ==
Evdokia Nikolova is an Assistant Professor at the Computer Science &
Engineering Department at Texas A&M University. Previously she was a
postdoctoral associate in the Computer Science and Artificial
Intelligence Laboratory at MIT. She graduated with a BA in Applied
Mathematics with Economics from Harvard University, MS in Mathematics
from Cambridge University (U.K.) and Ph.D. in Computer Science from
MIT. She is interested in risk analysis from an algorithmic
perspective arising in stochastic optimization, networks, economics
and complex systems. She has worked on applications to transportation
and is also interested in energy and other domains where her work may
apply.
== Abstract ==
Network routing games are instrumental in understanding
traffic patterns and improving congestion in networks. They have a
direct application in transportation and telecommunication networks
and extend to many other applications such as task planning, etc.
Theoretically, network games were one of the central examples in the
development of algorithmic game theory.
In these games, multiple users need to route between di fferent
source-destination pairs and links are congestible, namely, each link
delay is a non-decreasing function of the flow on the link. Many of
the fundamental game theoretic questions are now well understood for
these games, for example, does equilibrium exist, is it unique, can it
be computed e fficiently, does
it have a compact representation; the same questions can be asked of
the socially optimal solution that minimizes the total user delay.
So far, most research has focused on the classical models in which the
link delays are deterministic. In contrast, real world applications
contain a lot of uncertainty, which may stem from exogenous factors
such as weather, time of day, weekday versus weekend, etc. or
endogenous factors such as the network tra ffic. Furthermore, many
users are risk-averse in the presence of uncertainty, so that they do
not simply want to minimize expected delays and instead may need to
add a bu ffer to ensure a guaranteed arrival time to a destination.
I present my recent work on a new stochastic network game model with
risk-averse users. Risk-aversion poses a computational challenge and
it often fundamentally alters the mathematical structure of the game
compared to its deterministic counterpart, requiring new tools for
analysis. The talk will discuss best response and equilibrium
analysis, as well as equilibrium efficiency (price of anarchy) and a
new concept, the price of risk.
One relevant paper is here:
http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
A short summary of the paper is here:
http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf
