B | |
---|---|

[BMS+22] | Nathalie Bertrand,
Nicolas Markey,
Suman Sadhukhan, and
Ocan Sankur.
Semilinear Representations for Series-Parallel
Atomic Congestion Games.
In FSTTCS'22,
Leibniz International Proceedings in Informatics 250, pages 32:1-32:20. Leibniz-Zentrum für Informatik, December 2022.
- Abstract
We consider atomic congestion games on series-parallel networks, and study the structure of the sets of Nash equilibria and social local optima on a given network when the number of players varies. We establish that these sets are definable in Presburger arithmetic and that they admit semilinear representations whose all period vectors have a common direction. As an application, we prove that the prices of anarchy and stability converge to 1 as the number of players goes to infinity, and show how to exploit these semilinear representations to compute these ratios precisely for a given network and number of players.
@inproceedings{fsttcs2022-BMSS, author = {Bertrand, Nathalie and Markey, Nicolas and Sadhukhan, Suman and Sankur, Ocan}, title = {Semilinear Representations for Series-Parallel Atomic Congestion Games}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, booktitle = {{P}roceedings of the 42nd {C}onference on {F}oundations of {S}oftware {T}echnology and {T}heoretical {C}omputer {S}cience ({FSTTCS}'22)}, acronym = {{FSTTCS}'22}, publisher = {Leibniz-Zentrum f{\"u}r Informatik}, series = {Leibniz International Proceedings in Informatics}, volume = {250}, pages = {32:1-32:20}, year = {2022}, month = dec, doi = {10.4230/LIPIcs.FSTTCS.2022.32}, abstract = {We~consider atomic congestion games on series-parallel networks, and study the structure of the sets of Nash equilibria and social local optima on a given network when the number of players varies. We establish that these sets are definable in Presburger arithmetic and that they admit semilinear representations whose all period vectors have a common direction. As~an~application, we~prove that the prices of anarchy and stability converge to~1 as the number of players goes to infinity, and show how to exploit these semilinear representations to compute these ratios precisely for a given network and number of players.}, } |

- 1
- 1
- 1
- 1