لعبة الازدحام

يتكون التعريف الأساسي لـ CG من المكونات التالية.

• مجموعة أساسية E من العناصر القابلة للازدحام (وتسمى أيضًا الموارد أو العوامل ) . في المثال أعلاه، E هي مجموعة الطرق ( OA ، AT ، OB ، و BT ) .
• مجموعة من n لاعبًا. في المثال أعلاه${\displaystyle n=2}$.
• مجموعة محدودة من الاستراتيجيات${\displaystyle S_{i}}$لكل لاعب، حيث كل استراتيجية${\displaystyle P\in S_{i}}$هي مجموعة جزئية من E.
  • في المثال أعلاه، يمتلك كلا اللاعبين نفس مجموعة الاستراتيجيات:${\displaystyle S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}}$تُسمى ألعاب الورق الجماعية التي يمتلك فيها جميع اللاعبين نفس مجموعة الاستراتيجيات ألعاب الورق الجماعية المتناظرة . أما بشكل عام، فقد يمتلك اللاعبون المختلفون مجموعات استراتيجيات مختلفة، على سبيل المثال، إذا كان لكل لاعب مصدر مختلف و/أو هدف مختلف. تُسمى هذه الألعاب ألعاب الورق الجماعية غير المتناظرة .
  • بشكل عام، يمكن أن تكون الاستراتيجية أي مجموعة فرعية من E. تُسمى مخططات الرسم البياني التي لا يمكن أن تكون الاستراتيجية فيها إلا مسارًا في رسم بياني معين (كما في المثال أعلاه) مخططات الرسم البياني الشبكية . أما مخططات الرسم البياني التي لا يمكن أن تكون الاستراتيجية فيها إلا موردًا واحدًا فتُسمى مخططات الرسم البياني الأحادية .
• لكل عنصر${\displaystyle e\in E}$ومجموعة من الاستراتيجيات${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$يتم تعريف الحمل على النحو التالي :${\displaystyle x_{e}=\#\{i:e\in P_{i}\}}$.
• لكل عنصر${\displaystyle e\in E}$توجد دالة تأخير${\displaystyle d_{e}:\mathbb {N} \longrightarrow \mathbb {R} }$(وتُسمى أيضًا دالة زمن الاستجابة أو دالة التكلفة ). بالنظر إلى متجه من الاستراتيجيات، يكون التأخير على e هو${\displaystyle d_{e}(x_{e})}$. كل${\displaystyle d_{e}}$يُفترض أن تكون موجبة ومتزايدة بشكل رتيب .
• بافتراض وجود استراتيجية${\displaystyle P_{i}}$يواجه اللاعب i تأخيرًا${\displaystyle \textstyle \sum _{e\in P_{i}}d_{e}(x_{e})}$يسعى كل لاعب إلى تقليل التأخير الذي يقوم به.
• يمثل توازن ناش متجهًا للاستراتيجيات${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$بحيث، لكل لاعب i ، استبدال${\displaystyle P_{i}}$باستراتيجية مختلفة${\displaystyle Q_{i}}$لن يقلل ذلك من التأخير الذي يواجهه i .

لكل لعبة استراتيجية تفاضلية توازن ناش في الاستراتيجيات البحتة . ويمكن إثبات ذلك من خلال بناء دالة احتمالية تُسند قيمة لكل نتيجة. ^{[ 1 ]} علاوة على ذلك، سيُظهر هذا البناء أيضًا أن أفضل استجابة مُكررة تجد توازن ناش. عرّف${\displaystyle \textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)}$لاحظ أن هذه الوظيفة ليست وظيفة الرفاه الاجتماعي${\displaystyle \textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})}$بل هو بالأحرى تكامل منفصل من نوع ما. الخاصية الأساسية لدالة الجهد في لعبة الازدحام هي أنه إذا غيّر أحد اللاعبين استراتيجيته، فإن التغير في تأخيره يساوي التغير في دالة الجهد.

لنفترض الحالة التي ينتقل فيها اللاعب i من${\displaystyle P_{i}}$ل${\displaystyle Q_{i}}$العناصر الموجودة في كلتا الاستراتيجيتين تبقى دون تغيير، والعناصر التي يتركها اللاعب (أي${\displaystyle e\in P_{i}-Q_{i}}$) تقليل الإمكانات عن طريق${\displaystyle d_{e}(x_{e})}$والعناصر التي ينضم إليها اللاعب (أي${\displaystyle e\in Q_{i}-P_{i}}$) زيادة الإمكانات عن طريق${\displaystyle d_{e}(x_{e}+1)}$هذا التغيير في الإمكانات هو بالضبط التغيير في التأخير بالنسبة للاعب i ، لذا${\displaystyle \Phi }$هي في الواقع دالة محتملة.

