Stochastic game
گیم تھیوری میں، ایک اسٹاکسٹک گیم (یا مارکوف گیم)، جسے لائیڈ شیپلی نے 1950 کی دہائی کے اوائل میں متعارف کرایا تھا، ایک بار بار دہرایا جانے والا کھیل ہے جس میں ایک یا زیادہ کھلاڑی ممکنہ تبدیلیوں کے ساتھ کھیلتے ہیں۔ یہ کھیل کئی مراحل میں کھیلا جاتا ہے۔ ہر مرحلے کے آغاز میں کھیل کسی نہ کسی حالت میں ہوتا ہے۔ کھلاڑی ایکشن کا انتخاب کرتے ہیں اور ہر کھلاڑی کو ایک ادائیگی ملتی ہے جو موجودہ حالت اور منتخب کردہ ایکشن پر منحصر ہوتی ہے۔ اس کے بعد کھیل ایک نئی بے ترتیب حالت میں چلا جاتا ہے جس کی تقسیم پچھلی حالت اور کھلاڑیوں کے منتخب کردہ اقدامات پر منحصر ہوتی ہے۔ یہ طریقہ کار نئی حالت میں دہرایا جاتا ہے اور کھیل محدود یا لامحدود مراحل تک جاری رہتا ہے۔ کسی کھلاڑی کو کل ادائیگی اکثر اسٹیج ادائیگی کی رعایتی رقم یا اسٹیج ادائیگی کی اوسط سے کمتر حد کے طور پر لی جاتی ہے۔ سٹوچسٹک گیمز مارکوف کے فیصلہ سازی کے عمل کو متعدد تعامل کرنے والے فیصلہ سازوں کے ساتھ ساتھ اسٹریٹجک فارم کے کھیلوں کو متحرک حالات میں عام کرتے ہیں جن میں کھلاڑیوں کے انتخاب کے جواب میں ماحول بدلتا ہے۔ دو کھلاڑیوں کے کھیل ہدایت شدہ گراف پر دو کھلاڑیوں کے کھیل بڑے پیمانے پر نامعلوم (مخالف) ماحول میں کام کرنے والے مجرد نظاموں کی ماڈلنگ اور تجزیہ کے لیے استعمال ہوتے ہیں۔ کسی نظام اور اس کے ماحول کی ممکنہ ترتیبات کو عمودی طور پر پیش کیا جاتا ہے، اور منتقلی نظام، اس کے ماحول، یا "فطرت" کے اعمال سے مطابقت رکھتی ہے۔ نظام کا ایک رن پھر گراف میں ایک لامحدود راستے سے مطابقت رکھتا ہے۔ اس طرح، ایک نظام اور اس کے ماحول کو مخالفانہ مقاصد کے ساتھ دو کھلاڑیوں کے طور پر دیکھا جا سکتا ہے، جہاں ایک کھلاڑی (نظام) کا مقصد "اچھے" رنز کے امکان کو زیادہ سے زیادہ کرنا ہے، جبکہ دوسرے کھلاڑی (ماحول) کا مقصد اس کے برعکس ہے۔ بہت سے معاملات میں، اس امکان کی ایک توازن قدر موجود ہے، لیکن دونوں کھلاڑیوں کے لیے زیادہ سے زیادہ حکمت عملی موجود نہیں ہو سکتی ہے۔ ہم اس شعبے میں زیر مطالعہ بنیادی تصورات اور الگورتھمک سوالات متعارف کراتے ہیں، اور ہم کچھ دیرینہ کھلے مسائل کا ذکر کرتے ہیں۔ پھر، ہم منتخب حالیہ نتائج کا ذکر کرتے ہیں۔ سٹاکاسٹک گیم کے اجزاء یہ ہیں: کھلاڑیوں کا ایک محدود مجموعہ ؛ ایک ریاستی جگہ (یا تو ایک محدود سیٹ یا پیمائش کے قابل جگہ) ؛ ہر کھلاڑی کے لیے، ایک ایکشن سیٹ (یا تو ایک محدود سیٹ یا پیمائش کے قابل جگہ) ؛ جہاں سے منتقلی کا امکان ہے، جہاں ایکشن پروفائلز ہیں، جہاں موجودہ حالت اور موجودہ ایکشن پروفائل کو دیکھتے ہوئے اگلی ریاست کا امکان ہے ؛ اور جہاں سے ادائیگی کا فنکشن، جہاں-th کوآرڈینیٹ، کھلاڑی کو ریاست اور ایکشن پروفائل کے فنکشن کے طور پر ادائیگی ہے۔ کھیل کسی ابتدائی حالت میں شروع ہوتا ہے۔ مرحلے پر، کھلاڑی پہلے مشاہدہ کرتے ہیں، پھر بیک وقت اعمال کا انتخاب کرتے ہیں، پھر ایکشن پروفائل کا مشاہدہ کرتے ہیں، اور پھر قدرت امکان کے مطابق انتخاب کرتی ہے۔ اسٹوچسٹک گیم کا ایک کھیل، ادائیگی کے سلسلے کی وضاحت کرتا ہے، جہاں۔ ڈسکاؤنٹ فیکٹر () کے ساتھ رعایتی گیم وہ گیم ہے جس میں کھلاڑی کو ادائیگی ہوتی ہے۔ اسٹیج گیم وہ کھیل ہے جہاں کھلاڑی کو ادائیگی ہوتی ہے۔ بالترتیب، دو افراد کے صفر کے مجموعے والے اسٹوچسٹک گیم کی قدر، جس میں بالترتیب بہت سی ریاستیں اور اعمال موجود ہیں، اور ٹرومین بیولی اور ایلون کوہلبرگ (1976) نے ثابت کیا کہ یہ ایک حد تک یکجا ہوتا ہے جیسا کہ انفینیٹی تک جاتا ہے اور جو اسی حد تک یکجا ہوتا ہے جیسا کہ جاتا ہے۔ "غیر منقطع" کھیل وہ کھیل ہے جہاں کھلاڑی کو ادائیگی اسٹیج ادائیگی کی اوسط کی "حد" ہوتی ہے۔ دو افراد کے صفر کے مجموعے کی قدر کی وضاحت کرنے اور غیر صفر کے مجموعے کی توازن ادائیگی کی وضاحت کرنے میں کچھ احتیاطی تدابیر کی ضرورت ہے۔ دو افراد کے صفر کے مجموعے والے اسٹوچسٹک گیم کی یکساں قدر اس صورت میں موجود ہوتی ہے جب ہر ایک کے لیے ایک مثبت عدد اور کھلاڑی 1 اور کھلاڑی 2 کی حکمت عملی کی جوڑی ایسی ہو کہ ہر ایک کے لیے امکانات کے حوالے سے توقع کی جائے۔ کم از کم اور ہے، اور کھیلوں پر امکانات کے حوالے سے توقع کی وضاحت کی گئی ہے اور زیادہ سے زیادہ ہے۔ جین فرانکوئس مرٹنز اور ابراہم نیمین (1981) نے ثابت کیا کہ ہر دو افراد کے صفر کے مجموعے کے کھیل کی ایک یکساں قدر ہوتی ہے جس میں بہت سی ریاستیں اور اعمال ہوتے ہیں۔ اگر کھلاڑیوں کی ایک محدود تعداد ہے اور ایکشن سیٹ اور اسٹیٹس کا سیٹ محدود ہے، تو مراحل کی ایک محدود تعداد کے ساتھ ایک غیر معمولی کھیل میں ہمیشہ نیش توازن ہوتا ہے۔ لامحدود کئی مراحل والے کھیل کے لیے بھی یہی سچ ہے اگر کل ادائیگی رعایتی رقم ہے۔ نان زیرو سم اسٹوکاسٹک گیم میں یکساں توازن کی ادائیگی ہوتی ہے اگر ہر ایک کے لیے ایک مثبت عدد اور ایک حکمت عملی کا خاکہ ایسا ہو کہ کسی کھلاڑی کے ذریعے ہر یکطرفہ انحراف کے لیے، یعنی سب کے لیے ایک حکمت عملی کا خاکہ، اور کم از کم اس کے ذریعے بیان کردہ کھیلوں کے امکانات کے حوالے سے ہر ایک کی توقع ہو، اور اس کے ذریعے بیان کردہ کھیلوں کے امکانات کے حوالے سے توقع زیادہ سے زیادہ ہو۔ نکولس ویئلے نے دکھایا ہے کہ محدود حالت اور ایکشن خالی جگہوں والے تمام دو افراد کے اسٹاکسٹک گیمز میں یکساں توازن کی ادائیگی ہوتی ہے۔ نان زیرو سم اسٹوکاسٹک گیم میں ایک محدود اوسط توازن کی ادائیگی ہوتی ہے اگر ہر ایک کے لیے ایک حکمت عملی کا خاکہ ایسا ہو کہ کسی کھلاڑی کی طرف سے ہر یکطرفہ انحراف کے لیے، اسٹیج ادائیگی کی اوسط سے کمتر حد کی توقع کم از کم اس کے ذریعے بیان کردہ کھیلوں کے امکانات کے حوالے سے ہوتی ہے، اور اسٹیج ادائیگی کی اوسط سے اعلی حد کی توقع زیادہ سے زیادہ ہوتی ہے۔ جین فرانکوئس مرٹنز اور ابراہم نیمین (1981) یہ ثابت کرتے ہیں کہ محدود طور پر بہت سی ریاستوں اور اعمال کے ساتھ ہر دو افراد کے صفر کے مجموعے والے کھیل کی ایک محدود اوسط قیمت ہوتی ہے، اور نکولس ویئلے نے دکھایا ہے کہ محدود حالت اور ایکشن خالی جگہوں والے تمام دو افراد کے اسٹاکسٹک کھیلوں میں محدود اوسط توازن کی ادائیگی ہوتی ہے۔ خاص طور پر، ان نتائج سے یہ ظاہر ہوتا ہے کہ ان کھیلوں کی ایک قدر اور ایک تخمینہ توازن ادائیگی ہوتی ہے، جسے لمف اوسط (بالترتیب، لمس اپ اوسط) توازن ادائیگی کہا جاتا ہے، جب کل ادائیگی مرحلے کی ادائیگیوں کی اوسط کی حد کمتر (یا حد اعلی) ہوتی ہے۔ کیا محدود طور پر بہت سے کھلاڑیوں، ریاستوں اور اعمال کے ساتھ ہر غیر معمولی کھیل میں یکساں توازن کی ادائیگی ہوتی ہے، یا محدود اوسط توازن کی ادائیگی، یا یہاں تک کہ محدود اوسط توازن کی ادائیگی، ایک چیلنجنگ کھلا سوال ہے۔ مارکوف کامل توازن ذیلی کھیل کامل نیش توازن کے تصور کی سٹوچسٹک گیمز میں اصلاح ہے۔ کھلاڑیوں کی حکمت عملیوں پر غیر یقینی صورتحال کا نمونہ بنانے کے لیے اسٹوچسٹک گیمز کو بایسیئن گیمز کے ساتھ جوڑا گیا ہے۔ نتیجے میں آنے والے سٹوچسٹک بیسیئن گیم ماڈل کو بیسیئن نیش توازن مساوات اور بیلمین اصلاح مساوات کے تکراری امتزاج کے ذریعے حل کیا جاتا ہے۔ اسٹوکاسٹک گیمز کی ایپلی کیشنز معاشیات، ارتقائی حیاتیات اور کمپیوٹر نیٹ ورکس میں ہیں۔ یہ بار بار کھیلے جانے والے کھیلوں کی عمومی شکلیں ہیں جو اس خاص معاملے سے مطابقت رکھتی ہیں جہاں صرف ایک ریاست ہوتی ہے۔ مزید پڑھنا (انڈرگریجویٹ کے لیے موزوں ؛ اہم نتائج، کوئی ثبوت نہیں) بیرونی لنکس لیکچر آن اسٹوچسٹک ٹو پلیئر گیمز بذریعہ انتونین کوسیرا گیم تھیوری گیم کلاسز ریاضیاتی اور مقداری طریقے (معاشیات)