Приближенные решения для биматричного равновесия Нэша: различия между версиями

'''Для любого равновесия Нэша <math>(\mathbf{x, y})</math> биматричной игры с матрицами <math>n \times n</math> и для любого <math>\epsilon > 0 \, </math> существует, для каждого <math>k \ge(12 ln n)/ \epsilon \, </math>², пара k-однородных стратегий  <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> , таких, что ( <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> ) представляет собой <math>\epsilon \, </math>-равновесие Нэша.

'''

===Теорема 3 ===

[10]<big>''Рассмотрим любую биматричную игру <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>.''</big>

Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша: Выбрать произвольную строку для игрока по строкам, к примеру, строку <math>i</math>. Пусть <math>j = arg\;max_{j\prime}\,b_{ij\prime}</math>. Пусть <math>k = arg\;max_{k\prime}\,a_{k\prime j}</math>. Таким образом, <math>j</math> – это столбец с лучшим ответом для игрока по столбцам в строке <math>i</math>, а <math>k</math> – строка с лучшим ответом для игрока по строкам в столбце <math>j</math>. Пусть <math>\mathbf{\hat{x}} = 1/2 \mathbf{e_i} + 1/2 \mathbf{e_k}</math> и <math>\mathbf{\hat{y}} = \mathbf{e_j}</math>, т.е. игрок по строкам играет строку <math>i</math> или строку <math>k</math> с вероятностью 1/2 для каждой, тогда как игрок по столбцам играет столбец <math>j</math> с вероятностью 1. Тогда верна:

===Теорема 5 ===

[6]<big>''Профиль стратегии (<math>\mathbf{\hat{x}} ,\mathbf{\hat{y}}</math> ) является 1/2-равновесием Нэша.''</big>

===Теорема 6 ===

[11]<big>''Для любых биматричных игр с выигравшими и проигравшими возможно построить за полиномиальное время профиль, представляющий собой 1/2-поддерживаемое равновесие Нэша для этой игры.''</big>

===Теорема 7 ===

[11]<big>''Для любых биматричных игр возможно построить <math>( \sqrt{11} /2 - 1 )</math>-поддерживаемое равновесие Нэша за полиномиальное время.''</big>

===Теорема 8 ===

[2]<big>''Существует алгоритм с полиномиальным временем, основанный на алгоритмах линейного программирования, который строит 0.36392-равновесие Нэша.''</big>

Каннан и Теобальд [9] исследовали иерархию биматричных игры <math>\langle A, B \rangle </math>, получаемую из ограничения ранга матрицы <big>''А + В''</big> до фиксированного ранга, не превышающего <math>k</math>. Они предложили новую модель <math>\epsilon \, </math>-аппроксимации для игр ранга <math>k</math> и, используя результаты квадратичной оптимизации, показали, что приближенные равновесия Нэша для игр с константным рангом могут быть вычислены детерминированным образом за время, полиномиальное относительно 1/<math>\epsilon \, </math>. Кроме того, в [9] представлен рандомизированный алгоритм приближения для определенных задач квадратичной оптимизации, что позволяет создать рандомизированный алгоритм приближения для задачи нахождения равновесия Нэша. Этот рандомизированный алгоритм имеет практически ту же временную сложность, что и детерминированный, однако при условии истинности предположения позволяет найти точное решение за полиномиальное время. Наконец, эти же авторы предложили алгоритм с полиномиальным временем для относительного приближения (касающегося выигрышей при равновесии) для случая, когда матрица <big>''A + B''</big> имеет неотрицательную декомпозицию.