We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d + 1 clusters C0, C1, . . . , Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1 ≤ i ≤ d, have full information only about the members of C0 ∪ Ci and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (ii) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d = 2 in presence of unweighted players.

On Multidimensional Congestion Games

Flammini, Michele
;
Vinci, Cosimo
2020-01-01

Abstract

We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d + 1 clusters C0, C1, . . . , Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1 ≤ i ≤ d, have full information only about the members of C0 ∪ Ci and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (ii) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d = 2 in presence of unweighted players.
2020
congestion games; pure Nash equilibrium; potential games; price of anarchy; price of stability
File in questo prodotto:
File Dimensione Formato  
2020_Algorithms_13_Bilo.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Dominio pubblico
Dimensione 413.72 kB
Formato Adobe PDF
413.72 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/14376
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact