Markov zanjiri va dinamik dasturlash

1.3 Markov o‘yinlari
Stoxastik o'yinlar tushunchasi dastawal Shepli tomonidan kiritilgan. Stoxastik o‘yin Markov jarayonlari orqali amalga oshiriladi. Bunda o'tish jadvali elementlari o‘yinchilar tomonidan tanlangan yechimlarga bog'liq bodadi.
Obyektning holatlar soni N ta bodsin. Har bir qadamda o‘yin bu N ta holatlarning birortasida bodadi. Agar o'yhi holatda bodib, o'yinchi o‘yinchi yechimni tanlashgan bodsa, u holda o‘yinning holatga o'tish ehtimoli soniga teng bodadi. Bundan o'yinchining yutugd bodadi. o‘yinchi yigdlgan yutuqlarning o‘rtachasini maksimum qiluvchi strategiyani tanlaydi. o'yinchi bu yutuqni minimum qiluvchi strategiyani tanlashga harakat qiladi. Biror holatni tanlab olish hisobiga jadvalli o‘yinni hosil qilamiz. qilib, stoxastik o'yin jadvalli o'yinlar to‘plamidan iborat bo‘lar ekan.
Shepli tomonidan stoxastik o'yinlar uchun, to'xtash tushunchasi kiritilgan bo'lib, bunda har bir uchun:

tengsizlik bajarilishligi talab etiladi. Bunday o'yinlar to‘xtalishli
stoxastik deb ataladi. Shepli tomonidan to'xtalishli o'yinlar uchun, olingan natijalarni keltiramiz.
To'xtalishli stoxastik o'yinlar quyidagi:

ta jadvallar bilan beriladi, bu yerda ning elementlari


shartlarni qanoatlantiradi.
Agar o'yin holatda turgan bo'lsa o'yinchining sof yechimlari lardan, o'yinchiniki lardan iborat bo'ladi. holat uchun, sof yechim juftligini tashkil qiladi.
l-ta’rif. holatda o'yinchining sof yechimlari ustida taqsimlangan to'la ehtimollik aralash yechim deb ataladi.
Demak, aralash yechim ko'rinishda bo'lib:

2-ta’rif. o'yinchining statsionar aralash strategiyasi deb bu yerda ko'rinishdagi voktorga aytiladi.
Xuddi shunga o'xshash tushunchalarni o'yinchiga nisbatan ham kiritish mumkin. Agar bo'lsa sof yechimni beradi. B jadvalli o'yinda val bilan o'yinchining minimaks yutug'ini belgilaymiz. va bilan va o'yinchilarning mos optimal strategiyalari to'plamini belgilaymiz. va lar bir xil o'lchovli jadvallar bo'lishsa:
(3.1)
tengsizlik o'rinli bo'ladi. Stoxastik o'yinda jadvalning elementi

bilan aniqlanadi, bu yerda 1 < к < rtii 1 < I < щ va a = (oti, ce2, ...,а^)т vektor ustun. Ixtiyoriy a :u: boshlang'ich vektor olingan bo'lsin. Uning yordamida o ,") vektorlar ketma-ketligini quyidagicha quramiz: