We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1, horizontal ellipsis ,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

Vittorio Bilò
;
Cosimo Vinci
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, horizontal ellipsis ,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.
File in questo prodotto:
File Dimensione Formato  
algorithms-13-00261-v2.pdf

accesso aperto

Tipologia: Versione editoriale
Licenza: Creative commons
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/11587/445657
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact