Русская Википедия:Цена анархии
Цена ана́рхии (Шаблон:Lang-en, PoA)Шаблон:Sfn — концепция в экономике и теории игр, которая измеряет, насколько эффективность системы деградирует из-за эгоистического поведения её агентов.
Неформальное обсуждение
Цена анархии является общим понятием, которое может быть расширено на различные системы и понятия эффективности. Например, рассмотрим систему транспорта в городе, когда много агентов пытаются проехать из некоторого начального пункта в некоторый конечный пункт. Пусть эффективность в этом случае означает среднее время, за которое агент добирается до пункта назначения. В «централизованном» решении центральная власть может указать каждому агенту, какой маршрут агент должен выбрать, чтобы минимизировать среднее время проезда. В «децентрализованной» версии каждый агент выбирает маршрут по своему собственному усмотрению. Цена анархии отражает отношение средних времён в пути для этих двух случаев.
Обычно система моделируется как игра и эффективность является некоторой функцией от результата игры (например, максимальная задержка в сети, затор в транспортной системе, социальное благо на аукционах, и т. п.). Различные концепции равновесия могут быть использованы для моделирования эгоистического поведения агентов и среди них наиболее общей концепцией является равновесие Нэша. Различные вариации равновесия Нэша приводят к вариациям понятия цены анархии, как например, чистая цена анархии (для детерминированных равновесий), смешанная цена анархии (для рандомизированных равновесий) и цена анархии Байеса — Нэша (для игр с неполной информацией). Концепции, отличные от равновесия Нэша приводят к таким вариантам, как цена погруженияШаблон:Sfn.
Термин «цена анархии» впервые использовали Элиас Коутсоупиас и Христос ПападимитриуШаблон:Sfn, но идея измерения неэффективности равновесия старшеШаблон:Sfn. Концепция в её текущем виде была предназначена быть аналогией «аппроксимационного коэффициента» в аппроксимационном алгоритме или «уровня конкурентоспособности» в Шаблон:Не переведено 5. Термин лежит в русле современного тренда анализа игр с помощью алгоритмических линз (Шаблон:Не переведено 5).
Математическое определение
Рассмотрим игру <math>G=(N,S,u)</math>, определённую множеством игроков <math>N</math>, наборами стратегий <math>S_i</math> для каждого игрока и функции полезности <math>u_i: S \rightarrow \mathbb{R}</math> (где <math>S = S_1 \times ... \times S_n</math> называется также множеством исходов). Мы можем определить меру эффективности каждого исхода, которую мы назовём функцией блага <math>Welf: S \rightarrow \mathbb{R}</math>. Естественные кандидаты включают сумму полезностей игроков (целевые полезности) <math>Welf(s) = \sum_{i \in N} u_i(s),</math> минимальную полезность (целевая справедливость или эгалитарность) <math>Welf(s) = \min_{i \in N} u_i(s),</math> …, или любую функцию, имеющую смысл для конкретной анализируемой игры, которую следовало бы максимизировать.
Мы можем определить подмножество <math>Equil \subseteq S</math> как множество стратегий в равновесии (например, множество равновесий Нэша). Цена анархии тогда определяется как отношение оптимального «централизованного» решения и «худшего равновесия»:
<math>PoA = \frac{\max_{s \in S} Welf(s)}{\min_{s \in Equil} Welf(s)}</math>
Если вместо «блага», которое мы желаем максимизировать, функцией меры эффективности является «функция цены» <math>Cost : S \rightarrow \mathbb{R}</math>, которую мы желаем минимизировать (такие как задержки в сети), мы используем (следуя соглашениям, принятых в аппроксимационных алгоритмах):
<math>PoA = \frac{\max_{s \in Equil} Cost(s)}{\min_{s \in S} Cost(s)}</math>
Связанным понятием является цена стабильности (Шаблон:Lang-en, PoS), которая измеряет отношение между «лучшим равновесием» и оптимально «централизованным» решением:
<math>PoS = \frac{\max_{s \in S} Welf(s)}{\max_{s \in Equil} Welf(s)}</math>
или в случае функций цены:
<math>PoS = \frac{\min_{s \in Equil} Cost(s)}{\min_{s \in S} Cost(s)}</math>
Мы знаем, что <math>1 \leqslant PoS \leqslant PoA</math> по определению. Ожидается, что потеря в эффективности в результате ограничений из теории игр лежит где-то между PoS и PoA.
Оба значения, PoS и PoA, были вычислены для различных типов игр. Некоторые примеры приведены ниже.
Дилемма заключённого
Рассмотрим игру 2x2, называемую дилеммой заключённого, заданную следующей матрицей цены:
| Сотрудничать | Предать | |
|---|---|---|
| Сотрудничать | 1; 1 | 7; 0 |
| Предать | 0; 7 | 5; 5 |
и пусть функцией цены будет <math>C(s_1, s_2) = u_1(s_1,s_2) + u_2(s_1,s_2).</math> Теперь минимум цены будет, когда оба игрока скооперируются и результирующей ценой будет <math>1+1 = 2</math>. Однако равновесие Нэша наблюдается только тогда, когда оба предают, и в этом случае цена равна <math>5 + 5 = 10</math>. Тогда значение PoA этой игры будет равно <math>10/2 = 5</math>.
Поскольку игра имеет единственное равновесие Нэша, значение PoS равно PoA и тоже равно 5.
Распределение работ
Более естественным примером является одна из задач планирования работ. Имеется <math>N</math> игроков и каждый из них имеет некоторую требующую выполнения работу. Они могут выбрать одну из <math>M</math> машин для выполнения работы. Цена анархии сравнивает ситуацию, когда выбор машин определяется централизованно, и ситуацию, когда каждый игрок выбирает машину так, чтобы выполнить свою работу быстрее.
Каждая машина имеет скорость <math>s_1,\ldots,s_M>0.</math> Каждая работа имеет вес <math>w_1,\ldots,w_N>0.</math> Игрок выбирает машину для выполнения его/её работы. Таким образом, стратегиями каждого игрока будут <math>A_i=\{1,2,\ldots,M\}.</math> Определим загрузку на машине <math>j</math> как:
- <math>L_j(a)=\frac{\sum_{i:a_i=j} w_i}{s_j}.</math>
Цена для игрока <math>i</math> равна <math>c_i(a)=L_{a_i}(a),</math> то есть она равна загрузке машины, которую игрок выбирает. Мы рассмотрим эгалитарную функцию цены <math>\mbox{MS}(a)=\max_j L_j(a)</math>, которая здесь называется периодом обработки.
Мы рассмотрим две концепции равновесия — чистая стратегия Нэша и смешанная стратегия Нэша. Ясно, что смешанная PoA <math>\geqslant</math> чистой PoA, поскольку любое чистое равновесие Нэша является и смешанным равновесием Нэша (неравенство может оказаться строгим, например когда <math>N=2</math>, <math>w_1=w_2=1</math>, <math>M=2</math> и <math>s_1=s_2=1</math>, при смешанных стратегиях <math>\sigma_1=\sigma_2=(1/2,1/2)</math> получаем среднее время обработки 1,5, в то время как PoA чистой стратегии в этих условиях равна <math>\leqslant 4/3</math>). Первое, что нам нужно сделать, это показать существование чистого равновесия Нэша.
Утверждение. Для любой игры с распределением работ существует по меньшей мере одна равновесная по Нэшу чистая стратегия.
Доказательство. Нам нужно получить социально оптимальный набор стратегий <math>a^*</math>. Это может означать просто набор стратегий, для которых время обработки минимально. Однако этого не достаточно. Может иметься несколько таких наборов стратегий, приводящих к ряду различных распределений нагрузок (все имеющие одну и ту же максимальную нагрузку). Кроме того мы ограничим себя тем, что имеется вторая по минимуму загрузка. Снова, это приводит к множеству возможных распределений загрузок и мы повторяем процесс, пока мы не получим <math>M</math>-ую лучшую (то есть, наименьшую) загрузку, где может быть только одно распределение загрузок (единственное с точностью до перестановки). Это можно назвать также лексикографически наименьшим вектором отсортированных загрузок.
Мы утверждаем, что это равновесие Нэша чистой стратегии. Будем доказывать от противного. Предположим, что некоторый игрок <math>i</math> может улучшить свою работу путём перехода от машины <math>j</math> к машине <math>k</math>. Это означает, что увеличенная загрузка машины <math>k</math> после перехода остаётся меньше, чем загрузка машины <math>j</math> до перехода. Поскольку загрузка машины <math>j</math> должна уменьшиться в результате перехода и никакая другая машина не затронута, что означает, что новая конфигурация гарантирует сокращение <math>j</math>-ой наибольшей загрузки в распределении. Это, однако, нарушает предположение о лексикографической минимальности <math>a</math>. что и требовалось доказать
Утверждение. Для любой игры распределения работ PoA чистой стратегии не превосходит <math>M</math>.
Доказательство. Легко ограничить сверху благо, полученное как любая равновесная по Нэшу смешанная стратегия <math>\sigma</math>, по формуле
- <math>w(\sigma) \leqslant \frac{\sum_i{w_i}}{\max_j{s_j}}.</math>
Рассмотрим для ясности любой набор чистых стратегий <math>a</math>, тогда ясно, что
- <math>w(a) \geqslant \frac{\sum_i{w_i}}{\sum_j{s_j}} \geqslant \frac{\sum_i{w_i}}{M \cdot \max_j{s_j}}.</math>
Поскольку вышеуказанное выполняется также для социального оптимума, сравнение отношений <math>w(\sigma)</math> и <math>w(a)</math> доказывает утверждение. Что и требовалось доказать
Эгоистичная маршрутизация
Парадокс Браеса
Рассмотрим сеть дорог, на которых фиксированное число водителей должны проехать от общего начального пункта в общий конечный пункт. Предположим, что каждый водитель выбирает маршрут эгоистично и что время проезда зависит линейно от числа водителей, выбравших дорогу.
Мы можем формализовать эти условия как задачу выбора маршрута в направленном связном графе <math>G=(V, E)</math>, в котором мы хотим послать единицу потока из узла-источника <math>s \in V</math> в узел-сток <math>t \in V</math> (представим, что поток состоит из выбранных маршрутов различных водителей). В частности, пусть поток будет функцией <math>f: E \mapsto \Re</math> назначающей каждому ребру неотрицательное вещественное число и рассмотрим множество линейных функций <math>L = \{ l_e(f_e) = a \cdot f_e + b \; | \; e \in E, \; a \geqslant 0, \; b \geqslant 0\}</math>, которые отображают поток через ребро в задержку прохождения ребра. Давайте также определим социальное благо потока <math>f</math> как <math>w(f) = \sum_e{f_e \cdot l_e(f_e)}</math>
Рассмотрим пример на рисунке — если пунктирная дорога недоступна, равновесие Нэша в смешанных стратегиях получается, когда каждый игрок выбирает верхний маршрут и нижний маршрут с одинаковой вероятностью — это равновесие имеет общественные издержки 1,5, и для каждого водителя требуется 1,5 единицы времени для каждого водителя, чтобы пройти из <math>s</math> в <math>t</math>. В надежде улучшения прохождения через сеть законодатель может решить открыть для водителей пунктирную дорогу с малой задержкой. В этом случае равновесие Нэша может случиться только если любой водитель использует новую дорогу, поэтому общественные издержки возрастают на 2 и теперь потребуется 2 единицы времени для каждого водителя для проезда из <math>s</math> в <math>t</math>.
Следовательно, получается необычный результат — законодательный запрет использования более быстрой дороги в некоторых случаях может дать положительный результат.
Обобщённая задача маршрутизации
Задача маршрутизации, представленная в парадоксе Браеса, может быть обобщена ко многим различным потокам по тому же самому графу в одно и то же время.
Определение (Обобщённый поток). Пусть <math>G=(V, E)</math>, <math>L</math> и <math>w</math> определены так же как и выше и предположим, что мы желаем провезти величины <math>R = \{ r_1, r_2, \dots, r_k, \; | \; r_i > 0\}</math> через каждую различную пару узлов в <math>\Gamma = \{(s_1,t_1), (s_2,t_2), \dots, (s_k,t_k) \} \subseteq (V \times V)</math>. Поток <math>f_{\Gamma, R}</math> определяется как распределение <math>p \mapsto \Re</math> вещественных неотрицательных чисел каждому пути <math>p</math>, проходящему из <math>s_i</math> в <math>t_i</math> <math>\in \Gamma</math>, с ограничениями
- <math>\sum_{p: \, s_i \rightarrow t_i}{f_p} = r_i \; \; \forall (s_i,t_i) \in \Gamma.</math>
Поток, проходящий конкретное ребро графа <math>G</math> определяется как
- <math>f_{e,\Gamma, R}=\sum_{p: \, e \in p}{f_p}.</math>
Для краткости, мы будем писать <math>f_e</math>, если <math>\Gamma,R</math> ясны из контекста.
Определение (равновесный по Нэшу поток). Поток <math>f_{\Gamma, R}</math> является равновесным по Нэшу потоком тогда и только тогда, когда <math>\forall (s_i, t_i) \in \Gamma</math> и <math>\forall p, q</math> из <math>s_i</math> в <math>t_i</math>
- <math>f_{p}>0 \Rightarrow \sum_{e \in p}{l_e(f_e)} \leqslant \sum_{e \in q}{l_e(f_e)}.</math>
Это определение тесно связано с тем, что мы говорим о поддержке смешанной стратегией равновесия по Нэшу в играх в нормальной форме.
Определение (Условное благо потока). Пусть <math>f_{\Gamma, R}</math> и <math>f_{\Gamma, R}^{*}</math> будут двумя потоками в <math>G</math>, ассоциированными с множествами <math>\Gamma</math> и <math>R</math>. Далее мы будем опускать индекс, чтобы сделать обозначения проще. Представим фиксированные задержки, порождённые функциями <math>f</math> на графе — условное благо <math>f^{*}</math> по отношению к <math>f</math> определяется как
- <math>w^{f}(f^{*}) = \sum_{e \in E}{f^{*}_e \cdot l_{e}(f_{e})}</math>
Факт 1. Если имеется равновесный по Нэшу поток <math>f</math> и любой другой поток <math>f^{*}</math>, <math>w(f) = w^{f}(f) \leqslant w^{f}(f^{*})</math>.
Доказательство (от обратного). Предположим, что <math>w^{f}(f^{*}) < w^{f}(f)</math>. По определению,
- <math>\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)</math>.
Поскольку <math>f</math> и <math>f^{*}</math> связаны с теми же множествами <math>\Gamma, R</math>, мы знаем, что
- <math>\sum_{p: s_i \rightarrow t_i}f_p = \sum_{p: s_i \rightarrow t_i} f_p^{*} = r_i \; \; \forall i.</math>
Поэтому должна существовать пара <math>(s_i, t_i)</math> и два пути <math>p, q</math> из <math>s_i</math> в <math>t_i</math>, такой что <math>f_p^{*} > f_p</math>, <math>f_q^{*} < f_q</math>, и
- <math>\sum_{e \in p}l_e(f_e) < \sum_{e \in q}l_e(f_e).</math>
Другими словами, поток <math>f^{*}</math> может получить меньшее благо, чем <math>f</math>, только если два пути из <math>s_i</math> в <math>t_i</math> имеют различные цены, и если <math>f^{*}</math> перенаправляет некоторый поток <math>f</math> из пути с высокой ценой на путь с меньшей ценой. Ясно, что эта ситуация несовместима с предположением, что <math>f</math> является равновесным по Нэшу потоком. что и требовалось доказать.
Заметим, что Факт 1 не предполагает любую конкретную структуру множества <math>L</math>.
Факт 2. Если даны два вещественных числа <math>x</math> и <math>y</math>, <math>x \cdot y \leqslant x^2 + y^{2}/4</math>.
Доказательство. Это другой способ выразить верное неравенство <math>(x-y/2)^2 \geqslant 0</math>. что и требовалось доказать.
Теорема. PoA чистой стратегии любой обобщённой задачи маршрутизации <math>(G, L)</math> с линейными задержками равна <math>\leqslant 4/3</math>.
Доказательство. Заметим, что эта теорема эквивалентна высказыванию, что каждый равновесный по Нэшу поток <math>f</math>, <math>w(f) \leqslant (4/3) \cdot \min_{f^{*}} \{ w(f^{*}) \}</math>, где <math>f^{*}</math> является любым другим потоком. По определению
- <math>w^{f}(f^{*}) = \sum_{e \in E} f_e^{*}(a_e \cdot f_e + b_e)</math>
- <math>= \sum_{e}(a_{e}f_{e}f_{e}^{*}) + \sum_{e \in E}f_e^{*}b_e.</math>
Используя Факт 2 мы получаем
- <math>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</math>
- <math>= \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</math>
- <math>\leqslant w(f^{*}) + \frac{w(f)}{4},</math>
поскольку
- <math>(1/4) \cdot w(f) = (1/4) \cdot \sum_{e \in E}f_e(a_{e}f_{e}+b_{e})</math>
- <math>= (1/4) \cdot \sum_{e \in E}(f_{e})^2 + \underbrace{(1/4) \cdot \sum_{e \in E}f_{e}b_{e}}_{\geqslant 0}.</math>
Мы можем заключить, что <math>w^{f}(f^{*}) \leqslant w(f^{*}) + w(f)/4</math>, и доказываем высказывание с помощью Факта 1. что и требовалось доказать.
Заметим, что в доказательстве мы широко использовали предположение, что функции в <math>L</math> линейны. На самом деле выполняются более общие факты.
Теорема. Если дана обобщённая задача маршрутизации на графе <math>G</math> и полиномиальные функции задержки степени <math>d</math> с неотрицательными коэффициентами, PoA чистой стратегии <math>\leqslant d+1</math>.
Заметим, что PoA может расти с увеличением <math>d</math>. Рассмотрим пример, показанный на рисунке, где мы предполагаем единичный поток: равновесные по Нэшу потоки имеют социальное благо 1. Однако лучшее благо достигается, когда <math>x=1-1/{\sqrt{d+1}}</math> и в этом случае
- <math>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}}</math>
- <math>=\left(\left( 1-\frac{1}{\sqrt{d+1}} \right)^{\sqrt{d+1}}\right)^\sqrt{d+1}+\frac{1}{\sqrt{d+1}}</math>
- <math>\leqslant e^{-\sqrt{d+1}} + \frac{1}{\sqrt{d+1}}.</math>
Значение стремится к нулю по мере стремления <math>d</math> к бесконечности.
См. также
- Трагедия общих ресурсов
- Шаблон:Не переведено 5 — игра с маленькой ценой анархии.
- Шаблон:Не переведено 5
Примечания
Литература
Литература для дальнейшего чтения
- Fabio Cunial, Price of anarchy Шаблон:Wayback
