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

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

В результате появилась задача вычисления приближенного равновесия Нэша. На настоящий момент было опубликовано несколько вариантов приближенного равновесия Нэша; здесь будут рассмотрены понятия <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 = .

Биматричные игры [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами n × m – A и B. n строк матриц A и B представляют множество действий первого игрока (игрока по строкам), m столбцов представляют множество действий второго игрока (игрока по столбцам). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш aij, а второй – выигрыш bij. В силу этого биматричные игры обозначаются как Г = A; B.

Стратегия для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности 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 = – А.  

Определение 1 (<math>\epsilon \, </math>-равновесие Нэша)

Для любого <math>\epsilon \, </math> > 0 стратегический профиль (x, y) является <math>\epsilon \, </math>-равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если

1. Для всех чистых стратегий i  {1, …, n} игрока по строкам eTi Ay ≤ xT Ay + <math>\epsilon \, </math>;

2. Для всех чистых стратегий j  {1, …, m} игрока по столбцам xT Bej ≤ xT By + <math>\epsilon \, </math>.

Определение 2 (<math>\epsilon \, </math>-поддерживаемое равновесие Нэша)

Для любого <math>\epsilon \, </math> > 0 стратегический профиль (x, y) является <math>\epsilon \, </math>-поддерживаемым равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если

1. Для всех чистых стратегий i  {1, …, n} игрока по строкам

2. Для всех чистых стратегий j  {1, …, m} игрока по столбцам

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

 

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

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

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

Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении <math>\epsilon \, </math>-равновесия Нэша и <math>\epsilon \, </math>-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного 0 < <math>\epsilon \, </math> < 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. Тогда верна

Теорема 5 ([6]) Профиль стратегии ( , ) является 1/2-равновесием Нэша.

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

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

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

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

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

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