<p>You may be looking for something like Sink Equilibria (start from e.g. <a href="http://arxiv.org/abs/0902.0382" rel="nofollow">http://arxiv.org/abs/0902.0382</a> ) -- but the cycle length is not considered.</p>

CC BY-SA 2.5
2010-10-03T17:23:25.863Z
Ah, beautiful. The term "sink equilibrium" is what I was looking for. Thanks!
Henry Yuen
CC BY-SA 2.5
2010-10-03T07:30:54.720Z
2010-10-03T07:30:54.720Z
Noam
<p>This is probably not what you're looking for, but it's possible to define an approximate Nash equilibrium where the goal is to find states so that the player utilities are close to that defined by the Nash equlibrium. <a href="http://agtb.wordpress.com/2009/06/07/approximate-nash/" rel="nofollow">Noam Nisan has a nice post on this</a> (and since he hangs out here sometimes, he'll likely have a better answer for you). </p>

CC BY-SA 2.5
2010-10-03T06:47:15.450Z
2010-10-03T06:47:15.450Z
Suresh Venkat
<p>Joseph Y. Halpern from Cornell recently gave a talk at the CUNY Graduate Center with the title: Beyond Nash Equilibrium: Solution Concepts for the 21st Century. Perhaps his work would be of interest to you.</p>

<p><a href="http://web.cs.gc.cuny.edu/~kgb/seminar.html" rel="nofollow">http://web.cs.gc.cuny.edu/~kgb/seminar.html</a></p>

CC BY-SA 2.5
2010-10-03T19:43:27.877Z
This link doesn't seem to work for me?
András Salamon
CC BY-SA 2.5
2010-10-03T20:22:53.563Z
A paper that Halpern wrote and which perhaps was the basis for his talk is here: http://www.cs.cornell.edu/home/halpern/abstract.html#beyond
Joseph Malkevitch
CC BY-SA 2.5
2010-10-03T16:55:00.773Z
2010-10-03T16:55:00.773Z
Joseph Malkevitch
<p>Hopefully this is not too off-topic of an answer, since it looks at this question from the point of evolutionary game theory (EGT), instead of AGT. </p>

<p>Game theory as originally formulated by von Neumann and Morgenstern was a static theory. Hence, many of the popular equilibria concepts (Nash, Correlated, etc) are inherently static. To talk about non-static equilibria, we have to introduce some sort of dynamics. AGT often does this by considering specific reasoning (algorithms) agents might use to arrive at their decisions. </p>

<p>An alternative approach, and one embraced by EGT, is to consider the population dynamics of a large number of agents with very simple decision making. This usually creates non-linear dynamics in the population and places EGT as part of dynamic systems. Hence, you start to see all the crazy equilibria concepts of dynamic systems such as limit cycles or chaotic attractors pop-up as equilibrium concepts. These non-stationary equilibria are well studied in EGT, although often the analysis is purely from dynamic systems and not algorithmic. </p>

<p>If you are interested in EGT, then a standard (and accessible) starting point is Hofbauer and Sigmund's 2003 survey "<a href="http://www.ams.org/journals/bull/2003-40-04/S0273-0979-03-00988-1/S0273-0979-03-00988-1.pdf" rel="nofollow">Evolutionary game dynamics</a>"</p>

CC BY-SA 3.0
2011-05-04T06:57:30.940Z
2011-05-04T06:57:30.940Z
Artem Kaznatcheev
<p>One that I like is sometimes called a "Coarse Correlated Equilibrium". This is actually the limiting set of efficient "No-Regret" dynamics. </p>

<p>These have several nice properties, not least of which is that they can be reached by efficient, de-coupled dynamics, and include Nash equilibria as a special case  (so are ``strictly more plausible'' as a prediction of behavior). What might make them somewhat similar to what you are asking about, is that these learning dynamics need not ever converge to a fixed point -- indeed, they may cycle forever. Nevertheless, it is often possible to bound the fast convergence of social welfare under these dynamics (i.e. price of anarchy over coarse correlated equilibria), and whats more, often the social welfare is no worse over coarse correlated equilibria than it is over Nash equilibria. </p>

<p>Some relevant papers:</p>

<p><a href="http://portal.acm.org/citation.cfm?id=1374430" rel="nofollow">http://portal.acm.org/citation.cfm?id=1374430</a></p>

<p><a href="http://portal.acm.org/citation.cfm?id=1536414.1536485" rel="nofollow">http://portal.acm.org/citation.cfm?id=1536414.1536485</a></p>

<p><a href="http://portal.acm.org/citation.cfm?id=1536487" rel="nofollow">http://portal.acm.org/citation.cfm?id=1536487</a></p>

CC BY-SA 2.5
2010-10-03T20:13:35.680Z
2010-10-03T20:13:35.680Z
Aaron Roth
<p>I'm beginning my studies of algorithmic game theory, and it seems that the equilibrium concept usually taken is that of a fixed point in a graph. However, have people looked at alternative equilibrium concepts, such as limit cycles? I can imagine that a "tight" limit cycle - that is, a cycle in the graph of very small length - could be considered something that's "close" to the standard definition of equilibrium.</p>

<p>I've tried digging around Google Scholar, but to little avail. </p>

<gt.game-theory>
Algorithmic game theory - nonstandard equilibrium concepts?
Henry Yuen
# Algorithmic game theory - nonstandard equilibrium concepts?

(Asked by: username_0 on 2010-10-03)

I'm beginning my studies of algorithmic game theory, and it seems that the equilibrium concept usually taken is that of a fixed point in a graph. However, have people looked at alternative equilibrium concepts, such as limit cycles? I can imagine that a "tight" limit cycle - that is, a cycle in the graph of very small length - could be considered something that's "close" to the standard definition of equilibrium.

I've tried digging around Google Scholar, but to little avail.

**Tags:** gt.game-theory

---

## 5 answers

### Answer by username_6 on 2010-10-03. Score: 10 | Accepted answer

One that I like is sometimes called a "Coarse Correlated Equilibrium". This is actually the limiting set of efficient "No-Regret" dynamics.

These have several nice properties, not least of which is that they can be reached by efficient, de-coupled dynamics, and include Nash equilibria as a special case (so are ``strictly more plausible'' as a prediction of behavior). What might make them somewhat similar to what you are asking about, is that these learning dynamics need not ever converge to a fixed point -- indeed, they may cycle forever. Nevertheless, it is often possible to bound the fast convergence of social welfare under these dynamics (i.e. price of anarchy over coarse correlated equilibria), and whats more, often the social welfare is no worse over coarse correlated equilibria than it is over Nash equilibria.

Some relevant papers:

<http://portal.acm.org/citation.cfm?id=1374430>

<http://portal.acm.org/citation.cfm?id=1536414.1536485>

<http://portal.acm.org/citation.cfm?id=1536487>


---

### Answer by username_1 on 2010-10-03. Score: 15

You may be looking for something like Sink Equilibria (start from e.g. <http://arxiv.org/abs/0902.0382> ) -- but the cycle length is not considered.

> **Comments:**
> **username_0**: Ah, beautiful. The term "sink equilibrium" is what I was looking for. Thanks!  

---

### Answer by username_2 on 2010-10-03. Score: 4

This is probably not what you're looking for, but it's possible to define an approximate Nash equilibrium where the goal is to find states so that the player utilities are close to that defined by the Nash equlibrium. [Noam Nisan has a nice post on this](http://agtb.wordpress.com/2009/06/07/approximate-nash/) (and since he hangs out here sometimes, he'll likely have a better answer for you).


---

### Answer by username_3 on 2010-10-03. Score: 4

Joseph Y. Halpern from Cornell recently gave a talk at the CUNY Graduate Center with the title: Beyond Nash Equilibrium: Solution Concepts for the 21st Century. Perhaps his work would be of interest to you.

<http://web.cs.gc.cuny.edu/~kgb/seminar.html>

> **Comments:**
> **username_4**: This link doesn't seem to work for me?  
> **username_3**: A paper that Halpern wrote and which perhaps was the basis for his talk is here: http://www.cs.cornell.edu/home/halpern/abstract.html#beyond  

---

### Answer by username_5 on 2011-05-04. Score: 3

Hopefully this is not too off-topic of an answer, since it looks at this question from the point of evolutionary game theory (EGT), instead of AGT.

Game theory as originally formulated by von Neumann and Morgenstern was a static theory. Hence, many of the popular equilibria concepts (Nash, Correlated, etc) are inherently static. To talk about non-static equilibria, we have to introduce some sort of dynamics. AGT often does this by considering specific reasoning (algorithms) agents might use to arrive at their decisions.

An alternative approach, and one embraced by EGT, is to consider the population dynamics of a large number of agents with very simple decision making. This usually creates non-linear dynamics in the population and places EGT as part of dynamic systems. Hence, you start to see all the crazy equilibria concepts of dynamic systems such as limit cycles or chaotic attractors pop-up as equilibrium concepts. These non-stationary equilibria are well studied in EGT, although often the analysis is purely from dynamic systems and not algorithmic.

If you are interested in EGT, then a standard (and accessible) starting point is Hofbauer and Sigmund's 2003 survey "[Evolutionary game dynamics](http://www.ams.org/journals/bull/2003-40-04/S0273-0979-03-00988-1/S0273-0979-03-00988-1.pdf)"


---

