Article ID: | iaor2014928 |
Volume: | 69 |
Issue: | 3 |
Start Page Number: | 619 |
End Page Number: | 640 |
Publication Date: | Jul 2014 |
Journal: | Algorithmica |
Authors: | Mehlhorn Kurt, Christodoulou Giorgos, Pyrga Evangelia |
Keywords: | networks, networks: path |
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