समाधान अवधारणा

गेम सिद्धांत में चयनित संतुलन परिशोधन। तीर परिशोधन से अधिक सामान्य अवधारणा (अथार्त , ईएसएस) की ओर इशारा करते हैं $\subset$ उचित)।

गेम सिद्धांत में, समाधान अवधारणा यह अनुमान लगाने के लिए एक औपचारिक नियम है कि गेम कैसे खेला जाएगा। इन भविष्यवाणियों को "समाधान" कहा जाता है, और यह वर्णन करता है कि खिलाड़ियों द्वारा कौन सी रणनीतियाँ अपनाई जाएंगी और इसलिए, गेम का परिणाम क्या होगा। सबसे अधिक उपयोग की जाने वाली समाधान अवधारणाएँ संतुलन अवधारणाएँ हैं जिनमें सबसे प्रसिद्ध नैश संतुलन है।

कई खेलों के लिए कई समाधान अवधारणाओं का परिणाम एक से अधिक समाधान होगा। यह समाधानों में से किसी एक को संदेह में डाल देता है, इसलिए एक गेम सिद्धांतकार समाधानों को सीमित करने के लिए परिशोधन प्रयुक्त कर सकता है। निम्नलिखित में प्रस्तुत प्रत्येक क्रमिक समाधान अवधारणा समृद्ध खेलों में अकल्पनीय संतुलन को समाप्त करके अपने पूर्ववर्ती में सुधार करती है।

औपचारिक परिभाषा

मान लीजिए $\Gamma$ सभी गेम का वर्ग है और, प्रत्येक गेम $G\in \Gamma$ के लिए, मान लीजिए $S_{G}$, $G$ की रणनीति प्रोफाइल का सेट है। एक समाधान अवधारणा प्रत्यक्ष उत्पाद $\Pi _{G\in \Gamma }2^{S_{G}};$ का एक तत्व है; अथार्त एक कार्य $F:\Gamma \rightarrow \bigcup \nolimits _{G\in \Gamma }2^{S_{G}}$ ऐसा कि सभी $F(G)\subseteq S_{G}$ के लिए $G\in \Gamma .$ है ।

तर्कसंगतता और पुनरावृत्त प्रभुत्व

Main article: युक्तिसंगतता

इस समाधान अवधारणा में, खिलाड़ियों को तर्कसंगत माना जाता है और इसलिए प्रभुत्व (गेम सिद्धांत) या वर्चस्व वाली रणनीतियों को उन रणनीतियों के सेट से हटा दिया जाता है जिन्हें संभवतः खेला जा सकता है। एक रणनीति तब प्रभुत्व वाली रणनीति होती है जब खिलाड़ी के लिए कोई अन्य रणनीति उपलब्ध होती है जिसका लाभ सदैव अधिक होता है, तथापि अन्य खिलाड़ी कोई भी रणनीति चुनें। (अल्पमहिष्ठ गेम-ट्री खोज में सख्ती से प्रभावित रणनीतियां भी महत्वपूर्ण हैं।) उदाहरण के लिए, (एकल अवधि) कैदी की दुविधा में कैदियों की दुविधा (नीचे दिखाया गया है), दोनों खिलाड़ियों के लिए सहयोग पर दोष का सख्ती से प्रभुत्व है क्योंकि दोष की परवाह किए बिना कोई भी खिलाड़ी सदैव उत्तम होता है। उसका प्रतिद्वंद्वी क्या करता है.

	प्रिजनर 2 को-ओपरेट	प्रिजनर 2 डिफेक्ट
प्रिजनर 1 को-ओपरेट	−0.5, −0.5	−10, 0
प्रिजनर 1 डिफेक्ट	0, −10	−2, −2

नैश संतुलन

Main article: नैश संतुलन

नैश संतुलन एक रणनीति प्रोफ़ाइल है (एक रणनीति प्रोफ़ाइल प्रत्येक खिलाड़ी के लिए एक रणनीति निर्दिष्ट करती है, उदाहरण के लिए उपरोक्त कैदियों के दुविधा गेम में (सहयोग करें, दोष) निर्दिष्ट करता है कि कैदी 1 सहयोग खेलता है और कैदी 2 दोष खेलता है) जिसमें प्रत्येक रणनीति सर्वोत्तम होती है खेली गई हर दूसरी रणनीति का उत्तर में एक खिलाड़ी द्वारा बनाई गई रणनीति किसी अन्य खिलाड़ी की रणनीति के लिए सबसे अच्छी प्रतिक्रिया होती है यदि ऐसी कोई अन्य रणनीति नहीं है जिसे खेला जा सके जो कि किसी भी स्थिति में जिसमें दूसरे खिलाड़ी की रणनीति खेली जाती है, उच्च भुगतान प्राप्त करता है।