لاحظ الآن أن أي حد أدنى من${\displaystyle \Phi }$هو توازن ناش بحت. عند تثبيت جميع اللاعبين باستثناء لاعب واحد، فإن أي تحسن في استراتيجية ذلك اللاعب يقابله انخفاض في${\displaystyle \Phi }$وهو أمر لا يمكن أن يحدث على الأقل. الآن، بما أن هناك عددًا محدودًا من التكوينات، وكل منها${\displaystyle d_{e}}$إذا كان رتيبًا، فهناك حالة توازن.

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

فيما يلي نعرض امتدادات واختلافات متنوعة على نموذج CG الأساسي.

أصبحت الاستراتيجيات الآن عبارة عن مجموعات من ملفات تعريف الاستراتيجيات.${\displaystyle f_{P}}$بالنسبة لمجموعة استراتيجية${\displaystyle S_{i}}$إذا كان حجمها n ، فإن مجموعة جميع الملفات الشخصية الصالحة هي مجموعة فرعية مضغوطة من${\displaystyle [0,r_{i}]^{n}}$نُعرّف الآن دالة الجهد على النحو التالي:${\displaystyle \textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz}$، واستبدال التكامل المنفصل بالتكامل القياسي.

كجزء من الاستراتيجية،${\displaystyle \Phi }$متصل:${\displaystyle d_{e}}$هي دالة متصلة بافتراض، و${\displaystyle x_{e}}$هي دالة متصلة للاستراتيجية. وبناءً على نظرية القيمة القصوى ،${\displaystyle \Phi }$يصل إلى أدنى مستوى عالمي له.

الخطوة الأخيرة هي إثبات أن الحد الأدنى من${\displaystyle \Phi }$هو بالفعل توازن ناش. لنفترض جدلاً وجود مجموعة من${\displaystyle f_{P}}$ذلك يقلل${\displaystyle \Phi }$لكنها ليست توازن ناش. إذن، بالنسبة لنوع ما i ، يوجد تحسين ما${\displaystyle Q\in S_{i}}$على الخيار الحالي P. أي،${\displaystyle \textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})}$الفكرة الآن هي أخذ كمية صغيرة${\displaystyle \delta <f_{P}}$من اللاعبين الذين يستخدمون الاستراتيجية P ونقلهم إلى الاستراتيجية Q. الآن لأي${\displaystyle x_{e}\in Q}$لقد قمنا بزيادة حمولتها بواسطة${\displaystyle \delta }$، لذا فإن مصطلحها في${\displaystyle \Phi }$هو الآن${\displaystyle \textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz}$وباشتقاق التكامل، يكون هذا التغيير تقريبًا${\displaystyle \delta \cdot d_{e}(x_{e})}$، مع وجود خطأ${\displaystyle \delta ^{2}}$ينطبق التحليل المكافئ للتغيير عندما ننظر إلى الحواف في P.

وبالتالي، فإن التغير في الجهد يساوي تقريبًا${\displaystyle \textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))}$وهو أقل من الصفر. وهذا تناقض، لأنه حينها${\displaystyle \Phi }$لم يتم تقليلها إلى الحد الأدنى. لذلك، يجب أن يكون الحد الأدنى من${\displaystyle \Phi }$يجب أن يكون توازن ناش.

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

قام كل من كومينيتي وكوريا وستير-موسى ^{[ 11 ]} بدراسة مخططات التدرج المتقطع القابلة للتقسيم مع دوال تأخير خطية مستقلة عن اللاعب:${\displaystyle d_{e,i}(x)=a_{e}\cdot x_{e}+b_{e}}$حيث يمثل x_{_e} الحمل على الحافة e ، و a_{_e} و b _{_e} ثابتان مستقلان عن اللاعب. وقد أظهروا دالة جهد محدبة تكون نقاطها الدنيا المطلقة هي نقاط توازن الطاقة الاحتمالية (PNE). هذا يعني أنه يمكن حساب نقاط توازن الطاقة الاحتمالية التقريبية من نوع إبسيلون في زمن متعدد الحدود باستخدام البرمجة المحدبة .

كما نظر هوانغ ^{[ 14 ]} في دوال التأخير الأفينية المستقلة عن اللاعب. وقد ابتكر خوارزمية توافقية لحساب PNE دقيق للرسوم البيانية المتسلسلة القابلة للتقسيم على الرسوم البيانية المتناظرة التي تحقق شرطًا هيكليًا طبيعيًا يسميه "مصممًا جيدًا" (على سبيل المثال، الرسوم البيانية المتسلسلة المتوازية ).

