खिलाड़ी, रणनीतियाँ और पे-ऑफ़ मैट्रिक्स
एक खेल में होते हैं: खिलाड़ी, हर खिलाड़ी की रणनीतियाँ (strategies) यानी विकल्प, और पे-ऑफ़ यानी किसे क्या मिलता है।
दो खिलाड़ियों और कुछ विकल्पों के लिए पे-ऑफ़ मैट्रिक्स बनाते हैं। A पंक्ति चुनता है, B स्तंभ। हर खाने में (A का लाभ, B का लाभ) लिखा होता है।
| B: चुप | B: बताओ | |
|---|---|---|
| A: चुप | (3, 3) | (0, 5) |
| A: बताओ | (5, 0) | (1, 1) |
शून्य-योग खेल (zero-sum game) में एक जो जीतता है, दूसरा वही हारता है, इसलिए सिर्फ़ A का लाभ लिखते हैं। जब खिलाड़ी बारी-बारी चलते हैं (क्रमिक खेल), तब मैट्रिक्स की जगह खेल वृक्ष (game tree) बनाते हैं।
प्रभुत्व: बेकार विकल्प हटाना
कोई रणनीति अधीन (dominated) है अगर दूसरी रणनीति विरोधी के हर चुनाव पर कम से कम उतना ही अच्छा, और कम से कम एक पर बेहतर, लाभ देती है। समझदार खिलाड़ी उसे कभी नहीं चुनेगा, इसलिए उसे काट देते हैं। मैट्रिक्स छोटा हो जाता है।
ऊपर की तालिका में A की पंक्तियाँ देखो: B चुप हो तो बताओ = 5 > 3; B बताए तो बताओ = 1 > 0। इसलिए A के लिए बताओ, चुप पर प्रभावी है। यह प्रभावी रणनीति (dominant strategy) है: B कुछ भी करे, यही सबसे अच्छी। B के लिए भी यही सच है।
शून्य-योग मैट्रिक्स में स्तंभ वाला खिलाड़ी B चाहता है कि A की संख्या छोटी हो: जिस स्तंभ की सब संख्याएँ बड़ी हों, वह अधीन है।
नैश संतुलन और कैदी की दुविधा
नैश संतुलन (Nash equilibrium) रणनीतियों की वह जोड़ी है जहाँ हर खिलाड़ी दूसरे के चुनाव का सबसे अच्छा जवाब दे रहा है। कोई भी अकेले बदलकर बेहतर नहीं कर सकता।
ढूँढने का तरीका: हर स्तंभ में A की सबसे अच्छी पंक्ति पर निशान लगाओ; हर पंक्ति में B का सबसे अच्छा स्तंभ। जिस खाने पर दोनों निशान हों, वही संतुलन है।
कैदी की दुविधा (prisoner's dilemma) में दोनों का बताना (1, 1) ही अकेला संतुलन है, जबकि दोनों का चुप रहना (3, 3) दोनों के लिए बेहतर था। हर खिलाड़ी का निजी फ़ायदा सबको बुरे नतीजे पर ले जाता है। यही दाम-युद्ध, हथियारों की होड़ और ज़्यादा मछली पकड़ने को समझाता है।
कुछ खेलों में एक से ज़्यादा संतुलन होते हैं। तालमेल के खेल (दोनों चाय या दोनों कॉफ़ी) में दोनों मेल वाले खाने स्थिर हैं।
जब वही खेल कई बार दोहराया जाए, तो खिलाड़ी सहयोग का इनाम और धोखे की सज़ा दे सकते हैं ("जैसे को तैसा"), इसलिए सहयोग टिक सकता है। विश्वसनीय धमकी (credible threat) वह है जिसे खिलाड़ी सच में पूरा करेगा।
शून्य-योग खेल: सुरक्षित रणनीति और सैडल बिंदु
शून्य-योग खेल में सावधान खिलाड़ी सबसे बुरा मानकर चलता है।
- पंक्ति खिलाड़ी (A): हर पंक्ति का न्यूनतम लिखो, फिर सबसे बड़े न्यूनतम वाली पंक्ति चुनो (मैक्सिमिन)।
- स्तंभ खिलाड़ी (B): हर स्तंभ का अधिकतम लिखो, फिर सबसे छोटे अधिकतम वाला स्तंभ चुनो (मिनिमैक्स)।
ये सुरक्षित (play-safe) रणनीतियाँ हैं। अगर मैक्सिमिन = मिनिमैक्स, तो खेल में सैडल बिंदु और स्थिर हल है: कोई बदलकर फ़ायदा नहीं ले सकता। वह साझा संख्या खेल का मान (value) है।
उदाहरण: A के लाभ [[3, 1], [4, 2]]। पंक्ति न्यूनतम 1, 2 → मैक्सिमिन 2। स्तंभ अधिकतम 4, 2 → मिनिमैक्स 2। सैडल बिंदु (A2, B2), मान 2।
ग्राफ़ से मिश्रित रणनीति
अगर मैक्सिमिन < मिनिमैक्स, तो कोई स्थिर शुद्ध हल नहीं। तब खिलाड़ी को मिलाकर खेलना चाहिए: हर पंक्ति एक तय प्रायिकता से, बेतरतीब ढंग से, ताकि विरोधी अंदाज़ा न लगा सके।
मान लो A पंक्ति 1 को p और पंक्ति 2 को 1 − p प्रायिकता से खेलता है। B के हर स्तंभ के विरुद्ध A का अपेक्षित लाभ p में एक सीधी रेखा है। B वही स्तंभ चुनेगा जो A के लिए बुरा है, इसलिए A को रेखाओं की निचली किनारी मिलती है। A वह p चुनता है जहाँ यह निचली किनारी सबसे ऊँची हो, आमतौर पर रेखाओं के कटान पर।
उदाहरण [[4, 1], [2, 3]]: B1 के विरुद्ध E = 4p + 2(1 − p) = 2 + 2p। B2 के विरुद्ध E = p + 3(1 − p) = 3 − 2p। बराबर रखो: 2 + 2p = 3 − 2p → p = 1/4। मान = 2.5।
बड़े खेलों (जैसे 3×3) के लिए यही बात रैखिक प्रोग्रामन (linear programming) की समस्या बनती है: मान V अधिकतम करो, शर्त यह कि हर स्तंभ A को कम से कम V दे; इसे सिंप्लेक्स विधि से हल करते हैं।
करके देखो: 3D में और घर पर
3D में: आख़िरी चरण में हर खेल चुनो और रिंग दिखने से पहले संतुलन का अंदाज़ा लगाओ। मिश्रित खेल में p को 0 से 1 तक खिसकाओ और देखो लाल बिंदु कहाँ सबसे ऊँचा है।
घर पर (दोस्त के साथ): 10 टॉफ़ियों से अल्टीमेटम खेल खेलो। एक व्यक्ति बँटवारा प्रस्तावित करे; दूसरा माने (दोनों अपना हिस्सा रखें) या ठुकराए (किसी को कुछ नहीं)। सिद्धांत कहता है 0 से ज़्यादा हर प्रस्ताव मान लेना चाहिए, पर असली लोग अक्सर अन्यायपूर्ण प्रस्ताव ठुकरा देते हैं। इससे पता चलता है कि सिर्फ़ लाभ नहीं, न्याय और साख भी मायने रखते हैं।
परीक्षा पर ध्यान
आमतौर पर पूछा जाता है: कहानी से पे-ऑफ़ मैट्रिक्स बनाओ; प्रभुत्व से छोटा करो; सुरक्षित रणनीतियाँ और सैडल बिंदु जाँचो; नैश संतुलन ढूँढो; ग्राफ़ या दो समीकरणों से सबसे अच्छी मिश्रित रणनीति और मान निकालो; असली उदाहरण में कैदी की दुविधा समझाओ।
मुख्य सूत्र और परिभाषाएँ
- मैक्सिमिन (पंक्ति) = पंक्ति-न्यूनतमों में सबसे बड़ा
- मिनिमैक्स (स्तंभ) = स्तंभ-अधिकतमों में सबसे छोटा
- सैडल बिंदु ⇔ मैक्सिमिन = मिनिमैक्स = खेल का मान
- E(स्तंभ j) = p × a(1,j) + (1 − p) × a(2,j)
- सबसे अच्छा p: E(स्तंभ 1) = E(स्तंभ 2)
- नैश संतुलन: हर रणनीति दूसरी का सबसे अच्छा जवाब
हल किए गए उदाहरण
1. मैट्रिक्स [[3, 1], [4, 2]] (A के लाभ, शून्य-योग) में सुरक्षित रणनीतियाँ और सैडल बिंदु जाँचो।
पंक्ति न्यूनतम: 1, 2 → A पंक्ति 2 खेले (मैक्सिमिन 2)। स्तंभ अधिकतम: 4, 2 → B स्तंभ 2 (मिनिमैक्स 2)। बराबर, तो सैडल बिंदु (पंक्ति 2, स्तंभ 2), मान 2।
2. प्रभुत्व से छोटा करो: A के लाभ [[2, 5, 4], [1, 3, 2], [3, 6, 1]]।
पंक्ति 2 (1, 3, 2) पंक्ति 1 (2, 5, 4) से अधीन है: हटाओ। बचा [[2, 5, 4], [3, 6, 1]]। B (छोटा चाहता है) के लिए स्तंभ 2 (5, 6) दोनों पंक्तियों में स्तंभ 1 (2, 3) से बुरा है: हटाओ। बचा [[2, 4], [3, 1]]।
3. तालमेल खेल के नैश संतुलन: (चाय, चाय) = (4, 4), (चाय, कॉफ़ी) = (0, 0), (कॉफ़ी, चाय) = (0, 0), (कॉफ़ी, कॉफ़ी) = (3, 3)।
B चाय चुने तो A के लिए चाय सबसे अच्छी; B कॉफ़ी चुने तो कॉफ़ी। B के लिए भी यही। (चाय, चाय) और (कॉफ़ी, कॉफ़ी) दोनों पर दोनों के सबसे अच्छे जवाब हैं: दो संतुलन।
4. शून्य-योग खेल [[4, 1], [2, 3]] को A के लिए हल करो।
मैक्सिमिन = 2, मिनिमैक्स = 3: सैडल बिंदु नहीं। A पंक्ति 1 को p से खेले। E(B1) = 2 + 2p, E(B2) = 3 − 2p। बराबर जब p = 1/4। A पंक्ति 1 को 1/4 और पंक्ति 2 को 3/4 बार खेले; मान = 2 + 2(1/4) = 2.5।
5. इसी खेल में B का सबसे अच्छा मिश्रण निकालो।
B स्तंभ 1 को q से खेले। A की पंक्ति 1: 4q + (1 − q) = 1 + 3q; पंक्ति 2: 2q + 3(1 − q) = 3 − q। बराबर जब 4q = 2, q = 1/2। B दोनों स्तंभ आधे-आधे खेले; मान 2.5, A जितना ही।
6. दो कंपनियाँ ऊँचा या नीचा दाम चुनती हैं। (ऊँचा, ऊँचा) = (6, 6), (ऊँचा, नीचा) = (2, 8), (नीचा, ऊँचा) = (8, 2), (नीचा, नीचा) = (3, 3)। क्या होगा और क्यों?
हर कंपनी के लिए नीचा, ऊँचे पर प्रभावी है (8 > 6 और 3 > 2), तो दोनों नीचा चुनती हैं: संतुलन (3, 3)। ऊँचे दाम पर दोनों को 6 मिलते, तो यह कैदी की दुविधा है; बार-बार खेल या समझौते (साँठगाँठ) से दाम ऊँचे रह सकते हैं।
आम गलतियाँ
- स्तंभ खिलाड़ी के लिए मैक्सिमिन लगाना। A के लाभ वाले शून्य-योग मैट्रिक्स में B छोटी संख्या चाहता है, इसलिए मिनिमैक्स।
- सोचना कि नैश संतुलन हमेशा सबके लिए सबसे अच्छा है। कैदी की दुविधा दिखाती है कि ऐसा ज़रूरी नहीं।
- अपेक्षित लाभ की ऊपरी रेखा लेना। विरोधी आपके लिए बुरा जवाब चुनेगा, इसलिए निचली किनारी लो।
- ऐसी पंक्ति हटाना जो कुछ स्तंभों में बेहतर और कुछ में बुरी हो। प्रभुत्व के लिए हर स्तंभ में कम से कम बराबर होना ज़रूरी है।