Bureaucrats, editor, Administrators
373
edits
Changes
→Abstract
Line 15:
Line 15:
== 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
apply.
apply.
−The first part of this talk focuses on a network diffusion model
− that was recently introduced by Goldberg & Liu (SODA'13). Goldberg &
− Liu's model adapts the earlier linear threshold model of Kempe,
− Kleinberg & Tardos (KDD'03) in an effort to capture aspects of
− technology adaptation processes in networks. We present new,
− improved, yet simple algorithms for the so called Influence
− Maximization problem in this setting.
− A key component of our algorithm is a Langrangean multiplier
− preserving (LMP) algorithm for the Prize-collecting Node-weighted
− Steiner Tree problem (PC-NWST). This problem had been studied in
− prior work by Moss and Rabani (STOC'01 & SICOMP'07) who presented a
− primal-dual O(log |V|) approximate and LMP algorithm, and showed
− that this is best possible unless NP=P.
− We demonstrate that Moss & Rabani's algorithm for PC-NWST is
− seriously flawed. We then present a new, fundamentally different
− primal-dual method achieving the same performance guarantee. Our
− algorithm introduces several novel features to the primal-dual
− method that may be of independent interest.
− Joint work with Laura Sanita and Sina Sadeghian
−