बैकवर्ड इंडक्शन

Main article: पिछड़ा प्रेरण

कुछ खेलों में, कई नैश संतुलन होते हैं, किंतु उनमें से सभी यथार्थवादी नहीं होते हैं। गतिशील खेलों में, अवास्तविक नैश संतुलन को खत्म करने के लिए बैकवर्ड इंडक्शन का उपयोग किया जा सकता है। बैकवर्ड इंडक्शन मानता है कि खिलाड़ी तर्कसंगत हैं और अपनी भविष्य की अपेक्षाओं के आधार पर सर्वोत्तम निर्णय लेते है। जो की यह गैर-विश्वसनीय खतरों को समाप्त कर देता है, जो ऐसी धमकियाँ हैं जिन्हें एक खिलाड़ी तब पूरा नहीं करेगा जब उन्हें ऐसा करने के लिए कभी भी बुलाया जाएगा।

उदाहरण के लिए, एक उपस्थित फर्म और उद्योग में संभावित प्रवेशकर्ता के साथ एक गतिशील गेम पर विचार करें। पदधारी का एकाधिकार है और वह अपनी बाजार साझेदारी बनाए रखना चाहता है। यदि प्रवेशकर्ता प्रवेश करता है, तो पदधारी या तो प्रवेशकर्ता से लड़ सकता है या उसे समायोजित कर सकता है। यदि पदधारी समायोजित करता है, तो प्रवेशकर्ता प्रवेश करेगा और लाभ प्राप्त करता है। यदि सत्ताधारी लड़ता है, तो वह अपनी मूल्य कम कर देगा, प्रवेशकर्ता को व्यवसाय से बाहर कर देता है (बाहर निकलने की निवेश वहन करेगा) और अपने स्वयं के लाभ को हानि पहुंचाएगा।

यदि प्रवेशकर्ता प्रवेश करता है तो पदधारी के लिए सबसे अच्छी प्रतिक्रिया प्रवेश करना है, और यदि प्रवेशकर्ता समायोजित करता है तो प्रवेशकर्ता के लिए सर्वोत्तम प्रतिक्रिया प्रवेश करना है। इसका परिणाम नैश संतुलन में होता है। चूँकि यदि पदधारी लड़ने का विकल्प चुनता है, तो प्रवेशकर्ता के लिए सबसे अच्छी प्रतिक्रिया प्रवेश न करना है। यदि प्रवेशकर्ता प्रवेश नहीं करता है, तो इससे कोई प्रभाव नहीं पड़ता कि पदधारी क्या करना चाहता है। इसलिए, यदि प्रवेशकर्ता प्रवेश नहीं करता है तो लड़ाई को पदधारी के लिए सर्वोत्तम प्रतिक्रिया माना जा सकता है, जिसके परिणामस्वरूप एक और नैश संतुलन उत्पन्न होता है।

चूँकि इस दूसरे नैश संतुलन को बैकवर्ड इंडक्शन द्वारा समाप्त किया जा सकता है क्योंकि यह उपस्थित व्यक्ति के गैर-विश्वसनीय खतरे पर निर्भर करता है। जब तक पदधारी निर्णय बिंदु तक पहुंचता है जहां वह लड़ना चुन सकता है, ऐसा करना अतार्किक होगा क्योंकि प्रवेशकर्ता पहले ही प्रवेश कर चुका है। इसलिए, बैकवर्ड इंडक्शन इस अवास्तविक नैश संतुलन को समाप्त कर देता है।

यह सभी देखें:

• मौद्रिक नीति या मौद्रिक नीति सिद्धांत
• स्टैकेलबर्ग प्रतियोगिता

उपगेम परफेक्ट नैश संतुलन

Main article: उपखेल पूर्ण संतुलन

