Игра с пробками

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

Исследование игр с перегрузками было инициировано американским экономистом Робертом Розенталем в 1973 году. Он доказал, что каждая игра с перегрузками имеет равновесие Нэша в чистых стратегиях (также известное как чистое равновесие Нэша , PNE). В ходе доказательства он фактически доказал, что каждая игра с перегрузками является точной потенциальной игрой . Позже Мондерер и Шепли доказал обратный результат: любая игра с точной потенциальной функцией эквивалентна некоторой игре со скоплениями. Более поздние исследования были сосредоточены на таких вопросах, как:

• Распространяется ли существование равновесия, а также существование потенциальной функции на более общие модели игр с перегрузками?
• В чем количественная неэффективность игр с перегрузками ?
• Какова вычислительная сложность поиска равновесия?

Пример

Ориентированный граф для простой игры с перегрузками.

Рассмотрим сеть трафика, в которой два игрока исходят из точки $O$ и нужно добраться до точки $T$. Предположим, что узел $O$ подключен к узлу $T$ двумя путями: $O$- $A$- $T$ и $O$- $B$- $T$, где $A$ немного ближе, чем $B$ (т.е. $A$ с большей вероятностью будет выбран каждым игроком), как на рисунке справа.

Дороги от обеих точек соединения до $T$ легко перегружаться, а это означает, что чем больше игроков проходят через точку, тем больше становится задержка каждого игрока, поэтому, если оба игрока проходят через одну и ту же точку соединения, это приводит к дополнительной задержке. Формально задержка в каждом из $A$$T$ и $B$$T$ когда $x$ игроки идут, есть $x^{2}$.

Хорошим результатом в этой игре будет то, что два игрока «скоординируют свои действия» и пройдут через разные точки соединения. Можно ли добиться такого результата?

Следующая матрица выражает затраты игроков в виде задержек в зависимости от их выбора:

Матрица затрат

п2 п1	ОАТ	ОБТ
ОАТ	(5,5)	(2,3)
ОБТ	(3,2)	(6,6)

Чистыми равновесиями Нэша в этой игре являются (OAT,OBT) и (OBT,OAT): любое одностороннее изменение одного из игроков увеличивает стоимость этого игрока (обратите внимание, что значения в таблице являются затратами, поэтому игроки предпочитают их быть меньше). В этом примере равновесие Нэша эффективно — игроки выбирают разные дорожки, а сумма затрат минимальна.

Напротив, предположим, что задержка в каждом из $A$$T$ и $B$$T$ когда $x$ игроки идут, есть $0.8x$. Тогда матрица затрат имеет вид:

Матрица затрат

п2 п1	ОАТ	ОБТ
ОАТ	(2.6,2.6)	(1.8,2.8)
ОБТ	(2.8,1.8)	(3.6,3.6)

Теперь единственным чистым равновесием Нэша является (OAT,OAT): любой игрок, переключающийся на ОБТ, увеличивает свою стоимость с 2,6 до 2,8. Равновесие все еще существует, но оно неэффективно: сумма издержек равна 5,2, а сумма издержек в (OAT,OBT) и (OBT,OAT) равна 4,6.

Основной результат

Обозначения

Базовое определение CG состоит из следующих компонентов.

• Базовый набор $E$ перегруженных элементов (также называемых ресурсами или факторами ). В приведенном выше примере $E$ это набор дорог ( $O$$A$, $A$$T$, $O$$B$ и $B$$T$).
• Набор $n$ игроки. В приведенном выше примере $n=2$.
• Конечный набор стратегий $S_{i}$ для каждого игрока, где каждая стратегия $P\in S_{i}$ является подмножеством $E$.
  • В приведенном выше примере оба игрока имеют одинаковый набор стратегий: $S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}$. CG, в которых все игроки имеют одинаковый набор стратегий, называются симметричными CG . В общем, разные игроки могут иметь разные наборы, например, если у каждого игрока разные источники и/или разные цели. Такие ЦГ называются асимметричными ЦГ .
  • В общем, стратегия может представлять собой любое подмножество $E$. CG, в которых стратегией может быть только путь в данном графе (как в приведенном выше примере), называются сетевыми CG . CG, в которых стратегия может быть только одним ресурсом, называются одноэлементными CG .
