Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

0.00 Avg rating0 Votes
Article ID: iaor2014928
Volume: 69
Issue: 3
Start Page Number: 619
End Page Number: 640
Publication Date: Jul 2014
Journal: Algorithmica
Authors: , ,
Keywords: networks, networks: path
Abstract:

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 𝓁 e (x) is the latency function of an edge e, we replace it by ˆ e ( x ) equ1 with e ( x ) ˆ e ( x ) equ2 for all x. Then an adversary fixes a demand rate as input. The 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 C ˆ N ( r ) equ3 denotes the cost of the worst Nash flow in the modified network for rate r and C opt (r) denotes the cost of the optimal flow in the original network for the same rate then ePoA = max r 0 C ˆ N ( r ) C opt ( r ) . equ4 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 optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.

Reviews

Required fields are marked *. Your email address will not be published.