Игра о перегрузках - Википедия - Congestion game

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

Мотивация

Рассмотрим транспортную сеть, в которой два игрока исходят из точки. О и нужно перейти к делу Т. Предположим, что узел О подключен к узлу Т через точки подключения А и B, куда А немного ближе чем B (т.е. А с большей вероятностью будет выбран каждым игроком). Однако обе точки соединения легко перегружаются, а это означает, что чем больше игроков проходит через точку, тем больше становится задержка каждого игрока, поэтому прохождение обоих игроков через одну и ту же точку соединения вызывает дополнительную задержку. Хорошим исходом в этой игре будет то, что два игрока «координируют» и проходят через разные точки соединения. Можно ли добиться такого результата? И если да, то сколько будет стоить каждый игрок?

Определение

Игры с дискретными перегрузками - это игры со следующими компонентами.

  • Базовый набор сборных элементов ;
  • игроки;
  • Конечный набор стратегий для каждого игрока, где каждая стратегия это подмножество ;
  • Для каждого элемента и вектор стратегий , нагрузка ;
  • Для каждого элемента , функция задержки ;
  • Учитывая стратегию , игрок испытывает задержку . Предположим, что каждый положительный и монотонно возрастающий.

Пример

Рассмотрим следующий ориентированный граф, в котором у каждого игрока есть две доступные стратегии - пройти через A или пройти через B, что в сумме дает четыре возможности. Следующая матрица выражает затраты игроков с точки зрения задержек в зависимости от их выбора:

Ориентированный граф для простой игры с перегрузкой.
Матрица затрат
p2
p1
АB
А(5,5)(2,3)
B(3,2)(6,6)

И (A, B), и (B, A) чистые Равновесия Нэша в этой игре, поскольку любое одностороннее изменение одним из игроков увеличивает стоимость этого игрока (обратите внимание, что значения в таблице являются затратами, поэтому игроки предпочитают, чтобы они были меньше).

Существование равновесий по Нэшу

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

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

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

Игры с непрерывной перегрузкой

Игры с непрерывной перегрузкой являются предельным случаем, поскольку . В этой схеме мы считаем игроков «бесконечно маленькими». Мы продолжаем а конечный набор перегружаемых элементов. Вместо признания игроков, как и в дискретном случае, имеем типы игроков, где каждый тип связан с числом , представляющий ставка трафика для этого типа. Каждый тип выбирает стратегию из набора стратегий. , которые мы предполагаем не пересекающимися. Как и раньше, предположим, что монотонны и положительны, но добавим предположение, что они непрерывный Наконец, мы позволяем игрокам в типе дробно распределять свои стратегии. То есть для , позволять обозначим долю игроков типа используя стратегию . Предположить, что .

Существование равновесий в непрерывном случае

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

В зависимости от стратегии непрерывно: непрерывно, и является непрерывной функцией стратегии. Затем потеорема об экстремальном значении, достигает своего глобального минимума.

Последний шаг - показать, что минимум действительно, равновесие по Нэшу. Предположим от противного, что существует набор это минимизирует но не являются равновесием по Нэшу. , есть улучшения над текущим выбором . То есть, Идея сейчас взять небольшую сумму игроков, использующих стратегию и переместить их в стратегию . Теперь для любого , мы увеличили его нагрузку на , поэтому его срок в сейчас .Дифференцируя интеграл, это изменение приблизительно равно , с ошибкой Эквивалентный анализ изменения справедлив, когда мы смотрим на ребра в .

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

Качество решений и цена анархии

Поскольку в играх с непрерывной перегрузкой существуют равновесия по Нэшу, следующей естественной темой является анализ их качества. Мы выведем границы отношения между задержкой в ​​Нэше и оптимальной задержкой, иначе известной как Цена анархии. Во-первых, мы начнем с технического условия на функции задержки.

Определение Задержка составляет гладко, если для всех , .

Теперь, если задержка гладкий, является равновесием по Нэшу, а оптимальное размещение, то. Другими словами, цена анархии .Посмотрите эти конспект лекций для доказательства.

Смотрите также

Рекомендации

  • Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.
  • Конспект лекций Михал Фельдман и Ноам Нисан о Игры с потенциалом и перегрузкой
  • Розенталь, Роберт В. (1973), "Класс игр, обладающих равновесием Нэша чистой стратегией", Международный журнал теории игр, 2: 65–67, Дои:10.1007 / BF01737559, МИСТЕР  0319584.

внешняя ссылка

  1. ^ Кукушкин, Н. С .; Меньшиков, И. С .; Меньшикова О.Р .; Морозов, В. В. (1990). «Игры с распределением ресурсов». Вычислительная математика и моделирование. 1 (4): 433. Дои:10.1007 / BF01128293.