Цена анархии

Цена анархии (PoA ) - это концепция в экономика и теория игр, которая измеряет, как эффективность системы ухудшается из-за эгоистичного поведения ее агентов. Это общее понятие, которое может быть распространено на различные системы и понятия эффективности. Например, рассмотрим систему передвижения по городу и множество агентов, пытающихся перейти из некоторого исходного места в пункт назначения. Под эффективностью в данном случае будем понимать среднее время, за которое агент достигает пункта назначения. В «централизованном» решении центральный орган может указывать каждому агенту, какой путь выбрать, чтобы минимизировать среднее время в пути. В «децентрализованной» версии каждый агент выбирает свой собственный путь. Цена анархии измеряет соотношение между средним временем в пути в двух случаях.

Обычно система моделируется как игра, а эффективность является некоторой функцией результатов (например, максимальная задержка в сети, перегрузка в транспортной системе, социальное обеспечение на аукционе,...). Для моделирования эгоистичного поведения агентов могут использоваться различные концепции равновесия, среди которых наиболее распространенным является равновесие по Нэшу. Различные разновидности равновесия по Нэшу приводят к вариациям понятия цены анархии как чистой цены анархии (для детерминированных равновесий), смешанной цены анархии (для рандомизированных равновесий) и Цена анархии Байеса – Нэша (для игр с неполной информацией). Концепции решения, отличные от равновесия по Нэшу, приводят к таким вариациям, как Цена гибели .

Термин Цена анархии впервые был использован Элиасом Кутсупиасом и Христосом Пападимитриу, но идея измерения неэффективности равновесия старше. Концепция в ее нынешней форме была разработана как аналог «коэффициента приближения» в алгоритме аппроксимации или «коэффициента конкуренции» в онлайн-алгоритме. Это в контексте современной тенденции анализа игр с использованием алгоритмических линз (алгоритмическая теория игр ).

• 1 Математическое определение
• 2 Дилемма заключенного
• 3 Составление расписания
• 4 Эгоистичная маршрутизация
  • 4.1 Парадокс Брэсса
  • 4.2 Общая проблема маршрутизации
• 5 См. Также
• 6 Ссылки
• 7 Дополнительная литература

Рассмотрим игру $G\; =\; (N,\; S,\; u)\; \{\backslash \; displaystyle\; G\; =\; (N,\; S,\; u)\}$, определяемый набором игроков $N\; \{\backslash \; displaystyle\; N\}$, наборы стратегий $S\; i\; \{\backslash \; displaystyle\; S\_\; \{i\}\}$для каждого плеер и утилиты $ui:\; S\; \to \; R\; \{\backslash \; displaystyle\; u\_\; \{i\}:\; S\; \backslash \; rightarrow\; \backslash \; mathbb\; \{R\}\}$(где $S\; =\; S\; 1\; \times ...\; \times \; S\; n\; \{\backslash \; displaystyle\; S\; =\; S\_\; \{1\}\; \backslash \; times...\; \backslash \; times\; S\_\; \{n\}\}$также называется набором результатов). Мы можем определить меру эффективности каждого результата, которую мы называем функцией благосостояния $W\; e\; l\; f:\; S\; \to \; R\; \{\backslash \; displaystyle\; Welf:\; S\; \backslash \; rightarrow\; \backslash \; mathbb\; \{R\}\}$. Естественные кандидаты включают в себя сумму полезностей игроков (утилитарная цель) $W\; elf\; (s)\; =\; \sum \; i\; \in \; N\; ui\; (s),\; \{\backslash \; displaystyle\; Welf\; (s)\; =\; \backslash \; sum\; \_\; \{i\; \backslash \; in\; N\}\; u\_\; \{i\; \}\; (s),\}$минимальная полезность (справедливость или эгалитарная цель) $W\; elf\; (s)\; =\; min\; i\; \in \; N\; ui\; (s),\; \{\backslash \; displaystyle\; Welf\; (s)\; =\; \backslash \; min\; \_\; \{\; i\; \backslash \; in\; N\}\; u\_\; \{i\}\; (s),\}$... или любая функция, которая имеет значение для конкретной анализируемой игры и желательно максимизировать.

Мы можем определить подмножество $E\; quil\; \subseteq \; S\; \{\backslash \; displaystyle\; Equil\; \backslash \; substeq\; S\}$как набор стратегий в равновесии (например, набор из Равновесие по Нэшу ). Затем цена анархии определяется как соотношение между «наихудшим равновесием» и оптимальным «централизованным» решением:

$P\; o\; A\; =\; min\; s\; \in \; SW\; elf\; (s)\; min\; s\; \in \; E\; quil\; W\; elf\; (s)\; \{\; \backslash \; displaystyle\; PoA\; =\; \{\backslash \; frac\; \{\backslash \; min\; \{s\; \backslash \; in\; S\}\; Welf\; (s)\}\; \{\backslash \; min\; \_\; \{s\; \backslash \; in\; Equil\}\; Welf\; (s)\}\}\}$

