Сложность биматричного равновесия Нэша: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 15 промежуточных версий этого же участника) | |||
| Строка 6: | Строка 6: | ||
Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является | Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является <math>\mathcal PPAD</math>-полной (аргументы полиномиальной четности на ориентированных графах – polynomial parity argument, directed version) – этот класс сложности был введен Пападимитриу в работе [9]. Результаты в [4] основываются на технике, разработанной в [6]. Затем эта оценка сложности была улучшена для случая трех игроков Ченом и Денгом [1], а также Даскалакисом и Пападимитриу [5] – независимо друг от друга и с использованием разных доказательств. Наконец, Чен и Денг [2] доказали, что NASH – задача нахождения равновесия Нэша в биматричной игре (или игре для двух игроков) – является <math>\mathcal PPAD</math>-полной. | ||
Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера <math>m \times n</math>, <math>A = (a_{i, j})</math> и <math>B = (b_{i, j})</math>. Если первый игрок выбирает действие i, а второй игрок – действие j, то их | Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера <math>m \times n</math>, <math>\mathbf{A} = \big( a_{i, j} \big)</math> и <math>\mathbf{B} = \big( b_{i, j} \big)</math>. Если первый игрок выбирает действие i, а второй игрок – действие j, то их выигрыш составляет <math>a_{i, j}</math> и <math>b_{i, j}</math>, соответственно. Смешанная стратегия игрока представляет собой распределение вероятностей над его выборами. Обозначим за <math>\mathbb{P}^n</math> множество всех векторов вероятностей в <math>\mathbb{R}^n</math>, то есть неотрицательных векторов, сумма элементов которых равна 1. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры <math>\mathcal{G} = (\mathbf{A}, \mathbf{B})</math> существует пара смешанных стратегий <math>(\mathbf{x}^* \in \mathbb{P}^m, \mathbf{y}^* \in \mathbb{P}^n)</math>, называемая равновесием Нэша, такая, что для всех <math>\mathbf{x}^* \in \mathbb{P}^m</math> и <math>\mathbf{y}^* \in \mathbb{P}^n</math> выполняются соотношения <math>(\mathbf{x}^*)^T \mathbf{A} \mathbf{y}^* \ge \mathbf{x}^T \mathbf{A} \mathbf{y}^*</math> и <math>(\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^* \ge (\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^*</math>. | ||
С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за | С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за <math>\mathbf{A}_i</math> вектор i-й строки матрицы <math>\mathbf{A}</math>, а за <math>\mathbf{B}_i</math> – вектор i-го столбца матрицы <math>\mathbf{B}</math>. <math>\epsilon</math>-поддерживаемое равновесие Нэша для игры <math>(\mathbf{A}, \mathbf{B})</math> представляет собой пару смешанных стратегий <math>(\mathbf{x}^*, \mathbf{y}^*)</math>, такую, что: | ||
<math>\mathbf{A}_i \mathbf{y}^* > \mathbf{A}_j \mathbf{y}^* + \epsilon \implies x_j^* = 0, \forall i, j : 1 \le i, j \le m</math>; | |||
Определение 1 (2-NASH и NASH). | <math>(\mathbf{x}^*)^T \mathbf{B}_i > (\mathbf{x}^*)^T \mathbf{B}_j + \epsilon \implies y_j^* = 0, \forall i, j : 1 \le i, j \le n</math>. | ||
'''Определение 1 (2-NASH и NASH)'''. Входом задачи 2-NASH является пара <math>(\mathcal{G}, 0^k)</math>, где <math>\mathcal{G}</math> – биматричная игра, а выходом – <math>2^{-k}</math>-поддерживаемое равновесие Нэша для игры <math>\mathcal{G}</math>. Входом задачи NASH является биматричная игра <math>\mathcal{G}</math>, выходом – точное равновесие Нэша для <math>\mathcal{G}</math>. | |||
== Основные результаты == | == Основные результаты == | ||
Бинарное отношение R | Бинарное отношение <math>R \subset \{ 0, 1 \}^* \times \{0, 1 \}^*</math> является ''полиномиально сбалансированным'', если существует полином ''p'', такой, что для всех пар <math>(x, y) \in R</math> верно <math>|y| \le p(|x|)</math>. Это отношение ''вычислимо за полиномиальное время'', если для каждой пары (x,y) можно решить, имеет ли место <math>(x, y) \in R</math>, за время, полиномиальное относительно |x| + |y|. <math>\mathcal NP</math>-[[Классы P и NP|полная]] задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом: | ||
Пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет». | |||
Отношение R является ''полным'', если для каждого <math>x \in \{0, 1 \}^*</math> существует y, такое, что <math>(x, y) \in R</math>. Следуя [7], обозначим за <math>\mathcal TFNP</math> класс всех <math>\mathcal NP</math>-полных задач поиска, заданных полными отношениями. Задача поиска <math>Q_{R_1} \in \mathcal{TFNP}</math> ''[[Полиномиальная_сводимость_(трансформируемость)|полиномиально сводима]]'' к задаче <math>Q_{R_2} \in \mathcal{TFNP}</math>, если существует пара полиномиально вычислимых функций (f, g), таких, что для каждого x из <math>R_1</math> в случае, если y удовлетворяет условию <math>(f(x), y) \in R_2</math>, верно <math>(x, g(y)) \in R_1</math>. Более того, <math>Q_{R_1}</math> и <math>Q_{R_2}</math> полиномиально эквивалентны, если <math>Q_{R_2}</math> также сводима к <math>Q_{R_1}</math>. | |||
Класс сложности <math>\mathcal PPAD</math> является подклассом <math>\mathcal TFNP</math>, содержащим все задачи поиска, которые полиномиально сводимы к: | |||
'''Определение 2 (задача LEAFD)'''. Входными данными задачи LEAFD является пара <math>(M, O^n)</math>, где M определяет машину Тьюринга с полиномиальным временем работы, удовлетворяющую следующим условиям: | |||
1. для каждого <math>v \in \{ 0, 1 \}^n</math> M(v) является упорядоченной парой <math>(u_1, u_2)</math>, где <math>u_1, u_2 \in \{ 0, 1 \}^n \cup</math> {«нет»}; | |||
1. для каждого v | |||
2. <math>M(O^n)</math> = («нет», <math>1^n</math>), и первая компонента <math>M(1^n)</math> равна <math>O^n</math>. | |||
Этот экземпляр определяет ориентированный граф G = (V, E) с <math>V = \{ 0, 1 \}^n</math>. Ребро (u, v) имеется в E в том и только том случае, если v – вторая компонента M(u), а u – первая компонента M(v). | |||
Результатом решения задачи LEAFD является ориентированный лист G, отличный от <math>0^n</math>. Здесь вершина называется ''ориентированным листом'', если сумма ее [[полустепень исхода вершины|полустепени исхода]] и [[полустепень захода вершины|полустепени захода]] равна единице. | |||
Задача поиска в <math>\mathcal PPAD</math> называется ''полной'' в <math>\mathcal PPAD</math> (или <math>\mathcal PPAD</math>-полной), если существует редукция от LEAFD до нее за полиномиальное время. | |||
Теорема [2]. Задачи 2- | |||
'''Теорема [2]. Задачи 2-NASH и NASH являются <math>\mathcal PPAD</math>-полными.''' | |||
== Применение == | == Применение == | ||
Концепция равновесия Нэша традиционно является одним из наиболее влиятельных инструментов в изучении многих дисциплин, связанных со стратегиями, таких как политология и экономическая теория. Распространение Интернета и изучение его анархической среды сделали равновесие Нэша неотъемлемой частью компьютерных наук. За последние десятилетия сообщество специалистов в области компьютерных наук внесло большой вклад в разработку эффективных алгоритмов для решения соответствующих задач. | Концепция равновесия Нэша традиционно является одним из наиболее влиятельных инструментов в изучении многих дисциплин, связанных со стратегиями, таких как политология и экономическая теория. Распространение Интернета и изучение его анархической среды сделали равновесие Нэша неотъемлемой частью компьютерных наук. За последние десятилетия сообщество специалистов в области компьютерных наук внесло большой вклад в разработку эффективных алгоритмов для решения соответствующих задач. Последовательность результатов работ [1, 2, 3, 4, 5, 6] впервые дает ''некоторые свидетельства'' того, что задача нахождения равновесия Нэша, вероятно, является P-сложной. Эти результаты очень важны для активно развивающейся дисциплины – алгоритмической теории игр. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Упомянутая последовательность работ показывает, что игры с (r + 1) игроками полиномиально сводимы к играм с r игроками для любого r > | Упомянутая последовательность работ показывает, что игры с (r + 1) игроками полиномиально сводимы к играм с r игроками для любого <math>r \ge 2</math>, но редукция осуществляется путем сведения игр с (r + 1) игроками сначала к задаче с фиксированной точкой, а затем к играм с r игроками. Существует ли естественная редукция, которая переходит непосредственно от игр с (r + 1) игроками к играм с r игроками? Подобная редукция могла бы обеспечить лучшее понимание поведения в многопользовательских играх. | ||
Многие считают, что класс <math>\mathcal PPAD</math> является трудным в <math>\mathcal P</math>, однако веских доказательств или интуитивных соображений в пользу этого мнения нет. Остается открытым естественный вопрос: можно ли строго доказать, что класс <math>\mathcal PPAD</math> является трудным, при одном из общепринятых в теоретической информатике предположений, таких как «<math>\mathcal NP</math> не находится в <math>\mathcal P</math>» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для алгоритмической теории игр. | |||
== См. также == | == См. также == | ||
Текущая версия от 23:08, 29 октября 2021
Ключевые слова и синонимы
Равновесие Нэша в игре для двух игроков; игра для двух игроков; биматричная игра
Постановка задачи
В середине прошлого века Джон Нэш, изучая некооперативные игры общего вида [8], доказал, что существует набор смешанных стратегий, который сейчас принято называть равновесием Нэша, по одной для каждого игрока – такой, что ни один игрок не может получить преимущество, если изменит собственную стратегию в одностороннем порядке. С момента публикации теоремы Нэша исследователи работали над способами эффективного вычисления равновесия Нэша. Несмотря на то, что в последние полвека в этом направлении прилагались значительные усилия, не было достигнуто существенного прогресса в определении алгоритмической сложности, хотя для различных модифицированных версий были получены данные о сложности и разработаны алгоритмы.
Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является [math]\displaystyle{ \mathcal PPAD }[/math]-полной (аргументы полиномиальной четности на ориентированных графах – polynomial parity argument, directed version) – этот класс сложности был введен Пападимитриу в работе [9]. Результаты в [4] основываются на технике, разработанной в [6]. Затем эта оценка сложности была улучшена для случая трех игроков Ченом и Денгом [1], а также Даскалакисом и Пападимитриу [5] – независимо друг от друга и с использованием разных доказательств. Наконец, Чен и Денг [2] доказали, что NASH – задача нахождения равновесия Нэша в биматричной игре (или игре для двух игроков) – является [math]\displaystyle{ \mathcal PPAD }[/math]-полной.
Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера [math]\displaystyle{ m \times n }[/math], [math]\displaystyle{ \mathbf{A} = \big( a_{i, j} \big) }[/math] и [math]\displaystyle{ \mathbf{B} = \big( b_{i, j} \big) }[/math]. Если первый игрок выбирает действие i, а второй игрок – действие j, то их выигрыш составляет [math]\displaystyle{ a_{i, j} }[/math] и [math]\displaystyle{ b_{i, j} }[/math], соответственно. Смешанная стратегия игрока представляет собой распределение вероятностей над его выборами. Обозначим за [math]\displaystyle{ \mathbb{P}^n }[/math] множество всех векторов вероятностей в [math]\displaystyle{ \mathbb{R}^n }[/math], то есть неотрицательных векторов, сумма элементов которых равна 1. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры [math]\displaystyle{ \mathcal{G} = (\mathbf{A}, \mathbf{B}) }[/math] существует пара смешанных стратегий [math]\displaystyle{ (\mathbf{x}^* \in \mathbb{P}^m, \mathbf{y}^* \in \mathbb{P}^n) }[/math], называемая равновесием Нэша, такая, что для всех [math]\displaystyle{ \mathbf{x}^* \in \mathbb{P}^m }[/math] и [math]\displaystyle{ \mathbf{y}^* \in \mathbb{P}^n }[/math] выполняются соотношения [math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{A} \mathbf{y}^* \ge \mathbf{x}^T \mathbf{A} \mathbf{y}^* }[/math] и [math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^* \ge (\mathbf{x}^*)^T \mathbf{B} \mathbf{y}^* }[/math].
С вычислительной точки зрения можно остановиться на приближенном равновесии Нэша. Обозначим за [math]\displaystyle{ \mathbf{A}_i }[/math] вектор i-й строки матрицы [math]\displaystyle{ \mathbf{A} }[/math], а за [math]\displaystyle{ \mathbf{B}_i }[/math] – вектор i-го столбца матрицы [math]\displaystyle{ \mathbf{B} }[/math]. [math]\displaystyle{ \epsilon }[/math]-поддерживаемое равновесие Нэша для игры [math]\displaystyle{ (\mathbf{A}, \mathbf{B}) }[/math] представляет собой пару смешанных стратегий [math]\displaystyle{ (\mathbf{x}^*, \mathbf{y}^*) }[/math], такую, что:
[math]\displaystyle{ \mathbf{A}_i \mathbf{y}^* \gt \mathbf{A}_j \mathbf{y}^* + \epsilon \implies x_j^* = 0, \forall i, j : 1 \le i, j \le m }[/math];
[math]\displaystyle{ (\mathbf{x}^*)^T \mathbf{B}_i \gt (\mathbf{x}^*)^T \mathbf{B}_j + \epsilon \implies y_j^* = 0, \forall i, j : 1 \le i, j \le n }[/math].
Определение 1 (2-NASH и NASH). Входом задачи 2-NASH является пара [math]\displaystyle{ (\mathcal{G}, 0^k) }[/math], где [math]\displaystyle{ \mathcal{G} }[/math] – биматричная игра, а выходом – [math]\displaystyle{ 2^{-k} }[/math]-поддерживаемое равновесие Нэша для игры [math]\displaystyle{ \mathcal{G} }[/math]. Входом задачи NASH является биматричная игра [math]\displaystyle{ \mathcal{G} }[/math], выходом – точное равновесие Нэша для [math]\displaystyle{ \mathcal{G} }[/math].
Основные результаты
Бинарное отношение [math]\displaystyle{ R \subset \{ 0, 1 \}^* \times \{0, 1 \}^* }[/math] является полиномиально сбалансированным, если существует полином p, такой, что для всех пар [math]\displaystyle{ (x, y) \in R }[/math] верно [math]\displaystyle{ |y| \le p(|x|) }[/math]. Это отношение вычислимо за полиномиальное время, если для каждой пары (x,y) можно решить, имеет ли место [math]\displaystyle{ (x, y) \in R }[/math], за время, полиномиальное относительно |x| + |y|. [math]\displaystyle{ \mathcal NP }[/math]-полная задача поиска [math]\displaystyle{ Q_R }[/math], задаваемая R, определяется следующим образом:
Пусть дано [math]\displaystyle{ x \in \{0, 1 \}^* }[/math]. Если существует y, такое, что [math]\displaystyle{ (x, y) \in R }[/math], то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет».
Отношение R является полным, если для каждого [math]\displaystyle{ x \in \{0, 1 \}^* }[/math] существует y, такое, что [math]\displaystyle{ (x, y) \in R }[/math]. Следуя [7], обозначим за [math]\displaystyle{ \mathcal TFNP }[/math] класс всех [math]\displaystyle{ \mathcal NP }[/math]-полных задач поиска, заданных полными отношениями. Задача поиска [math]\displaystyle{ Q_{R_1} \in \mathcal{TFNP} }[/math] полиномиально сводима к задаче [math]\displaystyle{ Q_{R_2} \in \mathcal{TFNP} }[/math], если существует пара полиномиально вычислимых функций (f, g), таких, что для каждого x из [math]\displaystyle{ R_1 }[/math] в случае, если y удовлетворяет условию [math]\displaystyle{ (f(x), y) \in R_2 }[/math], верно [math]\displaystyle{ (x, g(y)) \in R_1 }[/math]. Более того, [math]\displaystyle{ Q_{R_1} }[/math] и [math]\displaystyle{ Q_{R_2} }[/math] полиномиально эквивалентны, если [math]\displaystyle{ Q_{R_2} }[/math] также сводима к [math]\displaystyle{ Q_{R_1} }[/math].
Класс сложности [math]\displaystyle{ \mathcal PPAD }[/math] является подклассом [math]\displaystyle{ \mathcal TFNP }[/math], содержащим все задачи поиска, которые полиномиально сводимы к:
Определение 2 (задача LEAFD). Входными данными задачи LEAFD является пара [math]\displaystyle{ (M, O^n) }[/math], где M определяет машину Тьюринга с полиномиальным временем работы, удовлетворяющую следующим условиям:
1. для каждого [math]\displaystyle{ v \in \{ 0, 1 \}^n }[/math] M(v) является упорядоченной парой [math]\displaystyle{ (u_1, u_2) }[/math], где [math]\displaystyle{ u_1, u_2 \in \{ 0, 1 \}^n \cup }[/math] {«нет»};
2. [math]\displaystyle{ M(O^n) }[/math] = («нет», [math]\displaystyle{ 1^n }[/math]), и первая компонента [math]\displaystyle{ M(1^n) }[/math] равна [math]\displaystyle{ O^n }[/math].
Этот экземпляр определяет ориентированный граф G = (V, E) с [math]\displaystyle{ V = \{ 0, 1 \}^n }[/math]. Ребро (u, v) имеется в E в том и только том случае, если v – вторая компонента M(u), а u – первая компонента M(v).
Результатом решения задачи LEAFD является ориентированный лист G, отличный от [math]\displaystyle{ 0^n }[/math]. Здесь вершина называется ориентированным листом, если сумма ее полустепени исхода и полустепени захода равна единице.
Задача поиска в [math]\displaystyle{ \mathcal PPAD }[/math] называется полной в [math]\displaystyle{ \mathcal PPAD }[/math] (или [math]\displaystyle{ \mathcal PPAD }[/math]-полной), если существует редукция от LEAFD до нее за полиномиальное время.
Теорема [2]. Задачи 2-NASH и NASH являются [math]\displaystyle{ \mathcal PPAD }[/math]-полными.
Применение
Концепция равновесия Нэша традиционно является одним из наиболее влиятельных инструментов в изучении многих дисциплин, связанных со стратегиями, таких как политология и экономическая теория. Распространение Интернета и изучение его анархической среды сделали равновесие Нэша неотъемлемой частью компьютерных наук. За последние десятилетия сообщество специалистов в области компьютерных наук внесло большой вклад в разработку эффективных алгоритмов для решения соответствующих задач. Последовательность результатов работ [1, 2, 3, 4, 5, 6] впервые дает некоторые свидетельства того, что задача нахождения равновесия Нэша, вероятно, является P-сложной. Эти результаты очень важны для активно развивающейся дисциплины – алгоритмической теории игр.
Открытые вопросы
Упомянутая последовательность работ показывает, что игры с (r + 1) игроками полиномиально сводимы к играм с r игроками для любого [math]\displaystyle{ r \ge 2 }[/math], но редукция осуществляется путем сведения игр с (r + 1) игроками сначала к задаче с фиксированной точкой, а затем к играм с r игроками. Существует ли естественная редукция, которая переходит непосредственно от игр с (r + 1) игроками к играм с r игроками? Подобная редукция могла бы обеспечить лучшее понимание поведения в многопользовательских играх.
Многие считают, что класс [math]\displaystyle{ \mathcal PPAD }[/math] является трудным в [math]\displaystyle{ \mathcal P }[/math], однако веских доказательств или интуитивных соображений в пользу этого мнения нет. Остается открытым естественный вопрос: можно ли строго доказать, что класс [math]\displaystyle{ \mathcal PPAD }[/math] является трудным, при одном из общепринятых в теоретической информатике предположений, таких как «[math]\displaystyle{ \mathcal NP }[/math] не находится в [math]\displaystyle{ \mathcal P }[/math]» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для алгоритмической теории игр.
См. также
- Равновесие в общем случае
- Экономическое равновесие Леонтьева
- Неаппроксимируемость биматричного равновесия Нэша
Литература
1. Chen, X., Deng, X.: 3-Nash is ppad-complete. ECCC,TR05-134 (2005)
2. Chen, X., Deng, X.: Settling the complexity of two-player Nash-equilibrium. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 261-272
3. Chen, X., Deng, X., Teng, S.H.: Computing Nash equilibria: approximation and smoothed complexity. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 603-612
4. Daskalakis, C., Goldberg, P.W. Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC'06, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 71-78
5. Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC,TR05-139 (2005)
6. Goldberg, P.W., Papadimitriou, C.H.: Reducibility among equilibrium problems. In: STOC'06, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 61-70
7. Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comp. Sci. 81,317-324(1991)
8. Nash, J.F.: Equilibrium point in n-person games. In: Proceedings of the National Academy of the USA, vol. 36, issue 1, pp. 48^9 (1950)
9. Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comp. Syst. Sci. 48, 498-532(1994)