Какие предположения и основные открытые проблемы являются наиболее важными в алгоритмической теории игр (или теории игр в целом применительно к CS)? Например, разрешение NASH как PPAD-полного, я думаю, было бы самым большим до тех пор, пока оно не было решено.
(Добавлено: разрешение отношения PPAD к P и NP - одна хорошая открытая проблема, но другие, не столь глубоко укоренившиеся в вычислительной сложности, тоже были бы хорошими.)
big-list
gt.game-theory
daveagp
источник
источник
Ответы:
Вот несколько открытых проблем:
1-Большая открытая проблема - это проблема вычисления приближенных равновесий Нэша.
2- Существование эффективного алгоритма для вычисления чистых равновесий Нэша в играх с перегрузками?
3-нахождения равновесия с минимальной неэффективностью?
4-Тим Рафгарден в Коммуникациях ACM поставил следующую открытую проблему:
Алгоритмическая теория игр, Сообщения ACM, том 53, выпуск 7 (июль 2010 года)
Кроме того, эти ссылки содержат некоторые открытые проблемы: Nisan, Roughgarden, Tardos и Vazirani, редакторы. Алгоритмическая теория игр. Издательство Кембриджского университета, 2007.
Т. Рафгарден. Алгоритмическая теория игр: некоторые лучшие хиты и будущие направления. В ТКС '08, с. 21-42.
источник
В этой ссылке Пападимитриу и Рафгарден ставят 6 открытых проблем, связанных с вычислением коррелированных равновесий:
Пападимитриу и Тим Рафгарден, Вычисление коррелированных равновесий в многопользовательских играх
Кроме того, в этой статье Пападимитриу ставит несколько открытых проблем, связанных с теорией игр и Интернетом:
Пападимитриу, Алгоритмы, Игры и Интернет, Учеб. STOC 2001
источник