Kooperativ o'yinlar nazariyasi - Cooperative game theory

Yilda o'yin nazariyasi, a kooperativ o'yin (yoki koalitsion o'yin) a o'yin bilan musobaqa guruhlari o'rtasida futbolchilar ("koalitsiyalar") kooperativ xatti-harakatlarini tashqi majburlash imkoniyati tufayli (masalan, orqali shartnoma qonuni ). Ular qarshi kooperativ bo'lmagan o'yinlar unda ittifoq tuzish imkoniyati yo'q yoki barcha kelishuvlar zarur o'zini o'zi bajaradigan (masalan, orqali ishonchli tahdidlar ).^[1]

Kooperativ o'yinlar ko'pincha doirasida tahlil qilinadi kooperativ o'yin nazariyasi, qaysi koalitsiyalar paydo bo'lishini, guruhlarning birgalikdagi harakatlarini va natijada kollektiv to'lovlarni bashorat qilishga qaratilgan. Bu an'anaviyga qarshi kooperativ bo'lmagan o'yin nazariyasi bu alohida o'yinchilarning harakatlari va to'lovlarini bashorat qilish va tahlil qilishga qaratilgan Nash muvozanati.^[2][3]

Kooperativ o'yinlar nazariyasi yuqori darajadagi yondashuvni taqdim etadi, chunki u faqat koalitsiyalarning tuzilishini, strategiyasini va to'lovlarini tavsiflaydi, kooperativ bo'lmagan o'yin nazariyasi ham savdolashish tartib-qoidalari har bir koalitsiya ichidagi to'lovlarni taqsimlashga qanday ta'sir qilishini ko'rib chiqadi. Kooperativ bo'lmagan o'yinlar nazariyasi umumiyroq bo'lganligi sababli, kooperativ o'yinlarni kooperativ bo'lmagan o'yinlar nazariyasi yondashuvi (tahlil qilinmaydi) orqali tahlil qilish mumkin, chunki bu imkoniyat tufayli o'yinchilar uchun mavjud bo'lgan barcha mumkin bo'lgan strategiyalarni qamrab olish uchun etarli taxminlar mavjud. hamkorlikning tashqi majburiyatini ta'minlash. Shunday qilib, barcha o'yinlarni kooperativ bo'lmagan doirada namoyish etish mumkin bo'lsa-da, ko'p hollarda strategik savdolashuv jarayonida o'yinchilar uchun mavjud bo'lgan rasmiy protseduralarni aniq modellashtirish uchun etarli ma'lumot mavjud emas yoki natijada paydo bo'lgan model juda yuqori bo'ladi. haqiqiy dunyoda amaliy vositani taklif qilish uchun murakkablik. Bunday hollarda, kooperativ o'yinlar nazariyasi soddalashtirilgan yondashuvni taqdim etadi, bu savdoning kuchlari to'g'risida hech qanday taxmin qilmasdan, umuman o'yinni tahlil qilishga imkon beradi.

Matematik ta'rif

Kooperativ o'yin har bir koalitsiya uchun qiymatni belgilash orqali beriladi. Rasmiy ravishda koalitsion o'yin cheklangan o'yinchilar to'plamidan iborat ${ displaystyle N}$, deb nomlangan katta koalitsiyava a xarakterli funktsiya ${ displaystyle v: 2 ^ {N} to mathbb {R}}$ ^[4] o'yinchilarning mumkin bo'lgan barcha koalitsiyalar to'plamidan qoniqtiradigan to'lovlar to'plamiga qadar ${ displaystyle v ( emptyset) = 0}$. Funksiya, bir qator o'yinchilar koalitsiya tuzish orqali qancha kollektiv to'lovlarni qo'lga kiritishlarini tavsiflaydi va o'yin ba'zan a deb nomlanadi qiymat o'yini yoki a foyda o'yini.

Aksincha, kooperativ o'yinni xarakterli xarajat funktsiyasi bilan ham aniqlash mumkin ${ displaystyle c: 2 ^ {N} to mathbb {R}}$ qoniqarli ${ displaystyle c ( emptyset) = 0}$. Ushbu parametrda o'yinchilar ba'zi bir vazifalarni va xarakterli funktsiyalarni bajarishlari kerak ${ displaystyle c}$ vazifani birgalikda bajaradigan o'yinchilar to'plamining narxini anglatadi. Bunday o'yin a nomi bilan tanilgan xarajat o'yini. Aksariyat kooperativ o'yinlar nazariyasi foyda o'yinlari bilan bog'liq bo'lsa-da, barcha tushunchalarni xarajatlarni belgilashga osongina o'tkazish mumkin.

Harsanyi dividendlari

The Harsanyi dividendlari (nomi bilan Jon Xarsani, kim uni umumlashtirish uchun ishlatgan Shapli qiymati 1963 yilda^[5]) kooperativ o'yinda o'yinchilar koalitsiyasi tomonidan hosil bo'ladigan ortiqcha narsani aniqlaydi. Ushbu ortiqcha narsani belgilash uchun ushbu koalitsiyaning qiymati subkoalitsiyalar tomonidan yaratilgan ortiqcha tomonidan tuzatiladi. Shu maqsadda dividend ${ displaystyle d_ {v} (S)}$ koalitsiya ${ displaystyle S}$ o'yinda ${ displaystyle v}$ tomonidan rekursiv ravishda aniqlanadi

${ displaystyle { begin {aligned} d_ {v} ( {i }) & = v ( {i }) d_ {v} ( {i, j }) & = v ( {i, j }) - d_ {v} ( {i }) - d_ {v} ( {j }) d_ {v} ( {i, j, k }) & = v ( {i, j, k }) - d_ {v} ( {i, j }) - d_ {v} ( {i, k }) - d_ {x} ( {j, k }) - d_ {v} ( {i }) - d_ {v} ( {j }) - d_ {v} ( {k }) & vdots d_ {v } (S) & = v (S) - sum _ {T subsetneq S} d_ {v} (T) end {hizalanmış}}}$

Dividendning aniq formulasi quyidagicha berilgan ${ textstyle d_ {v} (S) = sum _ {T subseteq S} (- 1) ^ {| S setminus T |} v (T)}$. Funktsiya ${ displaystyle d_ {v}: 2 ^ {N} to mathbb {R}}$ deb ham tanilgan Mobius teskari ning ${ displaystyle v: 2 ^ {N} to mathbb {R}}$.^[6] Darhaqiqat, biz tiklanishimiz mumkin ${ displaystyle v}$ dan ${ displaystyle d_ {v}}$ formula yordamida ${ textstyle v (S) = d_ {v} (S) + sum _ {T subseteq S} d_ {v} (T)}$.

Harsanyi dividendlari ikkala o'yinni va echim tushunchalarini tahlil qilish uchun foydalidir, masalan. The Shapli qiymati har bir koalitsiyaning dividendini uning a'zolari o'rtasida taqsimlash yo'li bilan olinadi, ya'ni Shapli qiymati ${ displaystyle phi _ {i} (v)}$ o'yinchi ${ displaystyle i}$ o'yinda ${ displaystyle v}$ futbolchining unga tegishli bo'lgan barcha koalitsiyalar dividendlaridagi ulushini yig'ish orqali beriladi, ${ textstyle phi _ {i} (v) = sum _ {S subset N: i in S} {d_ {v} (S)} / {| S |}}$.

Ikkilik

Ruxsat bering ${ displaystyle v}$ foyda o'yini bo'ling. The ikkilamchi o'yin ning ${ displaystyle v}$ bu xarajat o'yini ${ displaystyle v ^ {*}}$ sifatida belgilangan

${ displaystyle v ^ {*} (S) = v (N) -v (N setminus S), forall ~ S subseteq N}$

Intuitiv ravishda, ikkilamchi o'yin Tanlov narxi koalitsiya uchun ${ displaystyle S}$ katta koalitsiyaga qo'shilmaslik ${ displaystyle N}$. Ikki tomonlama foyda keltiradigan o'yin ${ displaystyle c ^ {*}}$ xarajatli o'yin uchun bir xil aniqlanishi mumkin ${ displaystyle c}$. Kooperativ o'yin va uning ikkiliklari ma'lum ma'noda tengdir va ular ko'plab xususiyatlarga ega. Masalan, yadro o'yin va uning ikkiliklari tengdir. Kooperativ o'yinlarning ikkilikligi haqida ko'proq ma'lumot olish uchun, masalan (Bilbao 2000 yil ).

Subgames

Ruxsat bering ${ displaystyle S subsetneq N}$ o'yinchilarning bo'sh bo'lmagan koalitsiyasi bo'ling. The subgame ${ displaystyle v_ {S}: 2 ^ {S} to mathbb {R}}$ kuni ${ displaystyle S}$ sifatida tabiiy ravishda belgilanadi

${ displaystyle v_ {S} (T) = v (T), forall ~ T subseteq S.$

Boshqacha qilib aytganda, biz shunchaki tarkibidagi koalitsiyalarga e'tiborimizni cheklaymiz ${ displaystyle S}$. Subgames foydali, chunki ular bizga murojaat qilishimizga imkon beradi echim tushunchalari kichik koalitsiyalar bo'yicha katta koalitsiya uchun belgilangan.

Xarakterlash uchun xususiyatlar

Yuqori qo'shilish

Xarakterli funktsiyalar ko'pincha qabul qilinadi o'ta ilg'or (Ouen 1995 yil, p. 213). Bu shuni anglatadiki, birlashma qiymati ajratish koalitsiyalar koalitsiyalarning alohida qiymatlari yig'indisidan kam emas:

${ displaystyle v (S cup T) geq v (S) + v (T)}$ har doim ${ displaystyle S, T subseteq N}$ qondirmoq ${ displaystyle S cap T = emptyset}$.

Monotonlik

Kattaroq koalitsiyalar ko'proq foyda olishadi:

${ displaystyle S subseteq T Rightarrow v (S) leq v (T)}$.

Bu quyidagidan kelib chiqadi o'ta qo'shilish. ya'ni to'lovlar normallashtirilgan bo'lsa, shuning uchun singleton koalitsiyalari nol qiymatga ega.

Oddiy o'yinlar uchun xususiyatlar

Koalitsion o'yin v ko'rib chiqiladi oddiy agar to'lovlar 1 yoki 0 bo'lsa, ya'ni koalitsiyalar "yutadi" yoki "yo'qotadi".^[7]

Teng ravishda, a oddiy o'yin to'plam sifatida aniqlanishi mumkin V a'zolari bo'lgan koalitsiyalar V deyiladi g'alaba qozonish koalitsiyalar va boshqalar yutqazish Ba'zan oddiy o'yin bo'sh emas yoki u bo'sh to'plamni o'z ichiga olmaydi deb taxmin qilinadi. Biroq, matematikaning boshqa sohalarida oddiy o'yinlar ham deyiladi gipergrafalar yoki Mantiqiy funktsiyalar (mantiqiy funktsiyalar).

• Oddiy o'yin V bu monotonik agar g'olib koalitsiyani o'z ichiga olgan har qanday koalitsiya ham g'alaba qozonsa, ya'ni ${ displaystyle S in W}$ va ${ displaystyle S subseteq T}$ nazarda tutmoq ${ displaystyle T in W}$.
• Oddiy o'yin V bu to'g'ri agar har qanday g'olib koalitsiyaning komplementi (qarama-qarshiligi) yutqazayotgan bo'lsa, ya'ni ${ displaystyle S in W}$ nazarda tutadi ${ displaystyle N setminus S notin W}$.
• Oddiy o'yin V bu kuchli agar biron bir yutqazgan koalitsiyaning to'ldiruvchisi g'olib chiqsa, ya'ni ${ displaystyle S notin W}$ nazarda tutadi ${ displaystyle N setminus S in W}$.
  • Agar oddiy o'yin bo'lsa V to'g'ri va kuchli, agar koalitsiya yutqazgan taqdirda, ya'ni koalitsiya g'alaba qozonadi, ya'ni ${ displaystyle S in W}$ iff ${ displaystyle N setminus S notin W}$. (Agar v to'g'ri va kuchli bo'lgan koalitsion oddiy o'yin, ${ displaystyle v (S) = 1-v (N setminus S)}$ har qanday kishi uchun S.)
• A veto pleyer (vetoer) oddiy o'yinda barcha g'olib koalitsiyalarga tegishli bo'lgan o'yinchi. Veto pleyeri bor deb taxmin qilsak, veto pleyeridan iborat bo'lmagan har qanday koalitsiya yutqazmoqda. Oddiy o'yin V bu zaif (kollegial) agar u veto pleyeriga ega bo'lsa, ya'ni kesishgan bo'lsa ${ displaystyle bigcap W: = bigcap _ {S in W} S}$ barcha g'olib koalitsiyalar bo'sh emas.
  • A diktator oddiy o'yinda veto o'yinchisidir, chunki bu tarkibdagi har qanday koalitsiya g'alaba qozonadi. Diktator mag'lub bo'lgan koalitsiyaga tegishli emas. (Diktator o'yinlari eksperimental iqtisodiyotda bu bilan bog'liq emas.)
• A tashuvchi oddiy o'yin V to'plamdir ${ displaystyle T subseteq N}$ har qanday koalitsiya uchun shunday S, bizda ... bor ${ displaystyle S in W}$ iff ${ displaystyle S cap T in W}$. Oddiy o'yinda tashuvchi bo'lsa, unga tegishli bo'lmagan har qanday o'yinchi e'tiborga olinmaydi. Ba'zan oddiy o'yin deyiladi cheklangan agar u cheklangan tashuvchiga ega bo'lsa (hatto bo'lsa ham) N cheksiz).
• The Nakamura raqami oddiy o'yinning minimal soni g'olib koalitsiyalar bo'sh kesishgan. Nakamura teoremasiga ko'ra, raqam ratsionallik darajasini o'lchaydi; bu birlashma qoidasining aniq belgilangan tanlovni berish darajasining ko'rsatkichidir.

Yuqoridagi aksiomalar orasida bir nechta munosabatlar keng tan olingan, masalan, quyidagilar (masalan, Peleg, 2002, 2.1-bo'lim).^[8]):

• Agar oddiy o'yin kuchsiz bo'lsa, bu to'g'ri.
• Oddiy o'yin kuchli va kuchsiz bo'lsa, faqat diktatorlikdir.

Umuman olganda, to'rtta an'anaviy aksiomalar (monotonlik, muvofiqlik, mustahkamlik va kuchsizlik), yakuniylik va algoritmik hisoblashlar o'rtasidagi munosabatlarni to'liq tekshirish.^[9]qilingan (Kumabe va Mixara, 2011)^[10]), natijalari quyidagi "Oddiy o'yinlarning mavjudligi" jadvalida umumlashtiriladi.

Oddiy o'yinlar uchun turli xil aksiomalar ularga qo'yadigan cheklovlar Nakamura raqami ham keng o'rganilgan.^[12]Xususan, veto pleyerisiz hisoblanadigan oddiy o'yin Nakamura raqamiga 3 dan katta bo'lsa, faqatgina a bo'lsa to'g'ri va kuchli emas o'yin.

Kooperativ bo'lmagan nazariya bilan aloqasi

Ruxsat bering G strategik (kooperativ bo'lmagan) o'yin bo'lishi. Keyinchalik, koalitsiyalar muvofiqlashtirilgan xatti-harakatlarni amalga oshirish qobiliyatiga ega deb taxmin qilsak, bir nechta kooperativ o'yinlar bilan bog'liq G. Ushbu o'yinlar ko'pincha deb nomlanadi G ning vakolatxonalari. Ikkala standart vakolatxonalar:^[13]

• A-effektiv o'yin har bir koalitsiya bilan kuchlarni birlashtirish orqali uning a'zolari "kafolatlashi" mumkin bo'lgan yutuqlar yig'indisini birlashtiradi. "Kafolat berish" deganda, bu qiymat maksimal-min ekanligini bildiradi, masalan. oppozitsiya strategiyasi bo'yicha qabul qilingan minimal qiymatning maksimal qiymati.
• Β samarali o'yin har bir koalitsiya bilan kuchlarni birlashtirish orqali "strategik kafolat" bera oladigan yutuqlar yig'indisini bog'laydi. "Strategik kafolat" deganda, bu qiymat min-max, masalan. oppozitsiya strategiyalariga kiritilgan maksimal qiymatning minimal qiymati.

Qaror tushunchalari

Kooperativ o'yin nazariyasidagi asosiy taxmin bu katta koalitsiya ${ displaystyle N}$ hosil qiladi.^[14] Keyin muammo to'lovni ajratishdir ${ displaystyle v (N)}$ ba'zi bir adolatli tarzda futbolchilar orasida. (Bu taxmin cheklovli emas, chunki o'yinchilar ajralib chiqib, kichik koalitsiyalar tuzgan taqdirda ham, biz har qanday koalitsiya tomonidan aniqlangan pastki o'yinlarga echim tushunchalarini qo'llashimiz mumkin.) A echim tushunchasi bu vektor ${ displaystyle x in mathbb {R} ^ {N}}$ bu har bir o'yinchi uchun ajratishni anglatadi. Tadqiqotchilar turli xil adolat tushunchalariga asoslangan holda turli xil echim tushunchalarini taklif qilishdi. Yechim kontseptsiyasida izlash kerak bo'lgan ba'zi xususiyatlarga quyidagilar kiradi:

• Samaradorlik: To'lov vektori umumiy qiymatni to'liq ajratadi: ${ displaystyle sum _ {i in N} x_ {i} = v (N)}$.
• Shaxsiy ratsionallik: Hech bir o'yinchi o'zi oladiganidan kamini olmaydi: ${ displaystyle x_ {i} geq v ( {i }), forall ~ i in N}$.
• Mavjudlik: har qanday o'yin uchun echim tushunchasi mavjud ${ displaystyle v}$.
• Noyoblik: echim kontseptsiyasi har qanday o'yin uchun o'ziga xosdir ${ displaystyle v}$.
• Marginallik: O'yinchining to'lovi faqatgina ushbu o'yinchining marginal hissasiga bog'liq, ya'ni, agar bu marginal hissalar ikki xil o'yinda bir xil bo'lsa, unda to'lov bir xil bo'ladi: ${ displaystyle v (S cup {i }) = w (S cup {i }), forall ~ S subseteq N setminus {i }}$ shuni anglatadiki ${ displaystyle x_ {i}}$ ichida bir xil ${ displaystyle v}$ va ${ displaystyle w}$.
• Monotonlik: Agar o'yinchining marginal hissasi oshsa, o'yinchining to'lovi oshadi: ${ displaystyle v (S cup {i }) leq w (S cup {i }), forall ~ S subseteq N setminus {i }}$ shuni anglatadiki ${ displaystyle x_ {i}}$ ichida kuchsizroq ${ displaystyle w}$ ga qaraganda ${ displaystyle v}$.
• Hisoblash qulayligi: Qaror kontseptsiyasini samarali hisoblash mumkin (ya'ni, o'yinchilar soniga nisbatan polinom vaqtida) ${ displaystyle | N |}$.)
• Simmetriya: Qaror tushunchasi ${ displaystyle x}$ teng to'lovlarni ajratadi ${ displaystyle x_ {i} = x_ {j}}$ nosimmetrik o'yinchilarga ${ displaystyle i}$, ${ displaystyle j}$. Ikkita o'yinchi ${ displaystyle i}$, ${ displaystyle j}$ bor nosimmetrik agar ${ displaystyle v (S cup {i }) = v (S cup {j }), forall ~ S subseteq N setminus {i, j }}$; ya'ni bitta o'yinchini o'z ichiga olgan har qanday koalitsiyada bitta o'yinchini boshqasiga almashtira olamiz va to'lovni o'zgartirmaymiz.
• Qo'shimcha: Ikkala o'yin yig'indisida o'yinchiga ajratish har bir alohida o'yinda o'yinchiga ajratmalar yig'indisidir. Matematik jihatdan, agar ${ displaystyle v}$ va ${ displaystyle omega}$ o'yinlar, o'yin ${ displaystyle (v + omega)}$ shunchaki har qanday koalitsiyaga ikki individual o'yinda koalitsiya tomonidan olinadigan to'lovlar summasini belgilaydi. Qo'shimcha echim kontseptsiyasi har bir o'yinchiga beriladi ${ displaystyle (v + omega)}$ u oladigan narsalarning yig'indisi ${ displaystyle v}$ va ${ displaystyle omega}$.
• Nol o'yinchilarga nol ajratish: nol pleyerga ajratish nolga teng. A bo'sh o'yinchi ${ displaystyle i}$ qondiradi ${ displaystyle v (S cup {i }) = v (S), forall ~ S subseteq N setminus {i }}$. Iqtisodiy nuqtai nazardan, nolinchi o'yinchining tarkibiga kirmagan har qanday koalitsiya uchun chegara qiymati nolga teng.

Samarali to'lov vektori a deb nomlanadi oldindan taxmin qilishva individual oqilona oldingi imputatsiya an deyiladi obro'-e'tibor. Ko'pgina echim tushunchalari - bu taxminlar.

Barqaror to'plam

O'yinning barqaror to'plami (shuningdek. Nomi bilan ham tanilgan fon Neyman-Morgenstern echimi (fon Neyman va Morgenstern 1944 yil )) ikkitadan ortiq o'yinchi bo'lgan o'yinlar uchun taklif qilingan birinchi echim edi. Ruxsat bering ${ displaystyle v}$ o'yin bo'ling va ruxsat bering ${ displaystyle x}$, ${ displaystyle y}$ ikki bo'ling obro'lar ning ${ displaystyle v}$. Keyin ${ displaystyle x}$ hukmronlik qiladi ${ displaystyle y}$ agar biron bir koalitsiya bo'lsa ${ displaystyle S neq emptyset}$ qondiradi ${ displaystyle x_ {i}> y_ {i}, forall ~ i in S}$ va ${ displaystyle sum _ {i in S} x_ {i} leq v (S)}$. Boshqacha qilib aytganda, futbolchilar ${ displaystyle S}$ to'lovlarni afzal ko'rsating ${ displaystyle x}$ kelganlarga ${ displaystyle y}$va agar ular katta koalitsiyani tark etish bilan tahdid qilishlari mumkin ${ displaystyle y}$ foydalaniladi, chunki ular o'zlari tomonidan olinadigan to'lov, hech bo'lmaganda, ular ajratgan mablag 'kabi katta ${ displaystyle x}$.

A barqaror to'plam to'plamidir obro'lar ikkita xususiyatni qondiradigan:

• Ichki barqarorlik: Barqaror to'plamdagi hech qanday to'lov vektori to'plamdagi boshqa vektor tomonidan ustunlik qilmaydi.
• Tashqi barqarorlik: To'plamdan tashqaridagi barcha to'lov vektorlari to'plamdagi kamida bitta vektor tomonidan boshqariladi.

Fon Neyman va Morgenstern barqaror to'plamni jamiyatdagi maqbul xatti-harakatlarning yig'indisi deb bildilar: Hech kim boshqasidan afzal emas, ammo har bir qabul qilinmaydigan xatti-harakat uchun afzal qilingan alternativa mavjud. Ta'rif juda umumiy bo'lib, kontseptsiyani turli xil o'yin formatlarida ishlatishga imkon beradi.

Xususiyatlari

• Barqaror to'plam mavjud bo'lishi yoki bo'lmasligi mumkin (Lukas 1969 yil ), va agar u mavjud bo'lsa, odatda noyob emas (Lukas 1992 yil ). Barqaror to'plamlarni topish odatda qiyin. Bu va boshqa qiyinchiliklar ko'plab boshqa echim tushunchalarini ishlab chiqishga olib keldi.
• Kooperativ o'yinlarning ijobiy qismi quyidagilardan iborat noyob barqaror to'plamlarga ega yadro (Ouen 1995 yil, p. 240).
• Kooperativ o'yinlarning ijobiy qismi kamsitadigan barqaror to'plamlarga ega ${ displaystyle n-2}$ futbolchilar. Bunday to'plamlarda hech bo'lmaganda ${ displaystyle n-3}$ diskriminatsiya qilingan o'yinchilar chiqarib tashlandi (Ouen 1995 yil, p. 240).

Yadro

Ruxsat bering ${ displaystyle v}$ o'yin bo'l The yadro ning ${ displaystyle v}$ to'lov vektorlari to'plamidir

${ displaystyle C (v) = left {x in mathbb {R} ^ {N}: sum _ {i in N} x_ {i} = v (N); quad sum _ { i in S} x_ {i} geq v (S), forall ~ S subseteq N right }.}$

Bir so'z bilan aytganda, yadro to'plamidir obro'lar unda hech bir koalitsiya o'z a'zolarining to'lovlari yig'indisidan katta qiymatga ega emas. Shu sababli, biron bir koalitsiya katta koalitsiyani tark etishga va undan katta foyda olishga unday olmaydi.

Xususiyatlari

• The yadro o'yin bo'sh bo'lishi mumkin (qarang Bondareva - Shapli teoremasi ). Bo'sh bo'lmagan yadrolari bo'lgan o'yinlar chaqiriladi muvozanatli.
• Agar u bo'sh bo'lmasa, yadroda noyob vektor bo'lishi shart emas.
• The yadro har qanday barqaror to'plamda mavjud va agar yadro barqaror bo'lsa, u noyob barqaror to'plamdir; qarang (Driessen 1988 yil ) dalil uchun.

Afzalliklar bo'yicha oddiy o'yinning asosiy qismi

Oddiy o'yinlar uchun yadroning yana bir tushunchasi mavjud, chunki har bir o'yinchi to'plamda afzalliklarga ega bo'lishi kerak ${ displaystyle X}$ alternativalar profil bu ro'yxat ${ displaystyle p = ( succ _ {i} ^ {p}) _ {i in N}}$ individual imtiyozlar ${ displaystyle succ _ {i} ^ {p}}$ kuni ${ displaystyle X}$.Bu yerda ${ displaystyle x succ _ {i} ^ {p} y}$ bu shaxsni anglatadi ${ displaystyle i}$ alternativani afzal ko'radi ${ displaystyle x}$ga ${ displaystyle y}$ profilda ${ displaystyle p}$.Oddiy o'yin berilgan ${ displaystyle v}$ va profil ${ displaystyle p}$, a ustunlik munosabat ${ displaystyle succ _ {v} ^ {p}}$ aniqlangan ${ displaystyle X}$ tomonidan ${ displaystyle x succ _ {v} ^ {p} y}$ agar va faqat g'olib koalitsiya bo'lsa ${ displaystyle S}$(ya'ni, ${ displaystyle v (S) = 1}$) qoniqarli ${ displaystyle x succ _ {i} ^ {p} y}$ Barcha uchun ${ displaystyle i in S}$.The yadro ${ displaystyle C (v, p)}$ oddiy o'yin ${ displaystyle v}$ profilga nisbatan ${ displaystyle p}$ imtiyozlar - ustunliksiz alternativalar to'plami ${ displaystyle succ _ {v} ^ {p}}$(ning maksimal elementlari to'plami ${ displaystyle X}$ munosabat bilan ${ displaystyle succ _ {v} ^ {p}}$):

${ displaystyle x in C (v, p)}$ agar va yo'q bo'lsa ${ displaystyle y in X}$ shu kabi ${ displaystyle y succ _ {v} ^ {p} x}$.

The Nakamura raqami oddiy o'yin - bu bo'sh kesishgan minimal koalitsiya soni.Nakamura teoremasi yadro ekanligini ta'kidlaydi ${ displaystyle C (v, p)}$ barcha profillar uchun bo'sh emas ${ displaystyle p}$ ning asiklik (muqobil ravishda, o'tish davri) imtiyozlar agar va faqat shunday bo'lsa ${ displaystyle X}$ cheklangan va ning asosiy raqami (elementlar soni) ning ${ displaystyle X}$ ning Nakamura sonidan kam ${ displaystyle v}$.Kumabe va Mixaraning bir variantida asosiy narsa deyilgan ${ displaystyle C (v, p)}$ barcha profillar uchun bo'sh emas ${ displaystyle p}$ a bo'lgan afzalliklar maksimal elementagar va faqat asosiy raqam bo'lsa ${ displaystyle X}$ ning Nakamura sonidan kam ${ displaystyle v}$. (Qarang Nakamura raqami batafsil ma'lumot uchun.)

Kuchli epsilon yadrosi

Chunki yadro bo'sh bo'lishi mumkin, umumlashtirish (Shapley va Shubik 1966 yil ). The kuchli ${ displaystyle varepsilon}$-kor ba'zi raqamlar uchun ${ displaystyle varepsilon in mathbb {R}}$ to'lov vektorlari to'plamidir

${ displaystyle C _ { varepsilon} (v) = left {x in mathbb {R} ^ {N}: sum _ {i in N} x_ {i} = v (N); quad sum _ {i in S} x_ {i} geq v (S) - varepsilon, forall ~ S subseteq N right }.}$

Iqtisodiy jihatdan kuchli ${ displaystyle varepsilon}$-core - bu biron bir koalitsiya katta koalitsiyadan chiqib, o'z jarimasini to'lashi kerak bo'lgan taqdirda, to'lovni yaxshilay olmasligi mumkin bo'lgan dastlabki taxminlar to'plami. ${ displaystyle varepsilon}$ ketish uchun. Yozib oling ${ displaystyle varepsilon}$ salbiy bo'lishi mumkin, bu holda bu katta koalitsiyadan chiqish uchun bonusni anglatadi. Shubhasiz, qat'i nazar yadro bo'sh, kuchli ${ displaystyle varepsilon}$-core qiymati etarlicha katta qiymat uchun bo'sh bo'lmaydi ${ displaystyle varepsilon}$ va etarli darajada kichik (ehtimol salbiy) qiymat uchun bo'sh ${ displaystyle varepsilon}$. Ushbu fikrlash satridan keyin eng kam yadroli, ichida kiritilgan (Maschler, Peleg & Shapley 1979 yil ), barcha bo'sh bo'lmagan kuchli tomonlarning kesishishi ${ displaystyle varepsilon}$-korlar. Bunga kuchli deb qarash mumkin ${ displaystyle varepsilon}$-ning eng kichik qiymati ${ displaystyle varepsilon}$ bu to'plamni bo'sh bo'lmagan qiladi (Bilbao 2000 yil ).

Shapli qiymati

The Shapli qiymati samarali, nosimmetrik va monotonlikni qondiradigan noyob to'lov vektori.^[15] Tomonidan kiritilgan Lloyd Shapli (Shapli 1953 ) samarali, nosimmetrik, qo'shimchalar va qo'pol o'yinchilarga nol to'lovlarni tayinlaydigan noyob to'lov vektori ekanligini ko'rsatdi. A ning Shapley qiymati o'ta ilg'or o'yin individual ravishda oqilona, ​​ammo bu umuman to'g'ri emas. (Driessen 1988 yil )

Yadro

Ruxsat bering ${ displaystyle v: 2 ^ {N} to mathbb {R}}$ o'yin bo'ling va ruxsat bering ${ displaystyle x in mathbb {R} ^ {N}}$ samarali to'lov vektori bo'ling. The maksimal ortiqcha o'yinchi men o'yinchi ustidan j munosabat bilan x bu

${ displaystyle s_ {ij} ^ {v} (x) = max left {v (S) - sum _ {k in S} x_ {k}: S subseteq N setminus {j }, i in S right },}$

maksimal miqdordagi o'yinchi men o'yinchi bilan hamkorlik qilmasdan yutishi mumkin j katta koalitsiyadan chiqish yo'li bilan N to'lov vektori ostida x, boshqa o'yinchilarni deb o'ylayman menChiqish koalitsiyasi o'zlarining to'lovlaridan qoniqishadi x. Maksimal ortiqcha - bu bitta o'yinchining boshqasiga nisbatan savdolashish kuchini o'lchash usuli. The yadro ning ${ displaystyle v}$ ning to'plami obro'lar x bu qondiradi

• ${ displaystyle (s_ {ij} ^ {v} (x) -s_ {ji} ^ {v} (x)) times (x_ {j} -v (j)) leq 0}$va
• ${ displaystyle (s_ {ji} ^ {v} (x) -s_ {ij} ^ {v} (x)) times (x_ {i} -v (i)) leq 0}$

har bir juftlik o'yinchisi uchun men va j. Intuitiv ravishda, o'yinchi men o'yinchiga qaraganda ko'proq savdolashish kuchiga ega j munosabat bilan obro'-e'tibor x agar ${ displaystyle s_ {ij} ^ {v} (x)> s_ {ji} ^ {v} (x)}$, lekin o'yinchi j o'yinchi uchun immunitetga ega menagar tahdidlar bo'lsa ${ displaystyle x_ {j} = v (j)}$, chunki u ushbu to'lovni o'zi olishi mumkin. Yadro tarkibida hammasi bor obro'lar bu erda hech bir o'yinchi boshqasiga nisbatan bu savdolashish kuchiga ega emas. Ushbu echim kontseptsiyasi birinchi marta (Devis va Maschler 1965 yil ).

Nukleus

Ruxsat bering ${ displaystyle v: 2 ^ {N} to mathbb {R}}$ o'yin bo'ling va ruxsat bering ${ displaystyle x in mathbb {R} ^ {N}}$ to'lov vektori bo'ling. The ortiqcha ning ${ displaystyle x}$ koalitsiya uchun ${ displaystyle S subseteq N}$ bu miqdor ${ displaystyle v (S) - sum _ {i in S} x_ {i}}$; ya'ni koalitsiya ishtirokchilarining yutug'i ${ displaystyle S}$ agar ular katta koalitsiyadan chiqsalar, olishlari mumkin ${ displaystyle N}$ to'lov ostida ${ displaystyle x}$ va buning o'rniga to'lovni oling ${ displaystyle v (S)}$.

Endi ruxsat bering ${ displaystyle theta (x) in mathbb {R} ^ {2 ^ {N}}}$ haddan oshish vektori bo'ling ${ displaystyle x}$, ortib bormaydigan tartibda joylashtirilgan. Boshqa so'zlar bilan aytganda, ${ displaystyle theta _ {i} (x) geq theta _ {j} (x), forall ~ i$. E'tibor bering ${ displaystyle x}$ ichida yadro ning ${ displaystyle v}$ agar va faqat bu oldindan taxmin qilish bo'lsa va ${ displaystyle theta _ {1} (x) leq 0}$. Nukleolni aniqlash uchun biz vektorlarning leksikografik tartibini ko'rib chiqamiz ${ displaystyle mathbb {R} ^ {2 ^ {N}}}$: Ikkita to'lov vektori uchun ${ displaystyle x, y}$, deymiz ${ displaystyle theta (x)}$ leksikografik jihatdan kichikroq ${ displaystyle theta (y)}$ agar biron bir indeks uchun bo'lsa ${ displaystyle k}$, bizda ... bor ${ displaystyle theta _ {i} (x) = theta _ {i} (y), forall ~ i$ va ${ displaystyle theta _ {k} (x) < theta _ {k} (y)}$. (Buyurtma lug'at tarkibidagi so'zlarni tartibga solish uchun ishlatiladigan alfavit tartibini taqlid qilgani uchun leksikografik deb nomlanadi.) nukleus ning ${ displaystyle v}$ leksikografik jihatdan minimaldir obro'-e'tibor, ushbu buyurtma asosida. Ushbu echim kontseptsiyasi birinchi marta (Shmeyder 1969 yil ).

Nukleolning ta'rifi mavhum bo'lib ko'rinsa ham, (Maschler, Peleg & Shapley 1979 yil ) yanada intuitiv tavsif berdi: eng kichik yadrodan boshlab, tenglamaning o'ng tomoni ta'rifidagi koalitsiyalarni yozing ${ displaystyle C _ { varepsilon} (v)}$ to'plamni bo'sh qilmasdan, uni yanada kamaytirish mumkin emas. Qolgan koalitsiyalar uchun o'ng tomonni kamaytirishni davom eting, toki to'plamni bo'sh qoldirmasdan uni kamaytirolmaysiz. Tengsizliklar teng bo'lgan yangi koalitsiyalar to'plamini yozing; qolgan koalitsiyalarning o'ng tomonini kamaytirishni davom eting va barcha koalitsiyalar ro'yxatga olinmaguncha bu jarayonni kerakli darajada takrorlang. Natijada to'lov vektori yadrodir.

Xususiyatlari

• Ta'rifda aniq aytilmagan bo'lsa ham, yadro har doim o'ziga xosdir. (Qarang: II.7 bo'limigaDriessen 1988 yil ) dalil uchun.)
• Agar yadro bo'sh bo'lmasa, yadro yadroda bo'ladi.
• Nukleus har doim yadroda bo'ladi va yadro savdolashuvlar to'plamida bo'lgani uchun, u har doim savdolashuvlar to'plamida bo'ladi (qarang (Driessen 1988 yil ) tafsilotlar uchun.)

Qavariq kooperativ o'yinlar

Tomonidan kiritilgan Shapli ichida (Shapli 1971 yil ), qavariq kooperativ o'yinlar intuitiv xususiyatni egallaydi, ba'zi o'yinlarda "qor to'plari" mavjud. Xususan, o'yin qavariq uning xarakterli funktsiyasi bo'lsa ${ displaystyle v}$ bu super modulli:

${ displaystyle v (S cup T) + v (S cap T) geq v (S) + v (T), forall ~ S, T subseteq N.)$

Uni ko'rsatish mumkin (qarang, masalan, V.1 bo'limiga (Driessen 1988 yil )) bu supermodularlik ning ${ displaystyle v}$ ga teng

