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

Vinci C.
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11386/4785704
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact