Graphical game theory
খেলা তত্ত্বে, একটি খেলা বর্ণনা করার সাধারণ উপায় হল স্বাভাবিক রূপ এবং বিস্তৃত রূপ। গ্রাফিক্যাল ফর্ম হল অংশগ্রহণকারীদের মধ্যে মিথস্ক্রিয়া ব্যবহার করে একটি খেলার একটি বিকল্প সংক্ষিপ্ত উপস্থাপনা। প্রতিটি কৌশল সহ খেলোয়াড়দের নিয়ে একটি খেলা বিবেচনা করুন। আমরা খেলোয়াড়দের একটি গ্রাফে নোড হিসাবে উপস্থাপন করব যেখানে প্রতিটি খেলোয়াড়ের একটি ইউটিলিটি ফাংশন রয়েছে যা কেবল তার এবং তার প্রতিবেশীদের উপর নির্ভর করে। যেহেতু ইউটিলিটি ফাংশন কম খেলোয়াড়ের উপর নির্ভর করে, তাই গ্রাফিকাল উপস্থাপনা ছোট হবে। আনুষ্ঠানিক সংজ্ঞা একটি গ্রাফিকাল গেম একটি গ্রাফ দ্বারা প্রতিনিধিত্ব করা হয়, যেখানে প্রতিটি খেলোয়াড়কে একটি নোড দ্বারা প্রতিনিধিত্ব করা হয় এবং দুটি নোডের মধ্যে একটি প্রান্ত থাকে এবং তাদের ইউটিলিটি ফাংশনগুলি অন্য খেলোয়াড় যে কৌশলটি বেছে নেবে তার উপর নির্ভরশীল। প্রতিটি নোডের একটি ফাংশন রয়েছে, যেখানে ভার্টেক্সের ডিগ্রি রয়েছে। খেলোয়াড়ের কার্যকারিতা তার কৌশলের পাশাপাশি তার প্রতিবেশীদের কার্যকারিতা হিসাবে নির্দিষ্ট করে। খেলার প্রতিনিধিত্বের আকার একটি সাধারণ খেলোয়াড়ের খেলার জন্য, যেখানে প্রতিটি খেলোয়াড়ের সম্ভাব্য কৌশল রয়েছে, একটি সাধারণ ফর্ম প্রতিনিধিত্বের আকার হবে। এই গেমের জন্য গ্রাফিকাল উপস্থাপনার আকার হল যেখানে গ্রাফের সর্বাধিক নোড ডিগ্রি রয়েছে। যদি, তাহলে গ্রাফিক্যাল গেমের উপস্থাপনা অনেক ছোট। একটি উদাহরণ যেখানে প্রতিটি খেলোয়াড়ের ইউটিলিটি ফাংশন শুধুমাত্র অন্য খেলোয়াড়ের উপর নির্ভর করেঃ গ্রাফের সর্বোচ্চ ডিগ্রি হল 1, এবং গেমটিকে আকারের ফাংশন (টেবিল) হিসাবে বর্ণনা করা যেতে পারে। সুতরাং, ইনপুটের মোট আকার হবে। ন্যাশ ভারসাম্য একটি খেলায় ন্যাশ ভারসাম্য খুঁজে পেতে প্রতিনিধিত্বের আকারে সূচকীয় সময় লাগে। যদি খেলার গ্রাফিক্যাল উপস্থাপনা একটি গাছ হয়, তাহলে আমরা বহুপদী সময়ে ভারসাম্য খুঁজে পেতে পারি। সাধারণ ক্ষেত্রে, যেখানে একটি নোডের সর্বোচ্চ ডিগ্রি 3 বা তার বেশি, সমস্যাটি এনপি-সম্পূর্ণ। আরও পড়ুন মাইকেল কেয়ার্নস (2007) "গ্রাফিকাল গেমস"। মাইকেল কেয়ার্নস, মাইকেল এল. লিটম্যান এবং সতীন্দর সিং (2001) "গ্রাফিকাল মডেলস ফর গেম থিওরি"। গেম তত্ত্ব গ্রাফ তত্ত্ব