نظرية الألعاب الرسومية

في نظرية الألعاب ، يُعدّ الشكل البياني أو اللعبة البيانية تمثيلاً بديلاً مُختصراً للتفاعلات الاستراتيجية، حيث يُحاكي بكفاءة المواقف التي تعتمد فيها نتائج اللاعبين على مجموعة فرعية فقط من نتائج اللاعبين الآخرين. ^{[ 1 ]} وقد صاغ هذا النهج رسميًا لأول مرة مايكل كيرنز ومايكل ليتمان وساتيندر سينغ في عام 2001، وهو يُكمّل التمثيلات التقليدية مثل الشكل العادي والشكل الموسّع ، وذلك بالاستفادة من مفاهيم نظرية الرسوم البيانية لتحقيق أوصاف أكثر إيجازًا للألعاب.

في التمثيل البياني للألعاب، يُصوَّر اللاعبون كعُقد في رسم بياني ، حيث تربط الحواف بين اللاعبين الذين تؤثر قراراتهم على بعضهم البعض بشكل مباشر. وتعتمد دالة منفعة كل لاعب على استراتيجيته الخاصة واستراتيجيات جيرانه المباشرين في الرسم البياني فقط، وليس على تصرفات جميع اللاعبين. يُعد هذا الإطار ذا قيمة خاصة لنمذجة تفاعلات الشبكات الاجتماعية ، والشبكات الاقتصادية، وسيناريوهات المنافسة المحلية حيث يستجيب اللاعبون بشكل أساسي لمن هم في محيطهم المباشر.

يُقدّم النهج البياني مزايا كبيرة عند تمثيل الألعاب الكبيرة ذات أنماط التفاعل المحدودة، إذ يُمكنه تقليل كمية المعلومات اللازمة لوصف اللعبة وصفًا كاملًا بشكل كبير. يُسهّل هذا التمثيل المُختصر إجراء تحليل حسابي أكثر كفاءة لأنظمة الوكلاء المتعددة المعقدة في مجالات مثل الذكاء الاصطناعي والاقتصاد وعلم الشبكات .

يتم تمثيل اللعبة الرسومية بواسطة رسم بياني${\displaystyle G}$، حيث يتم تمثيل كل لاعب بعقدة، وهناك حافة بين عقدتين${\displaystyle i}$و${\displaystyle j}$ إذا كانت وظائف المنفعة الخاصة بهم تعتمد على الاستراتيجية التي سيختارها اللاعب الآخر. كل عقدة${\displaystyle i}$في${\displaystyle G}$له وظيفة${\displaystyle u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R} }$، أين${\displaystyle d_{i}}$هي درجة الرأس${\displaystyle i}$. ${\displaystyle u_{i}}$يحدد فائدة اللاعب${\displaystyle i}$وذلك تبعاً لاستراتيجيته وكذلك استراتيجيات جيرانه.

للعرض العام${\displaystyle n}$لعبة اللاعبين، حيث يمتلك كل لاعب${\displaystyle m}$من بين الاستراتيجيات الممكنة، سيكون حجم تمثيل الشكل الطبيعي${\displaystyle O(m^{n})}$حجم التمثيل الرسومي لهذه اللعبة هو${\displaystyle O(m^{d})}$أين${\displaystyle d}$يمثل الحد الأقصى لدرجة العقدة في الرسم البياني. إذا${\displaystyle d\ll n}$وبالتالي، يصبح تمثيل اللعبة الرسومي أصغر بكثير.

في حالة اعتماد دالة منفعة كل لاعب على لاعب واحد فقط:

• 
  الشكل الرسومي للعبة الموصوفة

أقصى درجة للرسم البياني هي 1، ويمكن وصف اللعبة على النحو التالي:${\displaystyle n}$دوال (جداول) بحجم${\displaystyle m^{2}}$إذن، سيكون الحجم الإجمالي للمدخلات هو${\displaystyle nm^{2}}$.

يستغرق إيجاد توازن ناش في لعبة ما وقتًا أُسّيًا يتناسب مع حجم التمثيل. إذا كان التمثيل البياني للعبة عبارة عن شجرة، فيمكننا إيجاد التوازن في وقت متعدد الحدود. في الحالة العامة، حيث تكون الدرجة القصوى للعقدة 3 أو أكثر، تُصنَّف المسألة على أنها مسألة كاملة من فئة NP .

• مايكل كيرنز (2007) " الألعاب الرسومية ". في فازيراني، فيجاي ف . نيسان, نعوم ; روغاردن, تيم ; تاردوس، إيفا (2007). نظرية اللعبة الخوارزمية (PDF) . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. رقم ISBN 0-521-87282-0.
• مايكل كيرنز، مايكل ل. ليتمان وساتيندر سينغ (2001) " النماذج الرسومية لنظرية الألعاب ".