Théorie algorithmique des jeux - concepts d'équilibre non standard?

Je commence mes études de théorie des jeux algorithmiques, et il semble que le concept d'équilibre généralement utilisé est celui d'un point fixe dans un graphe. Cependant, les gens ont-ils envisagé d'autres concepts d'équilibre, tels que les cycles limites? Je peux imaginer qu'un cycle limite "serré" - c'est-à-dire un cycle dans le graphique de très petite longueur - pourrait être considéré comme quelque chose de "proche" de la définition standard de l'équilibre.

J'ai essayé de creuser autour de Google Scholar, mais en vain.

Celui que j'aime est parfois appelé un «équilibre corrélé grossier». Il s'agit en fait de l'ensemble limitatif de dynamiques «sans regret» efficaces.

Celles-ci ont plusieurs propriétés intéressantes, dont la plus importante est qu'elles peuvent être atteintes par une dynamique efficace et découplée, et incluent les équilibres de Nash comme cas spécial (ainsi sont `` strictement plus plausibles '' comme prédiction du comportement). Ce qui pourrait les rendre quelque peu similaires à ce que vous demandez, c'est que ces dynamiques d'apprentissage ne doivent jamais converger vers un point fixe - en fait, elles peuvent évoluer à l'infini. Néanmoins, il est souvent possible de limiter la convergence rapide du bien-être social dans ces dynamiques (c'est-à-dire le prix de l'anarchie sur les équilibres corrélés grossiers), et de plus, souvent le bien-être social n'est pas pire sur les équilibres corrélés grossiers que sur les équilibres de Nash.

Quelques articles pertinents:

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

Vous cherchez peut-être quelque chose comme Sink Equilibria (par exemple http://arxiv.org/abs/0902.0382 ) - mais la durée du cycle n'est pas prise en compte.

Ce n'est probablement pas ce que vous recherchez, mais il est possible de définir un équilibre Nash approximatif où le but est de trouver des états afin que les utilitaires du joueur soient proches de ceux définis par l'équilibrage Nash. Noam Nisan a un bon post à ce sujet (et comme il traîne parfois ici, il aura probablement une meilleure réponse pour vous).

Joseph Y. Halpern de Cornell a récemment donné une conférence au CUNY Graduate Center sous le titre: Beyond Nash Equilibrium: Solution Concepts for the 21st Century. Peut-être que son travail vous intéresserait.

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

Espérons que ce ne soit pas trop hors sujet d'une réponse, car il examine cette question du point de vue de la théorie des jeux évolutifs (EGT), au lieu d'AGT.

La théorie des jeux telle que formulée à l'origine par von Neumann et Morgenstern était une théorie statique. Par conséquent, de nombreux concepts d'équilibre populaires (Nash, corrélés, etc.) sont intrinsèquement statiques. Pour parler d'équilibres non statiques, nous devons introduire une sorte de dynamique. L'AGT le fait souvent en considérant un raisonnement spécifique (algorithmes) que les agents pourraient utiliser pour prendre leurs décisions.

Une approche alternative, et adoptée par EGT, consiste à considérer la dynamique de population d'un grand nombre d'agents avec une prise de décision très simple. Cela crée généralement une dynamique non linéaire dans la population et place l'EGT dans les systèmes dynamiques. Par conséquent, vous commencez à voir tous les concepts d'équilibre fous des systèmes dynamiques tels que les cycles limites ou les attracteurs chaotiques apparaître comme des concepts d'équilibre. Ces équilibres non stationnaires sont bien étudiés en EGT, bien que souvent l'analyse soit purement de systèmes dynamiques et non algorithmique.

Si vous êtes intéressé par l'EGT, alors un point de départ standard (et accessible) est l'enquête de Hofbauer et Sigmund de 2003 " Dynamique du jeu évolutionnaire "