• Для каждого элемента $e\in E$ и вектор стратегий $(P_{1},P_{2},\ldots ,P_{n})$, нагрузка определяется как $x_{e}=\#\{i:e\in P_{i}\}$.
• Для каждого элемента $e\in E$ есть функция задержки $d_{e}:\mathbb {N} \longrightarrow \mathbb {R}$ (также называемая функцией задержки или функцией стоимости ). Учитывая вектор стратегий, задержка на $e$ является $d_{e}(x_{e})$. Каждый $d_{e}$ предполагается положительным и монотонно возрастающим .
• Учитывая стратегию $P_{i}$, игрок $i$ испытывает задержку $\textstyle \sum _{e\in P_{i}}d_{e}(x_{e})$; каждый игрок хочет минимизировать свою задержку.
• Равновесие Нэша — это вектор стратегий $(P_{1},P_{2},\ldots ,P_{n})$ так, что для каждого игрока $i$, замена $P_{i}$ с другой стратегией $Q_{i}$ не уменьшит задержку, испытываемую $i$.

Существование

Каждая КГ имеет равновесие Нэша в чистых стратегиях . Это можно показать, построив потенциальную функцию , которая присваивает значение каждому результату. Более того, эта конструкция также покажет, что итерированный лучший ответ находит равновесие по Нэшу. Определять $\textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)$. Обратите внимание, что эта функция не является функцией социального обеспечения. $\textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})$, а скорее своего рода дискретный интеграл. Важнейшее свойство потенциальной функции для игры с перегрузкой состоит в том, что если один игрок меняет стратегию, изменение его задержки равно изменению потенциальной функции.

Рассмотрим случай, когда игрок $i$ переключается с $P_{i}$ к $Q_{i}$. Элементы, присутствующие в обеих стратегияхостаются незатронутыми, элементы, которые оставляет игрок (т.е. $e\in P_{i}-Q_{i}$) уменьшить потенциал на $d_{e}(x_{e})$и элементы, к которым присоединяется игрок (т.е. $e\in Q_{i}-P_{i}$) увеличить потенциал на $d_{e}(x_{e}+1)$. Это изменение потенциала и есть изменение задержки для игрока. $i$, так $\Phi$ на самом деле является потенциальной функцией.

Теперь заметим, что любой минимум $\Phi$ является чистым равновесием Нэша. При фиксировании всех игроков, кроме одного, любое улучшение стратегии этого игрока соответствует уменьшению $\Phi$, чего не может произойти как минимум. Поскольку существует конечное число конфигураций и каждая $d_{e}$ монотонна, то существует равновесие.

Существование потенциальной функции имеет дополнительное следствие, называемое свойством конечного улучшения (FIP) . Если мы начнем с любого вектора стратегии, произвольно выберем игрока и позволим ему изменить свою стратегию на лучшую для него стратегию и повторим, то последовательность улучшений должна быть конечной (то есть последовательность не будет циклической). Это потому, что каждое такое улучшение строго увеличивает потенциал.

Расширения

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

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

