The Price of Anarchy and Computation of Equilibria in Non-atomic Consumption-Relevance Congestion Games

We present an extension to the model of non-atomic congestion games (NCG). NCGs enforce a symmetry between the consumption of elements (e.g., network links) and their relevance for the players: players utilizing an element e through a strategy S (e.g., a multicast tree) with rate of consumption C_{eS}>0 experience the element's latency amplified by that same factor C_{eS}. Our extension instead allows a factor R_{eS}, independent of C_{eS}, to express the amplification of the element's latency from the players' perspective, or, in other words, the relevance of element e for strategy S. We therefore call the extended model non-atomic consumption-relevance congestion games (NCRCG). NCRCGs exhibit new phenomena, including multiple Nash equilibria of different social cost and -- even from a worst-case point of view -- a dependence of the price of anarchy on structural parameters not limited to the class of element latency functions used. It poses new computational challenges. We prove almost tight lower, upper, and bicriteria bounds for the price of anarchy for super-homogeneous classes of element latency functions. We show a positive computational result for affine element latency functions. A summary of experimental results is given, which suggest that our lower bound is the best possible.

Logo BII



Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.