درس بهاسكار ولولاكابوري ^{[ 19 ]} شبكات CG قابلة للتجزئة ذات دوال تأخير محدبة مستقلة عن اللاعبين. وقدّما خوارزميتين لحساب توازن ناش التقريبي: الأولى أسية بالنسبة لعدد اللاعبين، والثانية أسية بالنسبة لعدد الحواف. كما بيّنا أنه في الشبكات العامة، يُعدّ تحديد ما إذا كان هناك توازن ناش حيث تكون تكلفة كل لاعب على الأكثر قيمة ثابتة معينة C مسألة صعبة من نوع NP .

قام كليم ووارود ^{[ 20 ] [ 21 ]} بدراسة شبكات التتابع المتسلسلة القابلة للتقسيم الذري باستخدام دوال تأخير خطية خاصة بكل لاعب${\displaystyle d_{e,i}(x)=a_{e,i}\cdot x_{e}+b_{e,i}}$حيث يمثل x _e الحمل على الحافة e ، و a _ei و b _ei ثوابت خاصة بكل لاعب. وقد أثبتوا أن حساب PNE هو مسألة كاملة من نوع PPAD .

درس هاركس وتيمرمانز ^{[ 22 ] [ 23 ]} شبكات التتابع الذرية القابلة للتقسيم مع مجموعات استراتيجيات فردية - حيث يجب على كل لاعب توزيع حمولته على الحواف (وليس على المسارات). وهذا يتوافق مع شبكة من m حافة متوازية بين المصدر والهدف. تسمح هذه الشبكات بوظائف تأخير خاصة بكل لاعب. التكلفة الإجمالية التي يتكبدها كل لاعب i هي${\displaystyle \sum _{e}x_{i,e}\cdot d_{e,i}(x)}$يقدمون خوارزمية لحساب PNE في وقت${\displaystyle O((nm)^{3}+n^{2}m^{14}\log(D/k_{0}))}$، حيث n هو عدد اللاعبين، و m هو عدد الحواف، و D هو الحد الأقصى للطلب الخاص باللاعب، و k ₀ هو أصغر حجم للحزمة.

ويشيرون أيضًا إلى أن حساب PNE في CGs القابلة للتجزئة الذرية مع استراتيجيات المفردة ووظائف التأخير الأفيني يمكن تقديمه كمشكلة تكامل خطي . ^{[ 23 ]}

تناول ميلشتايش ^{[ 24 ]} الحالة الخاصة لألعاب التآمر الموزونة، حيث تمثل كل استراتيجية موردًا واحدًا ("لعبة تآمر أحادية المورد")، وتكون الأوزان مستقلة عن الموارد ، ويمتلك جميع اللاعبين نفس مجموعة الاستراتيجيات. وقد تم إثبات ما يلي:

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

درس ميلشتايش الحالة الخاصة لألعاب الشبكة الموزونة، حيث تمثل كل استراتيجية مسارًا في رسم بياني غير موجه مُعطى ("لعبة الشبكة الموزونة"). وقد أثبت أن كل لعبة محدودة يمكن تمثيلها كلعبة ازدحام شبكي موزونة ، ذات دوال تكلفة غير متناقصة (ولكن ليس بالضرورة سالبة). ^{[ 25 ]} وهذا يعني أنه ليس لكل لعبة من هذا النوع توازن ناش محتمل. وقد قدم ليبمان وأوردا ^{[ 26 ]} ، وكذلك غومانز ميروكني وفيتا [27]، ^{أمثلة ملموسة على ألعاب الشبكة الموزونة التي لا تحتوي على توازن ناش محتمل. [ 28 ] وهذا يثير التساؤل} حول الشروط التي تضمن وجود توازن ناش محتمل.

على وجه الخصوص، نقول إن رسمًا بيانيًا معينًا G يضمن خاصية معينة إذا كانت كل شبكة موزونة CG التي تكون الشبكة الأساسية فيها هي G تمتلك تلك الخاصية. وقد وصف ميلشتايش ^{[ 29 ]} الشبكات التي تضمن وجود توازن ناش المحتمل، بالإضافة إلى خاصية التحسين المحدود، مع شرط إضافي يتمثل في أن اللاعب ذو الوزن الأقل لديه استراتيجيات مسموح بها بشكل ضعيف أكثر (رسميًا،${\displaystyle w_{i}<w_{j}}$يشير إلى${\displaystyle |S_{i}|\geq |S_{j}|}$أثبت ذلك.

• يضمن الرسم البياني G خاصية التحسين المحدود إذا وفقط إذا كان G متماثلًا شكليًا إما مع شبكة متوازية (رسم بياني مكون من شبكة واحدة أو أكثر من الشبكات أحادية الحافة المتصلة بالتوازي )، أو مع شبكة متوازية متصلة على التوالي بشبكة واحدة أو شبكتين أحاديتي الحافة. ^{​​( نظرية 2)}
• يضمن الرسم البياني G وجود شبكة PNE إذا وفقط إذا كان G متماثلًا طوبولوجيًا مع اتصال متسلسل لشبكة واحدة أو أكثر من مجموعة من ست "شبكات مسموحة"؛ وشرط مكافئ هو عدم تضمين أي شبكة من مجموعة ست "شبكات ممنوعة" في ^G. : نظرية ³

في الحالة الخاصة التي يُسمح فيها لكل لاعب باستخدام أي استراتيجية ("الحواف العامة")، توجد شبكات أكثر تضمن وجود PNE؛ ويُطرح توصيف كامل لهذه الشبكات كمشكلة مفتوحة . ^{[ 29 ]}

يحلل ميلشتايش ^{[ 30 ]} تأثير بنية الشبكة على كفاءة PNE:

• يضمن الرسم البياني G أن كل شبكة باريتو فعالة، إذا وفقط إذا لم يتم تضمين ثلاث "شبكات محظورة" بسيطة في G.
• يضمن الرسم البياني G عدم حدوث مفارقة برايس ، إذا وفقط إذا كان رسمًا بيانيًا متسلسلًا متوازيًا .

يحلل ميلشتايش ^{[ 31 ]} تأثير بنية الشبكة على تفرد تكاليف PNE:

• يضمن الرسم البياني G أن تكون تكاليف PNE فريدة إذا وفقط إذا كان G عبارة عن اتصال في سلسلة من شبكة واحدة أو أكثر من عدة أنواع بسيطة.
• لا يضمن الرسم البياني G أن تكون تكاليف PNE فريدة إذا وفقط إذا كان G يحتوي على شبكة مضمنة من نوع بسيط معين.

كما قام هولزمان ولو-يون ^{[ 32 ]} بتوصيف الشبكات التي تضمن أن كل شبكة ذرية لها PNE قوي ، أو PNE فريد، أو PNE فعال من حيث باريتو .

يقوم ريتشمان وشيمكين ^{[ 15 ]} بتوصيف الشبكات التي تضمن أن كل شبكة قابلة للتقسيم لها شبكة PNE فريدة.

نقول إن فئة C من الدوال تضمن خاصية معينة إذا كانت كل مجموعة متدرجة موزونة تكون فيها جميع دوال التأخير عناصر من C تمتلك تلك الخاصية.

• أثبت فوتاكيس وكونتوغيانيس وسبيراكيس ^{[ 33 ]} أن فئة الدوال الخطية تضمن وجود جهد دقيق، وبالتالي وجود PNE.
• أثبت باناجوبولو وسبيراكيس ^{[ 34 ]} أن فئة الدوال الأسية تضمن وجود جهد مرجح، وبالتالي وجود PNE.
• أثبت هاركس وكليم ومورينغ ^{[ 35 ]} أن فئة من الدوال تضمن وجود جهد دقيق، إذا وفقط إذا كانت تحتوي على دوال خطية فقط . ويبقى هذا التوصيف صحيحًا عند حصره في ألعاب اللاعبين، وألعاب الموارد الثلاثة، وألعاب المجموعة الواحدة، والألعاب ذات الاستراتيجيات المتناظرة، أو الألعاب ذات الأوزان الصحيحة. علاوة على ذلك، تضمن فئة من الدوال وجود جهد مرجح، إذا وفقط إذا كانت (1) تحتوي على دوال خطية فقط، أو (2) تحتوي على دوال أسية فقط من الشكل${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$، أين${\displaystyle \phi }$ينطبق هذا على جميع الموارد. ويظل هذا التوصيف صحيحًا عند اقتصاره على ألعاب رباعية اللاعبين، أو ألعاب رباعية الموارد، أو ألعاب أحادية الموارد، أو ألعاب ذات استراتيجيات متناظرة، أو ألعاب ذات أوزان صحيحة. أما بالنسبة للألعاب ثنائية اللاعبين، فإن فئة من الدوال تضمن وجود جهد مرجح، إذا وفقط إذا كانت جميع الدوال فيها من الشكل التالي:${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$، حيث f دالة رتيبة (وهي نفسها لجميع الموارد).
• أثبت هاركس وكليم ^{[ 36 ]} نتيجة مماثلة لوجود PNE: فقد أثبتا أن فئة من الدوال تضمن وجود PNE إذا وفقط إذا كان (1) تحتوي فقط على دوال خطية، أو (2) تحتوي فقط على دوال أسية من الشكل${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$، أين${\displaystyle \phi }$ينطبق هذا على جميع الموارد. ويظل هذا التوصيف صحيحًا عند اقتصاره على ألعاب ثلاثية اللاعبين. أما في الألعاب ثنائية اللاعبين، فإن فئة من الدوال تضمن وجود توازن ناش المحتمل إذا وفقط إذا كانت جميع الدوال فيها من الشكل التالي:${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$، حيث f دالة رتيبة (وهي نفسها لجميع الموارد).

درس كلٌّ من غارينغ ومونين وتيمان ^{[ 10 ]} شبكات التتابع الموزونة مع تأخيرات خاصة بكل لاعب. وقد تناولوا التدفقات القابلة للتجزئة وغير القابلة للتجزئة. وعندما تكون دوال التأخير خطية (بدون حد ثابت ، أي b _e = 0)، قدموا دالتين محتملتين جديدتين واستنتجوا نتائج حول حساب توازن الطاقة الاحتمالي.

توجد العديد من الأبحاث الأخرى حول ألعاب الازدحام الموزونة. ^{[ 37 ] [ 38 ] [ 34 ]}

قام ميلشتايش ^{[ 24 ]} بتقديم ودراسة نماذج التصادم ذات التكاليف الخاصة باللاعب في الحالة الخاصة التالية:

• يختار كل لاعب موردًا واحدًا (تسمى هذه الألعاب ألعاب الرسوميات أحادية المورد )؛
• يمتلك جميع اللاعبين نفس مجموعة الاستراتيجيات.

تُسمى هذه الحالة الخاصة من ألعاب التزاحم أيضًا بلعبة التزاحم . ^{[ 39 ] [ 40 ]} وهي تمثل بيئة يختار فيها العديد من الأشخاص في وقت واحد مكانًا للذهاب إليه (مثل غرفة أو مستوطنة أو مطعم)، ويتم تحديد مكافأتهم من خلال المكان وعدد اللاعبين الآخرين الذين يختارون نفس المكان.

في لعبة الازدحام، بالنظر إلى استراتيجية${\displaystyle P_{i}=\{e\}}$يواجه اللاعب i تأخيرًا${\displaystyle d_{i,e}(x_{e})}$إذا قام اللاعب بالتحوّل إلى استراتيجية مختلفة f ، فسيكون تأخيره${\displaystyle d_{i,f}(x_{f}+1)}$وبالتالي، يكون متجه الاستراتيجية PNE إذا وفقط إذا كان لكل لاعب i،${\displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)}$لكل e و f .

بشكل عام، قد لا تقبل الرسوم البيانية ذات التأخيرات الخاصة باللاعبين دالة احتمالية . على سبيل المثال، لنفترض وجود ثلاثة موارد x وy وz ولاعبين A وB بدوال التأخير التالية:

• ${\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)}$
• ${\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)}$

فيما يلي مسار تحسين دوري:${\displaystyle (z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)}$يُظهر هذا أن خاصية التحسين المحدود غير صحيحة، لذا لا يمكن أن يكون للعبة دالة كامنة (ولا حتى دالة كامنة ترتيبية معممة). ومع ذلك:

• بوجود موردين فقط، تتحقق خاصية التحسين المحدود. ^{[ 24 ] : نظرية 1.} ومن ثم، يوجد توازن ناش المثالي.
• بوجود لاعبين فقط، تتحقق جميع خصائص الاستجابة المثلى المحدودة. وبالتالي، يوجد توازن ناش المثالي.

عند وجود ثلاثة لاعبين أو أكثر، قد تكون مسارات الاستجابة المثلى دورية. مع ذلك، لا يزال لكل لعبة CG توازن ناش محتمل. ^{[ 24 ] : نظرية 2.} البرهان بنائي ويُظهر خوارزمية تجد توازن ناش في مدة لا تتجاوز${\displaystyle {n+1 \choose 2}}$خطوات. علاوة على ذلك، كل مخطط تدرجي ضعيف غير دوري : لأي متجه استراتيجية أولي، يوجد على الأقل مسار استجابة مثلى واحد يبدأ من هذا المتجه بطول لا يتجاوز${\displaystyle r{n+1 \choose 2}}$، والتي تنتهي عند حالة توازن. ^{[ 24 ] : نظرية 3}

كل لعبة ازدحام قابلة للحل بالتتابع . ^{[ 39 ]} وهذا يعني أنه، لأي ترتيب للاعبين، فإن اللعبة المتتابعة التي يختار فيها كل لاعب استراتيجية بدوره، لها توازن مثالي في اللعبة الفرعية، حيث تكون تصرفات اللاعبين توازنًا مثاليًا في اللعبة الأصلية المتزامنة. كل لعبة ازدحام لها توازن مثالي قوي واحد على الأقل ؛ ^{[ 41 ]} ويمكن الوصول إلى كل توازن مثالي قوي في لعبة ازدحام كتوازن مثالي في اللعبة الفرعية لنسخة متتابعة من اللعبة. ^{[ 39 ]}

بشكل عام، قد تحتوي لعبة الازدحام على العديد من حلول التوازن الأمثل (PNE). على سبيل المثال، لنفترض وجود n لاعبًا و n موردًا، وأن التأثير السلبي للازدحام على العائد أعلى بكثير من القيمة الإيجابية للموارد. عندئذٍ، يوجد n! من حلول التوازن الأمثل المختلفة: كل تطابق فردي بين اللاعبين والموارد يُعد حل توازن أمثل، حيث لا ينتقل أي لاعب إلى مورد يشغله لاعب آخر. مع ذلك، إذا تكررت لعبة الازدحام m مرة، فإن مجموعة حلول التوازن الأمثل تتقارب إلى نقطة واحدة عندما يؤول m إلى اللانهاية. علاوة على ذلك، في لعبة ازدحام "كبيرة" (غير ذرية)، يوجد عادةً حل توازن أمثل فريد. يتميز هذا الحل بخاصية مثيرة للاهتمام في نظرية المخططات. ليكن G مخططًا ثنائي الأجزاء ، حيث يُمثل أحد جانبيه اللاعبين والآخر الموارد، ويكون كل لاعب مجاورًا لجميع الموارد التي يختارها نسخه في حل التوازن الأمثل الفريد. عندئذٍ، لا يحتوي G على دورات. ^{[ 40 ]}

تتمثل إحدى الحالات الخاصة لوظائف التأخير الخاصة باللاعب في إمكانية فصل وظائف التأخير إلى عامل خاص باللاعب وعامل عام. وهناك حالتان فرعيتان:

• دوال التكلفة القابلة للفصل ضربياً :${\displaystyle d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})}$، أين${\displaystyle a_{i,e}}$هو ثابت يمثل التكلفة الأساسية للمورد e للاعب i ، و d هي دالة تأخير عامة (وهي نفسها لجميع الموارد).
• دوال التكلفة القابلة للفصل الجمعي : ^{[ 42 ]}${\displaystyle d_{i,e}(x_{e})=a_{i,e}+d(x_{e})}$، أين${\displaystyle a_{i,e}}$هو ثابت يمثل التكلفة الثابتة للمورد e للاعب i، و d هي دالة تأخير عامة (وهي نفسها لجميع الموارد).

عند النظر فقط إلى الاستراتيجيات البحتة، يكون هذان المفهومان متكافئين، لأن لوغاريتم حاصل الضرب هو مجموع. علاوة على ذلك، عندما يمتلك اللاعبون أوزانًا خاصة بالموارد، يمكن اختزال الإعداد ذي دوال التأخير الخاصة بالموارد إلى الإعداد ذي دالة تأخير عامة. تظهر الألعاب ذات دوال التكلفة القابلة للفصل في موازنة الأحمال، ^{[ 43 ]} وجداول الانتظار M/M/1 ، ^{[ 26 ]} واختيار الموائل . ^{[ 44 ]} فيما يلي معلومات معروفة عن ألعاب التتابع المتسلسلة الموزونة أحادية المجموعة ذات التكاليف القابلة للفصل: ^{[ 45 ]}

• إذا كانت التكاليف الأساسية${\displaystyle a_{i,e}}$مستقلة عن اللاعب (${\displaystyle a_{i,e}=a_{e}}$لكل لاعب i )، فإن CG لديها FIP، وبالتالي لديها PNE. وينطبق الشيء نفسه إذا كانت التكاليف الأساسية مستقلة عن الموارد (${\displaystyle a_{i,e}=a_{i}}$لكل مورد e ). ^{[ 43 ] [ 46 ]} يعتمد البرهان على دالة جهد متجهة. لكل حالة من حالات اللعبة، يكون الجهد عبارة عن متجه بحجم n يحتوي على تكاليف جميع اللاعبين، مرتبة من الأكبر إلى الأصغر. عندما ينحرف لاعب إلى مورد بتكلفة أقل بالنسبة له، يصبح متجه التكاليف أصغر بترتيب ليكسيمين .
• إذا كانت الأوزان مستقلة عن اللاعب (أو بمعنى آخر: إذا كانت دالة التكلفة غير موزونة وكانت دوال التأخير خاصة بالموارد)، فإنها تمتلك شرط التوازن الكامل، وبالتالي تمتلك توازن ناش المحتمل. ^{[ 47 ] [ 42 ]} إذا كانت دوال التكلفة قابلة للفصل الجمعي، فإن اللعبة تمتلك دالة جهد دقيقة. وتظل هذه النتيجة صحيحة حتى لو لم تكن دوال التكلفة تتزايد بشكل رتيب مع الحمل. أما إذا لم تكن دوال التكلفة قابلة للفصل الجمعي، فقد لا يتحقق شرط التوازن الكامل، وقد لا توجد دالة جهد، ولكن سيظل توازن ناش المحتمل موجودًا. ^{[ 24 ] : نظرية 2}
• إذا كانت الأوزان مستقلة عن الموارد، فإن توازن الطاقة الاحتمالي موجود في الحالات التالية:
  • عندما يكون عدد اللاعبين ثلاثة على الأكثر ، توجد حالة توازن ناش المثالي (PNE)، ^{[ 48 ] : النتيجة 3،} على الرغم من أن خاصية تحسين الاستجابة المثلى قد لا تنطبق. في المقابل، توجد لعبة CG ذات تكاليف منفصلة وأوزان مستقلة عن الموارد مع ثمانية لاعبين لا توجد فيها حالة توازن ناش المثالي. ^{[ 45 ] : النظرية 3}
  • عندما تكون دوال التكلفة قابلة للفصل الجمعي مع دوال التكلفة المتغيرة الخطية، فإنّ نظام التكاليف المنسقة (CG) يمتلك إمكانات مرجحة، وبالتالي يمتلك نقطة توازن فيدرالية (FIP)، وبالتالي يمتلك نقطة توازن ناش (PNE). ^{[ 48 ] : نظرية 6}
  • عندما تكون دوال التكلفة قابلة للفصل الجمعي مع دالة تكلفة متغيرة لوغاريتمية، ولا يتجاوز عدد اللاعبين ثلاثة، فإن لعبة الكومنولث تتمتع بخاصية تحسين الاستجابة المثلى، وبالتالي تمتلك توازن ناش المثالي. مع ذلك، قد لا تمتلك خاصية التحسين المحدود. ^{[ 10 ]} أما بالنسبة لأكثر من ثلاثة لاعبين، فإن وجود توازن ناش المثالي يبقى غير مؤكد.

