Список проблем, полных PPAD
Это список PPAD -полных проблем.
Теоремы о неподвижной точке
[ редактировать ]Теория игр
[ редактировать ]Равновесия в теории игр и экономике
[ редактировать ]- Рыночное равновесие Фишера
- Равновесия Эрроу-Дебре
- Приблизительное конкурентное равновесие при равных доходах
- Поиск клиринговых платежей в финансовых сетях
Теория графов
[ редактировать ]- Проблемы с дробными устойчивыми путями
- Дробное сопоставление гиперграфов (см. также NP-полное сопоставление гиперграфов )
- Дробное сильное ядро
Разнообразный
[ редактировать ]Ссылки
[ редактировать ]- Пападимитриу, Христос (1994). «О сложности аргумента четности и других неэффективных доказательствах существования» . Журнал компьютерных и системных наук . 48 (3): 498–532. CiteSeerX 10.1.1.321.7008 . дои : 10.1016/S0022-0000(05)80063-7 . Статья доступна в Интернете на домашней странице Пападимитриу .
- К. Даскалакис, П.В. Голдберг и Ч. Пападимитриу (2009). «Сложность вычисления равновесия Нэша». SIAM Journal по вычислительной технике . 39 (3): 195–259. CiteSeerX 10.1.1.68.6111 . дои : 10.1137/070699652 .
- Си Чен и Сяоте Дэн (2006). «Урегулирование сложности равновесия Нэша для двух игроков». В Proc. 47-й ФОКС . стр. 261–272.