Если вместо 'благосостояния', которое мы хотим «максимизировать», функция измерения эффективности - это «функция затрат» $C\; ost:\; S\; \to \; R\; \{\backslash \; displaystyle\; Cost:\; S\; \backslash \; rightarrow\; \backslash \; mathbb\; \{R\}\}$, которую мы хотим «минимизировать» (например, задержку в сети) мы используем (следуя соглашению в алгоритмах аппроксимации):

$P\; o\; A\; =\; max\; s\; \in \; E\; quil\; C\; ost\; (s)\; min\; s\; \in \; SC\; ost\; (s)\; \{\backslash \; displaystyle\; PoA\; =\; \{\backslash \; frac\; \{\backslash \; max\; \_\; \{s\; \backslash \; in\; Equil\}\; Cost\; (s)\}\; \{\backslash \; min\; \_\; \{s\; \backslash \; in\; S\}\; Cost\; (s)\}\}\}$

Связанное с этим понятие - понятие Цена стабильности (PoS ), который измеряет соотношение между «наилучшим равновесием» и оптимальным «централизованным» решением:

$P\; o\; S\; =\; max\; s\; \in \; SW\; elf\; (s)\; max\; s\; \in \; E\; квил\; W\; эльф\; (ы)\; \{\backslash \; Displaystyle\; PoS\; =\; \{\backslash \; гидроразрыва\; \{\backslash \; м\; ax\; \_\; \{s\; \backslash \; in\; S\}\; Welf\; (s)\}\; \{\backslash \; max\; \_\; \{s\; \backslash \; in\; Equil\}\; Welf\; (s)\}\}\}$

или в случае функций стоимости:

$P\; o\; S\; =\; min\; s\; \in \; E\; quil\; C\; ost\; (s)\; min\; s\; \in \; SC\; ost\; (s)\; \{\backslash \; displaystyle\; PoS\; =\; \{\backslash \; frac\; \{\backslash \; min\; \_\; \{s\; \backslash \; in\; Equil\}\; Cost\; (s)\}\; \{\backslash \; min\; \_\; \{s\; \backslash \; in\; S\}\; Cost\; (s)\}\}\}$

Мы знаем, что $1\; \le \; P\; o\; S\; \le \; P\; o\; A\; \{\backslash \; displaystyle\; 1\; \backslash \; leq\; PoS\; \backslash \; leq\; PoA\}$по определению. Ожидается, что потеря эффективности из-за ограничений теории игр находится где-то между PoS и PoA.

И PoS, и PoA были рассчитаны для различных типов игр. Некоторые примеры представлены ниже.

Рассмотрим игру 2x2 под названием дилемма заключенного, представленная следующей матрицей затрат:

и пусть функция стоимости будет $C\; (s\; 1,\; s\; 2)\; =\; u\; 1\; (s\; 1,\; s\; 2)\; +\; u\; 2\; (s\; 1,\; s\; 2).\; \{\backslash \; displaystyle\; C\; (s\_\; \{1\},\; s\_\; \{2\})\; =\; u\_\; \{1\}\; (s\_\; \{1\},\; s\_\; \{2\})\; +\; u\_\; \{2\}\; (s\_\; \{1\},\; s\_\; \{2\}).\}$Итак, минимальная стоимость будет, когда оба игрока сотрудничают, и итоговая стоимость будет $1\; +\; 1\; =\; 2\; \{\backslash \; displaystyle\; 1\; +\; 1\; =\; 2\}$. Однако единственное равновесие по Нэшу возникает, когда оба дефектны, и в этом случае стоимость составляет $5\; +\; 5\; =\; 10\; \{\backslash \; displaystyle\; 5\; +\; 5\; =\; 10\}$. Таким образом, PoA этой игры будет $10/2\; =\; 5\; \{\backslash \; displaystyle\; 10/2\; =\; 5\}$.

Поскольку игра имеет уникальное равновесие по Нэшу, PoS равно PoA и тоже 5.

Более естественный пример - планирование заданий . Есть $N\; \{\backslash \; displaystyle\; N\}$игроков, и у каждого из них есть задание, которое нужно выполнить. Они могут выбрать одну из машин $M\; \{\backslash \; displaystyle\; M\}$для выполнения задания. Цена анархии сравнивает ситуацию, когда выбор машин осуществляется централизованно, с ситуацией, когда каждый игрок выбирает машину, которая будет выполнять свою работу быстрее всего.

