4430
правок
Приближенные решения для биматричного равновесия Нэша: различия между версиями
Материал из WEGA
Приближенные решения для биматричного равновесия Нэша (посмотреть исходный код)
Версия от 18:17, 8 марта 2012
, 8 марта 2012→Теорема 2
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
В результате этого получаем квазиполиномиальный алгоритм (<big>n<sup>O(ln n)</sup></big>) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4. | В результате этого получаем квазиполиномиальный алгоритм (<big>n<sup>O(ln n)</sup></big>) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4. | ||
'''Теорема 2''' ([4]) | |||
[4] | |||
'''Задача вычисления <math>1/n^{\Theta (1)} \, </math>-равновесия Нэша для биматричной игры с матрицами <math>n \times n</math> является PPAD-полной.''' | |||
Теорема 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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине. | Теорема 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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине. | ||
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного < | Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого ''константного'' <math>0 < \epsilon < 1 \, </math>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры: | ||
===Теорема 3 === | ===Теорема 3 === | ||
