Игры на насыщение

Игры на перегрузку (англ. Congestion Games, CG) — это класс игр в теории игр, моделирующих ситуации, где использование общих ресурсов несколькими участниками приводит к увеличению издержек для каждого из них. Такие модели находят применение при анализе транспортных потоков, коммуникационных сетей, олигополистических рынков и конкуренции за места обитания. В игре имеется набор ресурсов (например, дороги или каналы связи), и несколько игроков, каждый из которых выбирает некоторое подмножество этих ресурсов (например, маршрут). Задержка (или стоимость) на каждом ресурсе определяется количеством игроков, выбравших подмножество, содержащее данный ресурс. Индивидуальные издержки игрока представляют собой сумму задержек на всех выбранных им ресурсах. Каждый игрок стремится минимизировать свои собственные издержки, однако его выбор создаёт внешние эффекты (экстерналии) для других, что может приводить к социально неэффективным исходам.

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

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

Пример[править | править код]

Пример транспортной сети с двумя игроками.

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

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

Социально эффективным исходом в этой игре было бы, если бы два игрока «скоординировались» и выбрали разные промежуточные точки. Возможно ли достичь такого исхода?

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

Матрица издержек
	OAT	OBT
OAT	(5;5)	(2;3)
OBT	(3;2)	(6;6)

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

В отличие от этого, предположим, что задержка на каждом из участков $A T$ и $B T$ при нагрузке $x$ составляет $0, 8 x$ . Тогда матрица издержек будет следующей:

Матрица издержек
	OAT	OBT
OAT	(2,6;2,6)	(1,8;2,8)
OBT	(2,8;1,8)	(3,6;3,6)

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

Основные результаты[править | править код]

Обозначения[править | править код]

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

Базовое множество $E$ элементов, подверженных перегрузке (называются также ресурсами или факторами). В приведённом выше примере $E$ — это набор дорог ( $O A$ , $O B$ , $A T$ и $B T$ ).
Набор из $n$ игроков. В приведенном выше примере $n = 2$ .
Конечное множество стратегий Si для каждого игрока, где каждая стратегия P∈Si является подмножеством E.
- В приведённом выше примере оба игрока имеют одинаковый набор стратегий: $S_{1} = S_{2} = {{O A, A T}, {O B, B T}}$ . Игры, в которых все игроки имеют одинаковый набор стратегий, называются симметричными. В общем случае у разных игроков могут быть разные наборы, например, если у каждого игрока разный источник и/или разный пункт назначения. Такие игры на перегрузку называются асимметричными.
- В общем случае стратегия может быть любым подмножеством $E$ . Игры на перегрузку, в которых стратегия может быть только путём в заданном графе (как в примере выше), называются сетевыми играми на перегрузку. Игры на перегрузку, в которых стратегия может быть только одним ресурсом, называются играми заполнения.
Для каждого элемента $e \in E$ и вектора стратегий $(P_{1}, P_{2}, \dots, P_{n})$ , нагрузка определяется как $x_{e} = # {i : e \in P_{i}}$ .
Для каждого элемента $e \in E$ существует функция задержки $d_{e} : ℕ ⟶ ℝ$ (которая называется также функцией латентности или функцией цены). Если дан вектор стратегий, задержка на элементе $e$ равна $d_{e} (x_{e})$ . Предполагается, что каждая функция $d_{e}$ положительна и монотонно возрастает.
Если дана стратегия $P_{i}$ , игрок $i$ испытывает задержку $\sum_{e \in P_{i}} d_{e} (x_{e})$ . Каждый игрок стремится минимизировать свою задержку.
Равновесие по Нэшу — это такой вектор стратегий $(P_{1}, P_{2}, \dots, P_{n})$ , при котором для каждого игрока $i$ замена его стратегии $P_{i}$ на любую другую стратегию $Q_{i}$ не приведёт к уменьшению задержки, испытываемой этим игроком.

Существование равновесия Нэша[править | править код]

Любая игра на перегрузку имеет чистое равновесие Нэша. Это можно показать путём построения потенциальной функции, которая присваивает значение каждому исходу. Более того, такая конструкция также показывает, что итеративный процесс улучшения стратегий находит равновесие Нэша. Определим $Φ = \sum_{e \in E} \sum_{k = 1}^{x_{e}} d_{e} (k)$ . Заметим, что эта функция отличается от социальных издержек $\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$ , так что $Φ$ действительно является потенциальной функцией.

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

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

Расширения[править | править код]

Далее представлены различные расширения и варианты базовой модели игры на перегрузку.

Неатомарные игры на перегрузку[править | править код]

Неатомарная игра на перегрузку — это предел стандартной игры на перегрузку с $n$ игроками, когда $n \to \infty$ . Как и в любой игре с континуумом игроков, они считаются «бесконечно малыми», и каждый отдельный игрок оказывает незначительное влияние на перегрузку. Неатомарные игры на перегрузку изучали Мильчтайх, Фридман, Блонски, Рафгарден и Тардош.

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

Существование равновесия в неатомарных играх на перегрузку[править | править код]

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

Как функция стратегии, $Φ$ непрерывна: $d_{e}$ непрерывна по определению, а $x_{e}$ является непрерывной функцией от стратегий. Тогда по теореме Вейерштрасса о функции на компакте $Φ$ достигает своего глобального минимума.

Последний шаг — показать, что минимум $Φ$ действительно является равновесием Нэша. Предположим противное, что существует набор стратегий $f_{P}$ , минимизирующих $Φ$ , но не являющихся равновесием Нэша. Тогда для некоторого типа $i$ существует улучшение $Q \in S_{i}$ по сравнению с текущим выбором. То есть, $\sum_{e \in Q} d_{e} (x_{e}) < \sum_{e \in P} d_{e} (x_{e})$ . Идея состоит в том, чтобы взять небольшое количество $δ < f_{P}$ игроков, использующих стратегию $P$ , и перевести их на стратегию $Q$ . Теперь для любого $e \in Q$ мы увеличили его нагрузку на $δ$ , поэтому его вклад в $Φ$ теперь равен $\int_{0}^{x_{e} + δ} d_{e} (z) d z$ . Дифференцируя интеграл, это изменение приблизительно равно $δ \cdot d_{e} (x_{e})$ , с погрешностью $δ^{2}$ . Аналогичный анализ изменения справедлив и для рёбер, входящих в $P$ .

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

Расщепляемые игры на перегрузку[править | править код]

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

Расщепляемые игры на перегрузку первыми анализировали Ариэль Орда, Рафаэль Р

Ссылки[править | править код]