Umístění zařízení (kooperativní hra) - Facility location (cooperative game)

The kooperativní hra o umístění zařízení je kooperativní hra z sdílení nákladů. Cílem je sdílet náklady na otevření nových zařízení mezi klienty těšícími z těchto zařízení.[1]:386Hra 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 míst, kde lze stavět zařízení (např. Elektrárny).
  • 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].
  • Náklady na obsluhu skupiny spotřebitelů jsou nižší než součet nákladů na obsluhu každého spotřebitele samostatně.

PŘÍKLAD:

  • Existují dvě zařízení, F1, která stojí 2 a F2, která stojí 2.
  • Existují tři spotřebitelé, Alice Bob a Carl.
  • Alice může být obsluhována pouze z F1, s cenou 2. Takže náklady na její obsluhu samotné jsou 2 + 2 = 4.
  • Bob může být obsluhován z F1 s cenou 2 nebo z F2 s cenou 1. Takže náklady na jeho obsluhu samotnou jsou 2 + 1 = 3.
  • Carl může být obsluhován pouze z F2, s cenou 1. Takže náklady na obsluhu pouze jemu jsou 2 + 1 = 3.
  • Cena za obsluhu Alice a Boba je 2 + 2 + 2 = 6 (vybudováním pouze F1).
  • Cena za obsluhu Boba a Carla je 2 + 1 + 1 = 4 (vybudováním pouze F2).
  • Cena za obsluhu Alice a Carla je 2 + 2 + 2 + 1 = 7 (stavbou F1 a F2).
  • Cena za obsazení všech agentů je 2 + 2 + 2 + 1 + 1 = 8.

Společensky nejžádanějším výsledkem hry je, že jsou obslouženi všichni agenti. Náklady na tento výsledek (8 ve výše uvedeném příkladu) lze sdílet mezi agenty. Rozdělení nákladů je dobré, pokud se žádná podskupina agentů nemůže odchýlit a získat pro sebe nižší náklady (takové rozdělení nákladů se říká v jádro hry). Ve výše uvedeném příkladu:

  • Vektor nákladů (5,2,1) není v jádru, protože Alice se může odchýlit a získat cenu pouze 4. Podobně vektor (3,3,2) není v jádru, protože Bob a Carl mohou odchýlit se společně a získat celkovou cenu pouze 4.
  • Nákladové vektory (4,2,2) a (4,1,3) jsou v jádru.

Klasický výsledek v teorii her, Bondarevova – Shapleyova věta, dává nezbytné a dostatečné podmínky, aby hra měla neprázdné jádro.

Viz také

Reference

  1. ^ Kamal Jain a Mohammad Mahdian, „sdílení nákladů“. Kapitola 15 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.