Неатомарная ) (так называемая непрерывная компьютерная игра является пределом стандартной компьютерной игры с n игроками, поскольку $n\rightarrow \infty$. Существует континуум игроков, игроки считаются «бесконечно малыми», и каждый отдельный игрок оказывает незначительное влияние на перегрузку. Неатомные КГ изучал Мильхтайх. Фридман и Блонский.

• Мы держим $E$ конечное . множество перегруженных элементов
• Вместо того, чтобы признать $n$ игроков, как и в дискретном случае, имеем $n$ типы игроков, где каждый тип $i$ связан с номером $r_{i}$, представляющий скорость трафика для этого типа.
• Каждый агент типа i выбирает стратегию из набора стратегий. $S_{i}$.
• Как и раньше, функции задержки $d_{e}$ монотонны и положительны, но теперь мы добавим предположение, что они непрерывны . также
• Мы позволяем игрокам определенного типа дробно распределять свои стратегии. То есть для каждой стратегии $P\in S_{i}$, позволять $f_{P}$ обозначаем долю игроков в типе $i$ используя стратегию $P$. По определению, $\textstyle \sum _{P\in S_{i}}f_{P}=r_{i}$.
• Для каждого элемента $e\in E$, нагрузка определяется как сумма долей игроков, использующих e , то есть $x_{e}=\sum _{P\ni e}f_{P}$.

Существование равновесий в неатомных ЦГ

Стратегии теперь представляют собой коллекции профилей стратегий. $f_{P}$. Для набора стратегий $S_{i}$ размера $n$, совокупность всех допустимых профилей представляет собой компактное подмножество $[0,r_{i}]^{n}$. Теперь мы определим потенциальную функцию как $\textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz$, заменив дискретный интеграл стандартным.

В зависимости от стратегии, $\Phi$ является непрерывным: $d_{e}$ непрерывен по предположению, и $x_{e}$ является непрерывной функцией стратегии. Тогда по об крайних значениях теореме $\Phi$ достигает своего глобального минимума.

Последний шаг – показать, что минимум $\Phi$ действительно является равновесием Нэша. Предположим от противного, что существует совокупность $f_{P}$ которые минимизируют $\Phi$ но не являются равновесием Нэша. Тогда для некоторого типа $i$, есть некоторое улучшение $Q\in S_{i}$ над текущим выбором $P$. То есть, $\textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})$. Теперь идея состоит в том, чтобы взять небольшую сумму. $\delta <f_{P}$ игроков, использующих стратегию $P$ и перенесите их в стратегию $Q$. Теперь для любого $x_{e}\in Q$, мы увеличили его нагрузку на $\delta$, поэтому его срок в $\Phi$ сейчас $\textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz$. Дифференцируя интеграл, это изменение примерно равно $\delta \cdot d_{e}(x_{e})$, с ошибкой $\delta ^{2}$. Эквивалентный анализ изменения справедлив, если мы посмотрим на ребра в $P$.

Следовательно, изменение потенциала примерно равно $\textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))$, что меньше нуля. Это противоречие, так как тогда $\Phi$ не был сведен к минимуму. Поэтому минимум $\Phi$ должно быть равновесие Нэша.

Разделяемые игры с пробками

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

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

Игры с взвешенными пробками

В взвешенной компьютерной графике разные игроки могут по-разному влиять на перегрузку. Например, в дорожной сети грузовик создает затор гораздо больше, чем мотоцикл . В общем, вес игрока может зависеть от ресурса ( веса, специфичные для ресурса ): для каждого игрока i и ресурса e существует вес $w_{i,e}$, а нагрузка на ресурс e равна $x_{e}=\sum _{i:e\in P_{i}}w_{i,e}$. Важный частный случай — когда вес зависит только от игрока ( resource-независимые веса ), то есть каждый игрок i имеет вес $w_{i}$, и $x_{e}=\sum _{i:e\in P_{i}}w_{i}$.

Взвешенные одноэлементные CG с весами,

Мильхтайх рассматривается особый случай взвешенных CG, в которых каждая стратегия представляет собой один ресурс («Singleton CG»), веса не зависят от ресурсов и все игроки имеют одинаковый набор стратегий. Доказано следующее:

• Если все игроки имеют одинаковые функции задержки, то игра обладает свойством конечного улучшения (и, следовательно, имеет PNE).
• Если есть только две стратегии (и сколь угодно много игроков с, возможно, разными функциями задержки), то игра обладает свойством конечного улучшения (и, следовательно, имеет PNE).
• Если есть только два игрока (возможно, с разными функциями задержки), то игра обладает свойством конечного наилучшего ответа (и, следовательно, имеет PNE).
• Если есть три или более стратегий и три или более игроков с разными функциями задержки, PNE может не существовать.

Взвешенные сетевые CG

Мильхтаих рассмотрел частный случай взвешенных CG, в котором каждая стратегия представляет собой путь в заданном неориентированном графе («сетевом CG»). Он доказал, что каждую конечную игру можно представить как игру с взвешенной перегрузкой сети с неубывающими (но не обязательно отрицательными) функциями стоимости. Это означает, что не в каждой такой игре есть PNE. Конкретные примеры взвешенных КГ без ПНЕ приведены Либманом и Ордой. а также Гоеманс Миррокни и Ветта. Возникает вопрос, какие условия гарантируют существование ПНЕ.

