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

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показано 9 промежуточных версий этого же участника)
Строка 34: Строка 34:


== Основные результаты ==
== Основные результаты ==
В работе Альтхофера [1] показано, что для любого вектора вероятности <math>\mathbf{p}</math> существует вектор вероятности <math>\hat{p}</math> с логарифмической поддержкой, так что для фиксированной матрицы <math>C, max_j</math> <math>\left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, </math> для любой ''константы'' <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любой константы <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий <math>n</math>). Рассмотрим биматричную игру <math>\Gamma = \langle A,B \rangle</math>. Пусть <math>(\mathbf{x, y})</math> – равновесие Нэша для <math>\Gamma</math>. Зафиксируем положительное число <math>k</math> и сформируем мультимножество <math>S_1</math>, выполнив выборку <math>k</math> раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением <math>x</math>. Сформируем подобным же образом мультимножество <math>S_2</math>, выполнив выборку <math>k</math> раз из множества чистых стратегий игрока по столбцам в соответствии с распределением <math>y</math>. Пусть <math>\mathbf{\hat{x}}</math>  – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/''k'' каждому члену <math>S_1</math> и 0 – всем остальным чистым стратегиям, а <math>\mathbf{\hat{y}}</math> – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/''k'' каждому члену <math>S_2</math> и 0 – всем остальным чистым стратегиям. Тогда x и у называются ''k''-однородными [13], и для них выполняется:
В работе Альтхофера [1] показано, что для ''любого'' вектора вероятности <math>p \, </math> существует вектор вероятности <math>\hat{p}</math> с логарифмической поддержкой, так что для фиксированной матрицы C выполняется <math>max_j \left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, </math> для любого константного <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любого ''константного'' <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру <math>\Gamma = \langle A,B \rangle</math>. Пусть <math>(\mathbf{x, y})</math> – равновесие Нэша для <math>\Gamma</math>. Зафиксируем положительное число k и сформируем мультимножество <math>S_1 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением <math>\mathbf{x}</math>. Сформируем подобным же образом мультимножество <math>S_2 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением <math>\mathbf{y}</math>. Пусть <math>\mathbf{\hat{x}}</math>  – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену <math>S_1 \, </math> и 0 – всем остальным чистым стратегиям, а <math>\mathbf{\hat{y}}</math> – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену <math>S_2 \, </math> и 0 – всем остальным чистым стратегиям. Тогда <math>\mathbf{x}</math> и <math>\mathbf{y}</math> называются k-однородными [13], и для них выполняется:


===Теорема 1  ===
[13]<big>''Для любого равновесия Нэша ('''x, y''') биматричной игры с матрицами n х n и для любого <math>\epsilon \, </math> > 0 существует, для каждого <math>k \ge(12 ln n)/</math><math>\epsilon \, </math><sup>2</sup>, пара k-однородных стратегий  <math>\mathbf{\hat{x}}</math>,<math>\mathbf{\hat{y}}</math> , таких, что ( <math>\mathbf{\hat{x}}</math>,<math>\mathbf{\hat{y}}</math> ) представляет собой <math>\epsilon \, </math>-равновесие Нэша.''
</big>
В результате этого получаем квазиполиномиальный алгоритм сложности (<big>''n<sup>O(ln n)</sup>''</big>) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4.


===Теорема 2 ===
'''Теорема 1''' ([13])
[4]<big>''Задача вычисления <math>1/n \Theta ^{(1)}</math>-равновесия Нэша для биматричной игры с матрицами n × n является PPAD-полной.''</big>


