In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising from mutual actions of players v, z that are the endpoints of edges at any distance h < d from x, for a fixed threshold value d = n. In particular, the overall utility of player x is the sum of all the above payoffs, where each payoff is proportionally discounted by a factor depending on the distance h of the corresponding edge. Under the above framework, which is a natural generalization that is well-suited for capturing positive community interactions, we study the social inefficiency of equilibria resorting to standard measures of Price of Anarchy and Price of Stability. Namely, we provide suitable upper and lower bounds for the aforementioned quantities, both for bounded-degree and general graphs.

Distance Polymatrix Coordination Games

Vinci C.
2021-01-01

Abstract

In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising from mutual actions of players v, z that are the endpoints of edges at any distance h < d from x, for a fixed threshold value d = n. In particular, the overall utility of player x is the sum of all the above payoffs, where each payoff is proportionally discounted by a factor depending on the distance h of the corresponding edge. Under the above framework, which is a natural generalization that is well-suited for capturing positive community interactions, we study the social inefficiency of equilibria resorting to standard measures of Price of Anarchy and Price of Stability. Namely, we provide suitable upper and lower bounds for the aforementioned quantities, both for bounded-degree and general graphs.
2021
9780999241196
File in questo prodotto:
File Dimensione Formato  
0001.pdf

non disponibili

Tipologia: Versione editoriale
Note: Il prodotto è accessibile in full text sul sito editoriale (https://www.ijcai.org/proceedings/2021/1).
Licenza: Copyright dell'editore
Dimensione 180.02 kB
Formato Adobe PDF
180.02 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/484304
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact