Grafik o'yin nazariyasi - Graphical game theory

Yilda o'yin nazariyasi, o'yinni tasvirlashning umumiy usullari quyidagilardir normal shakl va keng shakl. Grafik shakli an muqobil ixcham vakillik ishtirokchilarning o'zaro ta'siridan foydalangan holda o'yin.

Bilan o'yinni ko'rib chiqing ${displaystyle n}$ bilan o'yinchilar ${displaystyle m}$ har birining strategiyasi. Biz o'yinchilarni har bir o'yinchida a bo'lgan grafadagi tugunlar sifatida namoyish etamiz yordamchi funktsiya bu faqat unga va qo'shnilariga bog'liq. Yordamchi dastur boshqa pleyerlarga bog'liq bo'lgani uchun grafik tasvir kichikroq bo'ladi.

Rasmiy ta'rif

Grafik o'yin grafik bilan ifodalanadi ${displaystyle G}$, unda har bir o'yinchi tugun bilan ifodalanadi va ikkita tugun o'rtasida chekka mavjud ${displaystyle i}$ va ${displaystyle j}$ agar ularning kommunal funktsiyalari boshqa o'yinchi tanlagan strategiyaga bog'liq bo'lsa. Har bir tugun ${displaystyle i}$ yilda ${displaystyle G}$ funktsiyaga ega ${displaystyle u_ {i}: {1ldots m} ^ {d_ {i} +1} ightarrow mathbb {R}}$, qayerda ${displaystyle d_ {i}}$ tepalik darajasi ${displaystyle i}$. ${displaystyle u_ {i}}$ pleerning yordam dasturini belgilaydi ${displaystyle i}$ uning strategiyasi, shuningdek qo'shnilarining vazifasi sifatida.

O'yinni namoyish etish hajmi

Umumiy uchun ${displaystyle n}$ har bir o'yinchi bor bo'lgan o'yinchilar ${displaystyle m}$ mumkin bo'lgan strategiyalar, normal shaklni namoyish etish hajmi bo'ladi ${displaystyle O (m ^ {n})}$. Ushbu o'yin uchun grafik tasvir hajmi ${displaystyle O (m ^ {d})}$ qayerda ${displaystyle d}$ grafadagi maksimal tugun darajasi. Agar ${displaystyle dll n}$, keyin grafik o'yin vakili ancha kichikroq.

Misol

Agar har bir o'yinchining foydali funktsiyasi faqat bitta boshqa o'yinchiga bog'liq bo'lsa:

• 

  Ta'riflangan o'yinning grafik shakli

Grafikning maksimal darajasi 1 ga teng va o'yinni quyidagicha ta'riflash mumkin ${displaystyle n}$ o'lchamdagi funktsiyalar (jadvallar) ${displaystyle m ^ {2}}$. Shunday qilib, kirishning umumiy hajmi bo'ladi ${displaystyle nm ^ {2}}$.

Nash muvozanati

O'yinda Nash muvozanatini topish, vakillik hajmida eksponent vaqtni oladi. Agar o'yinning grafik tasviri daraxt bo'lsa, biz polinom vaqtidagi muvozanatni topa olamiz. Umumiy holatda, bu erda tugunning maksimal darajasi 3 yoki undan ortiq bo'lsa, muammo shu erda bo'ladi To'liq emas.

Qo'shimcha o'qish

• Maykl Kearns (2007) "Grafik o'yinlar ". In Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Eva (2007). Algoritmik o'yin nazariyasi (PDF). Kembrij, Buyuk Britaniya: Kembrij universiteti matbuoti. ISBN  0-521-87282-0.
• Maykl Kearns, Maykl L. Littman va Satinder Singx (2001) "O'yin nazariyasi uchun grafik modellar ".