Semilinear Representations for Series-Parallel Atomic Congestion Games - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Semilinear Representations for Series-Parallel Atomic Congestion Games

Résumé

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.
Fichier principal
Vignette du fichier
LIPIcs-FSTTCS-2022-32-1.pdf (813.52 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03937259 , version 1 (13-01-2023)

Licence

Paternité

Identifiants

Citer

Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, Ocan Sankur. Semilinear Representations for Series-Parallel Atomic Congestion Games. FSTTCS 2022 - 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2022, Chennai, France. pp.1-20, ⟨10.4230/LIPIcs.FSTTCS.2022.32⟩. ⟨hal-03937259⟩
16 Consultations
43 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More