Каждая машина имеет скорость $с\; 1,\dots ,\; с\; M>0.\; \{\backslash \; displaystyle\; s\_\; \{1\},\; \backslash \; ldots,\; s\_\; \{M\}>0.\}$Каждое задание имеет вес $w\; 1,\dots ,\; w\; N>0.\; \{\backslash \; displaystyle\; w\_\; \{1\},\; \backslash \; Ndots,\; w\_\; \{\; \}>0.\}$Игрок выбирает машину, чтобы запустить его или ее работа продолжается. Итак, стратегии каждого игрока $A\; i\; =\; \{1,\; 2,\dots ,\; M\}.\; \{\backslash \; displaystyle\; A\_\; \{i\}\; =\; \backslash \; \{1,2,\; \backslash \; ldots,\; M\; \backslash \}.\}$Определите нагрузку на машину $j\; \{\backslash \; displaystyle\; j\}$как :

$L\; j\; (a)\; =\; \sum \; i:\; ai\; =\; jwisj.\; \{\backslash \; displaystyle\; L\_\; \{j\}\; (a)\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i:\; a\_\; \{i\}\; =\; j\}\; w\_\; \{i\}\}\; \{s\_\; \{j\}\}\}.\}$

Стоимость для игрока $я\; \{\backslash \; displaystyle\; i\}$равно $ci\; (a)\; =\; L\; ai\; (a),\; \{\backslash \; displaystyle\; c\_\; \{i\}\; (a)\; =\; L\_\; \{a\_\; \{i\}\}\; (a),\}$т. Е. Загрузка машины, которую они выбрали. Мы рассматриваем эгалитарную функцию затрат $MS\; (a)\; =\; max\; j\; L\; j\; (a)\; \{\backslash \; displaystyle\; \{\backslash \; t\_dv\; \{MS\}\}\; (a)\; =\; \backslash \; max\; \_\; \{j\}\; L\_\; \{j\}\; (a)\}$, здесь это называется периодом производства.

. Мы рассматриваем две концепции равновесия: чистый Нэш и смешанный Нэш. Должно быть ясно, что смешанный PoA ≥ чистый PoA, потому что любое чистое равновесие по Нэшу также является смешанным равновесием по Нэшу (это неравенство может быть строгим: например, когда $N\; =\; 2\; \{\backslash \; displaystyle\; N\; =\; 2\}$, $w\; 1\; =\; вес\; 2\; =\; 1\; \{\backslash \; displaystyle\; w\_\; \{1\}\; =\; w\_\; \{2\}\; =\; 1\}$, $M\; =\; 2\; \{\backslash \; displaystyle\; M\; =\; 2\}$и $s\; 1\; =\; s\; 2\; =\; 1\; \{\backslash \; Displaystyle\; s\_\; \{1\}\; =\; s\_\; \{2\}\; =\; 1\}$, смешанные стратегии $\sigma \; 1\; =\; \sigma \; 2\; =\; (1/2,\; 1/2)\; \{\backslash \; displaystyle\; \backslash \; sigma\; \_\; \{\; 1\}\; =\; \backslash \; sigma\; \_\; \{2\}\; =\; (1\; /\; 2,1\; /\; 2)\}$достичь средней продолжительности выполнения 1,5, в то время как любая PoA чистой стратегии в этой настройке составляет $\le \; 4/3\; \{\backslash \; displaystyle\; \backslash \; leq\; 4/3\}$). Сначала нам нужно доказать, что существуют чистые равновесия по Нэшу.

Претензия . Для каждой игры с планированием заданий существует по крайней мере одно равновесие по Нэшу в чистой стратегии.

Доказательство . Мы хотели бы выбрать социально оптимальный профиль действий $a\; \ast \; \{\backslash \; displaystyle\; a\; ^\; \{*\}\}$. Это будет означать просто профиль действия с минимальным временем создания. Однако этого будет недостаточно. Таких профилей действия может быть несколько, что приводит к множеству различных распределений нагрузок (все имеют одинаковую максимальную нагрузку). Среди них мы также ограничимся тем, у которого минимальная вторая по величине нагрузка. Опять же, это приводит к набору возможных распределений нагрузки, и мы повторяем до $M\; \{\backslash \; displaystyle\; M\}$th-наибольшей (то есть наименьшей) нагрузки, где может быть только одно распределение нагрузки (уникальные до перестановки). Это также будет называться лексикографическим наименьшим отсортированным вектором нагрузки.