كل شبكة تفاضلية أحادية موزونة ذات تفضيلات خاصة بكل لاعب قابلة للفصل، تكون متماثلة مع شبكة تفاضلية موزونة ذات تفضيلات مستقلة عن اللاعب. ^{[ 45 ] [ 2 ]}

درس ميلشتايش الحالة الخاصة لألعاب الشبكة ذات التكاليف الخاصة بكل لاعب، حيث تمثل كل استراتيجية مسارًا في رسم بياني معين ("لعبة شبكة ذات تكاليف خاصة"). وقد أثبت أن كل لعبة محدودة يمكن تمثيلها كلعبة ازدحام شبكي (غير موزونة) ذات تكاليف خاصة بكل لاعب، مع دوال تكلفة غير متناقصة (ولكن ليس بالضرورة سالبة). ^{[ 25 ]} ويُطرح توصيف كامل للشبكات التي تضمن وجود توازن ناش-إنجلترا في مثل هذه الألعاب كمسألة مفتوحة. ^{[ 29 ]}

يُعدّ إثبات وجود حلٍّ مثاليٍّ مُرضٍ (PNE) إثباتًا بنائيًا: فهو يُبيّن خوارزميةً محدودةً (مسار تحسين) تُؤدّي دائمًا إلى إيجاد حلٍّ مثاليٍّ مُرضٍ. وهذا يُثير التساؤل حول عدد الخطوات اللازمة لإيجاد هذا الحلّ المثاليّ المُرضٍ؟ وقد أثبت فابريكانت وباباديميتريو وتالوار ^{[ 46 ]} ما يلي:

