Graphical game theory
खेल सिद्धांत में, एक खेल का वर्णन करने के सामान्य तरीके सामान्य रूप और व्यापक रूप हैं। चित्रमय रूप प्रतिभागियों के बीच बातचीत का उपयोग करके एक खेल का एक वैकल्पिक संक्षिप्त प्रतिनिधित्व है। प्रत्येक रणनीति वाले खिलाड़ियों के साथ एक खेल पर विचार करें। हम खिलाड़ियों को एक ग्राफ में नोड्स के रूप में प्रस्तुत करेंगे जिसमें प्रत्येक खिलाड़ी का एक उपयोगिता कार्य होता है जो केवल उस पर और उसके पड़ोसियों पर निर्भर करता है। चूंकि उपयोगिता कार्य कम अन्य खिलाड़ियों पर निर्भर करता है, ग्राफिकल प्रतिनिधित्व छोटा होगा। औपचारिक परिभाषा एक चित्रमय खेल को एक ग्राफ द्वारा दर्शाया जाता है, जिसमें प्रत्येक खिलाड़ी को एक नोड द्वारा दर्शाया जाता है, और दो नोड्स के बीच एक किनारा होता है और उनके उपयोगिता कार्य उस रणनीति पर निर्भर होते हैं जिसे दूसरा खिलाड़ी चुनेगा। प्रत्येक नोड का एक कार्य होता है, जहाँ शीर्ष की डिग्री होती है। खिलाड़ी की उपयोगिता को उसकी रणनीति के साथ-साथ उसके पड़ोसियों के कार्य के रूप में निर्दिष्ट करता है। खेल के प्रतिनिधित्व का आकार एक सामान्य खिलाड़ी के खेल के लिए, जिसमें प्रत्येक खिलाड़ी की संभावित रणनीतियाँ होती हैं, एक सामान्य रूप प्रतिनिधित्व का आकार होगा। इस खेल के लिए चित्रमय प्रतिनिधित्व का आकार ग्राफ में अधिकतम नोड डिग्री है। यदि, तो चित्रमय खेल का प्रतिनिधित्व बहुत छोटा है। एक उदाहरण ऐसे मामले में जहां प्रत्येक खिलाड़ी का उपयोगिता कार्य केवल एक अन्य खिलाड़ी पर निर्भर करता हैः ग्राफ की अधिकतम डिग्री 1 है, और खेल को आकार के कार्यों (तालिकाओं) के रूप में वर्णित किया जा सकता है। तो, इनपुट का कुल आकार होगा। एक खेल में नैश संतुलन का पता लगाने में प्रतिनिधित्व के आकार में घातीय समय लगता है। यदि खेल का चित्रमय प्रतिनिधित्व एक वृक्ष है, तो हम बहुपद समय में संतुलन पा सकते हैं। सामान्य मामले में, जहां एक नोड की अधिकतम डिग्री 3 या उससे अधिक है, समस्या एन. पी.-पूर्ण है। आगे पढ़िए माइकल केयर्न्स (2007) "ग्राफिकल गेम्स"। माइकल केयर्न्स में, माइकल एल. लिटमैन और सतिंदर सिंह (2001) "गेम थ्योरी के लिए ग्राफिकल मॉडल"। खेल सिद्धांत ग्राफ सिद्धांत