${ displaystyle v (S cup {i }) - v (S) leq v (T cup {i }) - v (T), forall ~ S subseteq T subseteq N setminus {i }, forall ~ i in N;}$

ya'ni "koalitsiya tarkibiga kirishni rag'batlantirish koalitsiya o'sishi bilan ortadi" (Shapli 1971 yil ), yuqorida aytib o'tilgan qor to'pi effektiga olib keladi. Xarajat o'yinlari uchun tengsizliklar bekor qilinadi, shuning uchun biz xarajatlar o'yini deymiz qavariq agar xarakterli funktsiya bo'lsa submodular.

Xususiyatlari

Qavariq kooperativ o'yinlar ko'plab yaxshi xususiyatlarga ega:

• Supermodularlik ahamiyatsiz degani o'ta qo'shilish.
• Qavariq o'yinlar to'liq muvozanatli: The yadro qavariq o'yinning o'yini bo'sh emas va qavariq o'yinning har qanday pastki o'yini qavariq bo'lgani uchun yadro har qanday subgame ham bo'sh emas.
• Qavariq o'yin o'ziga xos bo'lgan barqaror turkumga ega yadro.
• The Shapli qiymati qavariq o'yin - uning og'irlik markazi yadro.
• An haddan tashqari nuqta ning (vertex) ning yadro yordamida polinom vaqtida topish mumkin ochko'zlik algoritmi: Ruxsat bering ${ displaystyle pi: N dan N} gacha$ bo'lishi a almashtirish futbolchilarning va ruxsat bering ${ displaystyle S_ {i} = {j in N: pi (j) leq i }}$ buyurtma qilingan o'yinchilar to'plami bo'ling ${ displaystyle 1}$ orqali ${ displaystyle i}$ yilda ${ displaystyle pi}$, har qanday kishi uchun ${ displaystyle i = 0, ldots, n}$, bilan ${ displaystyle S_ {0} = emptyset}$. Keyin to'lov ${ displaystyle x in mathbb {R} ^ {N}}$ tomonidan belgilanadi ${ displaystyle x_ {i} = v (S _ { pi (i)}) - v (S _ { pi (i) -1}), forall ~ i in N}$ ning tepasi yadro ning ${ displaystyle v}$. Ning har qanday tepasi yadro mosini tanlab shu tarzda qurilishi mumkin almashtirish ${ displaystyle pi}$.

