Tesis konumu (ortak oyun) - Facility location (cooperative game)

kooperatif tesis yeri oyunu bir kooperatif oyun nın-nin maliyet paylaşımı. Amaç, yeni tesisler açma maliyetini bu tesislerden yararlanan müşteriler arasında paylaşmaktır.[1]:386Oyun aşağıdaki bileşenlere sahiptir:

  • Elektrik bağlantısı gibi belirli bir hizmete ihtiyaç duyan birkaç tüketici vardır.
  • Tesislerin (örneğin elektrik santralleri) inşa edilebileceği birkaç yer vardır.
  • Her bir tüketici (C) ve konum (L) çifti için, L'den C'ye hizmet etmenin sabit bir maliyeti vardır (örneğin, elektrik santrali ile tüketicinin evi arasındaki mesafeye bağlı olarak). Bu maliyet, Maliyet [C, L] olarak ifade edilir.
  • Bir grup tüketiciye hizmet etmenin maliyeti, her bir tüketiciye tek başına hizmet etmenin maliyetinin toplamından daha düşüktür.

MİSAL:

  • İki tesis vardır, F1 2 ve F2 2'dir.
  • Üç tüketici var, Alice Bob ve Carl.
  • Alice'e yalnızca F1'den servis edilebilir, maliyeti 2'dir. Yani ona tek başına hizmet etmenin maliyeti 2 + 2 = 4'tür.
  • Bob'a 2 ücret karşılığında F1'den veya F2'den 1'e hizmet verilebilir. Yani ona tek başına hizmet etmenin maliyeti 2 + 1 = 3'tür.
  • Carl'a yalnızca F2'den hizmet verilebilir ve maliyeti 1'dir. Yani ona tek başına hizmet etmenin maliyeti 2 + 1 = 3'tür.
  • Alice ve Bob'a hizmet etmenin maliyeti 2 + 2 + 2 = 6'dır (sadece F1'i oluşturarak).
  • Bob ve Carl'a hizmet etmenin maliyeti 2 + 1 + 1 = 4'tür (yalnızca F2 oluşturarak).
  • Alice ve Carl'a hizmet etmenin maliyeti 2 + 2 + 2 + 1 = 7'dir (F1 ve F2'yi oluşturarak).
  • Tüm aracılara hizmet vermenin maliyeti 2 + 2 + 2 + 1 + 1 = 8'dir.

Oyunun sosyal olarak en çok arzu edilen sonucu, tüm ajanlara hizmet verilmesidir. Bu sonucun maliyeti (yukarıdaki örnekte 8) temsilciler arasında paylaşılabilir. Herhangi bir ajan alt grubu sapma gösteremiyorsa ve kendisi için daha düşük bir maliyet elde edemiyorsa, bir maliyet tahsisi iyidir (bu tür bir maliyet tahsisinin, çekirdek oyunun). Yukarıdaki örnekte:

  • Maliyet vektörü (5,2,1) çekirdekte değildir, çünkü Alice sapabilir ve yalnızca 4'lük bir maliyet alabilir. Benzer şekilde, vektör (3,3,2) çekirdekte değildir çünkü Bob ve Carl şunları yapabilir: birlikte sapın ve yalnızca 4'lük bir toplam maliyet elde edin.
  • Maliyet vektörleri (4,2,2) ve (4,1,3) çekirdekte.

Oyun teorisinde klasik bir sonuç olan Bondareva-Shapley teoremi, bir oyunun boş olmayan çekirdeğe sahip olması için gerekli ve yeterli koşulları sağlar.

Ayrıca bakınız

Referanslar

  1. ^ Kamal Jain ve Mohammad Mahdian, "Maliyet Paylaşımı". Bölüm 15 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algoritmik Oyun Teorisi (PDF). Cambridge, İngiltere: Cambridge University Press. ISBN  0-521-87282-0.