Цена анархии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

	Сотрудничать	Дефект
Сотрудничать	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}).$ Наихудшее (и единственное) равновесие Нэша будет тогда, когда оба игрока откажутся от участия, а результирующая цена будет равна $C_{equil}=5+5=10$. Однако наивысшее социальное благосостояние достигается тогда, когда оба сотрудничают, и в этом случае затраты равны. $C_{min}=1+1=2$. Таким образом, PoA этой игры будет $C_{equil}/C_{min}=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)$, здесь называется makepan .

Мы рассматриваем две концепции равновесия: чистый Нэш и смешанный Нэш . Должно быть ясно, что смешанное PoA ≥ чистое 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 в этих условиях $\leq 4/3$). Сначала нам нужно доказать, что существуют чистые равновесия по Нэшу.

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

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

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

Требовать . Для каждой игры по планированию заданий чистый PoA не превышает $M$.

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

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

Для ясности изложения рассмотрим любой чисто стратегический профиль действий. $a$: четко

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

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

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

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

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

Рассмотрим дорожную сеть, показанную на диаграмме рядом, по которой 4000 водителей желают проехать от точки начала до конца. Время в пути в минутах на дороге Старт-А представляет собой число пассажиров (Т), деленное на 100, а на дороге Старт-Б - постоянные 45 минут (аналогично и с дорогами напротив них). Если пунктирная дорога не существует (всего в дорожной сети 4 дороги), время, необходимое для проезда по маршруту Начало–А–Конец с $a$ водители были бы ${\tfrac {a}{100}}+45$. Время, необходимое для проезда по маршруту Начало–Б–Конец с $b$ водители были бы ${\tfrac {b}{100}}+45$. Поскольку имеется 4000 водителей, тот факт, что $a+b=4000$ можно использовать для вывода того факта, что $a=b=2000$ когда система находится в равновесии. Таким образом, каждый маршрут занимает ${\tfrac {2000}{100}}+45=65$ минут. Если бы любой маршрут занимал меньше времени, это не было бы равновесием Нэша: рациональный водитель переключился бы с более длинного маршрута на более короткий.

Теперь предположим, что пунктирная линия A–B представляет собой дорогу с чрезвычайно коротким временем в пути, примерно 0 минут. Предположим, что дорога открыта и один водитель пытается начать-А-Б-Конец. К своему удивлению, он обнаруживает, что его время истекло. ${\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01$ минут, экономия почти 25 минут. Вскоре еще больше из 4000 водителей опробуют этот новый маршрут. Затраченное время увеличивается с 40.01 и продолжает расти. Когда количество водителей, пробующих новый маршрут, достигнет 2500, а 1500 все еще будут на маршруте Начало-Б-Конец, их время будет равно ${\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65$ минут, что не является улучшением по сравнению с исходным маршрутом. Между тем, эти 1500 водителей замедлились до $45+{\tfrac {4000}{100}}=85$ минут, увеличение на 20 минут. Они также вынуждены перейти на новый маршрут через А, поэтому теперь требуется ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ минут. Ни у кого нет стимула ехать А-Конец или Старт-Б, потому что любому водителю потребуется 85 минут. Таким образом, открытие перекрестного маршрута вызывает необратимое изменение его всеми, что обходится каждому в 80 минут вместо первоначальных 65. Если бы каждый водитель согласился не использовать путь A–B или если бы этот маршрут был закрыт, каждый водитель выиграет от сокращения времени в пути на 15 минут.

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

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

Определение (Обобщенный поток) . Позволять $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})}\leq \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)\leq 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\leq x^{2}+y^{2}/4$.

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

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

Доказательство . Заметим, что эта теорема эквивалентна утверждению, что для каждого равновесного по Нэшу потока $f$, $w(f)\leq (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^{*})\leq \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$

$\leq 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}} _{\geq 0}.$

Мы можем заключить, что $w^{f}(f^{*})\leq w(f^{*})+w(f)/4$, и докажем утверждение, используя факт 1. КЭД

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

Теорема . Учитывая обобщенную задачу маршрутизации с графом $G$ и полиномиальные латентные функции степени $d$ с неотрицательными коэффициентами чистый PoA равен $\leq 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}}}$

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

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

Дальнейшие результаты

Верхние границы PoA можно получить, если показать, что игра удовлетворяет так называемому неравенству гладкости . Точнее, игра по минимизации затрат является ( λ , µ )-гладкой (с λ ≥ 0 и µ < 1), если выполнено неравенство

$\sum _{i=1}^{n}C_{i}\left(a_{i}^{*},a_{-i}\right)\leq \lambda C\left(a^{*}\right)+\mu C(a)$

справедливо для любого исхода a и a *. В этом случае PoA ограничено сверху величиной λ /(1 − µ ).

Для игр с разделением затрат с вогнутыми функциями затрат оптимальным правилом распределения затрат, которое оптимизирует цену анархии , за которой следует цена стабильности , является именно правило распределения затрат по ценности Шепли. (Утверждение о симметрии аналогично справедливо и для игр с разделением полезности с выпуклыми функциями полезности.) При проектировании механизмов это означает, что концепция решения ценности Шепли оптимальна для этих наборов игр.

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

См. также

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

Ссылки

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

Дальнейшее чтение

• Фабио Куниал, Цена анархии