Stochastic game
खेल सिद्धांत में, एक यादृच्छिक खेल (या मार्कोव खेल), जिसे 1950 के दशक की शुरुआत में लॉयड शेपली द्वारा पेश किया गया था, एक या एक से अधिक खिलाड़ियों द्वारा खेले जाने वाले संभावित परिवर्तनों के साथ एक दोहराए जाने वाला खेल है। खेल कई चरणों में खेला जाता है। प्रत्येक चरण की शुरुआत में खेल किसी न किसी स्थिति में होता है। खिलाड़ी क्रियाओं का चयन करते हैं और प्रत्येक खिलाड़ी को एक भुगतान प्राप्त होता है जो वर्तमान स्थिति और चुने गए कार्यों पर निर्भर करता है। खेल फिर एक नई यादृच्छिक स्थिति में चला जाता है जिसका वितरण पिछले राज्य और खिलाड़ियों द्वारा चुने गए कार्यों पर निर्भर करता है। प्रक्रिया को नए राज्य में दोहराया जाता है और खेल सीमित या अनंत चरणों के लिए जारी रहता है। एक खिलाड़ी को कुल भुगतान को अक्सर चरण भुगतान की रियायती राशि या चरण भुगतान के औसत से कम सीमा के रूप में लिया जाता है। स्टोकेस्टिक खेल कई परस्पर निर्णय निर्माताओं के लिए मार्कोव निर्णय प्रक्रियाओं को सामान्य बनाते हैं, साथ ही साथ रणनीतिक रूप वाले खेलों को गतिशील स्थितियों में बदलते हैं जिसमें खिलाड़ियों की पसंद के जवाब में वातावरण बदल जाता है। दो-खिलाड़ी खेल निर्देशित ग्राफ पर यादृच्छिक दो-खिलाड़ी खेल व्यापक रूप से एक अज्ञात (प्रतिकूल) वातावरण में काम करने वाली असतत प्रणालियों के मॉडलिंग और विश्लेषण के लिए उपयोग किए जाते हैं। एक प्रणाली और उसके पर्यावरण के संभावित विन्यासों को शीर्षों के रूप में दर्शाया जाता है, और संक्रमण प्रणाली, उसके वातावरण या "प्रकृति" की क्रियाओं के अनुरूप होते हैं। सिस्टम का एक रन तब ग्राफ में एक अनंत पथ से मेल खाता है। इस प्रकार, एक प्रणाली और उसके वातावरण को विरोधी उद्देश्यों वाले दो खिलाड़ियों के रूप में देखा जा सकता है, जहां एक खिलाड़ी (प्रणाली) का उद्देश्य "अच्छे" रनों की संभावना को अधिकतम करना है, जबकि दूसरा खिलाड़ी (वातावरण) विपरीत लक्ष्य रखता है। कई मामलों में, इस संभावना का एक संतुलन मूल्य मौजूद है, लेकिन दोनों खिलाड़ियों के लिए इष्टतम रणनीतियाँ मौजूद नहीं हो सकती हैं। हम इस क्षेत्र में अध्ययन की गई बुनियादी अवधारणाओं और एल्गोरिदमिक प्रश्नों का परिचय देते हैं, और हम कुछ लंबे समय से चली आ रही खुली समस्याओं का उल्लेख करते हैं। फिर, हम हाल के चयनित परिणामों का उल्लेख करते हैं। एक यादृच्छिक खेल के घटक हैंः खिलाड़ियों का एक सीमित समूह; एक राज्य स्थान (या तो एक सीमित समूह या एक मापने योग्य स्थान); प्रत्येक खिलाड़ी के लिए, एक कार्रवाई सेट (या तो एक सीमित सेट या एक मापने योग्य स्थान); एक संक्रमण संभावना, जहां से कार्रवाई प्रोफ़ाइल है, जहां संभावना है कि अगली स्थिति वर्तमान स्थिति और वर्तमान कार्रवाई प्रोफ़ाइल को देखते हुए है; और एक भुगतान समारोह से, जहां-th निर्देशांक, स्थिति और कार्रवाई प्रोफ़ाइल के एक कार्य के रूप में खिलाड़ी को भुगतान है। खेल किसी प्रारंभिक अवस्था में शुरू होता है। चरण में, खिलाड़ी पहले अवलोकन करते हैं, फिर एक साथ कार्यों का चयन करते हैं, फिर कार्रवाई प्रोफ़ाइल का निरीक्षण करते हैं, और फिर प्रकृति संभावना के अनुसार चयन करती है। यादृच्छिक खेल का एक खेल, भुगतान की एक धारा को परिभाषित करता है, जहाँ। छूट कारक () के साथ छूट वाला खेल वह खेल है जहाँ खिलाड़ी को भुगतान किया जाता है। स्टेज गेम वह खेल है जहाँ खिलाड़ी को भुगतान किया जाता है। एक दो-व्यक्ति शून्य-राशि यादृच्छिक खेल का मूल्य, क्रमशः, सीमित रूप से कई अवस्थाओं और कार्यों के साथ मौजूद है, और ट्रूमैन बेवले और एलोन कोलबर्ग (1976) ने साबित किया कि एक सीमा तक अभिसरण होता है जैसा कि अनंत तक जाता है और जो उसी सीमा तक अभिसरण करता है जैसा कि जाता है। "अघोषित" खेल वह खेल है जहाँ खिलाड़ी को भुगतान मंच भुगतान के औसत की "सीमा" है। दो-व्यक्ति शून्य-राशि के मूल्य को परिभाषित करने और गैर-शून्य-राशि के संतुलन भुगतान को परिभाषित करने में कुछ सावधानियों की आवश्यकता होती है। दो-व्यक्ति शून्य-राशि यादृच्छिक खेल का समान मूल्य तब मौजूद होता है जब प्रत्येक के लिए एक सकारात्मक पूर्णांक और खिलाड़ी 1 और खिलाड़ी 2 की एक रणनीति जोड़ी ऐसी हो कि प्रत्येक और प्रत्येक के लिए खेल की संभावना के संबंध में कम से कम परिभाषित और है, और द्वारा परिभाषित खेल पर संभावना के संबंध में की अपेक्षा और अधिक से अधिक है। जीन-फ्रैंकोइस मर्टेंस और अब्राहम नेमैन (1981) ने साबित किया कि हर दो-व्यक्ति शून्य-राशि यादृच्छिक खेल का एक समान मूल्य होता है जिसमें सीमित रूप से कई अवस्थाएँ और क्रियाएँ होती हैं। यदि खिलाड़ियों की एक सीमित संख्या है और एक्शन सेट और राज्यों का सेट सीमित है, तो चरणों की एक सीमित संख्या के साथ एक यादृच्छिक खेल में हमेशा एक नैश संतुलन होता है। असीम रूप से कई चरणों वाले खेल के लिए भी यही सच है यदि कुल भुगतान रियायती राशि है। गैर-शून्य-राशि यादृच्छिक खेल में एक समान संतुलन लाभ होता है यदि प्रत्येक के लिए एक सकारात्मक पूर्णांक और एक रणनीति प्रोफ़ाइल होती है जैसे कि एक खिलाड़ी द्वारा प्रत्येक एकतरफा विचलन के लिए, यानी सभी के लिए एक रणनीति प्रोफ़ाइल, और द्वारा परिभाषित खेलों पर संभावना के संबंध में प्रत्येक की अपेक्षा कम से कम है, और द्वारा परिभाषित खेलों पर संभावना के संबंध में अपेक्षा अधिक से अधिक है। निकोलस विएले ने दिखाया है कि सीमित अवस्था और एक्शन स्पेस वाले सभी दो-व्यक्ति यादृच्छिक खेलों में एक समान संतुलन लाभ होता है। गैर-शून्य-राशि यादृच्छिक खेल में एक सीमित-औसत संतुलन भुगतान होता है यदि प्रत्येक के लिए एक रणनीति प्रोफ़ाइल होती है जैसे कि एक खिलाड़ी द्वारा प्रत्येक एकतरफा विचलन के लिए, द्वारा परिभाषित खेलों पर संभावना के संबंध में चरण भुगतान के औसत से कम सीमा की अपेक्षा कम से कम होती है, और द्वारा परिभाषित खेलों पर संभावना के संबंध में चरण भुगतान के औसत से बेहतर सीमा की अपेक्षा अधिक से अधिक होती है। जीन-फ्रांकोइस मर्टेंस और अब्राहम नेमैन (1981) ने साबित किया कि सीमित रूप से कई अवस्थाओं और कार्यों के साथ प्रत्येक दो-व्यक्ति शून्य-राशि यादृच्छिक खेल का एक सीमित-औसत मूल्य होता है, और निकोलस विइले ने दिखाया है कि सीमित स्थिति और कार्रवाई स्थानों के साथ सभी दो-व्यक्ति यादृच्छिक खेलों में एक सीमित-औसत संतुलन लाभ होता है। विशेष रूप से, इन परिणामों से संकेत मिलता है कि इन खेलों का एक मूल्य और एक अनुमानित संतुलन भुगतान होता है, जिसे सीमित-औसत (क्रमशः, सीमित-औसत) संतुलन भुगतान कहा जाता है, जब कुल भुगतान चरण भुगतान के औसत की सीमा से कम (या सीमा से बेहतर) होता है। क्या सीमित रूप से कई खिलाड़ियों, राज्यों और कार्यों के साथ प्रत्येक यादृच्छिक खेल में एक समान संतुलन भुगतान होता है, या एक सीमित-औसत संतुलन भुगतान, या यहां तक कि एक सीमित-औसत संतुलन भुगतान, एक चुनौतीपूर्ण खुला सवाल है। एक मार्कोव परिपूर्ण संतुलन उप-खेल परिपूर्ण नैश संतुलन की अवधारणा का यादृच्छिक खेलों के लिए एक परिष्करण है। खिलाड़ियों की रणनीतियों पर अनिश्चितता का मॉडल बनाने के लिए स्टोकेस्टिक खेलों को बायेसियन खेलों के साथ जोड़ा गया है। परिणामी यादृच्छिक बायेसियन खेल मॉडल को बायेसियन नैश संतुलन समीकरण और बेलमैन इष्टतम समीकरण के पुनरावर्ती संयोजन के माध्यम से हल किया जाता है। अनुप्रयोग स्टोकेस्टिक खेलों के अर्थशास्त्र, विकासवादी जीव विज्ञान और कंप्यूटर नेटवर्क में अनुप्रयोग हैं। वे दोहराए गए खेलों के सामान्यीकरण हैं जो विशेष मामले के अनुरूप हैं जहां केवल एक राज्य है। यह भी देखें यादृच्छिक प्रक्रिया टिप्पणियाँ आगे पढ़ने के लिए (स्नातक के लिए उपयुक्त; मुख्य परिणाम, कोई प्रमाण नहीं) बाहरी लिंक व्याख्यान यादृच्छिक दो-खिलाड़ी खेलों पर एंटोनिन कुसेरा खेल सिद्धांत खेल वर्ग गणितीय और मात्रात्मक विधियाँ (अर्थशास्त्र)