Ob'ekt joylashgan joy (kooperativ o'yin) - Facility location (cooperative game)

The kooperativ ta'sis joylashuvi o'yini a kooperativ o'yin ning xarajatlarni taqsimlash. Maqsad - ushbu ob'ektlardan zavq olayotgan mijozlar o'rtasida yangi ob'ektlarni ochish xarajatlarini bo'lishish.[1]:386O'yin quyidagi tarkibiy qismlardan iborat:

  • Muayyan xizmatga muhtoj bo'lgan bir nechta iste'molchilar mavjud, masalan, elektr aloqasi.
  • Ob'ektlarni (masalan, elektr stantsiyalarini) qurish mumkin bo'lgan bir nechta joylar mavjud.
  • Iste'molchilarning har bir jufti (C) va joylashuvi (L) uchun L dan xizmat ko'rsatishda doimiy xarajatlar mavjud (masalan, elektr stantsiyasi va iste'molchilar uyi orasidagi masofaga qarab). Ushbu xarajat [C, L] qiymati bilan belgilanadi.
  • Iste'molchilar guruhiga xizmat ko'rsatish narxi har bir iste'molchiga xizmat ko'rsatish xarajatlari yig'indisidan pastdir.

O'RNAK:

  • Ikkita ob'ekt mavjud, ularning narxi F1 2 va F2 narxi 2 ga teng.
  • Uchta iste'molchi bor, Elis Bob va Karl.
  • Elisga faqat F1 dan xizmat qilish mumkin, narxi 2 ga teng. Shuning uchun unga xizmat ko'rsatish narxi 2 + 2 = 4 ni tashkil qiladi.
  • Bobga F1 dan 2 bahoga yoki F2 dan 1 narx bilan xizmat ko'rsatish mumkin, shuning uchun unga xizmat ko'rsatish narxi 2 + 1 = 3 ni tashkil qiladi.
  • Karlga faqat F2 dan xizmat ko'rsatish mumkin, narxi 1 ga teng. Demak, unga xizmat ko'rsatish narxi 2 + 1 = 3 ni tashkil qiladi.
  • Elis va Bobga xizmat ko'rsatish narxi 2 + 2 + 2 = 6 (faqat F1 qurish orqali).
  • Bob va Karlga xizmat ko'rsatish narxi 2 + 1 + 1 = 4 (faqat F2 qurish orqali).
  • Elis va Karlga xizmat ko'rsatish narxi 2 + 2 + 2 + 1 = 7 (F1 va F2 binolari bilan).
  • Barcha agentlarga xizmat ko'rsatish narxi 2 + 2 + 2 + 1 + 1 = 8.

O'yinning ijtimoiy jihatdan eng kerakli natijasi shundaki, barcha agentlarga xizmat ko'rsatiladi. Ushbu natijaning narxi (yuqoridagi misolda 8 ta) agentlar o'rtasida taqsimlanishi mumkin. Xarajatlarni taqsimlash yaxshi bo'ladi, agar agentlarning biron bir kichik guruhi og'ib keta olmasa va o'zi uchun arzonroq narx olmasa (bunday xarajatlarni taqsimlash yadro o'yin). Yuqoridagi misolda:

  • Xarajat-vektori (5,2,1) yadroda emas, chunki Elis og'ishi va faqat 4 narxini olishi mumkin. Xuddi shunday, Bob (3,3,2) vektori ham yadroda emas, chunki Bob va Karl birgalikda chetga chiqing va umumiy qiymati atigi 4 ga teng bo'lsin.
  • Xarajat vektorlari (4,2,2) va (4,1,3) yadroda.

O'yin nazariyasidagi klassik natija Bondareva - Shapli teoremasi, o'yin bo'sh bo'lmagan yadroga ega bo'lishi uchun zarur va etarli shartlarni beradi.

Shuningdek qarang

Adabiyotlar

  1. ^ Kamol Jayn va Muhammad Mahdiyan, "Xarajatlarni taqsimlash". 15-bob Vazirani, Vijay V.; Nison, Noam; Roughgarden, Tim; Tardos, Eva (2007). Algoritmik o'yin nazariyasi (PDF). Kembrij, Buyuk Britaniya: Kembrij universiteti matbuoti. ISBN  0-521-87282-0.