बैकवर्ड इंडक्शन का सामान्यीकरण उपगेम पूर्णता है। बैकवर्ड इंडक्शन मानता है कि भविष्य के सभी गेम तर्कसंगत होंगे। उपगेम परफेक्ट इक्विलिब्रिया में प्रत्येक उपगेम में खेलना तर्कसंगत है (विशेष रूप से नैश इक्विलिब्रियम) बैकवर्ड इंडक्शन का उपयोग केवल निश्चित लंबाई के गेम को समाप्त करने में किया जा सकता है और इसे अपूर्ण जानकारी वाले गेम पर प्रयुक्त नहीं किया जा सकता है। इन स्थिति में उपगेम पूर्णता का उपयोग किया जा सकता है। ऊपर वर्णित समाप्त नैश संतुलन उपगेम अपूर्ण है क्योंकि यह उपगेम का नैश संतुलन नहीं है जो प्रवेशकर्ता के प्रवेश करने के बाद नोड पर प्रारंभ होता है।

परफेक्ट बायेसियन संतुलन

Main article: बायेसियन गेम

कभी-कभी उपगेम पूर्णता अनुचित परिणामों पर पर्याप्त बड़ा प्रतिबंध नहीं लगाती है। उदाहरण के लिए चूंकि उपगेम सूचना सेट (गेम सिद्धांत) को नहीं तोड़ सकते है जो की अपूर्ण जानकारी वाले गेम में केवल एक ही उपगेम हो सकता है - स्वयं - और इसलिए किसी भी नैश संतुलन को खत्म करने के लिए उपगेम पूर्णता का उपयोग नहीं किया जा सकता है। एक पूर्ण बायेसियन संतुलन (पीबीई) खिलाड़ियों की रणनीतियों और विश्वासों का एक विनिर्देश है जिसके बारे में जानकारी सेट में कौन सा नोड गेम खेलने से पहुंचा है। निर्णय नोड के बारे में एक धारणा यह संभावना है कि एक विशेष खिलाड़ी सोचता है कि नोड गेम में है या होगा (संतुलन पथ पर)। विशेष रूप से पीबीई का अंतर्ज्ञान यह है कि यह खिलाड़ी की रणनीतियों को निर्दिष्ट करता है जो कि खिलाड़ी की मान्यताओं को देखते हुए तर्कसंगत हैं और जो मान्यताएं इसे निर्दिष्ट करती हैं वे इसके द्वारा निर्दिष्ट रणनीतियों के अनुरूप हैं।

बायेसियन गेम में एक रणनीति यह निर्धारित करती है कि एक खिलाड़ी उस खिलाड़ी द्वारा नियंत्रित प्रत्येक सूचना सेट पर क्या खेलता है। आवश्यकता यह है जो कि विश्वास रणनीतियों के अनुरूप होते है और यह उपगेम पूर्णता द्वारा निर्दिष्ट नहीं है। इसलिए, पीबीई खिलाड़ियों के विश्वास पर एक स्थिरता की स्थिति है। जिस प्रकार नैश संतुलन में किसी भी खिलाड़ी की रणनीति पर सख्ती से प्रभावित नहीं होती है, उसी के अनुसार पीबीई में, किसी भी सूचना सेट के लिए उस सूचना सेट से प्रारंभ करके किसी भी खिलाड़ी की रणनीति पर सख्ती से प्रभावित नहीं होती है। अर्थात् प्रत्येक विश्वास के लिए कि खिलाड़ी उस सूचना सेट पर बना रह सकता है, ऐसी कोई रणनीति नहीं है जो उस खिलाड़ी के लिए अधिक अपेक्षित भुगतान प्रदान करती हो। उपरोक्त समाधान अवधारणाओं के विपरीत किसी भी खिलाड़ी की रणनीति किसी भी सूचना सेट पर सख्ती से प्रभावित नहीं होती है, तथापि वह संतुलन पथ से दूर होता है। इस प्रकार पीबीई में, खिलाड़ी उन रणनीतियों को खेलने की धमकी नहीं दे सकते हैं जो संतुलन पथ से निर्धारित किसी भी जानकारी पर सख्ती से प्रभावित हैं।

इस समाधान अवधारणा के नाम में बायेसियन इस तथ्य की ओर संकेत करता है कि खिलाड़ी बेयस प्रमेय के अनुसार अपनी मान्यताओं को अद्यतन करते हैं। गेम में जो पहले ही हो चुका है उसे देखते हुए वे संभावनाओं की गणना करते हैं।

फॉरवर्ड इंडक्शन

