Цена анархии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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})}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}$

${\displaystyle =\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}$

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

поскольку

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

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

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

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

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

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

${\displaystyle 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}}}}$

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

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

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

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

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