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

''Биматричные игры'' [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>.

Для любого <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>, если

# Для всех чистых стратегий <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>;

# Для всех чистых стратегий <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>.

Для любого <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>, если

# Для всех чистых стратегий <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>

В работе Альтхофера [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], и для них выполняется:

 

 

 

 

 

 

'''Задача вычисления <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-равновесия Нэша для любой биматричной игры:

 

 

 

 

 

 

Даскалакис, Мета и Пападимитриу [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. Тогда верна

 

 

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

 

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

 

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

'''

 

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

 

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

 

 

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

 

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

 

 

 

 

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