Мы утверждаем, что это равновесие по Нэшу в чистой стратегии. Рассуждая от противного, предположим, что какой-то игрок $i\; \{\backslash \; displaystyle\; i\}$может строго улучшить, перейдя с машины $j\; \{\backslash \; displaystyle\; j\}$на машину $к\; \{\backslash \; Displaystyle\; к\}$. Это означает, что увеличенная нагрузка на машину $k\; \{\backslash \; displaystyle\; k\}$после перемещения все еще меньше, чем нагрузка на машину $j\; \{\backslash \; displaystyle\; j\}$до Движение. Поскольку нагрузка на машину $j\; \{\backslash \; displaystyle\; j\}$должна уменьшиться в результате перемещения, и никакая другая машина не пострадает, это означает, что новая конфигурация гарантированно уменьшит $j\; \{\backslash \; displaystyle\; j\}$-й наибольший (или более высокий рейтинг) нагрузка в распределении. Это, однако, нарушает предполагаемую лексикографическую минимальность $a\; \{\backslash \; displaystyle\; a\}$. Q.E.D.

Претензия . Для каждой игры с планированием заданий чистая PoA не превышает $M\; \{\backslash \; displaystyle\; M\}$.

Proof . Легко оценить сверху благосостояние, полученное при любом равновесии по Нэшу со смешанной стратегией $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$на

$w\; (\sigma )\; \le \; \sum \; i\; w\; i\; max\; j\; s\; j.\; \{\backslash \; displaystyle\; w\; (\backslash \; sigma)\; \backslash \; leq\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\}\; \{w\_\; \{i\}\}\}\; \{\backslash \; max\; \_\; \{j\}\; \{s\_\; \{j\}\}\}\}.\}$

Рассмотрим, для ясность изложения, любой профиль действия чистой стратегии $a\; \{\backslash \; displaystyle\; a\}$: очевидно

$w\; (a)\; \ge \; \sum \; iwi\; \sum \; jsj\; \ge \; \sum \; iwi\; M\; \cdot \; max\; jsj.\; \{\backslash \; displaystyle\; w\; (a)\; \backslash \; geq\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\}\; \{w\_\; \{i\}\}\}\; \{\backslash \; sum\; \_\; \{j\}\; \{s\_\; \{j\}\}\}\}\; \backslash \; geq\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\}\; \{w\_\; \{i\}\}\}\; \{M\; \backslash \; cdot\; \backslash \; max\; \_\; \{j\}\; \{s\_\; \{j\}\}\}\}.\}$

Поскольку вышесказанное справедливо и для социального оптимума, сравнение соотношений $w\; (\sigma )\; \{\backslash \; displaystyle\; w\; (\backslash \; sigma)\}$и $w\; (a)\; \{\backslash \; displaystyle\; w\; (a)\}$подтверждает утверждение. Q.E.D

Парадокс Брэсса

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

Мы можем формализовать эту настройку как задачу маршрутизации в ориентированном связном графе $G\; =\; (V,\; E)\; \{\backslash \; displaystyle\; G\; =\; (V,\; E)\}$, в который мы хотим отправить одну единицу потока из исходного узла $s\; \in \; V\; \{\backslash \; displaystyle\; s\; \backslash \; in\; V\}$в целевой узел $t\; \in \; V\; \{\backslash \; displaystyle\; t\; \backslash \; in\; V\; \}$(представьте, что поток состоит из решений о перемещении различных водителей). В частности, пусть поток является функцией $f:\; E\; \mapsto \; \Re \; \{\backslash \; displaystyle\; f:\; E\; \backslash \; mapsto\; \backslash \; Re\}$, присваивающей каждому ребру неотрицательное действительное число, и рассмотрим набор линейные функции $L\; =\; \{le\; (fe)\; =\; a\; \cdot \; fe\; +\; b\; |\; е\; \in \; E,\; a\; \ge \; 0,\; b\; \ge \; 0\}\; \{\backslash \; displaystyle\; L\; =\; \backslash \; \{l\_\; \{e\}\; (f\_\; \{e\})\; =\; a\; \backslash \; cdot\; f\_\; \{e\}\; +\; b\; \backslash ;\; |\; \backslash ;\; e\; \backslash \; in\; E,\; \backslash \; ;\; a\; \backslash \; geq\; 0,\; \backslash ;\; b\; \backslash \; geq\; 0\; \backslash \}\}$, которые сопоставляют поток, пересекающий каждый край, с задержкой для прохождения края. Давайте также определим социальное благополучие потока $f\; \{\backslash \; displaystyle\; f\}$как $w\; (f)\; =\; \sum \; efe\; \cdot \; le\; (fe)\; \{\backslash \; displaystyle\; w\; (f)\; =\; \backslash \; sum\; \_\; \{e\}\; \{f\_\; \{e\}\; \backslash \; cdot\; l\_\; \{e\}\; (f\_\; \{e\})\}\}$

