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

В середине прошлого века Джон Нэш, изучая некооперативные игры общего вида [ ], доказал, что существует набор смешанных стратегий, который сейчас принято называть равновесием Нэша, по одной для каждого игрока – такой, что ни один игрок не может получить преимущество, если изменит собственную стратегию в одностороннем порядке. С момента публикации теоремы Нэша исследователи работали над способами эффективного вычисления равновесия Нэша. Несмотря на то, что в последние полвека в этом направлении прилагались значительные усилия, не было достигнуто существенного прогресса в определении алгоритмической сложности, хотя для различных модифицированных версий были получены данные о сложности и разработаны алгоритмы.

Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [ ] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является PPAD-полной (аргументы полиномиальной четности на ориентированных графах – polynomial parity argument, directed version) – этот класс сложности был введен Пападимитриу в работе [ ]. Результаты [ ] основываются на технике, разработанной в [ ]. Затем эта оценка сложности была улучшена для случая трех игроков Ченом и Денгом [1], а также Даскалакисом и Пападимитриу [ ] – независимо друг от друга и с использованием разных доказательств. Наконец, Чен и Денг [2] доказали, что NASH – задача нахождения равновесия Нэша в биматричной игре (или игре для двух игроков) – является PPAD-полной.

Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера m x n, А = (fljj) и В = (bjj). Если первый игрок выбирает действие i, а второй игрок – действие j, то их вознаграждения равны ац и bij, соответственно. Смешанная стратегия игрока представляет собой распределение вероятностей над его выборами. Обозначим за Pn множество всех векторов вероятностей в Rn, то есть неотрицательных векторов, сумма элементов которых равна 1. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры G = (A, B) существует пара смешанных стратегий (x* 2 Pm,y* 2 Pn), называемая равновесием Нэша, такая, что для всех x 2 Pm и y 2 Pn имеет место (x*)TAy* > xrAy* и (x*)TBy* > (x*)TBy.