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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «Приближенные решения для биматричного равновесия Нэша Ключевые слова и синонимы -равно…»)
 
мНет описания правки
 
(не показана 21 промежуточная версия этого же участника)
Строка 1: Строка 1:
Приближенные решения для биматричного равновесия Нэша
Ключевые слова и синонимы: [[эпсилон-равновесие Нэша]]; [[эпсилон-поддерживаемое равновесие Нэша]]


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


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


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


Биматричные игры
== Биматричные игры ==
Биматричные игры [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами n × m – A и B. n строк матриц A и B представляют множество действий первого игрока (игрока по строкам), m столбцов представляют множество действий второго игрока (игрока по столбцам). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш aij, а второй – выигрыш bij. В силу этого биматричные игры обозначаются как Г = A; B.
''Биматричные игры'' [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами <math>n \times m</math> – A и B. n строк матриц A и B представляют множество действий первого игрока (''игрока по строкам''), m столбцов представляют множество действий второго игрока (''игрока по столбцам''). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш <math>a_{ij} \, </math>, а второй – выигрыш <math>b_{ij} \, </math>. В силу этого биматричные игры обозначаются как <math>\Gamma = \langle A,B \rangle</math>.
Стратегия для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности x  Pn, а стратегия для игрока по столбцам – в виде вектора вероятности y  Pm. Каждая точка экстремума ei  Pn (ej  Pm), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется чистой стратегией для игрока по строке (столбцу). Профиль стратегии (x, y) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии (x, y), игроки получают ожидаемый выигрыш xT Ay (игрок по строкам) и xT By (игрок по столбцам).
 
Если обе матрицы выигрышей принадлежат пространству [0, l]m × n, то игра называется [0, 1]-биматричной, или положительно нормализованной, игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с выигравшими и проигравшими. Биматричная игра A, B называется игрой с нулевой суммой, если B = – А.  
[[Стратегия]] для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности <math>\mathbf{x} \in \mathbb{P}^n</math>, а стратегия для игрока по столбцам – в виде вектора вероятности <math>\mathbf{y} \in \mathbb{P}^m</math>. Каждая точка экстремума <math>\mathbf{e_i} \in \mathbb{P}_n</math> (<math>\mathbf{e_j} \in \mathbb{P}^m</math>), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется ''чистой стратегией'' для игрока по строке (столбцу). ''Профиль стратегии'' (<math>\mathbf{x}, \mathbf{y}</math>) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии (<math>\mathbf{x}, \mathbf{y}</math>), игроки получают [[ожидаемый выигрыш]] <math>\mathbf{x}^T A \mathbf{y}</math> (игрок по строкам) и <math>\mathbf{x}^T B \mathbf{y}</math> (игрок по столбцам).
 
Приближенное равновесие Нэша
Если обе матрицы выигрышей принадлежат пространству [0, 1]<sup>m × n</sup>, то игра называется [0, 1]-биматричной, или ''положительно нормализованной'', игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с ''выигравшими и проигравшими''. Биматричная игра <math>\langle A, B \rangle</math> называется игрой с ''нулевой суммой'', если B = –А.
 
== Приближенное равновесие Нэша ==


Определение 1 (-равновесие Нэша)
===Определение 1 (<math>\epsilon \, </math>-равновесие Нэша)===
Для любого > 0 стратегический профиль (x, y) является -равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если
Для любого <math>\epsilon > 0 \, </math> профиль стратегии (<math>\mathbf{x}, \mathbf{y}</math>) является <math>\epsilon \, </math>-''равновесием Нэша'' для биматричной игры <math>\Gamma = \langle A,B \rangle</math> с матрицами <math>n \times m</math>, если
1. Для всех чистых стратегий i {1, , n} игрока по строкам eTi Ay ≤ xT Ay + ;
# Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>\mathbf{e_i}^T A \mathbf{y} \le \mathbf{x}^T A \mathbf{y}</math>  + <math>\epsilon \, </math>;
2. Для всех чистых стратегий j {1, , m} игрока по столбцам xT Bej ≤ xT By + .
# Для всех чистых стратегий <math> j \in \{1,\!...,m\}</math> игрока по столбцам <math>\mathbf{x}^T B \mathbf{e_j}\le \mathbf{x}^T B \mathbf{y}</math> + <math>\epsilon \, </math>.


Определение 2 (-поддерживаемое равновесие Нэша)
===Определение 2 (<math>\epsilon \, </math>-поддерживаемое равновесие Нэша)===
Для любого > 0 стратегический профиль (x, y) является -поддерживаемым равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если
Для любого <math>\epsilon \, </math> > 0 профиль стратегии (<math>\mathbf{x}, \mathbf{y}</math>) является <math>\epsilon \, </math>''-поддерживаемым равновесием Нэша'' для биматричной игры <math>\Gamma= \langle A,B \rangle</math> с матрицами <math>n \times m</math>, если
1. Для всех чистых стратегий i {1, , n} игрока по строкам
# Для всех чистых стратегий <math> i \in \{1,\!...,n\}</math> игрока по строкам <math>x_i > 0 \Rightarrow \; \mathbf{e_i}^T A \mathbf{y} \ge \mathbf{e_k}^T A \mathbf{y} - \epsilon</math>  <math>\forall k \in \{1,\!...,n\}</math>
# Для всех чистых стратегий <math> j \in \{1,\!...,m\}</math> игрока по столбцам <math>y_j > 0 \Rightarrow \; \mathbf{x}^T B \mathbf{e_j} \ge \mathbf{x}^T B \mathbf{e_k} - \epsilon</math>  <math>\forall k \in \{1,\!...,m\}</math>
   
   
2. Для всех чистых стратегий j  {1, …, m} игрока по столбцам
   
   
Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки <math>\epsilon \, </math>. Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.
Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки . Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.
 
== Основные результаты ==
В работе Альтхофера [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])
 
'''Для любого равновесия Нэша <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.
 
 
'''Теорема 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-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.


Основные результаты
В работе Альтхофера [1] показано, что для любого вектора вероятности p существует вектор вероятности p с логарифмической поддержкой, так что для фиксированной матрицы C maxj |pTCej –  TCej| ≤  для любой константы  > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любой константы  > 0 существует -равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру Г = A, B. Пусть let (x, y) – равновесие Нэша для Г. Зафиксируем положительное число k и сформируем мультимножество S1, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соотвествии с распределением x. Сформируем подобным же образом мультимножество S2, выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением y. Пусть  – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену S1 и 0 – всем остальным чистым стратегиям, а  – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену S2 и 0 – всем остальным чистым стратегиям. Тогда x и у называются k-однородными [13], и для них выполняется


Теорема 1 ([13]) Для любого равновесия Нэша (x, y) биматричной игры с матрциами n х n и для любого  > 0 существует, для каждого k  (12 ln n)/2, пара k-однородных стратегий  , , таких, что ( , ) представляет собой -равновесие Нэша.
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого ''константного'' <math>0 < \epsilon < 1 \, </math>. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:


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


Теорема 2 ([4]) Задача вычисления 1/n(1)-равновесия Нэша для биматричной игры с матрицами n × n является PPAD-полной.
'''Теорема 3''' ([10])


Теорема 2 утверждает, что за исключением случаев, когда PPAD  P, не существует схемы аппроксимации с полностью полиномиальным временем исполнения для вычисления равновесия в биматричных играх. Однако это не исключает существования схемы аппроксимации с полиномиальным временем для вычисления -равновесия Нэша, где  является абсолютной константой, и даже в случае  = (1/poly(ln n)). Более того, как было замечено в [4], если бы задача нахождения -равновесия Нэша была PPAD-полной в случае, когда  является абсолютной константой, то, согласно Теореме 1, все PPAD-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.
'''Рассмотрим любую биматричную игру <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>.'''
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении -равновесия Нэша и -поддерживаемого равновесия Нэша для биматричных игр и некоторого константного 0 < < 1. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:


Теорема 3 ([10]) Рассмотрим любую биматричную игру Г = A, B с матрицами n × m; пусть ai1,j1 = maxi,j aij и bi2,j2 = maxi,j bij. Тогда пара стратегий ( , ), где  i1 =  i2 =  j1 =  j2 = ½, является 3/4-равновесием Нэша для игры Г.


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


Теорема 4 ([10]) Рассмотрим биматричную игру Г = A, B  с матрицами n × m. Пусть 1* (2*) – минимальный среди всех равновесий Нэша для Г ожидаемый выигрыш для игрока по строке (столбцу); пусть  = max{1*, 2*}. Тогда существует (2 + )/4-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.


Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша: Выбрать произвольную строку для игрока по строкам, к примеру, строку i. Пусть j = arg maxj’ bij’. Пусть k = arg maxk’ ak’j. Таким образом, j – это столбец с лучшим ответом для игрока по столбцам в строке i, а k – строка с лучшим ответом для игрока по строкам в столбце j. Пусть   = 1/2ei + 1/2ek и   = ej, т.е. игрок по строкам играет строку i или строку k с вероятностью 1/2 для каждой, тогда как игрок по столбцам играет столбец j с вероятностью 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.'''
 
 
Даскалакис, Мета и Пападимитриу [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]) Профиль стратегии ( , ) является 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}-биматричную игру того же размера, в силу чего любое -поддерживаемое равновесие Нэша получившейся игры является (1 + )/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]) Для любых биматричных игр с выигравшими и проигравшими возможно построить за полиномиальное время профиль, представляющий собой 1/2-поддерживаемое равновесие Нэша для этой игры.


В той же публикации Контогианнис и Спиракис [11] параметризовали вышеописанную методологию для применения ее к произвольным биматричным играм. Новая техника способствует нахождению более слабого -поддерживаемого равновесия Нэша для игр с выигравшими и проигравшими, где  = (√5 – 1)/2 – величина золотого сечения. Тем не менее, эта параметризованная техника легко расширяется на произвольные биматричные игры, что гарантирует нахождение 0.658-поддерживаемого равновесия Нэша за полиномиальное время:
'''Теорема 6''' ([11])


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


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


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


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


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


Каннан и Теобальд [9] исследовали иерархию биматричных задач hA, Bi, получаемую из ограничения ранга матрицы A + B до фиксированного ранга, не превышающего k. Они предложили новую модель -аппроксимации для игр ранга k и, используя результаты квадратичной оптимизации, показали, что приближенные равновесия Нэша для игр с константным рангом могут быть вычислены детерминированным образом за время, полиномиальное относительно 1/. Кроме того, в [9] представлен рандомизированный алгоритм приближения для определенных задач квадратичной оптимизации, что позволяет создать рандомизированный алгоритм приближения для задачи нахождения равновесия Нэша. Этот рандомизированный алгоритм имеет практически ту же временную сложность, что и детерминированный, однако при условии истинности предположения позволяет найти точное решение за полиномиальное время. Наконец, эти же авторы предложили алгоритм с полиномиальным временем для относительного приближения (касающегося выигрышей при равновесии) для случая, когда матрица A + B имеет неотрицательную декомпозицию.
'''Теорема 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> имеет неотрицательную декомпозицию.
 
== Применение ==
Теория некооперативных игр и основное понятие для их решения – равновесие Нэша – широко использовались для понимания феноменов, наблюдаемых при взаимодействии лиц, принимающих решения, и применялись во множестве различных научных областей в таких сферах, как биология, экономика, социология и искусственный интеллект. Однако, поскольку вычисление равновесия Нэша в общем случае является PPAD-полной задачей, важное значение имеет создание эффективных алгоритмов для нахождения приближенного равновесия; изложенные выше алгоритмы представляют собой первые шаги на этом пути.


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


Перекрестные ссылки
* ''[[Сложность биматричного равновесия Нэша]]
Сложность биматричного равновесия Нэша
* ''[[Равновесие в общем случае]]
Равновесие в общем случае
* ''[[Неаппроксимируемость биматричного равновесия Нэша]]
Неаппроксимируемость биматричного равновесия Нэша


Литература
== Литература ==
1. Althofer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebr. Appl. 199, 339-355(1994)
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
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). Berke ley, 21-24 October 2005
 
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
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
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
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
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)
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
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
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
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)
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
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)
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)
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
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
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)
18. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ (1944)

Текущая версия от 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)