Рассмотрим пример на рисунке: если пунктирная дорога недоступна, равновесие Нэша смешанной стратегии происходит, когда каждый игрок выбирает верхний и нижний маршруты с одинаковой вероятностью: это равновесие имеет социальные издержки 1,5, и каждому водителю требуется 1,5 единицы времени, чтобы перейти от $s\; \{\backslash \; displaystyle\; s\}$- $t\; \{\backslash \; displaystyle\; t\}$. Надеясь улучшить производительность сети, законодатель мог бы решить сделать пунктирную границу с низкой задержкой доступной для водителей: в этом случае единственное равновесие по Нэшу произойдет, когда каждый водитель будет использовать новую дорогу, поэтому социальная стоимость увеличится до 2, и теперь каждому игроку потребуется 2 единицы времени, чтобы перейти с $s\; \{\backslash \; displaystyle\; s\}$на $t\; \{\backslash \; displaystyle\; t\}$.

Следовательно, необычный результат отказа централизованного управления доступом к самой быстрой дороге в некоторых случаях приносит пользу населению.

Обобщенная проблема маршрутизации

Проблема маршрутизации, представленная в парадоксе Браесса, может быть обобщена на множество различных потоков, пересекающих один и тот же граф в одно и то же время.

Определение (Обобщенный поток) . Пусть $G\; =\; (V,\; E)\; \{\backslash \; displaystyle\; G\; =\; (V,\; E)\}$, $L\; \{\backslash \; displaystyle\; L\}$и $w\; \{\backslash \; displaystyle\; w\}$будет таким, как определено выше, и предположим, что мы хотим направить величины $R\; =\; \{r\; 1,\; r\; 2,\dots ,\; rk,\; |\; ри>0\}\; \{\backslash \; displaystyle\; R\; =\; \backslash \; \{r\_\; \{1\},\; r\_\; \{2\},\; \backslash \; dots,\; r\_\; \{k\},\; \backslash ;\; |\; \backslash ;\; r\_\; \{i\}>0\; \backslash \}\}$через каждую отдельную пару узлов в $\Gamma \; =\; \{(s\; 1,\; t\; 1),\; (s\; 2,\; t\; 2),\dots ,\; (sk,\; tk)\}\; \subseteq \; (V\; \times \; V)\; \{\backslash \; displaystyle\; \backslash \; Gamma\; =\; \backslash \; \{(s\_\; \{1\},\; t\_\; \{1\}),\; (s\_\; \{2\},\; t\_\; \{2\}),\; \backslash \; dots,\; (s\_\; \{k\},\; t\_\; \{k\})\; \backslash \}\; \backslash \; substeq\; (V\; \backslash \; times\; V)\}$. Поток $f\; \Gamma ,\; R\; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; Gamma,\; R\}\}$определяется как присвоение $p\; \mapsto \; \Re \; \{\backslash \; displaystyle\; p\; \backslash \; mapsto\; \backslash \; Re\}$действительного неотрицательного числа для каждого пути $p\; \{\backslash \; displaystyle\; p\}$, идущего от $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$к $ti\; \{\backslash \; displaystyle\; t\_\; \{i\}\}$$\in \; \Gamma \; \{\backslash \; displaystyle\; \backslash \; in\; \backslash \; Gamma\}$с ограничением, что

$\sum \; p:\; si\; \to \; tifp\; =\; ri\; \forall \; (si,\; ti)\; \in \; \Gamma .\; \{\backslash \; Displaystyle\; \backslash \; sum\; \_\; \{p:\; \backslash ,\; s\_\; \{i\}\; \backslash \; rightarrow\; t\_\; \{i\}\}\; \{f\_\; \{p\}\}\; =\; r\_\; \{i\}\; \backslash ;\; \backslash ;\; \backslash \; forall\; (s\_\; \{i\},\; t\_\; \{\; i\})\; \backslash \; in\; \backslash \; Gamma.\}$

Переход потока Создание определенного края $G\; \{\backslash \; displaystyle\; G\}$определяется как

$f\; e,\; \Gamma ,\; R\; =\; \sum \; p:\; e\; \in \; p\; f\; p.\; \{\backslash \; displaystyle\; f\_\; \{e,\; \backslash \; Gamma,\; R\}\; =\; \backslash \; sum\; \_\; \{p:\; \backslash ,\; e\; \backslash \; in\; p\}\; \{f\_\; \{p\}\}.\}$

Для краткости мы пишем $fe\; \{\backslash \; displaystyle\; f\_\; \{e\}\}$, когда $\Gamma ,\; R\; \{\backslash \; displaystyle\; \backslash \; Gamma,\; R\}$ясны из контекста.

Определение (равновесный поток по Нэшу) . Поток $f\; \Gamma ,\; R\; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; Gamma,\; R\}\}$является потоком равновесия по Нэшу тогда и только тогда, когда $\forall \; (si,\; ti)\; \in \; \Gamma \; \{\backslash \; displaystyle\; \backslash \; forall\; (\; s\_\; \{i\},\; t\_\; \{i\})\; \backslash \; in\; \backslash \; Gamma\}$и $\forall \; p,\; q\; \{\backslash \; displaystyle\; \backslash \; forall\; p,\; q\}$из $si\; \{\; \backslash \; displaystyle\; s\_\; \{i\}\}$to $ti\; \{\backslash \; displaystyle\; t\_\; \{i\}\}$

