---
title: "Approximate Nash Equilibria with Near Optimal Social Welfare"
authors:
  - "Artur Czumaj"
  - "Michail Fasoulakis"
  - "Marcin Jurdzinski"
doi: ""
url: "https://ijcai.org/proceedings/2015/77"
pdf: "https://ijcai.org/proceedings/2015/0077.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "504-509"
track: "Main Track"
keywords:
---

# Approximate Nash Equilibria with Near Optimal Social Welfare

Artur Czumaj, Michail Fasoulakis, Marcin Jurdzinski

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 504-509.

## Abstract

It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed ε > 0, every bimatrix game (with values in [0, 1]) has an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 − √1 − ε)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ ε* < ε, if we can find an ε*-approximate Nash equilibrium in polynomial time, then we can find in polynomial time an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when ε ≥ 1/2. In this case, we show that for any bimatrix game there is an ε-approximate Nash equilibrium with constant size support whose social welfare is is at least 2√ε − ε ≥ 0.914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every ε ≥ 1/2 there is a bimatrix game for which every ε-approximate Nash equilibrium has social welfare at most 2√ε − ε times the optimal social welfare.