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

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

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

Игра представляет собой последовательную игру , состоящую из трех этапов:

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

Каждый потребитель имеет определенную частную ценность для принятия услуги.

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

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

Равновесие

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

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

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

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

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

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

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

См. также

Ссылки

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

[1]

[2]

[3]

[4]