<p>No, no-regret dynamics do not converge to Nash equilibrium in general games, and its not hard to think of examples. </p>

<p>On the other hand, no regret dynamics <em>do</em> always <a href="http://www.cs.cornell.edu/courses/CS6840/2012sp/Feb17Notes.pdf">converge to coarse correlated equilibrium</a> in any game, and no-internal regret dynamics always converge to the set of <a href="http://en.wikipedia.org/wiki/Correlated_equilibrium">correlated equilibria</a>. </p>

<p>They are also known to converge to Nash equilibrium in several special cases of n-player games: for example, <a href="http://people.csail.mit.edu/costis/network2.pdf">separable zero sum games</a>, <a href="http://dl.acm.org/citation.cfm?id=1146392">congestion games</a>, and a few others. </p>

<p>In general, there are no efficient learning dynamics that converge to Nash equilibrium though. Not only is computing a Nash equilibrium PPAD hard, but even ignoring computation, for any "decoupled learning dynamics" (among which no regret dynamics are a special case) <a href="http://dl.acm.org/citation.cfm?id=1250843">must exchange exponential communication</a> before finding a Nash equilibrium in general games.</p>

CC BY-SA 3.0
2013-05-26T13:40:25.593Z
2013-05-26T13:40:25.593Z
Aaron Roth
<p>There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.</p>

<p>The proof can be found in the survey <a href="http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf">Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour</a>.</p>

<p>Immediately arises question whether can we use external regret minimization to find mixed Nash equilibrium in finite non-zero two-player game, in other words does zero external regret leads to find mixed Nash equilibrium, in per round sense. </p>

<p>Intuitively it doesn't seem so, I am not sure that we can get external regret equals zero in general case, but there are polynomial time algorithm for good approximation (see the above paper), on the other hand approximation of Nash equilibrium seems like more difficult task.</p>

<p>I would appreciate if someone could help to answer the question.</p>

<gt.game-theory>
External Regret and Nash Equilibrium
user16168
# External Regret and Nash Equilibrium

(Asked by: username_0 on 2013-05-26)

There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.

The proof can be found in the survey [Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour](http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf).

Immediately arises question whether can we use external regret minimization to find mixed Nash equilibrium in finite non-zero two-player game, in other words does zero external regret leads to find mixed Nash equilibrium, in per round sense.

Intuitively it doesn't seem so, I am not sure that we can get external regret equals zero in general case, but there are polynomial time algorithm for good approximation (see the above paper), on the other hand approximation of Nash equilibrium seems like more difficult task.

I would appreciate if someone could help to answer the question.

**Tags:** gt.game-theory

---

## 1 answers

### Answer by username_1 on 2013-05-26. Score: 11 | Accepted answer

No, no-regret dynamics do not converge to Nash equilibrium in general games, and its not hard to think of examples.

On the other hand, no regret dynamics *do* always [converge to coarse correlated equilibrium](http://www.cs.cornell.edu/courses/CS6840/2012sp/Feb17Notes.pdf) in any game, and no-internal regret dynamics always converge to the set of [correlated equilibria](http://en.wikipedia.org/wiki/Correlated_equilibrium).

They are also known to converge to Nash equilibrium in several special cases of n-player games: for example, [separable zero sum games](http://people.csail.mit.edu/costis/network2.pdf), [congestion games](http://dl.acm.org/citation.cfm?id=1146392), and a few others.

In general, there are no efficient learning dynamics that converge to Nash equilibrium though. Not only is computing a Nash equilibrium PPAD hard, but even ignoring computation, for any "decoupled learning dynamics" (among which no regret dynamics are a special case) [must exchange exponential communication](http://dl.acm.org/citation.cfm?id=1250843) before finding a Nash equilibrium in general games.


---

