We consider finite two-player normal form games with random payoffs. Player A's payoffs are i.i.d. from a uniform distribution. Given p in [0,1], for any action profile, player B's payoff coincides with player A's payoff with probability p and is i.i.d. from the same uniform distribution with probability . This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive p, asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability.

Best-response dynamics in two-person random games with correlated payoffs / Mimun, Hlafo Alfie; Quattropani, Matteo; Scarsini, Marco. - In: GAMES AND ECONOMIC BEHAVIOR. - ISSN 0899-8256. - 145:(2024), pp. 239-262. [10.1016/j.geb.2024.03.011]

Best-response dynamics in two-person random games with correlated payoffs

Mimun, Hlafo Alfie
;
Quattropani, Matteo;Scarsini, Marco
2024

Abstract

We consider finite two-player normal form games with random payoffs. Player A's payoffs are i.i.d. from a uniform distribution. Given p in [0,1], for any action profile, player B's payoff coincides with player A's payoff with probability p and is i.i.d. from the same uniform distribution with probability . This model interpolates the model of i.i.d. random payoff used in most of the literature and the model of random potential games. First we study the number of pure Nash equilibria in the above class of games. Then we show that, for any positive p, asymptotically in the number of available actions, best response dynamics reaches a pure Nash equilibrium with high probability.
2024
Pure Nash equilibrium, Random games, Potential games, Best response dynamics
Best-response dynamics in two-person random games with correlated payoffs / Mimun, Hlafo Alfie; Quattropani, Matteo; Scarsini, Marco. - In: GAMES AND ECONOMIC BEHAVIOR. - ISSN 0899-8256. - 145:(2024), pp. 239-262. [10.1016/j.geb.2024.03.011]
File in questo prodotto:
File Dimensione Formato  
GEB2024MQS.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 782.87 kB
Formato Adobe PDF
782.87 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11385/237398
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact