لعبة موجزة

الألعاب الرسومية هي ألعاب تعتمد فيها فوائد كل لاعب على تصرفات عدد قليل جدًا من اللاعبين الآخرين.${\displaystyle d}$يمثل أكبر عدد من اللاعبين الذين تتأثر أفعالهم بأي لاعب منفرد (أي أنه درجة الدخول في مخطط اللعبة)، وعدد قيم المنفعة اللازمة لوصف اللعبة هو${\displaystyle ns^{d+1}}$، وهو ما يمثل، بالنسبة لـ${\displaystyle d}$يمثل ذلك تحسناً كبيراً.

لقد ثبت أن أي لعبة ذات شكل طبيعي قابلة للاختزال إلى لعبة بيانية ذات درجات محدودة بثلاثة واستراتيجيتين لكل لاعب. ^{[ 3 ]} على عكس الألعاب ذات الشكل الطبيعي، فإن مسألة إيجاد توازن ناش خالص في الألعاب البيانية (إن وُجد) هي مسألة NP-كاملة . ^{[ 4 ]} أما مسألة إيجاد توازن ناش (ربما مختلط) في لعبة بيانية فهي مسألة PPAD- كاملة. ^{[ 5 ]} يمكن إيجاد توازن مترابط للعبة بيانية في وقت متعدد الحدود، وبالنسبة للرسم البياني ذي عرض الشجرة المحدود ، ينطبق هذا أيضًا على إيجاد توازن مترابط أمثل . ^{[ 2 ]}

الألعاب المتفرقة هي تلك التي تكون فيها معظم الأدوات المساعدة معدومة. ويمكن اعتبار الألعاب الرسومية حالة خاصة من الألعاب المتفرقة.

في لعبة ثنائية اللاعبين، يمكن تعريف اللعبة المتفرقة بأنها لعبة تحتوي فيها كل صفوف وأعمدة مصفوفات العوائد (المنفعة) على عدد ثابت على الأكثر من العناصر غير الصفرية. وقد ثبت أن إيجاد توازن ناش في مثل هذه اللعبة المتفرقة يُعدّ مسألة صعبة من نوع PPAD، وأنه لا توجد طريقة تقريبية كاملة متعددة الحدود إلا إذا كانت PPAD تنتمي إلى ^{المجموعة} P. [ ^{6 ]}

في الألعاب المتناظرة، يكون جميع اللاعبين متطابقين، لذا عند تقييم جدوى مجموعة من الاستراتيجيات، فإن كل ما يهم هو عدد${\displaystyle n}$يلعب اللاعبون كلًا من${\displaystyle s}$الاستراتيجيات. وبالتالي، فإن وصف مثل هذه اللعبة يتطلب فقط ذكر الاستراتيجيات.${\displaystyle s{\tbinom {n+s-2}{s-1}}}$القيم النفعية.

في لعبة متناظرة ذات استراتيجيتين، يوجد دائمًا توازن ناش نقي، مع أن توازن ناش نقي متناظر قد لا يكون موجودًا. ^{[ 7 ]} تُصنَّف مسألة إيجاد توازن ناش نقي في لعبة متناظرة (مع احتمال وجود أكثر من لاعبين) ذات عدد ثابت من الإجراءات ضمن فئة AC ⁰ ؛ ومع ذلك، عندما يزداد عدد الإجراءات مع ازدياد عدد اللاعبين (حتى بشكل خطي)، تصبح المسألة من فئة NP-كاملة. ^{[ 8 ]} في أي لعبة متناظرة، يوجد توازن متناظر . بالنظر إلى لعبة متناظرة تضم n لاعبًا يواجهون k استراتيجية، يمكن إيجاد توازن متناظر في وقت متعدد الحدود إذا كان k=${\displaystyle O(\log n/\log \log n)}$[ ^{9 ]} يمكن إيجاد توازن مترابط في الألعاب المتناظرة في وقت متعدد الحدود ^{. [ 2 ]}

في الألعاب المجهولة ، يمتلك اللاعبون منافع مختلفة لكنهم لا يميزون بين اللاعبين الآخرين (على سبيل المثال، عليهم الاختيار بين "الذهاب إلى السينما" و"الذهاب إلى الحانة" مع الاهتمام فقط بمدى ازدحام كل مكان، وليس بمن سيقابلون هناك). في مثل هذه اللعبة، تعتمد منفعة اللاعب مرة أخرى على عدد أقرانه الذين يختارون أي استراتيجية، وعلى استراتيجيته هو أيضًا.${\displaystyle sn{\tbinom {n+s-2}{s-1}}}$القيم النفعية مطلوبة.

إذا ازداد عدد الإجراءات مع ازدياد عدد اللاعبين، فإن إيجاد توازن ناش الخالص في لعبة مجهولة الهوية يُعدّ مسألة صعبة من نوع NP . ^{[ 8 ]} يمكن إيجاد توازن مترابط أمثل للعبة مجهولة الهوية في وقت متعدد الحدود. ^{[ 2 ]} عندما يكون عدد الاستراتيجيات 2، توجد خوارزمية تقريب متعددة الحدود معروفة لإيجاد توازن ناش تقريبي من نوع إبسيلون . ^{[ 10 ]}

في لعبة المصفوفات المتعددة (المعروفة أيضًا باسم لعبة المصفوفات المتعددة )، توجد مصفوفة منفعة لكل زوج من اللاعبين (i، j) ، تُمثل مُكوّنًا من مُنفعة اللاعب i. المنفعة النهائية للاعب i هي مجموع كل هذه المُكوّنات. عدد قيم المنفعة المطلوبة لتمثيل هذه اللعبة هو${\displaystyle O(n^{2}*s^{2})}$.

تحتوي ألعاب المصفوفات المتعددة دائمًا على توازن ناش مختلط واحد على الأقل. ^{[ 11 ]} تُعدّ مسألة إيجاد توازن ناش في لعبة مصفوفات متعددة مسألة كاملة من فئة PPAD. ^{[ 5 ]} علاوة على ذلك، تُعدّ مسألة إيجاد توازن ناش تقريبي ثابت في لعبة مصفوفات متعددة مسألة كاملة من فئة PPAD أيضًا. ^{[ 12 ]} يمكن إيجاد توازن مترابط في لعبة مصفوفات متعددة في وقت متعدد الحدود. ^{[ 2 ]} تجدر الإشارة إلى أنه حتى لو كانت الألعاب الثنائية بين اللاعبين تحتوي على توازنات ناش خالصة، فإن التفاعل الكلي لا يسمح بالضرورة بوجود توازن ناش خالص (على الرغم من وجوب وجود توازن ناش مختلط). يُعدّ التحقق من وجود توازن ناش خالص مسألة كاملة من فئة NP بشدة . ^{[ 13 ]}

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

ألعاب المصفوفات المتعددة التي تحتوي على ألعاب تنسيق على حوافها هي ألعاب محتملة ^{[ 16 ]} ويمكن حلها باستخدام طريقة دالة محتملة.

إنّ أكثر الطرق مرونةً لتمثيل لعبة موجزة هي تمثيل كل لاعب بآلة تورينغ محدودة الزمن متعدد الحدود ، تأخذ كمدخلاتٍ لها أفعال جميع اللاعبين وتُخرج منفعة اللاعب. تُكافئ آلة تورينغ هذه دائرة منطقية ، وهذا التمثيل، المعروف باسم ألعاب الدوائر ، هو ما سنتناوله.

يُعد حساب قيمة لعبة الدائرة ذات المجموع الصفري بين لاعبين مسألةً كاملةً من حيث التعقيد الزمني (EXP -complete) ^{[ 17 ]} ، ومن المعروف أن تقريب قيمة هذه اللعبة حتى عامل ضربي يقع ضمن فضاء التعقيد الزمني (PSPACE) ^{[ 18 ]} . أما تحديد ما إذا كان هناك توازن ناش خالص فهو مسألةٌ من نوعٍ ما.${\displaystyle \Sigma _{2}^{\rm {P}}}$المسألة الكاملة (انظر التسلسل الهرمي متعدد الحدود ). ^{[ 19 ]}

توجد أنواع أخرى كثيرة من الألعاب الموجزة (يرتبط الكثير منها بتخصيص الموارد). ومن الأمثلة على ذلك ألعاب الازدحام ، وألعاب ازدحام الشبكة ، وألعاب الجدولة ، وألعاب التأثير المحلي ، وألعاب تحديد مواقع المرافق ، وألعاب الرسوم البيانية التفاعلية ، والألعاب فائقة الرسوم البيانية ، وغيرها.