Umístění zařízení (soutěžní hra) - Facility location (competitive game)

The konkurenční hra o umístění zařízení je druh soutěžní hra ve kterém si poskytovatelé služeb vybírají místa, kam umístí svá zařízení, aby maximalizovali své zisky.^[1]^[2]^:502–506 Hra má následující komponenty:

Existuje několik spotřebitelů, kteří potřebují určitou službu, například připojení k elektřině.
Existuje několik výrobců, kteří mohou poskytovat tuto službu, např. Energetické společnosti.
Každý výrobce může postavit své zařízení (např. Elektrárnu) na jednom z několika míst.
Pro každou dvojici spotřebitelů (C) a umístění (L) platí fixní náklady na obsluhu C z L (např. V závislosti na vzdálenosti mezi elektrárnou a domem spotřebitele). Tato cena se označuje jako náklady [C, L].

Tato hra je a sekvenční hra se třemi kroky:

Každý producent si vybere místo pro umístění svého zařízení.
Každý producent stanovil cenu pro každého uživatele (cenová diskriminace je povoleno, protože za obsluhu různých spotřebitelů se liší náklady).
Každý spotřebitel si vybere zařízení, ke kterému se připojí.

Každý spotřebitel má pro přijetí služby určitou soukromou hodnotu.

Pro každý pár spotřebitelů a výrobců:

Zisk spotřebitele pro připojení k zařízení výrobce je jeho hodnota minus cena;
Zisk výrobce je cena minus náklady na obsluhu spotřebitele;
Sociální blahobyt této dvojice je součtem zisků, tj. Hodnota spotřebitele minus náklady na službu.

Rovnováha

Hru analyzujeme pomocí zpětná indukce.

Krok 3 je jednoduchý: každý spotřebitel si vybere nejlevnější zařízení.

Krok 2 je také docela jednoduchý. Předpokládejme, že producent P má své zařízení v lokalitě L. Cena, kterou si vezme od spotřebitele C, musí být alespoň Cost [C, L]. Předpokládejme, že místa jsou řazena ve vzestupném pořadí podle nákladů, tj. Umístění jsou L1, L2, ... taková, že náklady [C, L1]

Krok 1 - krok umístění zařízení - je náročnější analyzovat (proto je hra pojmenována po tomto kroku). Je možné dokázat, že se jedná o potenciální hra (Potenciálem je celková sociální péče; když do hry vstoupí nový producent, přírůstek sociální péče se přesně rovná zisku producenta).^[2]^:503–504 Proto má tento krok čistou Nashovu rovnováhu a celá hra čistou subgame dokonalá rovnováha.

Kromě toho je každý výsledek maximálního blahobytu také výsledkem maximálního potenciálu, takže to musí být také Nashova rovnováha. To znamená, že cena stability je 1.

Hra o umístění zařízení může mít jiné čisté Nashovy rovnováhy, ve kterých sociální péče není maximální. Je však možné dokázat, že sociální blahobyt v takové rovnováze je nejméně polovina optima. Proto cena anarchie je maximálně 2.^[2]^:505–506

Navíc je možné ukázat, že cena anarchie je nanejvýš 2, i když hra nekonverguje do rovnováhy. Zvažte náhodnou sekvenci pohybů s nejlepší odezvou. Pokud je délka sekvence ${ displaystyle O (n cdot ln (1 / epsilon))}$ , pak je sociální péče po sledu alespoň ${ displaystyle 1 / 2- epsilon}$ krát optimální. Tento druhý výsledek platí v mnohem obecnější třídě her, tzv užitkové hry.^[3]^[4]

Viz také

Reference

^ Vetta, A. (2002). „Nashovy rovnováhy v konkurenčních společnostech s aplikacemi pro umístění zařízení, směrování provozu a aukce“. 43. výroční sympozium IEEE o základech informatiky, 2002. Sborník. p. 416. doi:10.1109 / SFCS.2002.1181966. ISBN 0-7695-1822-2.
^ ^A ^b ^C Eva Tardos a Tom Wexler, „Hry pro vytváření sítí“. Kapitola 19 v Vazirani, Vijay V.; Nisan, Noame; Roughgarden, Tim; Tardos, Éva (2007). Algoritmická teorie her (PDF). Cambridge, Velká Británie: Cambridge University Press. ISBN 0-521-87282-0.
^ Mirrokni, Vahab S .; Vetta, Adrian (2004). "Problémy konvergence v konkurenčních hrách". Aproximace, randomizace a kombinatorická optimalizace. Algoritmy a techniky. Přednášky z informatiky. 3122. p. 183. doi:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.
^ Goemans, M .; Mirrokni, V .; Vetta, A. (2005). „Sink Equilibria and Convergence“. 46. výroční sympozium IEEE o základech informatiky (FOCS'05). p. 142. doi:10.1109 / SFCS.2005.68. ISBN 0-7695-2468-0.

[vetta-1] Vetta, A. (2002). „Nashovy rovnováhy v konkurenčních společnostech s aplikacemi pro umístění zařízení, směrování provozu a aukce“. 43. výroční sympozium IEEE o základech informatiky, 2002. Sborník. p. 416. doi:10.1109 / SFCS.2002.1181966. ISBN 0-7695-1822-2.

[agt-2] A ^b ^C Eva Tardos a Tom Wexler, „Hry pro vytváření sítí“. Kapitola 19 v Vazirani, Vijay V.; Nisan, Noame; Roughgarden, Tim; Tardos, Éva (2007). Algoritmická teorie her (PDF). Cambridge, Velká Británie: Cambridge University Press. ISBN 0-521-87282-0.

[3] Mirrokni, Vahab S .; Vetta, Adrian (2004). "Problémy konvergence v konkurenčních hrách". Aproximace, randomizace a kombinatorická optimalizace. Algoritmy a techniky. Přednášky z informatiky. 3122. p. 183. doi:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.

[4] Goemans, M .; Mirrokni, V .; Vetta, A. (2005). „Sink Equilibria and Convergence“. 46. výroční sympozium IEEE o základech informatiky (FOCS'05). p. 142. doi:10.1109 / SFCS.2005.68. ISBN 0-7695-2468-0.

[1]

[2]

[3]

[4]