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

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

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

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

В результате появилась задача вычисления приближенного равновесия Нэша. На настоящий момент было опубликовано несколько вариантов приближенного равновесия Нэша; здесь будут рассмотрены понятия -равновесия Нэша и -поддерживаемого равновесия Нэша. -равновесие Нэша представляет собой профиль стратегии, такой, что ни один игрок, изменяющий решение, не может получить выигрыш больше, чем выигрыш при определенном профиле стратегии плюс . Более строгим является понятие -поддерживаемых равновесий Нэша; они представляют собой профили стратегий, такие, что каждый игрок использует только чистые стратегии с приближенно лучшим ответом с ненулевой вероятностью.

Нотация Для вектора 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 (-равновесие Нэша) Для любого  > 0 стратегический профиль (x, y) является -равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если 1. Для всех чистых стратегий i  {1, …, n} игрока по строкам eTi Ay ≤ xT Ay + ; 2. Для всех чистых стратегий j  {1, …, m} игрока по столбцам xT Bej ≤ xT By + .

Определение 2 (-поддерживаемое равновесие Нэша) Для любого  > 0 стратегический профиль (x, y) является -поддерживаемым равновесием Нэша для биматричной игры Г = A, B с матрицами n × m, если 1. Для всех чистых стратегий i  {1, …, n} игрока по строкам

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

Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки . Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.

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

В работе Альтхофера [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-однородных стратегий , , таких, что ( , ) представляет собой -равновесие Нэша.

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

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

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

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

В источнике [7] представлена полиномиальная конструкция (на базе линейного программирования) 0.38-равновесия Нэша.

Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое -поддерживаемое равновесие Нэша получившейся игры является (1 + )/2-поддерживаемым равновесием Нэша исходной игры. В работе Контогианниса и Спиракиса [11] приведен полиномиальный алгоритм вычисления 1/2-поддерживаемого равновесия Нэша для произвольных игр с выигравшими и проигравшими. В основе алгоритма лежит идея равномерного разделения величины отклонения от игры с нулевой суммой между двумя игроками и последующего решения получившейся игры с нулевой суммой за полиномиальное время, используя ее прямое сходство с алгоритмами линейного программирования. Доказано, что полученное равновесие Нэша для игры с нулевой суммой является 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. Они предложили новую модель -аппроксимации для игр ранга k и, используя результаты квадратичной оптимизации, показали, что приближенные равновесия Нэша для игр с константным рангом могут быть вычислены детерминированным образом за время, полиномиальное относительно 1/. Кроме того, в [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). Berke ley, 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)