В частности, мы говорим, что определенный граф G гарантирует определенное свойство, если каждая взвешенная сеть CG, в которой базовой сетью является G, обладает этим свойством. Мильхтайх охарактеризованные сети, гарантирующие существование PNE, а также свойство конечного улучшения, с дополнительным условием, что игрок с меньшим весом имеет слабо большее количество разрешенных стратегий (формально, $w_{i}<w_{j}$ подразумевает $|S_{i}|\geq |S_{j}|$). Он доказал, что:

• Граф G гарантирует свойство конечного улучшения тогда и только тогда, когда G гомеоморфен либо параллельной сети (графу, состоящему из одной или нескольких однореберных сетей, соединенных параллельно ), либо параллельной сети, последовательно соединенной с одним или двумя однореберными сетями. сети.
• Граф G гарантирует существование PNE тогда и только тогда, когда G гомеоморфен последовательному соединению одной или нескольких сетей из набора из шести «разрешенных сетей»; эквивалентным условием является то, что ни одна сеть из набора шести «запрещенных сетей» не вложена в G .

В особом случае, когда каждому игроку разрешено использовать любую стратегию («публичные границы»), существует больше сетей, гарантирующих существование PNE; полная характеристика таких сетей представляется открытой проблемой.

Отчаянный анализирует влияние топологии сети на эффективность PNE:

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

Мильхтайх анализирует влияние топологии сети на уникальность затрат PNE:

• Граф G гарантирует уникальность стоимостей PNE тогда и только тогда, когда G соединение представляет собой последовательное одной или нескольких сетей нескольких простых видов.
• Граф G не G гарантирует уникальность стоимостей PNE тогда и только тогда, когда содержит встроенную сеть определенного простого типа.

Хольцман и Лоу-Йон также характеризуют сети, которые гарантируют, что каждая атомарная CG имеет сильный PNE , уникальный PNE или эффективный по Парето PNE.

Ричман и Шимкин охарактеризовать сети, которые гарантируют, что каждый разделяемый CG имеет уникальный PNE.

Общие взвешенные CG

Мы говорим, что класс C функций гарантирует определенное свойство, если каждый взвешенный CG, в котором все функции задержки являются элементами C, обладает этим свойством.

• Фотакис, Контояннис и Спиракис докажите, что класс линейных функций гарантирует существование точного потенциала, а значит, и существование ПНЭ.
• Панагопулу и Спиракис доказать, что класс показательных функций гарантирует существование весового потенциала, а значит, и существование ПНЭ.
• Харкс, Климм и Моринг докажите, что класс функций гарантирует существование точного потенциала тогда и только тогда, когда он содержит только аффинные функции . Эта характеристика остается справедливой, когда она ограничена играми с двумя игроками, играми с тремя ресурсами, одноэлементными играми, играми с симметричными стратегиями или играми с целыми весами. При этом класс функций гарантирует существование весового потенциала тогда и только тогда, когда либо (1) он содержит только аффинные функции, либо (2) он содержит только показательные функции вида $a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}$, где $\phi$ одинаков для всех ресурсов. Эта характеристика остается справедливой, когда она ограничена играми с четырьмя игроками, играми с четырьмя ресурсами, одноэлементными играми, играми с симметричными стратегиями или играми с целыми весами. Для игр двух игроков класс функций гарантирует существование весового потенциала тогда и только тогда, когда все функции в нем имеют вид $a_{e}\cdot f(x_{e})+b_{e}$, где $f$ — монотонная функция (одинаковая для всех ресурсов).
• Харкс и Климм доказывают аналогичный результат для существования PNE: они доказывают, что класс функций гарантирует существование PNE тогда и только тогда, когда либо (1) он содержит только аффинные функции, либо (2) он содержит только показательные функции вида $a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}$, где $\phi$ одинаково для всех ресурсов. Эта характеристика остается справедливой, если ограничиться играми для трех игроков. Для игр двух игроков класс функций гарантирует существование PNE тогда и только тогда, когда все функции в нем имеют вид $a_{e}\cdot f(x_{e})+b_{e}$, где $f$ — монотонная функция (одинаковая для всех ресурсов).

Другие результаты

Есть много других статей об играх с взвешенной перегрузкой.

стоимости, специфичные

Базовую модель компьютерной графики можно расширить, разрешив функции задержки каждого ресурса зависеть от игрока. Таким образом, для каждого ресурса e и игрока i существует функция задержки. $d_{i,e}$. Учитывая стратегию $P_{i}$, игрок $i$ испытывает задержку $\textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})$.