Kombinatorial optimallashtirish bilan o'xshashlik va farqlar

Submodular va super modulli o'rnatilgan funktsiyalar ham o'rganiladi kombinatorial optimallashtirish. Ko'p natijalar (Shapli 1971 yil ) ning o'xshashlari bor (Edmonds 1970 yil ), qaerda submodular funktsiyalari birinchi bo'lib umumlashma sifatida taqdim etildi matroidlar. Shu nuqtai nazardan, yadro Qavariq xarajat o'yinining nomi asosiy ko'pburchak, chunki uning elementlari .ning asosiy xususiyatlarini umumlashtiradi matroidlar.

Biroq, optimallashtirish jamiyati odatda ko'rib chiqadi submodular qavariq funktsiyalarning diskret analoglari bo'lgan funktsiyalar (Lovash 1983 yil ), chunki ikkala turdagi funktsiyalarni minimallashtirish hisoblash yo'li bilan amalga oshiriladi. Afsuski, bu to'g'ridan-to'g'ri zid keladi Shapliningniki ning asl ta'rifi super modulli "konveks" vazifasini bajaradi.

Shuningdek qarang

• Konsensus bo'yicha qaror qabul qilish
• Muvofiqlashtiruvchi o'yin
• Uy ichidagi savdo-sotiq
• Hedonik o'yin
• Lineer ishlab chiqarish o'yini

