Ballmer रणनीति से स्वतंत्र खेल का सकारात्मक expected value

Steve Ballmer ग़लत थे

कुछ दिन पहले John Graham-Cumming की "Steve Ballmer का ग़लत binary search interview question" पर लिखी पोस्ट को HackerNews पर काफ़ी ध्यान मिला। Ballmer की पसंदीदा brain teaser यह है:

मैं 1 से 100 के बीच एक संख्या सोच रहा हूँ। आप अनुमान लगा सकते हैं, और हर अनुमान के बाद मैं बताऊँगा कि वह ज़्यादा है या कम। अगर आप पहले अनुमान में सही हों तो मैं आपको $5 दूँगा। $4, $3, $2, $1, $0, और फिर आपको मुझे $1, $2, $3 चुकाने होंगे.

क्या आप यह खेल खेलेंगे?

Steve Ballmer इस YouTube इंटरव्यू में दो कारण देते हैं कि आपको यह खेल नहीं खेलना चाहिए:

1. 1 से 100 के बीच की कई संख्याएँ नुकसान कराती हैं, इसलिए अगर संख्या random भी चुनी जाए तो expected value negative है.
2. वह रणनीतिक रूप से ऐसी संख्या चुन सकता है जिसे binary search से ढूँढने में सबसे ज़्यादा समय लगे.

लेकिन John पहले बिंदु का खंडन करते हैं और दिखाते हैं कि अगर Ballmer संख्या random चुने, तो खेल का expected value वास्तव में $0.20 positive है.

मैं दूसरे बिंदु का खंडन करूँगा और साबित करूँगा कि Ballmer की रणनीति चाहे जो भी हो, खेल का expected value positive है.

Ballmer संख्या को adversarial तरीके से कैसे चुन सकता है

मान लें कि आप हमेशा binary search strategy का इस्तेमाल करते हैं। 100 संख्याओं में से 37 के लिए अनुमान तक पहुँचने में 6 सवाल लगते हैं। अगर Ballmer आपकी strategy जानता है, तो वह हमेशा इन "हारने वाली" संख्याओं में से एक चुन सकता है और हर खेल में आपको नुकसान करवा सकता है। यह किसी भी fixed search pattern के लिए हमेशा सही है। कम-से-कम 37 संख्याएँ नुकसान कराएँगी, और Ballmer उनमें से एक चुन सकता है.

इसका जवाब कैसे दिया जा सकता है?

यहीं पर हम game theory के क्षेत्र में प्रवेश करते हैं। एक ही fixed search pattern की जगह, आप कई search patterns का एक set तैयार कर सकते हैं। फिर खेल शुरू होने पर आप इन patterns में से किसी एक को probability के साथ चुनते हैं और पूरे खेल में उसी पर टिके रहते हैं.

game theory में इसे mixed strategy कहा जाता है, जो कई pure strategies के strategy set पर आधारित होती है.

क्योंकि एक ही संख्या किसी एक search pattern में "जीत" और दूसरे में "हार" हो सकती है, ऐसी mixed strategy हर संख्या के expected payoff को "level" कर सकती है। संभव है कि mixed strategy हर संख्या को "जीत" में बदल दे, यानी हर संख्या के लिए positive expected payoff दे। हमें यही चाहिए.

जीतने वाली mixed strategy कैसे खोजें

नोट: हम ऐसी कोई strategy खोजना चाहते हैं जो हर संख्या पर जीतती हो, न कि सबसे अच्छी winning strategy (Nash equilibrium) जो worst case में maximum expected value दे.

अगर आप Nash equilibrium के बारे में जिज्ञासु हैं, तो Arthur O’Dwyer ने 5 संख्याओं तक के खेल के लिए closed-form solution का अध्ययन किया है, और Bo Waggoner ने 100-संख्या वाले खेल के equilibrium value को no-regret online learning का उपयोग करके approximate किया है.

हर संख्या पर जीतने वाली mixed strategy ढूँढना एक mathematical optimization problem की तरह देखा जा सकता है। हर strategy को एक "payoff" vector V=(v1,..,v100) से बताया जा सकता है, जहाँ vk वह expected जीत है जब Ballmer संख्या k चुनता है। उदाहरण के लिए, binary search एक ऐसे vector से मेल खा सकती है जहाँ v50=5, v25=4, v0=−1 हो.

मान लें कि हमारे पास pure strategies V1, V2, ..., Vn हैं, और mixed strategy probability pk के साथ strategy Vk चुनती है। तब mixed strategy का संबंधित "payoff" vector बस एक linear combination होगा: Vmixed=∑i=1npiVi.

इस व्याख्या में winning strategy खोजना ऐसी linear combination ढूँढने जैसा है जिस पर दो constraints हों:

• linear combination का हर element positive हो (यानी हर संख्या पर औसतन पैसा कमाया जा सके).
• इस linear combination के coefficients negative न हों (क्योंकि वे probabilities हैं).

यह एक सामान्य linear programming problem है, और scipy में इसके लिए एक efficient solver है। mixed strategy खोजने के लिए मैंने कई pure strategies (binary search के अलग-अलग रूप) सोचे और उन्हें scipy.linprog() में डाला, और voilà — solution ने एक winning strategy दे दी!

एक उदाहरण winning strategy

पूरा code gukoff/ballmer_puzzle में उपलब्ध है. नोट: शुरुआती परिणाम $0.07 था, जिसे Arthur O’Dwyer ने नई pure strategies जोड़कर काफ़ी बेहतर किया.

• अगर Ballmer random चुने तो औसत जीत: $0.16
• अगर Ballmer adversarial तरीके से चुने तो worst-case जीत: $0.14

