Игры на насыщение (, CG) — это класс в теории игр. Игры моделируют ситуации, часто встречающиеся на дорогах, в сетях связи, на олигополистических рынках и естественных средах обитания. Есть набор ресурсов (например, дороги или каналы связи), есть несколько игроков, которые выбирают подмножество этих ресурсов (например, водители или пользователи сети). Задержка на каждом ресурсе определяется числом игроков, выбравших подмножество, содержащее данный ресурс. Стоимость для каждого игрока — это сумма задержек на всех выбранных им ресурсах. Естественно, каждый игрок стремится минимизировать собственную задержку, однако выбор каждого игрока оказывает негативное внешнее воздействие на других игроков, что может приводить к неэффективным результатам.
Начало исследования игр на насыщение было положено американским экономистом в 1973. Он доказал, что любая игра на насыщение имеет равновесие Нэша в чистых стратегиях (, PNE). При доказательстве этого факта он, фактически, доказал, что любая игра на насыщение является точной потенциальной игрой. Позднее Мондерер и Шепли доказали обратный результат — любая игра с точной эквивалентна некоторой игре на насыщение. Позднее исследования сфокусировались на таких вопросах как:
Распространяется ли существование равновесия и потенциальной функции на более общие модели игр на насыщение? Какова количественная ? Какова нахождения равновесия?
Пример
Рассмотрим транспортную сеть, где два игрока начинают свой путь в точке и должны добраться до точки . Предположим, что вершина соединена с вершиной двумя путями: и , где чуть ближе, чем (то есть, наиболее вероятно выберут оба игрока), как показано на рисунке справа.
Дороги от обеих промежуточных точек до пункта легко нвсыщаются. Это означает, что чем больше игроков проезжает через одну точку, тем больше задержка для каждого игрока. Таким образом, если оба игрока выберут одну и ту же промежуточную точку, это вызовет дополнительную задержку. Формально, задержка на участках и , когда через них проезжает игроков, составляет .
Хорошим исходом в этой игре было бы, если бы два игрока «скоординировались» и выбрали разные промежуточные точки. Возможно ли достичь такого исхода?
Следующая матрица показывает издержки игроков в виде задержек в зависимости от их выбора: +Матрица цен OAT OBT OAT (5;5) (2;3) OBT (3;2) (6;6) Чистое равновесие Нэша в игре достигается при выборе стратегий (OAT;OBT) и (OBT;OAT): любое одностороннее изменение со стороны одного из игроков увеличивает его затраты (заметим, что значения в таблице — это затраты, поэтому игроки предпочитают их минимизировать). В данном примере равновесие Нэша эффективно — игроки выбирают разные полосы, и сумма затрат минимальна.
В отличие от этого, предположим, что задержка на каждой из полос и , когда туда направляются , составляет . Тогда матрица затрат будет следующей: + Матрица цен 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.
Основные результаты
Нотация Базовое определение игры на насыщение включает следующие компоненты. Базовый набор элементов, подверженных насыщению или переполнению (называются также ресурсами или факторами). В приведённом выше примере — это набор дорог (, , и ). Набор из игроков. В приведенном выше примере . Конечное множество стратегий для каждого игрока, где каждая стратегия является подмножеством . В приведённом выше примере оба игрока имеют одинаковый набор стратегий: . Игры, в которых все игроки имеют одинаковый набор стратегий, называются симметричными. В общем случае у разных игроков могут быть разные наборы, например, если у каждого игрока разный источник и/или разный пункт назначения. Такие игры на насыщение называются асимметричными. В общем случае стратегия может быть любым подмножеством . Игры на насыщение, в которых стратегия может быть только путём в заданном графе (как в примере выше), называются сетевыми играми на насыщение . Игры на насыщение, в которых стратегия может быть только одним ресурсом, называются играми заполнения. Для каждого элемента и вектора стратегий , нагрузка определяется как . Для каждого элемента существует функция задержки (которая называется также функцией латентности или функцией цены). Если дан вектор стратегий, задержка на элементе равна . Предполагается, что каждая функция положительна и монотонно возрастает. Если дана стратегия , игрок испытывает задержку . Каждый игрок стремится минимизировать свою задержку. Равновесие по Нэшу — это такой вектор стратегий , при котором для каждого игрока замена его стратегии на любую другую стратегию не приведёт к уменьшению задержки, испытываемой этим игроком .
Существование равновесия Нэша Любая игра на насыщение имеет равновесие Нэша в чистых стратегиях. Это можно показать путём построения , которая присваивает значение каждому исходу. Более того, такая конструкция также покажет, что итеративный находит равновесие Нэша. Определим . Заметим, что эта функция отличается от социальной выгоды и является своего рода дискретным интегралом. Ключевое свойство потенциальной функции для игры на насыщение заключается в том, что при смене стратегии одним игроком, изменение его задержки равно изменению потенциальной функции.
Рассмотрим ситуацию, когда игрок переключается со стратегии на . Элементы, присутствующие в обеих стратегиях, остаются неизменными, а элементы, которые игрок покидает (то есть ), уменьшают потенциал на величину . Элементы, к которым игрок присоединяется (то есть ), увеличивают потенциал на величину . Это изменение потенциала в точности соответствует изменению задержки для игрока , так что действительно является потенциальной функцией.
Теперь заметим, что любой минимум функции является чистым равновесием Нэша. Если мы зафиксируем стратегии всех игроков, кроме одного, то любое улучшение стратегии этого игрока привело бы к уменьшению , что невозможно в точке минимума. Поскольку количество конфигураций конечно, а каждая монотонна, равновесие существует.
Существование потенциальной функции имеет ещё одно следствие, известное как свойство конечного улучшения (, FIP). Если мы начнём с любого вектора стратегий, произвольно выберем игрока и позволим ему изменить свою стратегию на более выгодную для него, а затем повторим этот процесс, то последовательность улучшений обязательно будет конечной (то есть, последовательность не будет зацикливаться). Это происходит потому, что каждое такое улучшение строго увеличивает потенциал.
Расширения Ниже представим различные расширения и варианты базовой модели игры на насыщение.
Неатомарные игры на насыщение Неатомарная игра на насыщение — это предел стандартной игры на насыщение с n игроками, когда . Как и в любой , имеется континуум игроков, они считаются «бесконечно малыми», и каждый отдельный игрок оказывает незначительное влияние на насыщение. Неатомарные игры на насыщение изучали Мильчтайх, Фридман, Блонски, Рафгарден и Тардош.
Мы храним конечное множество элементов, подверженных переполнению. Вместо игроков, как в дискретном случае, у нас есть типов игроков, где каждому типу соответствует число , представляющее интенсивность трафика для этого типа. Каждый агент типа i выбирает стратегию из множества стратегий . Как и прежде, функции задержки монотонны и положительны, но теперь мы добавляем предположение, что они также непрерывны. Мы позволяем игрокам определённого типа распределяться дробно по их набору стратегий. То есть, для каждой стратегии , пусть обозначает долю игроков этого типа , использующих стратегию . По определению, . Для каждого элемента нагрузка определяется как сумма долей игроков, использующих этот элемент e, то есть, .
Существование равновесия в неатомарных играх на насыщение Стратегии теперь представляют собой наборы профилей стратегий . Для множества стратегий размера совокупность всех допустимых профилей является компактным подмножеством . Теперь мы определяем потенциальную функцию как , заменяя дискретный интеграл стандартным.
Как функция стратегии, непрерывна: непрерывна по определению, а является непрерывной функцией от стратегий. Тогда по теореме Вейерштрасса достигает своего глобального минимума.
Последний шаг — показать, что минимум действительно является равновесием Нэша. Предположим противное, что существует набор стратегий , минимизирующих , но не являющихся равновесием Нэша. Тогда для некоторого типа , существует улучшение по сравнению с текущим выбором . То есть, . Идея состоит в том, чтобы взять небольшое количество игроков, использующих стратегию , и перевести их на стратегию . Теперь для любого мы увеличили его нагрузку на , поэтому его вклад в теперь равен . Дифференцируя интеграл, это изменение приблизительно равно , с погрешностью . Аналогичный анализ изменения справедлив и для рёбер, входящих в .
Следовательно, изменение потенциала приблизительно равно , что меньше нуля. Это противоречие, поскольку тогда не был бы минимизирован. Таким образом, минимум должен быть равновесием Нэша.
Расщепляемые игры на насыщение В расщепляемых играх на насыщение (также называемых атомарно расщепляемыми играми на насыщение), как в атомарных играх на насыщение, имеется конечное число игроков, каждый из которых имеет определённую нагрузку. Как и в неатомарных играх на насыщение, каждый игрок может разделить свою нагрузку на доли, проходящие по различным путям, подобно транспортной компании, выбирающей маршрут для массовой перевозки. В отличие от неатомарной игры на насыщение каждый игрок оказывает существенное влияние на загруженность сети.
Расщепляемые игры на насыщение первыми анализировали Ариэль Орда, Рафаэль Ром и Нахум Шимкин в 1993 году в контексте коммуникационной сети. Они показали, что для простой сети с двумя вершинами и множеством параллельных соединений равновесие Нэша единственно при разумных условиях выпуклости и имеет некоторые интересные свойства монотонности. Для общих топологий сетей нужны более сложные условия, чтобы гарантировать единственность равновесия Нэша.
Параллельно Хор и Маркотт изучали расщепляемые игры на насыщение в контексте транспортных сетей. Они определили равновесие Курно — Нэша и дали условия для его существования и единственности. Они показали, что при разумных условиях асимптотическое поведение этого равновесия приводит к вектору общего потока, соответствующему .
Цену анархии в расщепляемых играх на насыщение изучали Гайринг, Мониен и Тиманн, Коминетти, Кореа и Штир-Моузес, Харкс и, наконец, Рафгарден и Шоппманн. .
Хуан изучал эффект сговора на общественные издержки в расщепляемых играх на насыщение. Он показал, что если сеть удовлетворяет некоторым естественным структурным условиям, а все функции задержки являются аффинными, то сговор снижает общественные издержки в равновесии.
Ричман и Шимкин описывают сети, которые гарантируют единственность равновесия по Нэшу для всех расщепляемых играх на насыщение. Харкс и Тиммерманс изучали также единственность равновесного состояния в атомарных расщепляемых полиматроидных играх на насыщение.
Вычисления Маркотт представил четыре числовых алгоритма для вычисления равновесия Нэша на насыщенных транспортных сетях и анализировал их свойства сходимости. Менье и Прадо представил численный алгоритм, аналогичный , для неатомарных сетевых игр на насыщение с аффинной зависящей от игрока функцией задержки. Для обоих этих алгоритмов не было показано полиномиального времени работы.
Коминетти, Корреа и Штир-Моузес изучали расщепляемые игры на насыщение с аффинными не зависящими от игроков функциями задержки: , где xe — насыщение на дуге e, а ae,be — не зависящие от игроков константы. Они показали выпуклую потенциальную функцию, глобальный минимум которой является PNE. Это означает, что эпсилон-приближённые PNE могут быть вычислены за полиномиальное время методами выпуклого программирования.