4430
правок
Приближенные решения для биматричного равновесия Нэша: различия между версиями
Материал из WEGA
Приближенные решения для биматричного равновесия Нэша (посмотреть исходный код)
Версия от 18:25, 8 марта 2012
, 8 марта 2012→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
'''Теорема 1''' ([13]) | '''Теорема 1''' ([13]) | ||
'''Для любого равновесия Нэша <math>(\mathbf{x, y})</math> биматричной игры с матрицами <math>n \times n</math> и для любого <math>\epsilon > 0 \, </math> существует, для каждого <math>k \ge(12 ln n)/ \epsilon \, </math><sup>2</sup>, пара k-однородных стратегий <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> , таких, что ( <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> ) представляет собой <math>\epsilon \, </math>-равновесие Нэша. | '''Для любого равновесия Нэша <math>(\mathbf{x, y})</math> биматричной игры с матрицами <math>n \times n</math> и для любого <math>\epsilon > 0 \, </math> существует, для каждого <math>k \ge(12 ln n)/ \epsilon \, </math><sup>2</sup>, пара k-однородных стратегий <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> , таких, что ( <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> ) представляет собой <math>\epsilon \, </math>-равновесие Нэша.''' | ||
''' | |||
В результате этого получаем квазиполиномиальный алгоритм (<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. | ||
| Строка 48: | Строка 47: | ||
'''Задача вычисления <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, не существует схемы аппроксимации с полностью полиномиальным временем исполнения для вычисления равновесия в биматричных играх. Однако это не исключает существования схемы аппроксимации с полиномиальным временем для вычисления <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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине. | ||
| Строка 57: | Строка 55: | ||
'''Теорема 3''' ([10]) | '''Теорема 3''' ([10]) | ||
'''Рассмотрим любую биматричную игру <math>\Gamma = \langle A, B\rangle</math> с матрицами n × m; пусть <math> a_{i1}, _{j1} = max_i, _j a_{ij}</math> и <math>b_{i2}, _{j2} = max_i, _j b_{ij} </math>. Тогда пара стратегий (<math>\mathbf{\hat{x}} , \mathbf{\hat{y}}</math> ), где <math>\mathbf{\hat{x}}_i1 = \mathbf{\hat{x}}_i2 = \mathbf{\hat{y}}_j1 = \mathbf{\hat{y}}_j2 = 1/2</math>, является 3/4-равновесием Нэша для игры <math>\Gamma</math>. | '''Рассмотрим любую биматричную игру <math>\Gamma = \langle A, B\rangle</math> с матрицами n × m; пусть <math> a_{i1}, _{j1} = max_i, _j a_{ij}</math> и <math>b_{i2}, _{j2} = max_i, _j b_{ij} </math>. Тогда пара стратегий (<math>\mathbf{\hat{x}} , \mathbf{\hat{y}}</math> ), где <math>\mathbf{\hat{x}}_i1 = \mathbf{\hat{x}}_i2 = \mathbf{\hat{y}}_j1 = \mathbf{\hat{y}}_j2 = 1/2</math>, является 3/4-равновесием Нэша для игры <math>\Gamma</math>.''' | ||
''' | |||
Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение: | Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение: | ||
| Строка 96: | Строка 94: | ||
'''Теорема 8''' ([2]) | '''Теорема 8''' ([2]) | ||
'''Существует алгоритм с полиномиальным временем, основанный на алгоритмах линейного программирования, который строит 0.36392-равновесие Нэша. | '''Существует алгоритм с полиномиальным временем, основанный на алгоритмах линейного программирования, который строит 0.36392-равновесие Нэша.''' | ||
''' | |||
Следующий результат на данный момент является наилучшим: | Следующий результат на данный момент является наилучшим: | ||
'''Теорема 9''' ([17]) | '''Теорема 9''' ([17]) | ||
