Расположение объекта (соревновательная игра) - Facility location (competitive game)

В соревновательная игра по поиску объектов это своего рода соревновательная игра в котором поставщики услуг выбирают места для размещения своих объектов, чтобы максимизировать свою прибыль.^[1]^[2]^:502–506 В игре есть следующие компоненты:

Есть несколько потребителей, которым нужна определенная услуга, например, подключение к электричеству.
Есть несколько производителей, которые могут предоставить эту услугу, например, электроэнергетические компании.
Каждый производитель может построить свой объект (например, электростанцию) в одном из нескольких мест.
Для каждой пары потребителей (C) и местоположения (L) существует фиксированная стоимость обслуживания C от L (например, в зависимости от расстояния между электростанцией и домом потребителя). Эта стоимость обозначается Стоимость [C, L].

Игра представляет собой последовательная игра с тремя шагами:

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

У каждого потребителя есть определенная личная ценность для принятия услуги.

Для каждой пары потребитель-производитель:

Выигрыш потребителя от подключения к объекту производителя - это его стоимость за вычетом цены;
Выигрыш производителя - это цена за вычетом затрат на обслуживание потребителя;
Социальное благосостояние этой пары - это сумма выгод, то есть ценность потребителя за вычетом стоимости услуг.

Равновесие

Анализируем игру с помощью обратная индукция.

Шаг 3 прост: каждый потребитель просто выбирает самое дешевое заведение.

Шаг 2 тоже довольно простой. Предположим, что производитель P имеет свое предприятие в местоположении L. Тогда цена, которую он берет от потребителя C, должна быть не менее Cost [C, L]. Предположим, что местоположения упорядочены в порядке возрастания стоимости, т. Е. Местоположениями являются L1, L2, ... такие, что Cost [C, L1]

Шаг 1 - шаг расположения объекта - сложнее проанализировать (поэтому игра названа в честь этого шага). Можно доказать, что это потенциальная игра (Потенциал - это общее социальное благосостояние; когда в игру вступает новый производитель, рост общественного благосостояния в точности равен прибыли производителя).^[2]^:503–504 Следовательно, этот шаг имеет чистое равновесие по Нэшу, и вся игра имеет чистое равновесие. подигра идеальное равновесие.

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

Игра «объект - расположение» может иметь другие чистые равновесия по Нэшу, в которых общественное благосостояние не является максимальным. Однако можно доказать, что общественное благосостояние в таких равновесиях составляет по крайней мере половину оптимума. Следовательно цена анархии не больше 2.^[2]^:505–506

Более того, можно показать, что цена анархии не превышает 2, даже если игра не сходится к равновесию. Рассмотрим случайную последовательность ходов с наилучшим ответом. Если длина последовательности равна ${ Displaystyle О (п cdot ln (1 / epsilon))}$ , то социальное благополучие после последовательности не менее ${ displaystyle 1 / 2- epsilon}$ раз оптимальнее. Последний результат верен в гораздо более общем классе игр, называемых служебные игры.^[3]^[4]

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

использованная литература

^ Ветта, А. (2002). «Равновесия по Нэшу в конкурентных обществах с приложениями к расположению объектов, маршрутизации трафика и аукционам». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы. п. 416. Дои:10.1109 / SFCS.2002.1181966. ISBN 0-7695-1822-2.
^ ^а ^б ^c Ева Тардос и Том Векслер, "Network Formation Games". Глава 19 в Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
^ Миррокни, Вахаб С .; Ветта, Адриан (2004). «Проблемы конвергенции в соревновательных играх». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Конспект лекций по информатике. 3122. п. 183. Дои:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.
^ Goemans, M .; Миррокни, В .; Ветта, А. (2005). «Равновесие раковины и конвергенция». 46-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS'05). п. 142. Дои:10.1109 / SFCS.2005.68. ISBN 0-7695-2468-0.

[vetta-1] Ветта, А. (2002). «Равновесия по Нэшу в конкурентных обществах с приложениями к расположению объектов, маршрутизации трафика и аукционам». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы. п. 416. Дои:10.1109 / SFCS.2002.1181966. ISBN 0-7695-1822-2.

[agt-2] а ^б ^c Ева Тардос и Том Векслер, "Network Formation Games". Глава 19 в Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.

[3] Миррокни, Вахаб С .; Ветта, Адриан (2004). «Проблемы конвергенции в соревновательных играх». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы. Конспект лекций по информатике. 3122. п. 183. Дои:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.

[4] Goemans, M .; Миррокни, В .; Ветта, А. (2005). «Равновесие раковины и конвергенция». 46-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS'05). п. 142. Дои:10.1109 / SFCS.2005.68. ISBN 0-7695-2468-0.

[1]

[2]

[3]

[4]