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

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

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

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

Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении -равновесия Нэша и -поддерживаемого равновесия Нэша для биматричных игр и некоторого константного 0 <  < 1. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:

Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое -поддерживаемое равновесие Нэша получившейся игры является (1 + )/2-поддерживаемым равновесием Нэша исходной игры.

Два недавних результата улучшили статус приближения -равновесия Нэша:

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