Average Case Equilibria

ACO Student Seminar
Friday, March 28, 2014 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
Since the 50s and Nash general proof of equilibrium existence in games it is well understood that even simple games may have many, even uncountably infinite, equilibria with different properties. In such cases a natural question arises, which equilibrium is the right one? In this work, we perform average case analysis of evolutionary dynamics in such cases of games. Intuitively, we assign to each equilibrium a probability mass that is proportional to the size of its region of attraction. We develop new techniques to compute these likelihoods for classic games such as the Stag Hunt game (and generalizations) as well as balls-bins games. Our proofs combine techniques from information theory (relative entropy), dynamical systems (center manifold theorem), and algorithmic game theory. Joint work with Georgios Piliouras