We investigate the loss in optimality due to the presence of selfish players in sequential games, a relevant subclass of extensive form games with perfect information recently introduced in Paes Leme et al. (Proceedings of innovations in theoretical computer science (ITCS), ACM, New York, pp. 60–67, 2012). In such a setting, the notion of subgame perfect equilibrium is preferred to that of Nash equilibrium since it better captures the farsighted rationality of the players who can anticipate future strategic opportunities. We prove that the sequential price of anarchy, that is the worst-case ratio between the social performance at a subgame perfect equilibrium and that of the best possible solution, is exactly 3 in cut and consensus games. Moreover, we improve the known Ω(n) lower bound for unrelated scheduling to 2(√) and refine the corresponding upper bound to 2n, where n is the number of players. Finally, we determine essentially tight bounds for fair cost sharing games by proving that the sequential price of anarchy is between n+1−H n and n. A surprising lower bound of (n+1)/2 is also determined for the singleton case. Our results are quite interesting and counterintuitive, as they show that a farsighted behavior may lead to a worse performance with respect to a myopic one: in fact, either Nash equilibria and simple Nash rounds, consisting of a single (myopic) move per player starting from the empty state, achieve a price of anarchy which results to be lower or equivalent to the sequential price of anarchy in almost all the considered cases.

Some Anomalies of Farsighted Strategic Behavior

Flammini M;
2015-01-01

Abstract

We investigate the loss in optimality due to the presence of selfish players in sequential games, a relevant subclass of extensive form games with perfect information recently introduced in Paes Leme et al. (Proceedings of innovations in theoretical computer science (ITCS), ACM, New York, pp. 60–67, 2012). In such a setting, the notion of subgame perfect equilibrium is preferred to that of Nash equilibrium since it better captures the farsighted rationality of the players who can anticipate future strategic opportunities. We prove that the sequential price of anarchy, that is the worst-case ratio between the social performance at a subgame perfect equilibrium and that of the best possible solution, is exactly 3 in cut and consensus games. Moreover, we improve the known Ω(n) lower bound for unrelated scheduling to 2(√) and refine the corresponding upper bound to 2n, where n is the number of players. Finally, we determine essentially tight bounds for fair cost sharing games by proving that the sequential price of anarchy is between n+1−H n and n. A surprising lower bound of (n+1)/2 is also determined for the singleton case. Our results are quite interesting and counterintuitive, as they show that a farsighted behavior may lead to a worse performance with respect to a myopic one: in fact, either Nash equilibria and simple Nash rounds, consisting of a single (myopic) move per player starting from the empty state, achieve a price of anarchy which results to be lower or equivalent to the sequential price of anarchy in almost all the considered cases.
2015
Subgame Perfect Equilibria, Sequential Price of Anarchy, Cost Sharing Games, Cut Games, Scheduling Games
File in questo prodotto:
File Dimensione Formato  
2015_TheoryComputSyst_56_Flammini.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 487.12 kB
Formato Adobe PDF
487.12 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/20.500.12571/2878
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact