Efficiency of equilibria in random binary games
share
We consider normal-form games with n players and two strategies for each player where the payoffs are Bernoulli random variables. We define the average social utility associated to a strategy profile as the sum of the payoffs of all players divided by n. We assume that payoff vectors corresponding to different profiles are i.i.d., and the payoffs within the same profile are conditionally independent given some underlying random parameter. Under these conditions we examine the asymptotic behavior of the average social utilities that correspond to the optimum, to the best and to the worst pure Nash equilibria. We perform a detailed analysis of some particular cases showing that these random quantities converge, as n→∞, to some function of the models' parameters. Moreover, we show that these functions exhibit some interesting phase-transition phenomena.
READ FULL TEXT