для игрока, в одноэлементных CG (играх с толпой

Мильхтайх представил и изучил CG с затратами, специфичными для игрока, в следующем частном случае:

• Каждый игрок выбирает один ресурс (такие игры называются одноэлементными CG );
• У всех игроков одинаковый набор стратегий.

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

В многолюдной игре с учетом стратегии $P_{i}=\{e\}$, игрок $i$ испытывает задержку $d_{i,e}(x_{e})$. Если игрок переключается на другую стратегию $f$, его задержка будет $d_{i,f}(x_{f}+1)$; следовательно, вектор стратегии является PNE тогда и только тогда, когда для каждого игрока i: $d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)$ для всех e , f .

В общем, компьютерная графика с задержками, специфичными для игрока, может не иметь потенциальной функции. Например, предположим, что есть три ресурса x,y,z и два игрока A и B со следующими функциями задержки:

• $d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)$
• $d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)$

Ниже приводится циклический путь улучшения: $(z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)$. Это показывает, что свойство конечного улучшения не выполняется, поэтому в игре не может быть потенциальной функции (даже функции обобщенного порядкового потенциала). Однако:

• При наличии только двух ресурсов свойство конечного улучшения сохраняется. Следовательно, PNE существует.
• При наличии только двух игроков все конечные свойства наилучшего ответа сохраняются. Следовательно, PNE существует.

Когда есть три или более игроков, даже пути наилучшего ответа могут быть циклическими. Однако у каждого CG по-прежнему есть PNE. Доказательство конструктивно и показывает алгоритм, который находит равновесие по Нэшу не более чем в ${n+1 \choose 2}$ шаги. Более того, каждая CG слабо ациклична : для любого начального вектора стратегии по крайней мере один путь наилучшего ответа, начинающийся с этого вектора, имеет длину не более $r{n+1 \choose 2}$, которое заканчивается в равновесии.

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

В общем, в игре с толпой может быть много разных PNE. Например, предположим, что имеется n игроков и n ресурсов, и отрицательное влияние перегрузки на выигрыш намного выше, чем положительное значение ресурсов. Тогда есть n! разные PNE: каждое взаимно однозначное сопоставление игроков с ресурсами является PNE, поскольку ни один игрок не перейдет к ресурсу, занятому другим игроком. Однако если игра с скоплением повторяется m раз, то набор PNE сходится к одной точке, когда m стремится к бесконечности. Более того, в «большой» (неатомарной) игре с толпой обычно существует уникальный PNE. Этот PNE обладает интересным теоретико-графовым свойством. Пусть G — двудольный граф с игроками на одной стороне и ресурсами на другой, где каждый игрок соседствует со всеми ресурсами, которые выбирают его копии в уникальном PNE. Тогда G не содержит циклов.

функции

Особым случаем функций задержки, специфичных для игрока, является то, что функции задержки можно разделить на фактор, специфичный для игрока, и общий фактор. Есть два подслучая:

• Мультипликативно-разделимые функции стоимости : $d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})$, где $a_{i,e}$ — константа, представляющая базовую стоимость ресурса e для игрока i , а d — общая функция задержки (одинаковая для всех ресурсов).
• Аддитивно-разделимые функции стоимости : $d_{i,e}(x_{e})=a_{i,e}+d(x_{e})$, где $a_{i,e}$ — константа, представляющая фиксированную стоимость ресурса e для игрока i, а d — общая функция задержки (одинаковая для всех ресурсов).

Когда рассматриваются только чистые стратегии, эти два понятия эквивалентны, поскольку логарифм продукта представляет собой сумму. Более того, когда игроки могут иметь веса, зависящие от ресурса, настройку с функциями задержки, зависящими от ресурса, можно свести к настройке с универсальной функцией задержки. Игры с отделимыми функциями стоимости возникают при балансировке нагрузки. Очередь М/М/1 , и выбор среды обитания . О взвешенных одноэлементных CG с отделимыми затратами известно следующее:

