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

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

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

Джон Форбс Нэш [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 }[/math] × [math]\displaystyle{ 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 в [math]\displaystyle{ i }[/math]-й координате и 0 – во всех остальных. Для матрицы [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n }[/math] × [math]\displaystyle{ m }[/math] обозначим за [math]\displaystyle{ a_{ij} }[/math] элемент в [math]\displaystyle{ i }[/math]-й строке и [math]\displaystyle{ j }[/math]-м столбце матрицы [math]\displaystyle{ A }[/math]. Пусть [math]\displaystyle{ \mathbb{P}^n }[/math] обозначает множество всех векторов вероятности в [math]\displaystyle{ n }[/math] измерениях: [math]\displaystyle{ \mathbb{P}^n = \left\{ \mathbf{z} \ni \mathbb{R}^n_{\ge 0} : \sum_{j=1}^n z_i=1 \right\} }[/math]

Биматричные игры

Биматричные игры [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами [math]\displaystyle{ n }[/math] × [math]\displaystyle{ m }[/math] – [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math]. [math]\displaystyle{ n }[/math] строк матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] представляют множество действий первого игрока (игрока по строкам), [math]\displaystyle{ m }[/math] столбцов представляют множество действий второго игрока (игрока по столбцам). Если игрок по строкам выбирает действие [math]\displaystyle{ i }[/math], а игрок по столбцам выбирает действие [math]\displaystyle{ j }[/math], то первый получает выигрыш [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}_n }[/math]. Каждая точка экстремума [math]\displaystyle{ \mathbf{e_i} \in \mathbb{P}_n }[/math] ([math]\displaystyle{ \mathbf{e_i} \in \mathbb{P}_n }[/math]), соответствующая стратегии, назначающей вероятность 1 [math]\displaystyle{ i }[/math]-й строке ([math]\displaystyle{ j }[/math]-му столбцу), называется чистой стратегией для игрока по строке (столбцу). Профиль стратегии ([math]\displaystyle{ \mathbf{x} }[/math], [math]\displaystyle{ \mathbf{y} }[/math]) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии ([math]\displaystyle{ \mathbf{x} }[/math], [math]\displaystyle{ \mathbf{y} }[/math]), игроки получают ожидаемый выигрыш [math]\displaystyle{ \mathbf{x}^T }[/math] [math]\displaystyle{ A \mathbf{y} }[/math] (игрок по строкам) и [math]\displaystyle{ \mathbf{x}^T }[/math] [math]\displaystyle{ B \mathbf{y} }[/math] (игрок по столбцам).

Если обе матрицы выигрышей принадлежат пространству [0, 1]^{m × n}, то игра называется [0, 1]-биматричной, или положительно нормализованной, игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с выигравшими и проигравшими. Биматричная игра [math]\displaystyle{ \langle }[/math]A, B [math]\displaystyle{ \rangle }[/math] называется игрой с нулевой суммой, если B = – А.

Приближенное равновесие Нэша

Определение 1 ([math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша)

Для любого [math]\displaystyle{ \epsilon \, }[/math] > 0 стратегический профиль (x, y) является [math]\displaystyle{ \epsilon \, }[/math]-равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n }[/math] × [math]\displaystyle{ 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{ i \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ \mathbf{x}^T B \mathbf{_{ej}}\le \mathbf{x}^T B \mathbf{_y} }[/math] + [math]\displaystyle{ \epsilon \, }[/math].

Определение 2 ([math]\displaystyle{ \epsilon \, }[/math]-поддерживаемое равновесие Нэша)

Для любого [math]\displaystyle{ \epsilon \, }[/math] > 0 стратегический профиль (x, y) является [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемым равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma= \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n }[/math] × [math]\displaystyle{ 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} A \mathbf{_k} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,n\} }[/math]
2. Для всех чистых стратегий [math]\displaystyle{ j \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ y_i \gt \ 0 \rightarrow \mathbf{x_i}^T B \mathbf{_{ej}} \ge \mathbf{x}^T B \mathbf{_{ek}} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,m\} }[/math]

Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки [math]\displaystyle{ \epsilon \, }[/math]. Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.

Основные результаты

