Цена анархии в играх с пробками

Цена анархии (PoA) — это концепция теории игр и проектирования механизмов , которая измеряет, насколько ухудшается социальное благосостояние системы из-за эгоистичного поведения ее агентов. Он широко изучался в различных контекстах, особенно в играх с перегрузками (CG).

Пример

Неэффективность игр с перегрузками была впервые продемонстрирована Пигу в 1920 году. используя следующую простую игру с перегрузками. Предположим, есть две дороги, ведущие из пункта А в пункт Б:

• Дорога 1 широкая, но медленная. По этой дороге дорога от А до Б занимает 1 минуту, независимо от того, сколько водителей ею пользуются.
• Дорога 2 быстрая, но узкая, поэтому она становится перегруженной и медленнее по мере того, как ею пользуется все больше водителей. Если x водителей воспользуются этой дорогой, им понадобится x/1000 минут, чтобы добраться из A в B.

Предположим, есть 1000 водителей, которым нужно проехать из А в Б. Каждый водитель хочет минимизировать свою задержку, но правительство хотело бы минимизировать общую задержку (сумму задержек всех водителей).

• Сначала вычислим минимально возможную задержку. Предположим, что x водителей едут на дорогу 2, а 1000 − x едут на дорогу 1. Тогда общая задержка равна x. ² /1000+(1000 - х ). Это минимизируется, когда x ≈ 500, то есть 500 водителей едут по дороге 2, а остальные 500 — по дороге 1; общая задержка составляет 500×1/2 + 500×1 ≈ 750 минут.
• Для каждого отдельного водителя задержка всегда меньше при движении по дороге 2, поскольку x /1000 < 1. Это означает, что выбор дороги 2 является доминирующей стратегией . Таким образом, в «анархии» (то есть без централизованного планирования) все водители выбирают дорогу 2, их задержка составляет 1 минуту, а общая задержка составляет 1000 минут. Проблема в том, что каждый агент минимизирует свою задержку, но игнорирует издержки, налагаемые его собственными действиями на задержку других; существует отрицательный внешний эффект , который приводит к неэффективному результату.

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

Влияние функций задержки

Чтобы проиллюстрировать влияние функций задержки на PoA, рассмотрим вариант приведенного выше примера, в котором задержка на дороге 1 по-прежнему составляет 1 минуту, но задержка на дороге 2, когда x водителей ее используют, равна $(x/1000)^{d}$, для некоторого d>1.

• Минимально возможная задержка достигается, когда число водителей, выезжающих на дорогу 2, равно $x={\frac {1000}{(d+1)^{1/d}}}$. Как $d\to \infty$, это число приближается к 1000, поэтому $1000\cdot (1-\epsilon _{d})$ водители выезжают на дорогу 2, где $\epsilon _{d}\to 0$. Общая задержка составляет $1000\epsilon _{d}+1000\cdot (1-\epsilon _{d})^{d+1}$, который приближается к 0 как $d\to \infty$.
• Однако каждому водителю на дороге 1 все равно стоит переехать на дорогу 2. Следовательно, при анархии все водители едут на дорогу 2, и задержка составляет $1000\cdot 1^{d+1}=1000$ минут.

Поэтому цена анархии приближается к бесконечности, поскольку $d\to \infty$.

Определения

Игра с перегрузкой (CG) определяется набором ресурсов . Например, в дорожной сети каждая дорога представляет собой отдельный ресурс. Для каждого

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

Равновесие Нэша — это ситуация, в которой ни один игрок не может улучшить свою задержку, в одностороннем порядке изменив свой выбор. Цена анархии (PoA) — это соотношение между наибольшей задержкой равновесия Нэша и наименьшей возможной задержкой в ​​целом. Цена стабильности (PoS) — это соотношение между наименьшей задержкой в ​​равновесии Нэша (то есть наилучшим возможным равновесием) и наименьшей возможной задержкой в ​​целом. PoA и PoS также можно рассчитать с учетом других концепций равновесия, таких как смешанное равновесие или коррелированное равновесие .

Существует несколько основных классов игр с перегрузками:

• В атомарных CG имеется конечное число игроков, и каждый игрок выбирает один путь (- одно подмножество ресурсов). У игр с атомной перегрузкой есть два варианта:
  • В невзвешенных CG каждый игрок вносит одинаковую сумму 1 в перегруженность используемых им ресурсов. Следовательно, перегруженность каждого ресурса — это просто количество игроков, выбирающих этот ресурс.
  • В взвешенных CG каждый игрок i имеет разный вес w _i . Например, в дорожных сетях вес водителя может быть равен длине его автомобиля. Перегруженность каждого ресурса равна сумме весов всех игроков, выбравших этот ресурс.
