Mavzu: ko’p qadamli o’yinlar reja

Fikr-mulohaza o'yinlari
Agentlar va multi-agentlar o'rtasidagi dinamik o'zaro ta'sirni o'rganish maqsadida
traektoriyani rejalashtirish muammolari, ko'p bosqichli o'rganishni cheklash qilona
fikr-mulohaza o'yinlarining kichik sinfiga o'yinlar. Bu sinf to'liq bo'lmasa-da, u Ushbu sohalarda amaliy stsenariylarning ko'pini o'z ichiga oladigan darajada katta. Bundan tashqari, u umumiy ko'p bosqichli o'yinlarda mavjud bo'lmagan ba'zi muhim xususiyatlarni namoyish etadi, va u hisoblash jihatidan ancha qulayroqdir.
De nition 3.26 (Tekshiruv o'yinlari). Ko'p bosqichli o'yin - bu fikr-mulohaza o'yini (qarang 3-rasm) agar
1. hech qanday ma'lumot to'plami bir nechta bosqichlarni o'z ichiga olmaydi
2. har bir bosqichdagi pastki daraxtlar hech qanday ma'lumot to'plami bilan bog'lanmagan" Teskari aloqa o'yinlarining birinchi asosiy xususiyati o'rtasidagi yaqin aloqadir quyidagi natijalar bilan ta'kidlanganidek, xatti-harakatlar strategiyalari va tasodifiy strategiyalar.
teorema. Fikr-mulohaza o'yinida xulq-atvor strategiyasi h a ga mos keladi aralash strategiya h.
Isbot. Biz ekvivalent aralash strategiya hâ elementini element bo'yicha qurishimiz mumkin. Sof strategiyani ko'rib chiqing. Har bir maʼlumot uchun ℐ oʻrnatilgan
ℎ, qilaylik(ℐ h_a ℎ) = h∗ℎ∈h_a h_a ℎ. Keyin elementlar h ekvivalent aralash strategiyaning h lar sifatida belgilanadi.

E'tibor bering, biz randomizatsiyaning mustaqilligidan turli vaqtlarda foydalanganmiz ma'lumotlar to'plami (xulq-atvor strategiyasida) va teskari aloqada
o'yinda siz bir xil ma'lumotlar to'plamiga ikki marta tashrif buyurmaysiz.
teorema (Kun teoremasi). Fikr-mulohaza o'yinida, har qanday aralash strategiya uchun o'yinchi uchun xulq-atvor strategiyasi mavjud har qanday aralash strategiya uchun o'yinchi uchun bo'ling Boshqa o'yinchilar tomonidan o'ynadi.
Daraxtning barglari bo'yicha va shuning uchun natijalar bo'yicha bir xil ehtimollik taqsimotiga ega bo'ling. Kuhn teoremasi aralash strategiyalar xulq-atvor rategiyasi ekanligini aytmasa-da, ikkala sinf barcha maqsadlar uchun (teskari aloqa o'yinlarida) ekvivalentdir. Bu natija, ayniqsa, hisoblash nuqtai nazaridan kuchli: xulq-atvor strategiyalari to'plami aralash strategiyalar to'plamidan ancha kichikroqdir (bunday ikki to'plamning o'lchamiga qarab qarang) va xulq-atvor yechimi bo'lishi mumkin. O'yin daraxtida orqaga iteratsiya orqali topildi, biz keyingi ko'rib chiqamiz.