• إذا كانت جميع الاستراتيجيات مسارات في شبكة ("شبكة CG")، وكان لدى جميع اللاعبين نفس مجموعة الاستراتيجيات ("شبكة CG متناظرة")، فإنه يمكن حساب توازن ناش المحتمل في وقت متعدد الحدود عن طريق تعظيم الجهد الكامن، من خلال اختزاله إلى تدفق بأقل تكلفة . ويمكن تكييف الخوارزمية مع شبكات CG غير الذرية: ففي ظل افتراضات معينة تتعلق بسلاسة اللعب، يمكن تقريب توازن ناش في مثل هذه اللعبة في وقت متعدد الحدود بشكل كبير .
• إذا كانت الاستراتيجيات عبارة عن مجموعات فرعية عامة، أو إذا كان لدى اللاعبين مجموعات مختلفة من الاستراتيجيات ("اللعب الجماعي غير المتماثل")، فإن حساب توازن ناش المحتمل يُعد مسألة كاملة من فئة PLS . وهذا يعني وجود أمثلة ذات مسارات تحسين طويلة أُسّيًا. كما يعني أيضًا أن إيجاد توازن ناش يمكن الوصول إليه من حالة محددة يُعد مسألة كاملة من فئة PSPACE .
• لكل مشكلة في فئة التعقيد PLS (بشكل أساسي، كل مشكلة بحث محلي)، توجد لعبة احتمالية ترتيبية مع عدد متعدد الحدود من اللاعبين، بحيث تكون مجموعة توازنات ناش النقية مساوية لمجموعة الحلول المثلى المحلية.

