Que tipo de conjecturas e grandes problemas em aberto são os mais importantes na teoria algorítmica dos jogos (ou na teoria dos jogos em geral no que se refere ao CS)? Por exemplo, a resolução do NASH como sendo completa no PPAD seria, creio, a maior até que fosse resolvida.
(Adicionado: resolver a relação do PPAD com P e NP é um bom problema em aberto, mas outros não tão profundamente arraigados na complexidade computacional também seriam bons.)
big-list
gt.game-theory
daveagp
fonte
fonte
Respostas:
Aqui estão vários problemas em aberto:
1-O principal problema aberto é o problema de calcular os equilíbrios aproximados de Nash.
2- Existência de algoritmo eficiente para calcular equilíbrios puros de Nash em jogos de congestionamento?
3-encontrar equilíbrios com o mínimo de ineficiência?
4-Tim Roughgarden, em Communications of the ACM, colocou o seguinte problema em aberto:
Teoria algorítmica dos jogos, Communications of the ACM, volume 53, edição 7, (julho de 2010)
Além disso, essas referências contêm alguns problemas em aberto: Nisan, Roughgarden, Tardos e Vazirani, editores. Teoria Algorítmica dos Jogos. Cambridge University Press, 2007.
T. Roughgarden. Teoria algorítmica dos jogos: alguns dos maiores sucessos e direções futuras. No TCS '08, p. 21-42.
fonte
Nesta referência, Papadimitriou e Roughgarden apresentam 6 problemas em aberto relacionados à computação de equilíbrios correlatos:
Papadimitriou e Tim Roughgarden, computando equivalentes correlatos em jogos multijogador
Além disso, neste artigo, Papadimitriou apresenta vários problemas abertos relacionados à teoria dos jogos e à Internet:
Papadimitriou, Algoritmos, Jogos e Internet, Proc. STOC 2001
fonte