• Если база стоит $a_{i,e}$ независимы от игрока ( $a_{i,e}=a_{e}$ для каждого игрока i ), то у CG есть FIP, следовательно, у него есть PNE. То же самое справедливо, если базовые затраты не зависят от ресурсов ( $a_{i,e}=a_{i}$ для каждого ресурса e ). Доказательство основано на векторнозначной потенциальной функции. Для каждого состояния игры потенциал представляет собой вектор размера n, содержащий затраты всех игроков, отсортированные от больших к меньшим. Всякий раз, когда игрок отклоняется к ресурсу с меньшей для него стоимостью, вектор затрат становится меньшим в порядке лексимина .
• Если веса не зависят от игрока (эквивалентно: CG не взвешен, а функции задержки зависят от ресурса), то у него есть FIP, следовательно, у него есть PNE. Если функции стоимости аддитивно разделимы, то игра даже имеет точную потенциальную функцию. Результат справедлив, даже если функции стоимости не монотонно возрастают с нагрузкой. Если функции стоимости не являются аддитивно-разделимыми, то FIP может не выполняться, и потенциальной функции может не быть, но PNE все еще существует.
• Если веса не зависят от ресурсов, то PNE существует в следующих случаях:
  • Когда игроков не более трех , существует PNE, хотя свойство улучшения наилучшего отклика может не соблюдаться. Напротив, существует CG с отделимыми затратами и независимыми от ресурсов весами с восемью игроками, в которых не существует PNE.
  • Когда функции стоимости аддитивно разделимы с линейными функциями переменной стоимости, CG имеет взвешенный потенциал, следовательно, у него есть FIP, следовательно, у него есть PNE.
  • Когда функции стоимости аддитивно разделимы с логарифмической функцией переменной стоимости и имеется не более трех игроков, CG обладает свойством улучшения наилучшего ответа, следовательно, у него есть PNE. Однако он может не обладать свойством конечного улучшения. Для более чем трех игроков существование ПНЕ открыто.

Каждая взвешенная одноэлементная CG с отделяемыми предпочтениями, специфичными для игрока, изоморфна взвешенной сетевой CG с предпочтениями, независимыми от игрока.

Сетевые CG со стоимостью,

Мильхтайх рассмотрел особый случай CG с затратами, специфичными для игрока, в котором каждая стратегия представляет собой путь в заданном графе («сетевое CG»). Он доказал, что каждую конечную игру можно представить как (невзвешенную) игру с перегрузкой сети с затратами, специфичными для игрока, с неубывающими (но не обязательно отрицательными) функциями стоимости. Полная характеристика сетей, гарантирующих существование PNE в таких CG, ставится как открытая задача.

чистого

Вычисление равновесия в невзвешенных CG

Доказательство существования PNE конструктивно: оно показывает конечный алгоритм (путь улучшения), который всегда находит PNE. Возникает вопрос, сколько шагов необходимо для нахождения этого PNE? Фабрикант, Пападимитриу и Талвар доказал:

• Если все стратегии являются путями в сети («сетевая CG») и все игроки имеют одинаковый набор стратегий («симметричная CG»), то PNE можно вычислить за полиномиальное время путем максимизации потенциала путем сведения к минимуму. поток затрат . Алгоритм может быть адаптирован к неатомным КГ: при определенных предположениях о гладкости равновесие Нэша в такой игре может быть аппроксимировано за сильно полиномиальное время.
• Если стратегии могут быть общими подмножествами или игроки могут иметь разные наборы стратегий («асимметричная CG»), то вычисление PNE является PLS-полным . Это означает, что существуют примеры с экспоненциально длинными путями улучшения. Это также означает, что нахождение равновесия Нэша, достижимого из заданного состояния, является PSPACE-полным .
• Любую задачу класса PLS можно представить как игру, существование чистого равновесия в которой гарантируется аргументом потенциальной функции.

Эвен-Дар, Кессельман и Мансур проанализировать количество шагов, необходимых для достижения равновесия в условиях балансировки нагрузки.

Караяннис, Фанелли, Гравин и Скопалик представить алгоритм, который вычисляет аппроксимацию PNE с постоянным коэффициентом. В частности:

• При использовании линейных функций задержки коэффициент аппроксимации равен 2+ε, а время выполнения полиномиально от количества игроков, количества ресурсов и 1/ε.
• Когда функции задержки представляют собой полиномы степени d , коэффициент аппроксимации равен d ^{О( д )} .

