4430
правок
Приближенные решения для биматричного равновесия Нэша: различия между версиями
Материал из WEGA
Приближенные решения для биматричного равновесия Нэша (посмотреть исходный код)
Версия от 13:59, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 48: | Строка 48: | ||
'''Задача вычисления <math>1/n^{\Theta (1)} \, </math>-равновесия Нэша для биматричной игры с матрицами <math>n \times n</math> является PPAD-полной.''' | '''Задача вычисления <math>1/n^{\Theta (1)} \, </math>-равновесия Нэша для биматричной игры с матрицами <math>n \times n</math> является PPAD-полной.''' | ||
Теорема 2 утверждает, что за исключением случаев, когда PPAD <math>\subseteq</math> P, не существует схемы | Теорема 2 утверждает, что за исключением случаев, когда PPAD <math>\subseteq</math> P, не существует аппроксимационной схемы с полностью полиномиальным временем выполнения для вычисления равновесия в биматричных играх. Однако это не исключает существования аппроксимационной схемы с полиномиальным временем для вычисления <math>\epsilon \, </math>-равновесия Нэша, где <math>\epsilon \, </math> является абсолютной константой, и даже в случае <math>\epsilon \, = \Theta \big( 1/poly(ln n) \big). </math>Более того, как было замечено в [4], если бы задача нахождения <math>\epsilon \, </math>-равновесия Нэша была PPAD-полной в случае, когда <math>\epsilon \, </math> является абсолютной константой, то, согласно Теореме 1, все PPAD-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине. | ||
