| Line 15: |
Line 15: |
| | apply. | | apply. |
| | | | |
| − | == Abstract ==
| + | The first part of this talk focuses on a network diffusion model |
| − | Network routing games are instrumental in understanding
| + | that was recently introduced by Goldberg & Liu (SODA'13). Goldberg & |
| − | traffic patterns and improving congestion in networks. They have a
| + | Liu's model adapts the earlier linear threshold model of Kempe, |
| − | direct application in transportation and telecommunication networks
| + | Kleinberg & Tardos (KDD'03) in an effort to capture aspects of |
| − | and extend to many other applications such as task planning, etc.
| + | technology adaptation processes in networks. We present new, |
| − | Theoretically, network games were one of the central examples in the
| + | improved, yet simple algorithms for the so called Influence |
| − | development of algorithmic game theory.
| + | Maximization problem in this setting. |
| | | | |
| − | In these games, multiple users need to route between di fferent
| + | A key component of our algorithm is a Langrangean multiplier |
| − | source-destination pairs and links are congestible, namely, each link
| + | preserving (LMP) algorithm for the Prize-collecting Node-weighted |
| − | delay is a non-decreasing function of the flow on the link. Many of
| + | Steiner Tree problem (PC-NWST). This problem had been studied in |
| − | the fundamental game theoretic questions are now well understood for
| + | prior work by Moss and Rabani (STOC'01 & SICOMP'07) who presented a |
| − | these games, for example, does equilibrium exist, is it unique, can it
| + | primal-dual O(log |V|) approximate and LMP algorithm, and showed |
| − | be computed e fficiently, does
| + | that this is best possible unless NP=P. |
| − | 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
| + | We demonstrate that Moss & Rabani's algorithm for PC-NWST is |
| − | link delays are deterministic. In contrast, real world applications
| + | seriously flawed. We then present a new, fundamentally different |
| − | contain a lot of uncertainty, which may stem from exogenous factors
| + | primal-dual method achieving the same performance guarantee. Our |
| − | such as weather, time of day, weekday versus weekend, etc. or
| + | algorithm introduces several novel features to the primal-dual |
| − | endogenous factors such as the network tra ffic. Furthermore, many
| + | method that may be of independent interest. |
| − | 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
| + | Joint work with Laura Sanita and Sina Sadeghian |
| − | 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
| |