$fp>0\; \Rightarrow \; \sum \; e\; \in \; ple\; (fe)\; \le \; \sum \; e\; \in \; qle\; (fe).\; \{\backslash \; displaystyle\; f\_\; \{p\}>0\; \backslash \; Rightarrow\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; p\}\; \{l\_\; \{e\}\; (f\_\; \{e\})\}\; \backslash \; leq\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; q\}\; \{l\_\; \{e\}\; (f\_\; \{e\})\}.\}$

Это определение тесно связано с тем, что мы говорили о поддержке равновесия Нэша смешанной стратегии в играх нормальной формы.

Определение (Условное благополучие потока) . Пусть $е\; \Gamma ,\; R\; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; Gamma,\; R\}\}$и $f\; \Gamma ,\; R\; \ast \; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; Gamma,\; R\}\; ^\; \{*\}\}$быть двумя потоками в $G\; \{\backslash \; displaystyle\; G\}$, связанными с одними и теми же наборами $\Gamma \; \{\backslash \; displaystyle\; \backslash \; Gamma\}$и $R\; \{\backslash \; displaystyle\; R\}$. В дальнейшем мы опустим нижний индекс, чтобы обозначение было более понятным. Предположим, что исправлены задержки, вызванные $f\; \{\backslash \; displaystyle\; f\}$на графике : условное благосостояние $f\; \ast \; \{\backslash \; d\; isplaystyle\; f\; ^\; \{*\}\}$по отношению к $f\; \{\backslash \; displaystyle\; f\}$определяется как

$wf\; (f\; \ast )\; =\; \sum \; e\; \in \; E\; fe\; \ast \; \cdot \; ле\; (е)\; \{\backslash \; Displaystyle\; ш\; ^\; \{е\}\; (е\; ^\; \{*\})\; =\; \backslash \; сумма\; \_\; \{е\; \backslash \; в\; Е\}\; \{е\_\; \{е\}\; ^\; \{*\}\; \backslash \; cdot\; l\_\; \{е\}\; (е\_\; \{е\})\; \}\}$

Факт 1 . Для данного потока равновесия по Нэшу $f\; \{\backslash \; displaystyle\; f\}$и любого другого потока $f\; \ast \; \{\backslash \; displaystyle\; f\; ^\; \{*\}\}$, $w\; (f)\; =\; wf\; (f)\; \le \; wf\; (f\; *)\; \{\backslash \; displaystyle\; w\; (f)\; =\; w\; ^\; \{f\}\; (f)\; \backslash \; leq\; w\; ^\; \{f\}\; (f\; ^\; \{*\})\}$.

Доказательство (от противного) . Предположим, что . По определению

.

Поскольку $f\; \{\backslash \; displaystyle\; f\}$и $f\; \ast \; \{\backslash \; displaystyle\; f\; ^\; \{*\}\}$связаны с теми же наборами $\Gamma ,\; R\; \{\backslash \; displaystyle\; \backslash \; Gamma,\; R\}$, мы знаем, что

$\sum \; p:\; si\; \to \; tifp\; =\; \sum \; p:\; si\; \to \; tifp\; \ast \; =\; ri\; \forall \; i.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{p:\; s\_\; \{i\}\; \backslash \; rightarrow\; t\_\; \{i\}\}\; f\_\; \{p\}\; =\; \backslash \; sum\; \_\; \{p:\; s\_\; \{i\}\; \backslash \; rightarrow\; t\_\; \{i\}\}\; f\_\; \{p\}\; ^\; \{*\}\; =\; r\_\; \{i\}\; \backslash ;\; \backslash ;\; \backslash \; forall\; i.\}$

Следовательно, должна быть пара $(si,\; ti)\; \{\backslash \; displaystyle\; (s\_\; \{i\},\; t\_\; \{i\})\}$и два пути $p,\; q\; \{\backslash \; displaystyle\; p,\; q\}$от $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$до $ti\; \{\; \backslash \; displaystyle\; t\_\; \{i\}\}$такой, что $fp\; \ast >fp\; \{\backslash \; displaystyle\; f\_\; \{p\}\; ^\; \{*\}>f\_\; \{p\}\}$, , и

