Conjecturas pendentes e problemas em aberto na teoria dos jogos (algorítmica)?

14

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.)

daveagp
fonte
3
Esta pergunta funcionaria melhor se você a sinalizasse como CW (Community Wiki). Veja aqui: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Concordo. marque CW.
Suresh Venkat

Respostas:

5

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:

até que ponto a computação eficiente “compatível com incentivos” é fundamentalmente menos poderosa que a computação eficiente “clássica”?

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.

Mohammad Al-Turkistany
fonte
A pesquisa recente é muito útil. Na verdade, eu olhei para o livro de Nisan +++ - uma pesquisa de texto por "conjectura" dá apenas alguns hits! --- mas existem muitos problemas em aberto. Quaisquer conjecturas específicas, ou problemas abertos específicos menos técnicos, ainda serão bem-vindos em minha pesquisa.
daveagp 26/09/10
A computação de um equilíbrio puro de Nash de um jogo geral de congestionamento é completa em PLS; portanto, é improvável que exista um algoritmo eficiente.
Rahul Savani
1

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

Mohammad Al-Turkistany
fonte
2
A pesquisa da Papadimitriou está um pouco ultrapassada, em que um progresso significativo tem sido feito na maioria dos problemas em aberto desde 2001.
Ryan Williams