Цена анархии (Eyug gugj]nn)

Цена ана́рхии (англ. Price of Anarchy, PoA) — концепция в экономике и теории игр, которая измеряет, насколько эффективность системы деградирует из-за эгоистического поведения её агентов.

Неформальное обсуждение

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

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

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

Математическое определение

Рассмотрим игру $G=(N,S,u)$, определённую множеством игроков $N$, наборами стратегий $S_{i}$ для каждого игрока и функции полезности $u_{i}:S\rightarrow \mathbb {R}$ (где $S=S_{1}\times ...\times S_{n}$ называется также множеством исходов). Мы можем определить меру эффективности каждого исхода, которую мы назовём функцией блага $Welf:S\rightarrow \mathbb {R}$. Естественные кандидаты включают сумму полезностей игроков (целевые полезности) $Welf(s)=\sum _{i\in N}u_{i}(s),$ минимальную полезность (целевая справедливость или эгалитарность) $Welf(s)=\min _{i\in N}u_{i}(s),$ …, или любую функцию, имеющую смысл для конкретной анализируемой игры, которую следовало бы максимизировать.

Мы можем определить подмножество $Equil\subseteq S$ как множество стратегий в равновесии (например, множество равновесий Нэша). Цена анархии тогда определяется как отношение оптимального «централизованного» решения и «худшего равновесия»:

$PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}$

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

$PoA={\frac {\max _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}$

Связанным понятием является цена стабильности (англ. Price of Stability, PoS), которая измеряет отношение между «лучшим равновесием» и оптимально «централизованным» решением:

$PoS={\frac {\max _{s\in S}Welf(s)}{\max _{s\in Equil}Welf(s)}}$

или в случае функций цены:

$PoS={\frac {\min _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}$

Мы знаем, что $1\leqslant PoS\leqslant PoA$ по определению. Ожидается, что потеря в эффективности в результате ограничений из теории игр лежит где-то между PoS и PoA.

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

Дилемма заключённого

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

	Сотрудничать	Предать
Сотрудничать	1; 1	7; 0
Предать	0; 7	5; 5

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

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

Распределение работ

Более естественным примером является одна из задач планирования работ. Имеется $N$ игроков и каждый из них имеет некоторую требующую выполнения работу. Они могут выбрать одну из $M$ машин для выполнения работы. Цена анархии сравнивает ситуацию, когда выбор машин определяется централизованно, и ситуацию, когда каждый игрок выбирает машину так, чтобы выполнить свою работу быстрее.

Каждая машина имеет скорость $s_{1},\ldots ,s_{M}>0.$ Каждая работа имеет вес $w_{1},\ldots ,w_{N}>0.$ Игрок выбирает машину для выполнения его/её работы. Таким образом, стратегиями каждого игрока будут $A_{i}=\{1,2,\ldots ,M\}.$ Определим загрузку на машине $j$ как:

$L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.$

Цена для игрока $i$ равна $c_{i}(a)=L_{a_{i}}(a),$ то есть она равна загрузке машины, которую игрок выбирает. Мы рассмотрим эгалитарную функцию цены ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$, которая здесь называется периодом обработки.

Мы рассмотрим две концепции равновесия — чистая стратегия Нэша и смешанная стратегия Нэша. Ясно, что смешанная PoA $\geqslant$ чистой PoA, поскольку любое чистое равновесие Нэша является и смешанным равновесием Нэша (неравенство может оказаться строгим, например когда $N=2$, $w_{1}=w_{2}=1$, $M=2$ и $s_{1}=s_{2}=1$, при смешанных стратегиях $\sigma _{1}=\sigma _{2}=(1/2,1/2)$ получаем среднее время обработки 1,5, в то время как PoA чистой стратегии в этих условиях равна $\leqslant 4/3$). Первое, что нам нужно сделать, это показать существование чистого равновесия Нэша.

Утверждение. Для любой игры с распределением работ существует по меньшей мере одна равновесная по Нэшу чистая стратегия.

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

Мы утверждаем, что это равновесие Нэша чистой стратегии. Будем доказывать от противного. Предположим, что некоторый игрок $i$ может улучшить свою работу путём перехода от машины $j$ к машине $k$. Это означает, что увеличенная загрузка машины $k$ после перехода остаётся меньше, чем загрузка машины $j$ до перехода. Поскольку загрузка машины $j$ должна уменьшиться в результате перехода и никакая другая машина не затронута, что означает, что новая конфигурация гарантирует сокращение $j$-ой наибольшей загрузки в распределении. Это, однако, нарушает предположение о лексикографической минимальности $a$. что и требовалось доказать

Утверждение. Для любой игры распределения работ PoA чистой стратегии не превосходит $M$.

Доказательство. Легко ограничить сверху благо, полученное как любая равновесная по Нэшу смешанная стратегия $\sigma$, по формуле

$w(\sigma )\leqslant {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.$

Рассмотрим для ясности любой набор чистых стратегий $a$, тогда ясно, что

$w(a)\geqslant {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geqslant {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.$

Поскольку вышеуказанное выполняется также для социального оптимума, сравнение отношений $w(\sigma )$ и $w(a)$ доказывает утверждение. Что и требовалось доказать

Эгоистичная маршрутизация

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

Основная статья: Парадокс Браеса

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

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

Рассмотрим пример на рисунке — если пунктирная дорога недоступна, равновесие Нэша в смешанных стратегиях получается, когда каждый игрок выбирает верхний маршрут и нижний маршрут с одинаковой вероятностью — это равновесие имеет общественные издержки 1,5, и для каждого водителя требуется 1,5 единицы времени для каждого водителя, чтобы пройти из $s$ в $t$. В надежде улучшения прохождения через сеть законодатель может решить открыть для водителей пунктирную дорогу с малой задержкой. В этом случае равновесие Нэша может случиться только если любой водитель использует новую дорогу, поэтому общественные издержки возрастают на 2 и теперь потребуется 2 единицы времени для каждого водителя для проезда из $s$ в $t$.

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

Обобщённая задача маршрутизации

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

Определение (Обобщённый поток). Пусть $G=(V,E)$, $L$ и $w$ определены так же как и выше и предположим, что мы желаем провезти величины $R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}$ через каждую различную пару узлов в $\Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)$. Поток $f_{\Gamma ,R}$ определяется как распределение $p\mapsto \Re$ вещественных неотрицательных чисел каждому пути $p$, проходящему из $s_{i}$ в $t_{i}$ $\in \Gamma$, с ограничениями

$\sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma .$

Поток, проходящий конкретное ребро графа $G$ определяется как

$f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}.$

Для краткости, мы будем писать $f_{e}$, если $\Gamma ,R$ ясны из контекста.

Определение (равновесный по Нэшу поток). Поток $f_{\Gamma ,R}$ является равновесным по Нэшу потоком тогда и только тогда, когда $\forall (s_{i},t_{i})\in \Gamma$ и $\forall p,q$ из $s_{i}$ в $t_{i}$

$f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leqslant \sum _{e\in q}{l_{e}(f_{e})}.$

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

Определение (Условное благо потока). Пусть $f_{\Gamma ,R}$ и $f_{\Gamma ,R}^{*}$ будут двумя потоками в $G$, ассоциированными с множествами $\Gamma$ и $R$. Далее мы будем опускать индекс, чтобы сделать обозначения проще. Представим фиксированные задержки, порождённые функциями $f$ на графе — условное благо $f^{*}$ по отношению к $f$ определяется как

$w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}$

Факт 1. Если имеется равновесный по Нэшу поток $f$ и любой другой поток $f^{*}$, $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$.

Доказательство (от обратного). Предположим, что $w^{f}(f^{*})<w^{f}(f)$. По определению,

$\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}\cdot \sum _{e\in p}l_{e}(f_{e})<\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}\cdot \sum _{e\in p}l_{e}(f_{e})$.

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