Другими словами, поток $f\; \ast \; \{\backslash \; displaystyle\; f\; ^\; \{*\}\}$может достичь более низкого благосостояния, чем $f\; \{\backslash \; displaystyle\; f\}$, только если есть два пути от $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$до $ti\; \{\backslash \; displaystyle\; t\_\; \{i\}\}$с разными затратами, и если $f\; \ast \; \{\backslash \; displaystyle\; f\; ^\; \{*\}\}$перенаправляет некоторый поток $f\; \{\backslash \; displaystyle\; f\}$от пути с более высокой стоимостью к пути с меньшей стоимостью. Эта ситуация явно несовместима с предположением, что $f\; \{\backslash \; displaystyle\; f\}$является потоком, равновесным по Нэшу. Q.E.D.

Обратите внимание, что Факт 1 не предполагает какой-либо конкретной структуры на множестве $L\; \{\backslash \; displaystyle\; L\}$.

Факт 2 . Даны любые два действительных числа $x\; \{\backslash \; displaystyle\; x\}$и $y\; \{\backslash \; displaystyle\; y\}$, $x\; \cdot \; y\; \le \; x\; 2\; +\; y\; 2/4\; \{\backslash \; displaystyle\; x\; \backslash \; cdot\; y\; \backslash \; leq\; x\; ^\; \{2\}\; +\; y\; ^\; \{2\}\; /\; 4\}$.

Доказательство . Это еще один способ выразить истинное неравенство $(x\; -\; y\; /\; 2)\; 2\; \ge \; 0\; \{\backslash \; displaystyle\; (x-y\; /\; 2)\; ^\; \{2\}\; \backslash \; geq\; 0\}$. Q.E.D.

Теорема . Чистая PoA любой обобщенной задачи маршрутизации $(G,\; L)\; \{\backslash \; displaystyle\; (G,\; L)\}$с линейными задержками $\le \; 4/3\; \{\backslash \; displaystyle\; \backslash \; leq\; 4/3\; \}$.

Доказательство . Обратите внимание, что эта теорема эквивалентна утверждению, что для каждого потока равновесия по Нэшу $f\; \{\backslash \; displaystyle\; f\}$, $w\; (f)\; \le \; (4/3)\; \cdot \; min\; f\; \ast \; \{w\; (f\; \ast )\}\; \{\backslash \; displaystyle\; w\; (f)\; \backslash \; leq\; (4/3)\; \backslash \; cdot\; \backslash \; min\; \_\; \{f\; ^\; \{*\}\}\; \backslash \; \{w\; (f\; ^\; \{*\})\; \backslash \}\}$, где $f\; \ast \; \{\backslash \; displaystyle\; f\; ^\; \{*\}\}$- любой другой поток. По определению

$wf\; (f\; \ast )\; =\; \sum \; e\; \in \; E\; fe\; \ast \; (ae\; \cdot \; fe\; +\; be)\; \{\backslash \; displaystyle\; w\; ^\; \{f\}\; (f\; ^\; \{*\})\; =\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; f\_\; \{e\}\; ^\; \{*\}\; (a\_\; \{e\}\; \backslash \; cdot\; f\_\; \{e\}\; +\; b\_\; \{e\})\}$

$=\; \sum \; e\; (aefefe\; \ast )\; +\; e\; \in \; E\; fe\; \ast \; be.\; \{\backslash \; displaystyle\; =\; \backslash \; sum\; \_\; \{e\}\; (a\_\; \{e\}\; f\_\; \{e\}\; f\_\; \{e\}\; ^\; \{*\})\; +\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; f\_\; \{e\}\; ^\; \{*\}\; b\_\; \{e\}.\}$

Используя факт 2, получаем, что

$wf\; (f\; \ast )\; \le \; \sum \; e\; \in \; E\; (ae\; \cdot \; ((fe\; \ast )\; 2\; +\; (fe)\; 2/4))\; +\; \sum \; e\; \in \; E\; fe\; *\; \cdot \; быть\; \{\backslash \; displaystyle\; w\; ^\; \{f\}\; (f\; ^\; \{*\})\; \backslash \; leq\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; \backslash \; left\; (a\_\; \{e\}\; \backslash \; cdot\; \backslash \; left\; ((f\_\; \{e\}\; ^\; \{*\})\; ^\; \{2\}\; +\; (f\_\; \{e\})\; ^\; \{2\}\; /\; 4\; \backslash \; right)\; \backslash \; right)\; +\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; f\_\; \{e\}\; ^\; \{*\}\; \backslash \; cdot\; b\_\; \{e\}\}$

$=\; (\sum \; e\; \in \; E\; ae\; (fe\; \ast )\; 2\; +\; fe\; \ast \; be)\; +\; \sum \; e\; \in \; E\; ae\; (fe)\; 2/4\; \{\backslash \; displaystyle\; =\; \backslash \; left\; (\backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; a\_\; \{e\; \}\; (f\_\; \{e\}\; ^\; \{*\})\; ^\; \{2\}\; +\; f\_\; \{e\}\; ^\; \{*\}\; b\_\; \{e\}\; \backslash \; right)\; +\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; a\_\; \{e\}\; (f\_\; \{e\})\; ^\; \{2\}\; /\; 4\}$