В работе Альтхофера [1] показано, что для любого вектора вероятности [math]\displaystyle{ \mathbf{p} }[/math] существует вектор вероятности [math]\displaystyle{ \hat{p} }[/math] с логарифмической поддержкой, так что для фиксированной матрицы [math]\displaystyle{ C, max_j }[/math] [math]\displaystyle{ \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]-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий [math]\displaystyle{ n }[/math]). Рассмотрим биматричную игру [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math]. Пусть [math]\displaystyle{ (\mathbf{x, y}) }[/math] – равновесие Нэша для [math]\displaystyle{ \Gamma }[/math]. Зафиксируем положительное число [math]\displaystyle{ k }[/math] и сформируем мультимножество [math]\displaystyle{ S_1 }[/math], выполнив выборку [math]\displaystyle{ k }[/math] раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением [math]\displaystyle{ x }[/math]. Сформируем подобным же образом мультимножество [math]\displaystyle{ S_2 }[/math], выполнив выборку [math]\displaystyle{ k }[/math] раз из множества чистых стратегий игрока по столбцам в соответствии с распределением [math]\displaystyle{ 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 – всем остальным чистым стратегиям. Тогда x и у называются k-однородными [13], и для них выполняется:

Теорема 1

[13]Для любого равновесия Нэша (x, y) биматричной игры с матрицами n х n и для любого [math]\displaystyle{ \epsilon \, }[/math] > 0 существует, для каждого [math]\displaystyle{ k \ge(12 ln n)/ }[/math][math]\displaystyle{ \epsilon \, }[/math]², пара k-однородных стратегий [math]\displaystyle{ \mathbf{\hat{x}} }[/math],[math]\displaystyle{ \mathbf{\hat{y}} }[/math] , таких, что ( [math]\displaystyle{ \mathbf{\hat{x}} }[/math],[math]\displaystyle{ \mathbf{\hat{y}} }[/math] ) представляет собой [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша. В результате этого получаем квазиполиномиальный алгоритм сложности (n^{O(ln n)}) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4.

Теорема 2

[4]Задача вычисления [math]\displaystyle{ 1/n \Theta ^{(1)} }[/math]-равновесия Нэша для биматричной игры с матрицами n × n является 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]-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного 0 < [math]\displaystyle{ \epsilon \, }[/math] < 1. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:

Теорема 3

[10]Рассмотрим любую биматричную игру [math]\displaystyle{ \Gamma = \langle A, B\rangle }[/math] с матрицами n × m; пусть [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] с матрицами n × m. Пусть [math]\displaystyle{ \lambda_1^* ( \lambda_2^* ) }[/math] – минимальный среди всех равновесий Нэша для [math]\displaystyle{ \Gamma }[/math] ожидаемый выигрыш для игрока по строке (столбцу); пусть [math]\displaystyle{ \lambda = max{ \lambda_1^*, \lambda_2^*} }[/math]. Тогда существует [math]\displaystyle{ (2 + \lambda)/4 }[/math]-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.

Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша: Выбрать произвольную строку для игрока по строкам, к примеру, строку [math]\displaystyle{ i }[/math]. Пусть [math]\displaystyle{ j = arg\;max_{j\prime}\,b_{ij\prime} }[/math]. Пусть [math]\displaystyle{ k = arg\;max_{k\prime}\,a_{k\prime j} }[/math]. Таким образом, [math]\displaystyle{ j }[/math] – это столбец с лучшим ответом для игрока по столбцам в строке [math]\displaystyle{ i }[/math], а [math]\displaystyle{ k }[/math] – строка с лучшим ответом для игрока по строкам в столбце [math]\displaystyle{ j }[/math]. Пусть [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], т.е. игрок по строкам играет строку [math]\displaystyle{ i }[/math] или строку [math]\displaystyle{ k }[/math] с вероятностью 1/2 для каждой, тогда как игрок по столбцам играет столбец [math]\displaystyle{ j }[/math] с вероятностью 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], получаемую из ограничения ранга матрицы А + В до фиксированного ранга, не превышающего [math]\displaystyle{ k }[/math]. Они предложили новую модель [math]\displaystyle{ \epsilon \, }[/math]-аппроксимации для игр ранга [math]\displaystyle{ k }[/math] и, используя результаты квадратичной оптимизации, показали, что приближенные равновесия Нэша для игр с константным рангом могут быть вычислены детерминированным образом за время, полиномиальное относительно 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)