Adabiyotlar

Qo'shimcha o'qish

• Bilbao, Jezus Mario (2000), Kombinator tuzilmalar bo'yicha kooperativ o'yinlar, Kluwer Academic Publishers, ISBN  9781461543930

• Devis, M.; Masler, M. (1965), "Kooperativ o'yin yadrosi", Har chorakda dengiz tadqiqotlari logistikasi, 12 (3): 223–259, doi:10.1002 / nav.3800120303

• Driessen, Teo (1988), Kooperativ o'yinlar, echimlar va dasturlar, Kluwer Academic Publishers, ISBN  9789401577878

• Edmonds, Jek (1970), "Submodular funktsiyalar, matroidlar va ma'lum ko'p qirrali narsalar", Gayda, R.; Xanani, X .; Zauer, N .; Shonxaym, J. (tahr.), Kombinatoriya tuzilmalari va ularning qo'llanilishi, Nyu-York: Gordon va buzilish, 69-87 betlar

• Lovash, Laslo (1983), "Submodular funktsiyalar va konveksiya", Bachemda, A.; Grotschel, M.; Korte, B. (tahr.), Matematik dasturlash - San'at holati, Berlin: Springer, 235–257 betlar

• Leyton-Braun, Kevin; Shoham, Yoav (2008), O'yin nazariyasining asoslari: qisqa, ko'p tarmoqli kirish, San Rafael, Kaliforniya: Morgan & Claypool Publishers, ISBN  978-1-59829-593-1. 88 betlik matematik kirish; 8-bobga qarang. Bepul onlayn(obuna kerak) ko'plab universitetlarda.

