Список проблем PPAD-complete - List of PPAD-complete problems

Это список PPAD -полные проблемы.

Теоремы о неподвижной точке

• Лемма Спернера
• Теорема Брауэра о неподвижной точке
• Теорема Какутани о неподвижной точке

Теория игры

• равновесие по Нэшу
• Ядро сбалансированных игр

Равновесия в теории игр и экономике

• Равновесие на рынке Фишера
• Равновесия Эрроу-Дебре
• Приблизительное конкурентное равновесие на основе равных доходов
• Поиск клиринговых платежей в финансовых сетях

Теория графов

• Проблемы с дробными стабильными путями
• Дробное сопоставление гиперграфов (см. также NP-полный Сопоставление гиперграфа )
• Фракционное сильное ядро

Разное

• Лемма Шарфа
• Игры с дробным ограниченным бюджетом

использованная литература

• Пападимитриу, Христос (1994). «О сложности аргумента о четности и других неэффективных доказательствах существования». Журнал компьютерных и системных наук. 48 (3): 498–532. Дои:10.1016 / S0022-0000 (05) 80063-7. Бумага доступна в Интернете по адресу Домашняя страница Пападимитриу.

• К. Даскалакис, П.В. Гольдберг и C.H. Пападимитриу (2009). «Сложность вычисления равновесия по Нэшу». SIAM Журнал по вычислениям. 39 (3): 195–259. CiteSeerX  10.1.1.68.6111. Дои:10.1137/070699652.

• Си Чен и Сяотэ Дэн (2006). Урегулирование сложности равновесия по Нэшу для двух игроков. С. 261–272.