## 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 language | English |
---|---|

Title of host publication | EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation |

Publisher | Association for Computing Machinery, Inc |

Pages | 223-240 |

Number of pages | 18 |

ISBN (Electronic) | 9781450345279 |

DOIs | |

Publication status | Published - 20 Jun 2017 |

Event | 18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States Duration: 26 Jun 2017 → 30 Jun 2017 |

### Publication series

Name | EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation |
---|

### Conference

Conference | 18th ACM Conference on Economics and Computation, EC 2017 |
---|---|

Country | United States |

City | Cambridge |

Period | 26/06/17 → 30/06/17 |