Can I read Smooth Nash Equilibria: Algorithms and Complexity on EtoBox?

Smooth Nash Equilibria: Algorithms and Complexity by Daskalakis, Constantinos; Golowich, Noah; Haghtalab, Nika; Shetty, Abhishek is a scholarly article available to read on EtoBox.

What is Smooth Nash Equilibria: Algorithms and Complexity about?

A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called $\sigma$-smooth Nash equilibrium, for a smoothness parameter $\sigma$. In a $\sigma$-smooth Nash equilibrium, players only need to achieve utility at least as high as their best deviation to a $\sigma$-smooth strategy, which is a distribution that does not put too much mass (as parametrized by $\sigma$) on any fixed action. We distinguish two variants of $\sigma$-smooth Nash equilibria: strong $\sigma$-smooth Nash equilibria, in which players are required to play $\sigma$-smooth strategies under equilibrium play, and weak $\sigma$-smooth Nash equilibria, where there is no such requirement. We show that both weak and strong $\sigma$-smooth Nash equilibria have superior computational properties to Nash equilibria: when $\sigma$ as well as an approximation parameter $\epsilon$ and the number of players are all constants, there is a constant-time randomized algorithm to find a weak $\epsilon$-approximate $\sigm

Author

Daskalakis, Constantinos; Golowich, Noah; Haghtalab, Nika; Shetty, Abhishek

Published

2023

Language

EN