$\le \; вес\; (е\; *)\; +\; вес\; (е)\; 4,\; \{\backslash \; displaystyle\; \backslash \; leq\; w\; (f\; ^\; \{*\})\; +\; \{\backslash \; frac\; \{w\; (f)\}\; \{4\}\; \},\}$

, поскольку

$(1/4)\; \cdot \; w\; (f)\; =\; (1/4)\; \cdot \; \sum \; e\; \in \; E\; fe\; (aefe\; +\; be)\; \{\backslash \; displaystyle\; (1/4)\; \backslash \; cdot\; w\; (f)\; =\; (1/4)\; \backslash \; cdot\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; f\_\; \{e\}\; (a\_\; \{e\}\; f\_\; \{e\}\; +\; b\_\; \{e\})\}$

$=\; (1/4)\; \cdot \; \sum \; e\; \in \; E\; (fe)\; 2\; +\; (1/4)\; \cdot \; \sum \; e\; \in \; E\; febe\; ⏟\; \ge \; 0.\; \{\backslash \; displaystyle\; =\; (1/4)\; \backslash \; cdot\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; (f\_\; \{e\})\; ^\; \{2\}\; +\; \backslash \; underbrace\; \{(1/4)\; \backslash \; cdot\; \backslash \; sum\; \_\; \{e\; \backslash \; in\; E\}\; f\_\; \{e\}\; b\_\; \{e\}\}\; \_\; \{\backslash \; geq\; 0\}.\}$

Мы можем заключить, что $wf\; (f\; \ast )\; \le \; w\; (f\; \ast )\; +\; w\; (f)\; /\; 4\; \{\backslash \; displaystyle\; w\; ^\; \{f\}\; (f\; ^\; \{*\})\; \backslash \; leq\; w\; (f\; ^\; \{*\})\; +\; w\; (f)\; /\; 4\}$, и докажите тезис, используя Факт 1. QED

Обратите внимание, что в доказательстве мы широко использовали предположение, что функции в $L\; \{\backslash \; displaystyle\; L\}$являются линейными. На самом деле имеет место более общий факт.

Теорема . Учитывая обобщенную задачу маршрутизации с графом $G\; \{\backslash \; displaystyle\; G\}$и полиномиальными функциями задержки степени $d\; \{\backslash \; displaystyle\; d\}$с неотрицательными коэффициентами, чистый PoA равно $\le \; d\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; leq\; d\; +\; 1\}$.

Обратите внимание, что PoA может расти с $d\; \{\backslash \; displaystyle\; d\}$. Рассмотрим пример, показанный на следующем рисунке, где мы предполагаем единичный поток: потоки равновесия по Нэшу имеют социальное благосостояние 1; однако наилучшее благополучие достигается, когда $x\; =\; 1\; -\; 1\; /\; d\; +\; 1\; \{\backslash \; displaystyle\; x\; =\; 1-1\; /\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}$, в этом случае

$вес\; =\; (1\; -\; 1\; d\; +\; 1)\; d\; \cdot \; (1\; -\; 1\; d\; +\; 1)\; +\; 1\; \cdot \; 1\; d\; +\; 1\; \{\backslash \; displaystyle\; w\; =\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{d\; +1\}\}\}\; \backslash \; right)\; ^\; \{d\}\; \backslash \; cdot\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}\; \backslash \; right)\; +1\; \backslash \; cdot\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}\}$

$=\; ((1\; -\; 1\; d\; +\; 1)\; d\; +\; 1)\; d\; +\; 1\; +\; 1\; d\; +\; 1\; \{\backslash \; displaystyle\; =\; \backslash \; left\; (\backslash \; left\; (1\; -\; \{\backslash \; frac\; \{\; 1\}\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}\; \backslash \; right)\; ^\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\; \backslash \; right)\; ^\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{d\; +1\}\}\}\}$

$\le \; e\; -\; d\; +\; 1\; +\; 1\; d\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; leq\; e\; ^\; \{-\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{d\; +\; 1\}\}\}.\}$

Эта величина стремится к нулю, когда $d\; \{\backslash \; displaystyle\; d\}$стремится к бесконечности.

• Tragedy of the Commons
• Конкурсная игра по поиску объектов - игра с небольшой ценой анархии.
• Цена анархии на аукционах

• Тим Рофгарден и Ева Тардос, «Введение в неэффективность равновесий». Глава 17 в Вазирани, Виджай В. ; Нисан, Ноам ; Грубогарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0..
• Тим Рафгарден (2005). Эгоистичный марш и цена анархии. MIT Нажмите. ISBN 0-262-18243-2. CS1 maint: использует параметр авторов (ссылка )

• Fabio Cunial, Price анархии