Randomness Requirements and Asymmetries in Nash Equilibria

In general, Nash equilibria in normal-form games may require players to play (probabilistically) mixed strategies. We define a measure of the complexity of finite probability distributions and study the complexity required to play NEs in finite two player n× n games with rational payoffs. Our central results show that there exist games in which there is an exponential vs. linear gap in the complexity of the mixed distributions that the two players play at (the unique) NE. This gap induces gaps in the amount of space required to represent and sample from the corresponding distributions using known state-of-the-art sampling algorithms. We also establish upper and lower bounds on the complexity of any NE in the games that we study. These results highlight (i) the nontriviality of the assumption that players can any mixed strategy and (ii) the disparities in resources that players may require to play NEs in the games that we study.