Их алгоритм определяет короткую последовательность ходов с лучшим ответом, которая приводит к приблизительному равновесию. Они также показывают, что для более общих CG достижение любой полиномиальной аппроксимации PNE является PLS-полным.

Вычисление равновесия во взвешенных сетевых CG

Фотакис, Контояннис и Спиракис представить алгоритм, который в любой взвешенной сети CG с линейными функциями задержки находит PNE за псевдополиномиальное время (полиномиальное по числу игроков n и сумме весов игроков W ). Их алгоритм представляет собой жадный алгоритм лучшего ответа : игроки входят в игру в порядке убывания своего веса и выбирают лучший ответ на стратегии существующих игроков.

Панагопулу и Спиракис покажите эмпирические доказательства того, что алгоритм Фотакиса, Контоянниса и Спиракиса на самом деле работает за время, полиномиальное по и log W. n Они также предлагают начальный вектор стратегии, который значительно ускоряет этот алгоритм.

В общем, взвешенный сетевой CG может не иметь PNE. Мильхтайх доказывает, что решение о том, имеет ли данная взвешенная сеть CG PNE, является NP-трудным даже в следующих случаях:

• Есть два игрока; всем игрокам разрешено использовать все пути; все функции стоимости неотрицательны.
• Есть два игрока; ЦТ не взвешен; затраты зависят от игрока и неотрицательны.

Доказательство основано на задаче о направленных путях с непересекающимися ребрами.

Караяннис, Фанелли, Гравин и Скопалик представить алгоритм, который вычисляет аппроксимацию PNE с постоянным коэффициентом во взвешенных CG. В частности:

• При использовании линейных функций задержки коэффициент аппроксимации равен ${\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )$, а время выполнения является полиномиальным по количеству игроков, количеству ресурсов и 1/ε.
• Когда функции задержки представляют собой полиномы степени d , коэффициент аппроксимации равен $d^{2d+o(d)}$.

Чтобы доказать свои результаты, они показывают, что, хотя взвешенные КГ могут не иметь потенциальной функции, каждая взвешенная КГ может быть аппроксимирована определенной потенциальной игрой. Это позволяет им показать, что каждая взвешенная CG имеет ( d !)-приблизительную PNE. Их алгоритм определяет короткую последовательность ходов с лучшим ответом, что приводит к такому приблизительному PNE.

игр с

Подводя итог, CG можно классифицировать по различным параметрам:

• Количество и разделяемость игроков: атомарная CG , разделяемая CG или неатомарная CG ;
• Вес игроков: невзвешенный ЦТ или взвешенный ЦГ (с весами, независимыми от ресурсов или весами, зависящими от ресурсов );
• Функции стоимости для разных игроков, использующих один и тот же ресурс: идентичные или специфичные для игрока (с разделяемыми или неразделимыми функциями стоимости).
• Возможные стратегии: один ресурс ( одиночный CG ) или путь в сети ( сетевой CG ) или любое подмножество ( общий CG) .
• Наборы стратегий разных игроков: разные ( асимметричная КГ ) или одинаковые ( симметричная КГ ).

См. также

• Поскольку каждая КГ имеет равновесие Нэша, следующей естественной темой является анализ их качества. Это делается с использованием концепции цены анархии в играх с перегрузками .
• ּИгры по распределению ресурсов в некоторой степени связаны с играми с перегрузками.
• Неполная информация : Факкини, ван Меген, Борм и Тийс. расширить модель Розенталя на ситуацию с неполной информацией . Они доказывают, что соответствующие байесовские игры являются потенциальными играми и, следовательно, имеют чистое равновесие Байеса-Нэша .
• Коалиции : Фотакис, Контояннис и Спиракис. изучите CG, в которых игроки участвуют в коалициях.
• Перегруженные игры в природе: Милинский описывает эксперимент, в котором естественная ЦТ сходится к равновесию Нэша. В своем эксперименте он кормил шесть колюшек с двух концов аквариума. Распределение рыб между двумя концами было в среднем аналогично соотношению норм кормовой базы, так что ни одна отдельная рыба не могла увеличить свою норму питания, перейдя на другую сторону. Млихтаих представляет более общую трактовку CG в межвидовой конкуренции .

Внешние ссылки

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