Computer Science – Computer Science and Game Theory
Scientific paper
2012-02-13
Computer Science
Computer Science and Game Theory
17 pages, 2 figures, preliminary version appeared at ESA 2011
Scientific paper
We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if $\ell_e(x)$ is the latency function of an edge $e$, we replace it by $\hat{\ell}_e(x)$ with $\ell_e(x) \le \hat{\ell}_e(x)$ for all $x$. Then an adversary fixes a demand rate as input. The \emph{engineered Price of Anarchy} of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\CM(r)$ denotes the cost of the worst Nash flow in the modified network for rate $r$ and $\Copt(r)$ denotes the cost of the optimal flow in the original network for the same rate then \[ \ePoA = \max_{r \ge 0} \frac{\CM(r)}{\Copt(r)}.\] We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an {\em optimal} mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.
Christodoulou George
Mehlhorn Kurt
Pyrga Evangelia
No associations
LandOfFree
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-88325