Теорема 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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.
'''Для любого равновесия Нэша <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>-равновесие Нэша.'''


Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного <big>0 < <math>\epsilon \, </math> < 1</big>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:
В результате этого получаем квазиполиномиальный алгоритм (<big>n<sup>O(ln n)</sup></big>) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4.
 
 
'''Теорема 2''' ([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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.
 
 
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого ''константного'' <math>0 < \epsilon < 1 \, </math>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:
 
 
'''Теорема 3''' ([10])
 
'''Рассмотрим любую биматричную игру <math>\Gamma = \langle A, B\rangle</math> с матрицами <math>n \times m</math>; пусть <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>.'''


===Теорема 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>


Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение:
Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение:


===Теорема 4 ===
[10]<big>''Рассмотрим биматричную игру <math>\Gamma = \langle A, B \rangle</math> с матрицами n × m. Пусть <math>\lambda_1^* ( \lambda_2^* )</math> – минимальный среди всех равновесий Нэша для <math>\Gamma</math> ожидаемый выигрыш для игрока по строке (столбцу); пусть <math>\lambda = max{ \lambda_1^*, \lambda_2^*}</math>. Тогда существует <math>(2 + \lambda)/4</math>-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.''</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. Тогда верна:
'''Теорема 4''' ([10])
 
'''Рассмотрим биматричную игру <math>\Gamma = \langle A, B \rangle</math> с матрицами <math>n \times m</math>. Пусть <math>\lambda_1^* ( \lambda_2^* )</math> – минимальный среди всех равновесий Нэша для <math>\Gamma \, </math> ожидаемый выигрыш для игрока по строке (столбцу); пусть <math>\lambda = max \, </math> '''{''' <math>\lambda_1^*, \lambda_2^*</math> '''}'''. Тогда существует <math>(2 + \lambda)/4 \, </math>-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.'''
 


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


В источнике [7] представлена полиномиальная конструкция (на базе линейного программирования) 0.38-равновесия Нэша.  
В источнике [7] представлена полиномиальная конструкция (на базе линейного программирования) 0.38-равновесия Нэша.  


Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое <math>\epsilon \, </math>-поддерживаемое равновесие Нэша получившейся игры является (1 + <math>\epsilon \, </math>)/2-поддерживаемым равновесием Нэша исходной игры.
Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое <math>\epsilon \, </math>-поддерживаемое равновесие Нэша получившейся игры является (1 + <math>\epsilon \, </math>)/2-поддерживаемым равновесием Нэша исходной игры.
В работе Контогианниса и Спиракиса [11] приведен полиномиальный алгоритм вычисления 1/2-поддерживаемого равновесия Нэша для произвольных игр с выигравшими и проигравшими. В основе алгоритма лежит идея равномерного разделения величины отклонения от игры с нулевой суммой между двумя игроками и последующего решения получившейся игры с нулевой суммой за полиномиальное время, используя ее прямое сходство с алгоритмами линейного программирования. Доказано, что полученное равновесие Нэша для игры с нулевой суммой является 1/2-поддерживаемым равновесием Нэша для исходной игры с выигравшими и проигравшими. Таким образом, верна
В работе Контогианниса и Спиракиса [11] приведен полиномиальный алгоритм вычисления 1/2-поддерживаемого равновесия Нэша для произвольных игр с выигравшими и проигравшими. В основе алгоритма лежит идея равномерного разделения величины отклонения от игры с нулевой суммой между двумя игроками и последующего решения получившейся игры с нулевой суммой за полиномиальное время, используя ее прямое сходство с алгоритмами линейного программирования. Доказано, что полученное равновесие Нэша для игры с нулевой суммой является 1/2-поддерживаемым равновесием Нэша для исходной игры с выигравшими и проигравшими. Таким образом, верна


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


В той же публикации Контогианнис и Спиракис [11] параметризовали вышеописанную методологию для применения ее к произвольным биматричным играм. Новая техника способствует нахождению более слабого <math>\phi</math>-поддерживаемого равновесия Нэша для игр с выигравшими и проигравшими, где <math>\phi = \left ( \sqrt{5} -1 \right )/2 </math> – величина золотого сечения. Тем не менее, эта параметризованная техника легко расширяется на произвольные биматричные игры, что гарантирует нахождение 0.658-поддерживаемого равновесия Нэша за полиномиальное время:
В той же публикации Контогианнис и Спиракис [11] параметризовали вышеописанную методологию для применения ее к произвольным биматричным играм. Новая техника способствует нахождению более слабого <math>\phi</math>-поддерживаемого равновесия Нэша для игр с выигравшими и проигравшими, где <math>\phi = \left ( \sqrt{5} -1 \right )/2 </math> – величина золотого сечения. Тем не менее, эта параметризованная техника легко расширяется на произвольные биматричные игры, что гарантирует нахождение 0.658-поддерживаемого равновесия Нэша за полиномиальное время:


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


Два недавних результата улучшили статус приближения <math>\epsilon \, </math>-равновесия Нэша:
Два недавних результата улучшили статус приближения <math>\epsilon \, </math>-равновесия Нэша:


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


Следующий результат на данный момент является наилучшим:
Следующий результат на данный момент является наилучшим:


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


== Применение ==
== Применение ==

Текущая версия от 13:59, 1 октября 2023

Ключевые слова и синонимы: эпсилон-равновесие Нэша; эпсилон-поддерживаемое равновесие Нэша


Постановка задачи

Джон Форбс Нэш [14] ввел понятие равновесия Нэша в некооперативных играх и доказал, что для любой игры существует по меньшей мере одно такое равновесие. Хорошо известный алгоритм вычисления равновесия Нэша для игры с двумя игроками – алгоритм Лемке-Хоусона [12] – в худшем случае имеет экспоненциальную сложность от количества доступных чистых стратегий [16]. Недавно Даскалакис и коллеги [5] показали, что задача вычисления равновесия Нэша для игры с четырьмя и более игроками является PPAD-полной; этот результат был впоследствии распространен на игры с тремя игроками [8]. В конечном счете, Чен и Денг [3] доказали, что задача является PPAD-полной также и для игр с двумя игроками.

В результате появилась задача вычисления приближенного равновесия Нэша. На настоящий момент было опубликовано несколько вариантов приближенного равновесия Нэша; здесь будут рассмотрены понятия [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша и [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемого равновесия Нэша. [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша представляет собой профиль стратегии, такой, что ни один игрок, изменяющий решение, не может получить выигрыш больше, чем выигрыш при определенном профиле стратегии плюс [math]\displaystyle{ \epsilon \, }[/math]. Более строгим является понятие [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемых равновесий Нэша; они представляют собой профили стратегий, такие, что каждый игрок использует только чистые стратегии с приближенно лучшим ответом с ненулевой вероятностью.

Нотация

Для вектора [math]\displaystyle{ \mathbf{x} }[/math] формата [math]\displaystyle{ n \times 1 }[/math] обозначим за [math]\displaystyle{ x_1,\!...,x_n }[/math] компоненты [math]\displaystyle{ \mathbf{x} }[/math] и за [math]\displaystyle{ \mathbf{x}^T }[/math] – перестановку вектора [math]\displaystyle{ \mathbf{x} }[/math]. Обозначим за [math]\displaystyle{ \mathbf{e}_i }[/math] вектор столбца, имеющего значение 1 в i-й координате и 0 – во всех остальных. Для матрицы A размера [math]\displaystyle{ n \times m }[/math] обозначим за [math]\displaystyle{ a_{ij} \, }[/math] элемент в i-й строке и j-м столбце матрицы A. Пусть [math]\displaystyle{ \mathbb{P}^n }[/math] обозначает множество всех векторов вероятности в n измерениях: [math]\displaystyle{ \mathbb{P}^n = \left\{ \mathbf{z} \in \mathbb{R}^n_{\ge 0} : \sum_{i=1}^n z_i=1 \right\} }[/math]

Биматричные игры

Биматричные игры [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами [math]\displaystyle{ n \times m }[/math] – A и B. n строк матриц A и B представляют множество действий первого игрока (игрока по строкам), m столбцов представляют множество действий второго игрока (игрока по столбцам). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш [math]\displaystyle{ a_{ij} \, }[/math], а второй – выигрыш [math]\displaystyle{ b_{ij} \, }[/math]. В силу этого биматричные игры обозначаются как [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math].

Стратегия для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности [math]\displaystyle{ \mathbf{x} \in \mathbb{P}^n }[/math], а стратегия для игрока по столбцам – в виде вектора вероятности [math]\displaystyle{ \mathbf{y} \in \mathbb{P}^m }[/math]. Каждая точка экстремума [math]\displaystyle{ \mathbf{e_i} \in \mathbb{P}_n }[/math] ([math]\displaystyle{ \mathbf{e_j} \in \mathbb{P}^m }[/math]), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется чистой стратегией для игрока по строке (столбцу). Профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]), игроки получают ожидаемый выигрыш [math]\displaystyle{ \mathbf{x}^T A \mathbf{y} }[/math] (игрок по строкам) и [math]\displaystyle{ \mathbf{x}^T B \mathbf{y} }[/math] (игрок по столбцам).

Если обе матрицы выигрышей принадлежат пространству [0, 1]m × n, то игра называется [0, 1]-биматричной, или положительно нормализованной, игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с выигравшими и проигравшими. Биматричная игра [math]\displaystyle{ \langle A, B \rangle }[/math] называется игрой с нулевой суммой, если B = –А.

Приближенное равновесие Нэша

Определение 1 ([math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша)

Для любого [math]\displaystyle{ \epsilon \gt 0 \, }[/math] профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) является [math]\displaystyle{ \epsilon \, }[/math]-равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math], если

  1. Для всех чистых стратегий [math]\displaystyle{ i \in \{1,\!...,n\} }[/math] игрока по строкам [math]\displaystyle{ \mathbf{e_i}^T A \mathbf{y} \le \mathbf{x}^T A \mathbf{y} }[/math] + [math]\displaystyle{ \epsilon \, }[/math];
  2. Для всех чистых стратегий [math]\displaystyle{ j \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ \mathbf{x}^T B \mathbf{e_j}\le \mathbf{x}^T B \mathbf{y} }[/math] + [math]\displaystyle{ \epsilon \, }[/math].

Определение 2 ([math]\displaystyle{ \epsilon \, }[/math]-поддерживаемое равновесие Нэша)

Для любого [math]\displaystyle{ \epsilon \, }[/math] > 0 профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) является [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемым равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma= \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math], если

  1. Для всех чистых стратегий [math]\displaystyle{ i \in \{1,\!...,n\} }[/math] игрока по строкам [math]\displaystyle{ x_i \gt 0 \Rightarrow \; \mathbf{e_i}^T A \mathbf{y} \ge \mathbf{e_k}^T A \mathbf{y} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,n\} }[/math]
  2. Для всех чистых стратегий [math]\displaystyle{ j \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ y_j \gt 0 \Rightarrow \; \mathbf{x}^T B \mathbf{e_j} \ge \mathbf{x}^T B \mathbf{e_k} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,m\} }[/math]


Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки [math]\displaystyle{ \epsilon \, }[/math]. Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.

Основные результаты

В работе Альтхофера [1] показано, что для любого вектора вероятности [math]\displaystyle{ p \, }[/math] существует вектор вероятности [math]\displaystyle{ \hat{p} }[/math] с логарифмической поддержкой, так что для фиксированной матрицы C выполняется [math]\displaystyle{ max_j \left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, }[/math] для любого константного [math]\displaystyle{ \epsilon \, }[/math] > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любого константного [math]\displaystyle{ \epsilon \, }[/math] > 0 существует [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math]. Пусть [math]\displaystyle{ (\mathbf{x, y}) }[/math] – равновесие Нэша для [math]\displaystyle{ \Gamma }[/math]. Зафиксируем положительное число k и сформируем мультимножество [math]\displaystyle{ S_1 \, }[/math], выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением [math]\displaystyle{ \mathbf{x} }[/math]. Сформируем подобным же образом мультимножество [math]\displaystyle{ S_2 \, }[/math], выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением [math]\displaystyle{ \mathbf{y} }[/math]. Пусть [math]\displaystyle{ \mathbf{\hat{x}} }[/math] – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену [math]\displaystyle{ S_1 \, }[/math] и 0 – всем остальным чистым стратегиям, а [math]\displaystyle{ \mathbf{\hat{y}} }[/math] – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену [math]\displaystyle{ S_2 \, }[/math] и 0 – всем остальным чистым стратегиям. Тогда [math]\displaystyle{ \mathbf{x} }[/math] и [math]\displaystyle{ \mathbf{y} }[/math] называются k-однородными [13], и для них выполняется:


Теорема 1 ([13])

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

В результате этого получаем квазиполиномиальный алгоритм (nO(ln n)) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4.


Теорема 2 ([4])

Задача вычисления [math]\displaystyle{ 1/n^{\Theta (1)} \, }[/math]-равновесия Нэша для биматричной игры с матрицами [math]\displaystyle{ n \times n }[/math] является PPAD-полной.

Теорема 2 утверждает, что за исключением случаев, когда PPAD [math]\displaystyle{ \subseteq }[/math] P, не существует аппроксимационной схемы с полностью полиномиальным временем выполнения для вычисления равновесия в биматричных играх. Однако это не исключает существования аппроксимационной схемы с полиномиальным временем для вычисления [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша, где [math]\displaystyle{ \epsilon \, }[/math] является абсолютной константой, и даже в случае [math]\displaystyle{ \epsilon \, = \Theta \big( 1/poly(ln n) \big). }[/math]Более того, как было замечено в [4], если бы задача нахождения [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша была PPAD-полной в случае, когда [math]\displaystyle{ \epsilon \, }[/math] является абсолютной константой, то, согласно Теореме 1, все PPAD-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.


Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша и [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного [math]\displaystyle{ 0 \lt \epsilon \lt 1 \, }[/math]. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:


Теорема 3 ([10])

Рассмотрим любую биматричную игру [math]\displaystyle{ \Gamma = \langle A, B\rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math]; пусть [math]\displaystyle{ a_{i1}, _{j1} = max_i, _j a_{ij} \, }[/math] и [math]\displaystyle{ b_{i2}, _{j2} = max_i, _j b_{ij} \, }[/math]. Тогда пара стратегий ([math]\displaystyle{ \mathbf{\hat{x}}, \mathbf{\hat{y}} }[/math] ), где [math]\displaystyle{ \mathbf{\hat{x}}_{i1} = \mathbf{\hat{x}}_{i2} = \mathbf{\hat{y}}_{j1} = \mathbf{\hat{y}}_{j2} = 1/2 }[/math], является 3/4-равновесием Нэша для игры [math]\displaystyle{ \Gamma }[/math].


Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение:


Теорема 4 ([10])

Рассмотрим биматричную игру [math]\displaystyle{ \Gamma = \langle A, B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math]. Пусть [math]\displaystyle{ \lambda_1^* ( \lambda_2^* ) }[/math] – минимальный среди всех равновесий Нэша для [math]\displaystyle{ \Gamma \, }[/math] ожидаемый выигрыш для игрока по строке (столбцу); пусть [math]\displaystyle{ \lambda = max \, }[/math] { [math]\displaystyle{ \lambda_1^*, \lambda_2^* }[/math] }. Тогда существует [math]\displaystyle{ (2 + \lambda)/4 \, }[/math]-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.


Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша:

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


Теорема 5 ([6])

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

В источнике [7] представлена полиномиальная конструкция (на базе линейного программирования) 0.38-равновесия Нэша.


Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемое равновесие Нэша получившейся игры является (1 + [math]\displaystyle{ \epsilon \, }[/math])/2-поддерживаемым равновесием Нэша исходной игры.


В работе Контогианниса и Спиракиса [11] приведен полиномиальный алгоритм вычисления 1/2-поддерживаемого равновесия Нэша для произвольных игр с выигравшими и проигравшими. В основе алгоритма лежит идея равномерного разделения величины отклонения от игры с нулевой суммой между двумя игроками и последующего решения получившейся игры с нулевой суммой за полиномиальное время, используя ее прямое сходство с алгоритмами линейного программирования. Доказано, что полученное равновесие Нэша для игры с нулевой суммой является 1/2-поддерживаемым равновесием Нэша для исходной игры с выигравшими и проигравшими. Таким образом, верна


Теорема 6 ([11])

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

В той же публикации Контогианнис и Спиракис [11] параметризовали вышеописанную методологию для применения ее к произвольным биматричным играм. Новая техника способствует нахождению более слабого [math]\displaystyle{ \phi }[/math]-поддерживаемого равновесия Нэша для игр с выигравшими и проигравшими, где [math]\displaystyle{ \phi = \left ( \sqrt{5} -1 \right )/2 }[/math] – величина золотого сечения. Тем не менее, эта параметризованная техника легко расширяется на произвольные биматричные игры, что гарантирует нахождение 0.658-поддерживаемого равновесия Нэша за полиномиальное время:


Теорема 7 ([11])

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


Два недавних результата улучшили статус приближения [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша:


Теорема 8 ([2])

Существует алгоритм с полиномиальным временем, основанный на алгоритмах линейного программирования, который строит 0.36392-равновесие Нэша.


Следующий результат на данный момент является наилучшим:


Теорема 9 ([17])

Существует алгоритм с полиномиальным временем, основанный на нахождении неподвижных точек в естественной задаче оптимизации, который строит 0.3393-равновесие Нэша.


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

Применение

Теория некооперативных игр и основное понятие для их решения – равновесие Нэша – широко использовались для понимания феноменов, наблюдаемых при взаимодействии лиц, принимающих решения, и применялись во множестве различных научных областей в таких сферах, как биология, экономика, социология и искусственный интеллект. Однако, поскольку вычисление равновесия Нэша в общем случае является PPAD-полной задачей, важное значение имеет создание эффективных алгоритмов для нахождения приближенного равновесия; изложенные выше алгоритмы представляют собой первые шаги на этом пути.

См. также

Литература

1. Althofer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebr. Appl. 199, 339-355(1994)

2. Bosse, H., Byrka, J., Markakis, E.: New Algorithms for Approximate Nash Equilibria in Bimatrix Games. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), San Diego, 12-14 December 2007

3. Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). Berkeley, 21-24 October 2005

4. Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: Approximation and smoothed complexity. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), Berkeley, 21-24 October 2006

5. Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), pp. 71-78. Seattle, 21-23 May 2006

6. Daskalakis, C., Mehta, A., Papadimitriou, C.: A note on approximate Nash equilibria. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 297-306. Patras, 15-17 December 2006

7. Daskalakis, C., Mehta, A., Papadimitriou, C: Progress in approximate Nash equilibrium. In: Proceedings of the 8th ACM Conference on Electronic Commerce (EC07), San Diego, 11-15 June 2007

8. Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: Electronic Colloquium on Computational Complexity (ECCC) (2005)

9. Kannan, R., Theobald, T.: Games of fixed rank: A hierarchy of bimatrix games. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007

10. Kontogiannis, S., Panagopoulou, P.N., Spirakis, P.G.: Polynomial algorithms for approximating Nash equilibria of bimatrix games. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 286-296. Patras, 15-17 December 2006

11. Kontogiannis, S., Spirakis, P.G.: Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A: Algorithms and Complexity), Wroclaw, 9-13 July 2007

12. Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12,413-423 (1964)

13. Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple startegies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC'03), pp. 36-41. San Diego, 9-13 June 2003

14. Nash, J.: Noncooperative games. Ann. Math. 54, 289-295 (1951)

15. Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian Symposium on Combinatorics 1990, Prachatice (1991)

16. Savani, R., von Stengel, B.: Exponentially many steps for finding a nash equilibrium in a bimatrix game. In: Proceedings of the45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 258-267. Rome, 17-19 October 2004

17. Tsaknakis, H., Spirakis, P.: An Optimization Approach for Approximate Nash Equilibria. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), also in the Electronic Colloquium on Computational Complexity, (ECCC),TR07-067 (Revision), San Diego, 12-14 December 2007

18. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ (1944)