मिलने वाली mixed strategy इस प्रकार है:

• probability 0.4714%: binary search, पहला अनुमान 29। हर step पर interval के middle element का अनुमान। tie होने पर बाएँ element का अनुमान
• probability 0.1691%: binary search, पहला अनुमान 33। हर step पर interval के middle element का अनुमान। tie होने पर बाएँ element का अनुमान
• probability 0.1299%: binary search, पहला अनुमान 36। हर step पर interval के middle element का अनुमान। tie होने पर दाएँ element का अनुमान
• probability 3.3341%: binary search, पहला अनुमान 37। हर step पर interval के middle element का अनुमान। tie होने पर दाएँ element का अनुमान
• probability 1.7818%: binary search, पहला अनुमान 43। हर step पर interval के सबसे दाएँ element का अनुमान, बशर्ते worst-case complexity न बढ़े
• probability 1.1608%: binary search, पहला अनुमान 44। हर step पर interval के सबसे बाएँ element का अनुमान, बशर्ते worst-case complexity न बढ़े
• probability 2.1310%: binary search, पहला अनुमान 42। हर step पर interval के किसी end element का अनुमान, बशर्ते worst-case complexity न बढ़े

...

पूरी strategy 74 पंक्तियों की है, जिसे संक्षिप्तता के लिए यहाँ छोड़ा गया है। रुचि हो तो GitHub पर देख सकते हैं.

निष्कर्ष

अगर आप औसतन प्रति खेल 14 सेंट कमा सकते हैं, तो अगली बार जब Steve Ballmer यह खेल पेश करें, तो आपको ज़रूर खेलना चाहिए.

GN⁺ का सार

• यह लेख Steve Ballmer के binary search game पर चल रही बहस पर है.
• इसमें बताया गया है कि game theory का उपयोग करके Ballmer की strategy से स्वतंत्र जीतने वाली mixed strategy कैसे खोजी जा सकती है.
• यह लेख game theory और optimization problems में रुचि रखने वालों के लिए उपयोगी हो सकता है.
• मिलती-जुलती क्षमताओं वाले अन्य projects में game theory से जुड़े विभिन्न research और papers शामिल हैं.

[GN⁺]

Hacker News राय

• Ballmer का तर्क tail risk के बारे में है

  • अगर आप survival को महत्व देते हैं, तो expected value सट्टेबाज़ी का अच्छा तरीका नहीं है
  • यह वैसा ही है जैसे poker में expected value ज़्यादा होने पर भी हर बार all-in नहीं जाते
  • औसतन जीतने की संभावना ज़्यादा हो सकती है, लेकिन आपको सिर्फ एक ही परिणाम मिलता है
  • अगर लक्ष्य जीतना है, तो Ballmer का पैसा उधार न लेना बेहतर है
  • Monte Carlo simulation के ज़रिए इस रणनीति की जीत-हार distribution देखना ज़्यादा दिलचस्प होगा

• जब Ballmer ने "hostile" कहा, तो वह इस बात को ध्यान में रख रहा था कि उसे कोई fixed संख्या चुनने की ज़रूरत नहीं है

  • वह हर guess पर ऐसा जवाब दे सकता है जिससे संभव संख्याओं की अधिकतम संख्या बची रहे और रणनीति चाहे जो हो, हार सुनिश्चित हो जाए

• "random offset binary search" नाम का एक algorithm प्रस्तावित किया गया

  • 0-100 के बीच एक random संख्या चुनें और उसे 'offset' कहें
  • binary search algorithm चलाएँ, लेकिन हर चरण में मान में 'offset' जोड़ें और 100 से modulo करें
  • Ballmer इस रणनीति को जानता हो तब भी वह कोई खास संख्या चुनकर performance खराब नहीं कर सकता
  • इसलिए expected result अब भी प्रति game $0.20 है

• यह Ballmer के गलत होने वाली कई बातों में से एक है

• "Little Mathematics Library – Elements of Game Theory" किताब की सिफारिश की गई

  • यह mixed strategies in game theory पर एक अच्छी किताब है
  • किताब में motivation के लिए दो कार्ड वाला एक game उदाहरण के रूप में दिया गया है
    • अगर खिलाड़ी A को ace मिलता है, तो वह प्रतिद्वंद्वी से 1 डॉलर मांगता है
    • अगर उसे deuce मिलता है, तो वह प्रतिद्वंद्वी से 1 डॉलर मांग सकता है या 1 डॉलर दे सकता है
    • प्रतिद्वंद्वी स्वेच्छा से 1 डॉलर ले सकता है, या यह जाँचने की मांग कर सकता है कि क्या वह ace है
    • अगर सचमुच ace है, तो वह 2 डॉलर चुकाता है, और अगर bluff है, तो 2 डॉलर पाता है
    • game का विश्लेषण किया जाता है और हर खिलाड़ी की optimal strategy और expected payoff निकाले जाते हैं

• Nash equilibrium के अधिक व्यापक विश्लेषण और पूरे game के numerical solution वाला एक लिंक साझा किया गया

• आधुनिक tech interview process का यह एक बिल्कुल पागलपन भरा उदाहरण है

• मैं "यह सही लगता है, अच्छा किया!" वाली टिप्पणी ढूंढ रहा था, नहीं मिली तो खुद ही छोड़ दी

  • यह सही लगता है, अच्छा किया

• Steve Ballmer की net worth 120 अरब डॉलर है

  • अगर मान लें कि हर game में 30 सेकंड लगते हैं, तो उसका सारा पैसा जीतने में 16 लाख साल लगेंगे