Graphical game theory
گیم تھیوری میں، کھیل کو بیان کرنے کے عام طریقے عام شکل اور وسیع شکل ہیں۔ گرافیکل شکل شرکاء کے درمیان تعامل کا استعمال کرتے ہوئے کھیل کی ایک متبادل کمپیکٹ نمائندگی ہے۔ ہر ایک حکمت عملی کے ساتھ کھلاڑیوں کے ساتھ ایک کھیل پر غور کریں۔ ہم کھلاڑیوں کو ایک گراف میں نوڈس کے طور پر پیش کریں گے جس میں ہر کھلاڑی کا ایک یوٹیلیٹی فنکشن ہوتا ہے جو صرف اس پر اور اس کے پڑوسیوں پر منحصر ہوتا ہے۔ چونکہ یوٹیلیٹی فنکشن کا انحصار کم دوسرے کھلاڑیوں پر ہوتا ہے، اس لیے گرافیکل نمائندگی کم ہوگی۔ رسمی تعریف ایک گرافیکل گیم کی نمائندگی ایک گراف کے ذریعے کی جاتی ہے، جس میں ہر کھلاڑی کی نمائندگی ایک نوڈ کے ذریعے کی جاتی ہے، اور دو نوڈس کے درمیان ایک کنارے ہوتا ہے اور آئی ایف ایف ان کی افادیت کے افعال اس حکمت عملی پر منحصر ہوتے ہیں جسے دوسرا کھلاڑی منتخب کرے گا۔ ہر نوڈ میں ایک فنکشن ہوتا ہے، جہاں ورٹیکس کی ڈگری ہوتی ہے۔ کھلاڑی کی افادیت کو اس کی حکمت عملی کے ساتھ ساتھ اس کے پڑوسیوں کے کام کے طور پر بیان کرتا ہے۔ کھیل کی نمائندگی کا سائز عام کھلاڑیوں کے کھیل کے لیے، جس میں ہر کھلاڑی کی ممکنہ حکمت عملی ہوتی ہے، عام فارم کی نمائندگی کا سائز ہوگا۔ اس کھیل کے لیے گرافیکل نمائندگی کا سائز یہ ہے کہ گراف میں زیادہ سے زیادہ نوڈ ڈگری کہاں ہے۔ اگر، تو گرافیکل گیم کی نمائندگی بہت کم ہے۔ ایک مثال ایسی صورت میں جہاں ہر کھلاڑی کا یوٹیلیٹی فنکشن صرف ایک دوسرے کھلاڑی پر منحصر ہو: گراف کی زیادہ سے زیادہ ڈگری 1 ہے، اور گیم کو سائز کے افعال (ٹیبلز) کے طور پر بیان کیا جا سکتا ہے۔ تو، ان پٹ کا کل سائز ہوگا۔ نیش توازن کسی کھیل میں نیش توازن تلاش کرنے میں نمائندگی کے سائز میں تیزی سے وقت لگتا ہے۔ اگر کھیل کی گرافیکل نمائندگی ایک درخت ہے، تو ہم کثیر الجہتی وقت میں توازن تلاش کر سکتے ہیں۔ عام صورت میں، جہاں نوڈ کی زیادہ سے زیادہ ڈگری 3 یا اس سے زیادہ ہے، مسئلہ این پی مکمل ہے۔ مزید پڑھنے کے لیے مائیکل کیرنس (2007) "گرافیکل گیمز"۔ مائیکل کیرنز میں، مائیکل ایل لٹ مین اور ستندر سنگھ (2001) "گرافیکل ماڈلز فار گیم تھیوری"۔ گیم تھیوری گراف تھیوری