قام كل من Even-Dar و Kesselman و Mansour ^{[ 43 ]} بتحليل عدد الخطوات المطلوبة للتقارب نحو التوازن في بيئة موازنة الأحمال.

يقدم كاراغيانيس، فانيلي، غرافين، وسكوباليك ^{[ 49 ]} خوارزمية لحساب تقريب PNE ذي عامل ثابت. على وجه الخصوص:

• باستخدام دوال التأخير الخطية، تكون نسبة التقريب 2+ε، ويكون وقت التشغيل متعدد الحدود في عدد اللاعبين وعدد الموارد و 1/ε.
• عندما تكون دوال التأخير عبارة عن كثيرات حدود من الدرجة d ، فإن نسبة التقريب هي d ^{O( d )} .

تحدد خوارزميتهم سلسلة قصيرة من أفضل تحركات الاستجابة، مما يؤدي إلى توازن تقريبي. كما يوضحون أنه بالنسبة لأنظمة التدرج المترافق الأكثر عمومية، فإن تحقيق أي تقريب متعدد الحدود لمسألة توازن التوازن الجزئي هو مسألة كاملة من نوع PLS.

يقدم فوتاكيس، وكونتوغيانيس، وسبيراكيس ^{[ 33 ]} خوارزميةً تجد، في أي شبكة مُرجّحة ذات دوال تأخير خطية، توازنًا مثاليًا في وقت شبه متعدد الحدود (متعدد الحدود بالنسبة لعدد اللاعبين n ومجموع أوزانهم W ). خوارزميتهم هي خوارزمية جشعة لأفضل استجابة : يدخل اللاعبون اللعبة بترتيب تنازلي حسب وزنهم، ويختارون أفضل استجابة لاستراتيجيات اللاعبين الحاليين.

أظهر باناجوبولو وسبيراكيس ^{[ 34 ]} أدلة تجريبية على أن خوارزمية فوتاكيس وكونتوغيانيس وسبيراكيس تعمل في الواقع في وقت متعدد الحدود في n و log W. كما اقترحوا متجه استراتيجية أولي يعمل على تسريع هذه الخوارزمية بشكل كبير.

بشكل عام، قد لا تمتلك شبكة CG الموزونة شبكة PNE. يثبت ميلشتايش ^{[ 29 ]} أن تحديد ما إذا كانت شبكة CG الموزونة المعطاة تمتلك شبكة PNE هو مسألة صعبة الحل (NP-hard) حتى في الحالات التالية:

• يوجد لاعبان؛ يُسمح لجميع اللاعبين باستخدام جميع المسارات؛ جميع دوال التكلفة غير سالبة.
• يوجد لاعبان؛ والتكلفة الإجمالية غير مرجحة؛ والتكاليف خاصة بكل لاعب وغير سالبة.

يتم البرهان عن طريق الاختزال من مسألة المسارات الموجهة المنفصلة الحواف. ^{[ 50 ]}

يقدم كاراغيانيس، فانيلي، غرافين، وسكوباليك ^{[ 51 ]} خوارزمية لحساب تقريب PNE ذي عامل ثابت في الشبكات المتدرجة الموزونة. على وجه الخصوص:

• في حالة دوال التأخير الخطية، تكون نسبة التقريب هي${\displaystyle {\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )}$، ووقت التشغيل متعدد الحدود في عدد اللاعبين، وعدد الموارد، و 1/ε.
• عندما تكون دوال التأخير متعددة الحدود من الدرجة d ، فإن نسبة التقريب هي${\displaystyle d^{2d+o(d)}}$.

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