• В неатомарных CG количество игроков приближается к бесконечности, а это значит, что вклад каждого отдельного игрока в перегрузку незначителен. Игроки представлены непрерывным количеством. Пример Пигу (показанный выше) изначально был заявлен как неатомарная игра. Предположим, что задержка на дороге 1 равна 1. Имеется 1 непрерывная единица игроков. Минимальная общая задержка достигается, когда 1/2 игроков переходят на дорогу 1 и 1/2 игроков переходят на дорогу 2; общая задержка составляет 1*1/2+1/2*1/2 = 3/4. Однако для каждого отдельного игрока задержка на пути 2 всегда меньше, поэтому в равновесии Нэша общая задержка равна 1*1=1.
• В разделяемых CG имеется конечное число игроков, каждый игрок имеет вес, и каждый игрок может разделить свой вес между несколькими путями (- несколькими подмножествами ресурсов).

Другая классификация CG основана на наборе стратегий, доступных игрокам:

• В симметричных CG все игроки имеют одинаковый набор возможных стратегий, как в примере Пигу выше.
• В асимметричных CG разные игроки могут иметь разные наборы возможных стратегий, например, водители с разными местоположениями источника и назначения.

Более того:

• В одноэлементных CG каждая стратегия каждого игрока представляет собой одноэлементный набор. То есть: каждый игрок выбирает один ресурс.
• В сетевых CG существует базовый граф, и каждая стратегия каждого игрока представляет собой простой путь в графе. Если компьютерная графика симметрична, то у всех игроков одинаковый источник и пункт назначения; если он асимметричен, то у разных игроков могут быть разные источники или пункты назначения.

Игры с атомными перегрузками

Христодулу и Куцупиас проанализировали атомарные невзвешенные CG. Они доказали, что PoA, когда все функции задержки линейны, составляет ровно 2,5 (то есть: PoA всегда не превышает 2,5, а в некоторых случаях оно равно ровно 2,5). Они также дали верхние и нижние оценки для PoA, когда функции задержки являются полиномами ограниченной степени. В другой статье Христодулу и Куцупиас проанализировали PoS атомарных игр с невзвешенной перегрузкой и линейными функциями задержки. Они доказали, что PoS не превышает 1,6 , и показали пример, в котором PoS равен 1,577 . Они также показали, что PoA коррелированных равновесий в этом случае составляет ровно 2,5 для невзвешенных игр и ровно 2,618 для взвешенных игр.

Авербух, Азар и Эпштейн проанализировали проанализированные атомно- взвешенные CG. Они доказали, что PoA, когда все функции задержки линейны, составляет ровно 2,618 . Они также показали, что, когда функции задержки являются полиномами степени d , PoA находится в $d^{\Theta (d)}$.

Аланд, Думрауф, Гайринг, Моньен и Шоппманн вычислил точный PoA для атомарных CG для функций задержки, которые являются полиномами степени не выше d :

• Для невзвешенных игр PoA $(\Phi _{d})^{d+1}$, где $\Phi _{d}$ является единственным неотрицательным вещественным решением $(x+1)^{d}=x^{d+1}$. Обратите внимание, что $\Phi _{1}$ это золотое сечение , и $\Phi _{d}$ растет как $\Theta \left({\frac {d}{\log {d}}}\right)$. Итак, PoA в силе. $\Theta \left({\frac {d}{\log {d}}}\right)^{d+1}$.
• Для взвешенных игр PoA ${\frac {(k_{d}+1)^{2d+1}-(k_{d}+2)^{d}\cdot (k_{d})^{d+1}}{(k_{d}+1)^{d+1}-(k_{d}+2)^{d}+(k_{d}+1)^{d}-(k_{d})^{d+1}}}$, где $k_{d}:=\lfloor \Phi _{d}\rfloor$. Асимптотически это все еще растет как $\Theta \left({\frac {d}{\log {d}}}\right)^{d+1}$.

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

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

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

Де-Йонг и Уетц изучайте последовательные компьютерные игры , в которых игроки выбирают свои стратегии последовательно, а не одновременно. Они анализируют PoA идеального равновесия в подыграх . Они показывают, что последовательный PoA с аффинными функциями стоимости равен ровно 1,5 для двух игроков, ≈ 2,13 для трех игроков и как минимум 2,46 для четырех игроков. Для одноэлементных игр с перегрузкой и аффинными функциями стоимости, когда есть n игроков, последовательный PoA не превышает n -1; когда $n\to \infty$, последовательный PoA составляет не менее 2+1/e ≈ 2,37 . Для симметричных одноэлементных игр с атомарной перегрузкой и аффинными функциями стоимости последовательный PoA равен точно 4/3 .

Фотакис изучает PoA CG с линейно независимыми путями, что является расширением настройки параллельных каналов.

Ло, Хуан и Лю изучить PoA CG в сетях когнитивного радио .

Гейринг, Буркхард и Карстен изучить PoA компьютерных игр с специфичными для игрока функциями линейной задержки.

Млихтаих анализирует влияние топологии сети на эффективность PNE в атомарных CG:

• Граф G гарантирует, что каждый PNE эффективен по Парето, если только три простые «запрещенные сети» не вложены G. в
• Граф G гарантирует, что парадокс Брасса не произойдет, если он является последовательно-параллельным графом .

