शून्य-राशि गेम के रूप में यादृच्छिक एल्गोरिदम

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

खेल को औपचारिक बनाना

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

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

विश्लेषण

खेल में मिश्रित रणनीतियों को सम्मिलित करने से हमें जॉन वॉन न्यूमैन। वॉन न्यूमैन के अल्पमहिष्ठ प्रमेय का उपयोग करने की अनुमति मिलती है:

$\min _{R}\max _{D}T(A,D)=\max _{D}\min _{A}T(A,D)\,$

जहां आर एल्गोरिदम पर एक वितरण है, D इनपुट पर एक वितरण है, A एक एकल नियतात्मक एल्गोरिदम है, और T (A, D) इनपुट D पर एल्गोरिदम A का औसत चलने का समय है। अधिक विशेष रूप से:

$T(A,D)=\,{\underset {x\sim D}{\operatorname {E} }}[T(A,X)].\,$

यदि हम एल्गोरिदम के समुच्चय को एक विशिष्ट परिवार तक सीमित करते हैं (उदाहरण के लिए, त्वरित सॉर्ट एल्गोरिदम में पिवोट्स के लिए सभी नियतात्मक विकल्प), तो R से एल्गोरिदम A चुनना एक यादृच्छिक एल्गोरिदम चलाने के समकक्ष है (उदाहरण के लिए, त्वरित सॉर्ट चलाना और प्रत्येक चरण में पिवोट्स को यादृच्छिक रूप से चुनना)।

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