Potential function minimizers of combinatorial congestion games: Efficiency and computation

Pieter Kleer, Guido Schäfer

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We study the inefficiency and computation of pure Nash equilibria in unweighted congestion games, where the strategies of each player i are given implicitly by the binary vectors of a polytope Pi . Given these polytopes, a strategy profile naturally corresponds to an integral vector in the aggregation polytope PN = Σ i Pi . We identify two general properties of the aggregation polytope PN that are sufficient for our results to go through, namely the integer decomposition property (IDP) and the box-Totally dual integrality property (box-TDI). Intuitively, the IDP is needed to decompose a load profile in PN into a respective strategy profile of the players, and box-TDI ensures that the intersection of a polytope with an arbitrary integer box is an integral polytope. Examples of polytopal congestion games which satisfy IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, r -Arborescences and strongly base-orderable matroids). Our main contributions for polytopal congestion games satisfying IDP and box-TDI are as follows: (1) We derive tight bounds on the price of stability for these games. .is extends a result of Fotakis (2010) on the price of stability for symmetric network congestion games to the larger class of polytopal congestion games. Our bounds improve upon the ones for general polynomial congestion games obtained by Christodoulou and Gairing (2016). (2) We show that pure Nash equilibria can be computed in strongly polynomial time for these games. To this aim, we generalize a recent aggregation/decomposition framework by Del Pia et al. (2017) for symmetric totally unimodular and non-symmetric matroid congestion games, both being a special case of our polytopal congestion games. (3) Finally, we generalize and extend results on the computation of strong equilibria in bo.leneck congestion games studied by Harks, Hoefer, Klimm and Skopalik (2013). In particular, we show that strong equilibria can be computed efficiently for symmetric totally unimodular bottleneck congestion games. In general, our results reveal that the combination of IDP and box-TDI gives rise to an effiicient approach to compute a pure Nash equilibrium whose inefficiency is be.er than in general congestion games.

Original languageEnglish
Title of host publicationEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages223-240
Number of pages18
ISBN (Electronic)9781450345279
DOIs
Publication statusPublished - 20 Jun 2017
Event18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States
Duration: 26 Jun 201730 Jun 2017

Publication series

NameEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation

Conference

Conference18th ACM Conference on Economics and Computation, EC 2017
CountryUnited States
CityCambridge
Period26/06/1730/06/17

Fingerprint

Dive into the research topics of 'Potential function minimizers of combinatorial congestion games: Efficiency and computation'. Together they form a unique fingerprint.

Cite this