PoA игр с неатомной перегрузкой

Рафгарден и Тардос проанализировали неатомные CG. Они показали, что, когда функции задержки являются полиномами степени не выше d , PoA находится в $\Theta \left({\frac {d}{\log {d}}}\right)$, что существенно меньше PoA атомных игр. В частности, когда d =1, PoA составляет 4/3; это показывает, что простой пример Пигу является наихудшим случаем для линейных функций задержки.

Чау и Сим расширить результаты Рафгардена и Тардоса путем (1) рассмотрения симметричных карт затрат и (2) включения эластичных требований.

Корреа, Шульц и Штир-Мозес представить краткое геометрическое доказательство результатов о РоА для неатомных КГ. Они также дают более строгие границы PoA, когда равновесные затраты находятся в разумных пределах постоянных затрат.

Блюм, Эвен-Дар и Лигетт показал, что все эти границы PoA применимы при относительно слабых поведенческих предположениях: достаточно, чтобы все пользователи достигли исчезающего среднего сожаления при повторных проходах в игру.

Полезным понятием при анализе PoA является гладкость . Функция задержки d называется $(\lambda ,\mu )$-гладко если для всех $x,y>0$, $yd(x)\leq \lambda yd(y)+\mu xd(x)$. Если задержка $(\lambda ,\mu )$ гладкий, $f$ является равновесием Нэша, и $f^{*}$ является оптимальным распределением, то $\textstyle \sum _{e}x_{e}d_{e}(x_{e})\leq {\frac {\lambda }{1-\mu }}\sum _{e}x_{e}^{*}d_{e}(x_{e}^{*})$. Другими словами, цена анархии $\textstyle {\frac {\lambda }{1-\mu }}$.

Млихтаих проанализировали одноэлементные неатомные CG со следующими дополнительными характеристиками:

• Полезность каждого игрока состоит из двух частей: значения , специфичная для ресурса , специфичного для игрока, минус задержка . Формально, если игрок i выбирает ресурс e , то $u_{i}=v_{i}(e)-d_{e}(x_{e})$, где $v_{i}(e)$ — это внутренняя ценность, которую я присваиваю e.
• Функции задержки $d_{e}(x_{e})$ строго увеличиваются.
• Предельные социальные издержки перегрузки любого ресурса e (определяемые как производная ${\frac {d}{dx}}[x\cdot d_{e}(x)]$) строго возрастает.

В таких играх равновесные выигрыши всегда уникальны и эффективны по Парето, но не могут максимизировать сумму полезностей. Более того:

• Если имеется хотя бы три ресурса, равновесие максимизирует сумму (то есть PoS=PoA=1) тогда и только тогда, когда функции задержки логарифмические . Для нелогарифмических функций задержки всегда существуют фиксированные полезности или затраты, для которых никакое равновесие не максимизирует сумму полезностей (PoS>1, что подразумевает PoA>1). Когда имеется только два ресурса, класс функций задержки, для которых PoA=1, несколько шире.
• Если функции задержки не «слишком» выпуклые, то максимизировать сумму полезностей можно с помощью переговорного процесса, и существует явная формула, определяющая долю максимальной совокупной полезности, которая должна быть распределена между каждой группой игроков. .

PoA разделяемых игр с перегрузкой

Рафгарден и Шоппманн проанализировали разделяемые игры с перегрузкой. Они показали, что, когда функции задержки являются полиномами степени не выше d , PoA находится в $\left({\frac {1+{\sqrt {d+1}}}{2}}\right)^{d+1}$. В частности, когда d =1, PoA составляет не более 3/2. PoA для разделяемых игр меньше, чем для атомарных игр, но больше, чем для неатомарных игр. Например:

• Когда d=1, PoA составляет 1,333 для неатомарных игр, 1,5 для разделяемых игр и 2,5 для атомарных игр;
• Когда d=8, PoA составляет 3,081 для неатомарных игр, 512 для разделяемых игр и 1 101 126 для атомарных игр.

PoA с альтруистическими игроками

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

• В атомных CG, как правило, даже частичный альтруизм может нанести вред общей эффективности. Однако в частном случае игр с симметричной балансировкой нагрузки оптимальная эффективность может быть достигнута за счет баланса эгоизма и альтруизма.
• В атомарных CG и играх с разделением затрат устойчивый PoA ухудшается с ростом альтруизма, тогда как в действительных служебных играх альтруизм на него не влияет. Но в общих неатомных CG с равномерным альтруизмом PoA улучшается с увеличением альтруизма. Для атомных и неатомных одноэлементных CG существуют границы чистого PoA, которые улучшаются с увеличением среднего альтруизма.

Есть и другие работы, изучающие влияние альтруизма на PoA. Альтернативный способ измерения влияния альтруизма на эффективность — с помощью сравнительной статики : в одной игре (не обязательно в худшем случае) как увеличение коэффициента альтруизма влияет на социальные издержки? Для некоторых классов КГ влияние альтруизма на эффективность может быть отрицательным.

См. также

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