• Lukas, Uilyam F. (1969), "O'yinning echimi bo'lmasligi mumkinligi isboti", Amerika Matematik Jamiyatining operatsiyalari, 136: 219–229, doi:10.2307/1994798, JSTOR  1994798.

• Lukas, Uilyam F. (1992), "Fon Neyman-Morgensternning barqaror to'plamlari", yilda Aumann, Robert J.; Xart, Sergiu (tahr.), O'yin nazariyasi bo'yicha qo'llanma, I tom, Amsterdam: Elsevier, 543-590 betlar

• Lyus, R.D. va Raiffa, H. (1957) O'yinlar va qarorlar: kirish va tanqidiy so'rov, Wiley & Sons. (8-bobga qarang).
• Masler, M.; Peleg, B .; Shapli, Lloyd S. (1979), "Yadroning geometrik xususiyatlari, yadrosi va unga bog'liq echim tushunchalari", Amaliyot tadqiqotlari matematikasi, 4 (4): 303–338, doi:10.1287 / moor.4.4.303

• Osborne, MJ va Rubinshteyn, A. (1994) O'yin nazariyasi kursi, MIT Press (13,14,15-boblarga qarang)
• Moulin, Xerv (1988), Kooperativ qarorlar qabul qilish aksiomalari (1-nashr), Kembrij: Kembrij universiteti matbuoti, ISBN  978-0-521-42458-5

