Conjectures en suspens et problèmes ouverts dans la théorie des jeux (algorithmique)?

14

Quels types de conjectures et de grands problèmes ouverts sont les plus importants dans la théorie des jeux algorithmiques (ou la théorie des jeux en général en ce qui concerne CS)? Par exemple, la résolution de NASH comme PPAD-complete aurait, je pense, été la plus importante jusqu'à ce qu'elle soit résolue.

(Ajouté: la résolution de la relation de PPAD avec P et NP est un bon problème ouvert, mais d'autres moins profondément ancrés dans la complexité de calcul seraient également intéressants.)

big-list gt.game-theory daveagp
la source
3
Cette question fonctionnerait mieux si vous la signaliez comme CW (Community Wiki). Voir ici: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Je suis d'accord. veuillez le marquer CW.
Suresh Venkat

Réponses:

5

Voici plusieurs problèmes ouverts:

1-Le problème ouvert majeur est le problème du calcul des équilibres de Nash approximatifs.

2- Existence d'un algorithme efficace pour calculer les équilibres Nash purs dans les jeux de congestion?

Trouver des équilibres avec un minimum d'inefficacité?

4-Tim Roughgarden, dans Communications of the ACM, a posé le problème ouvert suivant:

dans quelle mesure le calcul efficace «compatible avec les incitations» est-il fondamentalement moins puissant que le calcul efficace «classique»?

Théorie algorithmique des jeux, Communications de l'ACM, Volume 53, Numéro 7, (juillet 2010)

En outre, ces références contiennent des problèmes ouverts: Nisan, Roughgarden, Tardos et Vazirani, éditeurs. Théorie algorithmique des jeux. Cambridge University Press, 2007.

T. Roughgarden. Théorie algorithmique des jeux: quelques grands succès et orientations futures. Dans TCS '08, p. 21–42.

Mohammad Al-Turkistany
la source
L'enquête récente est très utile. J'avais en fait regardé le livre de Nisan +++ --- une recherche de texte pour "conjecture" ne donne que quelques coups! --- mais il y a en effet beaucoup de problèmes ouverts. Toute conjecture spécifique ou problème ouvert moins technique spécifique serait toujours le bienvenu dans ma recherche.
daveagp
Le calcul d'un équilibre Nash pur d'un jeu de congestion générale est complet en PLS, il est donc peu probable qu'un algorithme efficace existe.
Rahul Savani
1

Dans cette référence, Papadimitriou et Roughgarden posent 6 problèmes ouverts liés au calcul des équilibres corrélés:

Papadimitriou et Tim Roughgarden, Calculer les équilibres corrélés dans les jeux multi-joueurs

De plus, dans cet article, Papadimitriou pose plusieurs problèmes ouverts liés à la théorie des jeux et à Internet:

Papadimitriou, Algorithmes, jeux et Internet, Proc. STOC 2001

Mohammad Al-Turkistany
la source
2
L'enquête de Papadimitriou est un peu dépassée, en ce sens que des progrès significatifs ont été réalisés sur la plupart des problèmes ouverts depuis 2001.
Ryan Williams