Аноним

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

Материал из WEGA

Приближенные решения для биматричного равновесия Нэша (посмотреть исходный код)

Версия от 18:39, 8 марта 2012

38 байт убрано ,  8 марта 2012
→‎Основные результаты
Строка 49: Строка 49:


Теорема 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>-поддерживаемого равновесия Нэша для биматричных игр и некоторого ''константного'' <math>0 < \epsilon < 1 \, </math>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого ''константного'' <math>0 < \epsilon < 1 \, </math>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:


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


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


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


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


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


Даскалакис, Мета и Пападимитриу [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. Тогда верна:
Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша:


Выбрать произвольную строку для игрока по строкам, к примеру, строку 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])
'''Теорема 5''' ([6])


'''Профиль стратегии (<math>\mathbf{\hat{x}} ,\mathbf{\hat{y}}</math> ) является 1/2-равновесием Нэша.'''
'''Профиль стратегии (<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-поддерживаемым равновесием Нэша для исходной игры с выигравшими и проигравшими. Таким образом, верна


Irina
4446

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10247