$\sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i.$

Поэтому должна существовать пара $(s_{i},t_{i})$ и два пути $p,q$ из $s_{i}$ в $t_{i}$, такой что $f_{p}^{*}>f_{p}$, $f_{q}^{*}<f_{q}$, и

$\sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).$

Другими словами, поток $f^{*}$ может получить меньшее благо, чем $f$, только если два пути из $s_{i}$ в $t_{i}$ имеют различные цены, и если $f^{*}$ перенаправляет некоторый поток $f$ из пути с высокой ценой на путь с меньшей ценой. Ясно, что эта ситуация несовместима с предположением, что $f$ является равновесным по Нэшу потоком. что и требовалось доказать.

Заметим, что Факт 1 не предполагает любую конкретную структуру множества $L$.

Факт 2. Если даны два вещественных числа $x$ и $y$, $x\cdot y\leqslant x^{2}+y^{2}/4$.

Доказательство. Это другой способ выразить верное неравенство $(x-y/2)^{2}\geqslant 0$. что и требовалось доказать.

Теорема. PoA чистой стратегии любой обобщённой задачи маршрутизации $(G,L)$ с линейными задержками равна $\leqslant 4/3$.

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

$w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})$

$=\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.$

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

$w^{f}(f^{*})\leqslant \sum _{e\in E}\left(a_{e}\cdot \left((f_{e}^{*})^{2}+(f_{e})^{2}/4\right)\right)+\sum _{e\in E}f_{e}^{*}\cdot b_{e}$

$=\left(\sum _{e\in E}a_{e}(f_{e}^{*})^{2}+f_{e}^{*}b_{e}\right)+\sum _{e\in E}a_{e}(f_{e})^{2}/4$

$\leqslant w(f^{*})+{\frac {w(f)}{4}},$

поскольку

$(1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})$

$=(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E}f_{e}b_{e}} _{\geqslant 0}.$

Мы можем заключить, что $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$, и доказываем высказывание с помощью Факта 1. что и требовалось доказать.

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

Теорема. Если дана обобщённая задача маршрутизации на графе $G$ и полиномиальные функции задержки степени $d$ с неотрицательными коэффициентами, PoA чистой стратегии $\leqslant d+1$.

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

$w=\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{d}\cdot \left(1-{\frac {1}{\sqrt {d+1}}}\right)+1\cdot {\frac {1}{\sqrt {d+1}}}$

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

$\leqslant e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.$

Значение стремится к нулю по мере стремления $d$ к бесконечности.

См. также

• Трагедия общих ресурсов
• Размещение объектов (конкурентная игра) — игра с маленькой ценой анархии.
• Цена анархии в аукционах

Литература для дальнейшего чтения

• Fabio Cunial, Price of anarchy Архивная копия от 10 сентября 2008 на Wayback Machine