फॉरवर्ड इंडक्शन को ऐसा इसलिए कहा जाता है क्योंकि जैसे बैकवर्ड इंडक्शन मानता है कि भविष्य का गेम तर्कसंगत होगा, फॉरवर्ड इंडक्शन मानता है कि पिछला गेम तर्कसंगत था। जहां एक खिलाड़ी को यह नहीं पता होता है कि दूसरा खिलाड़ी किस प्रकार का है (अथार्त अपूर्ण और असममित जानकारी है), तो वह खिलाड़ी उस खिलाड़ी के पिछले कार्यों को देखकर यह धारणा बना सकता है कि वह खिलाड़ी किस प्रकार का है। इसलिए उस खिलाड़ी द्वारा प्रतिद्वंद्वी के एक निश्चित प्रकार के होने की संभावना के बारे में बनाई गई धारणा उस प्रतिद्वंद्वी के पिछले गेम के तर्कसंगत होने पर आधारित है। एक खिलाड़ी अपने कार्यों के माध्यम से अपने प्रकार का संकेत देने का चुनाव कर सकता है।

कोहलबर्ग और मर्टेंस (1986) ने स्थिर संतुलन की समाधान अवधारणा प्रस्तुत की कि एक शोधन जो आगे के प्रेरण को संतुष्ट करता है। एक प्रति-उदाहरण पाया गया जहां ऐसा स्थिर संतुलन पिछड़े प्रेरण को संतुष्ट नहीं करता था। समस्या को हल करने के लिए जीन-फ्रांकोइस मर्टेंस ने प्रस्तुत किया जिसे गेम सिद्धांतकार अब मर्टेंस-स्थिर संतुलन अवधारणा कहते हैं, संभवतः पहली समाधान अवधारणा जो आगे और पीछे दोनों प्रेरण को संतुष्ट करती है।

फॉरवर्ड इंडक्शन बर्निंग मनी गेम के लिए एक विचित्र समाधान देता है।

यह भी देखें

• व्यापक रूप का खेल
• कांपते हाथ का संतुलन
• सहज मानदंड (Cho & Kreps 1987)

संदर्भ

• Cho, I-K.; Kreps, D. M. (1987). "Signaling Games and Stable Equilibria". Quarterly Journal of Economics. 102 (2): 179–221. CiteSeerX 10.1.1.407.5013. doi:10.2307/1885060. JSTOR 1885060. S2CID 154404556.
• Fudenberg, Drew; Tirole, Jean (1991). Game theory. Cambridge, Massachusetts: MIT Press. ISBN 9780262061414. Book preview.
• Harsanyi, J. (1973) Oddness of the number of equilibrium points: a new proof. International Journal of Game Theory 2:235–250.
• Govindan, Srihari & Robert Wilson, 2008. "Refinements of Nash Equilibrium," The New Palgrave Dictionary of Economics, 2nd Edition.[1]
• Hines, W. G. S. (1987) Evolutionary stable strategies: a review of basic theory. Theoretical Population Biology 31:195–272.
• Kohlberg, Elon & Jean-François Mertens, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-37, September.
• Leyton-Brown, Kevin; Shoham, Yoav (2008). Essentials of Game Theory: A Concise, Multidisciplinary Introduction. San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.
• Mertens, Jean-François, 1989. "Stable Equilibria - A reformulation. Part 1 Basic Definitions and Properties," Mathematics of Operations Research, Vol. 14, No. 4, Nov. [2]
• Noldeke, G. & Samuelson, L. (1993) An evolutionary analysis of backward and forward induction. Games & Economic Behaviour 5:425–454.
• Maynard Smith, J. (1982) Evolution and the Theory of Games. ISBN 0-521-28884-3
• Osborne, Martin J.; Rubinstein, Ariel (1994). A course in game theory. MIT Press. ISBN 978-0-262-65040-3..
• Selten, R. (1983) Evolutionary stability in extensive two-person games. Math. Soc. Sci. 5:269–363.
• Selten, R. (1988) Evolutionary stability in extensive two-person games – correction and further development. Math. Soc. Sci. 16:223–266
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7.
• Thomas, B. (1985a) On evolutionary stable sets. J. Math. Biol. 22:105–115.
• Thomas, B. (1985b) Evolutionary stable sets in mixed-strategist models. Theor. Pop. Biol. 28:332–341