Выдающиеся предположения и открытые проблемы в (алгоритмической) теории игр?

14

Какие предположения и основные открытые проблемы являются наиболее важными в алгоритмической теории игр (или теории игр в целом применительно к CS)? Например, разрешение NASH как PPAD-полного, я думаю, было бы самым большим до тех пор, пока оно не было решено.

(Добавлено: разрешение отношения PPAD к P и NP - одна хорошая открытая проблема, но другие, не столь глубоко укоренившиеся в вычислительной сложности, тоже были бы хорошими.)

daveagp
источник
3
Этот вопрос будет работать лучше, если вы отметите его как CW (Community Wiki). Смотрите здесь: meta.cstheory.stackexchange.com/questions/225/…
Даниэль Апон
2
Я согласен. пожалуйста, отметьте это CW.
Суреш Венкат

Ответы:

5

Вот несколько открытых проблем:

1-Большая открытая проблема - это проблема вычисления приближенных равновесий Нэша.

2- Существование эффективного алгоритма для вычисления чистых равновесий Нэша в играх с перегрузками?

3-нахождения равновесия с минимальной неэффективностью?

4-Тим Рафгарден в Коммуникациях ACM поставил следующую открытую проблему:

В какой степени «совместимые по стимулам» эффективные вычисления принципиально менее мощны, чем «классические» эффективные вычисления?

Алгоритмическая теория игр, Сообщения ACM, том 53, выпуск 7 (июль 2010 года)

Кроме того, эти ссылки содержат некоторые открытые проблемы: Nisan, Roughgarden, Tardos и Vazirani, редакторы. Алгоритмическая теория игр. Издательство Кембриджского университета, 2007.

Т. Рафгарден. Алгоритмическая теория игр: некоторые лучшие хиты и будущие направления. В ТКС '08, с. 21-42.

Мухаммед Аль-Туркистани
источник
Недавний опрос очень полезен. Я на самом деле посмотрел на книгу Нисана +++ - текстовый поиск по «гипотезе» дает всего пару ударов! --- но действительно много открытых проблем. Любые конкретные предположения или менее технические специфические открытые проблемы все равно будут приветствоваться в моем поиске.
daveagp
Вычисление чистого равновесия по Нэшу для общей игры с перегрузками является PLS-полным, поэтому эффективный алгоритм вряд ли существует.
Рахул Савани
1

В этой ссылке Пападимитриу и Рафгарден ставят 6 открытых проблем, связанных с вычислением коррелированных равновесий:

Пападимитриу и Тим Рафгарден, Вычисление коррелированных равновесий в многопользовательских играх

Кроме того, в этой статье Пападимитриу ставит несколько открытых проблем, связанных с теорией игр и Интернетом:

Пападимитриу, Алгоритмы, Игры и Интернет, Учеб. STOC 2001

Мухаммед Аль-Туркистани
источник
2
Опрос Пападимитриу несколько устарел, поскольку с 2001 года был достигнут значительный прогресс по большинству открытых проблем.
Райан Уильямс,