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

Джон Форбс Нэш [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 (-равновесие Нэша)

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

В работе Альтхофера [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], и для них выполняется

Каннан и Теобальд [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)