Approximate Plutocratic and Egalitarian Nash Equilibria (Extended Abstract)

We pose the problem of computing approximate Nash equilibria in bimatrix games with two simultaneous criteria of optimization: minimization of the incentives to deviate from a strategy profile and maximization of a measure of quality of the strategy profile. We consider two natural measures of quality: the maximum and the minimum of the payoffs of the two players. Maximizing the former yields plutocratic Nash equilibria, and maximizing the latter yields egalitarian Nash equilibria. We give polynomial-time algorithms that compute ε-Nash equilibria for ε ≥ 3-√ 5 2 ≈ 0.382, and that approximate the quality of plutocratic and egalitarian Nash equilibria to various degrees. * Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by the EPSRC awards EP/D063191/1 and EP/G069034/1.