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

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

 

 

 

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

 

 

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

 

'''Теорема 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> имеет неотрицательную декомпозицию.