TY - GEN
T1 - Potential function minimizers of combinatorial congestion games
T2 - 18th ACM Conference on Economics and Computation, EC 2017
AU - Kleer, Pieter
AU - Schäfer, Guido
PY - 2017/6/20
Y1 - 2017/6/20
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85025815886&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85025815886&partnerID=8YFLogxK
U2 - 10.1145/3033274.3085149
DO - 10.1145/3033274.3085149
M3 - Conference contribution
AN - SCOPUS:85025815886
T3 - EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
SP - 223
EP - 240
BT - EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PB - Association for Computing Machinery, Inc
Y2 - 26 June 2017 through 30 June 2017
ER -