Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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
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.
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 (and since he hangs out here sometimes, he'll likely have a better answer for you).
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.
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"