• Ouen, Gilyermo (1995), O'yin nazariyasi (3-nashr), San-Diego: Akademik matbuot, ISBN  978-0-12-531151-9

• Shmeydler, D. (1969), "Xarakterli funktsiya o'yinining yadrosi", Amaliy matematika bo'yicha SIAM jurnali, 17 (6): 1163–1170, doi:10.1137/0117107.

• Shapli, Lloyd S. (1953), "uchun qiymat ${ displaystyle n}$- odam o'yinlari ", Künda, X.; Taker, A.W. (tahr.), II o'yinlar nazariyasiga qo'shgan hissalari, Princeton, Nyu-Jersi: Princeton University Press, 307-317 betlar

• Shapli, Lloyd S. (1971), "Qavariq o'yinlarning tomirlari", Xalqaro o'yin nazariyasi jurnali, 1 (1): 11–26, doi:10.1007 / BF01753431, S2CID  123385556

• Shapli, Lloyd S.; Shubik, M. (1966), "Konveks bo'lmagan imtiyozlarga ega bo'lgan pul iqtisodiyotidagi kvazi yadrolar", Ekonometrika, 34 (4): 805–827, doi:10.2307/1910101, JSTOR  1910101

• Shoham, Yoav; Leyton-Braun, Kevin (2009), Multiagentli tizimlar: algoritmik, o'yin nazariy va mantiqiy asoslar, Nyu York: Kembrij universiteti matbuoti, ISBN  978-0-521-89943-7. Hisoblash nuqtai nazaridan keng qamrovli ma'lumotnoma; 12-bobga qarang. Bepul onlayn yuklab olish.

• fon Neyman, Jon; Morgenstern, Oskar (1944), "O'yinlar nazariyasi va iqtisodiy xulq", Tabiat, Prinston: Prinston universiteti matbuoti, 157 (3981): 172, Bibcode:1946 yil natur.157..172R, doi:10.1038 / 157172a0, S2CID  29754824

• Yeung, Devid U.K. va Leon A. Petrosyan. Kooperativ stoxastik differentsial o'yinlar (Springer Series in Operations Research and Financial Engineering), Springer, 2006. Softcover-ISBN  978-1441920942.
• Yeung, Devid U.K. va Leon A. Petrosyan. Subgame izchil iqtisodiy optimallashtirish: rivojlangan kooperativ dinamik o'yin tahlili (statik va dinamik o'yin nazariyasi: asoslar va qo'llanmalar), Birkhäuser Boston; 2012 yil. ISBN  978-0817682613

Tashqi havolalar

• "Kooperativ o'yin", Matematika entsiklopediyasi, EMS Press, 2001 [1994]