توازن ناش القوي

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

أثبت نيسا وتيان ^{[ 3 ]} أن SNE موجود إذا تحققت الشروط التالية:

• مساحة الاستراتيجية لكل لاعب مضغوطة ومحدبة ؛
• دالة العائد لكل لاعب مقعرة ومتصلة؛
• خاصية اتساق التحالف : يوجد متجه وزن w ، يخصص متجه وزن w _S لكل تحالف ممكن S ، بحيث لكل ملف تعريف استراتيجية x ، يوجد ملف تعريف استراتيجية z حيث z _S يزيد من الرفاه الاجتماعي المرجح (بواسطة w S ₎ لأعضاء S ، بالنظر إلى x _{− S.}
  • لاحظ أنه إذا كان x نفسه SNE، فيمكن اعتبار z مساوياً لـ x . أما إذا لم يكن x SNE، فإن الشرط يتطلب إمكانية الانتقال إلى ملف تعريف استراتيجي مختلف يمثل أفضل استجابة للرفاهية الاجتماعية لجميع التحالفات في آن واحد.

على سبيل المثال، لنفترض لعبة بين لاعبين، بمساحتي استراتيجية [1/3، 2] و[3/4، 2]، وهما مساحتان متراصتان ومحدبتان بوضوح. دوال المنفعة هي:

• u1(x) = - x1 ² + x2 + 1
• u2(x) = x1 - x2 ² + 1

وهي متصلة ومحدبة. يبقى التحقق من اتساق التحالف. لكل مجموعة استراتيجية x، نتحقق من أفضل استجابة مرجحة لكل تحالف:

• بالنسبة للتحالف {1}، نحتاج إلى إيجاد، لكل x2، max _y1 (-y1 ² + x2 + 1)؛ من الواضح أن الحد الأقصى يتم تحقيقه عند أصغر نقطة في فضاء الاستراتيجية، وهي y1=1/3.
• بالنسبة للتحالف {2}، نرى بالمثل أنه لكل x1، يتم تحقيق أقصى عائد عند أصغر نقطة، y2=3/4.
• بالنسبة للتحالف {1,2}، بأوزان w1 و w2، نحتاج إلى إيجاد القيمة القصوى _{لـ y1 و y2} (w1*(-y1² ⁺ y2 + 1)+w2*(y1 - y2² ⁺ 1)). باستخدام اختبار المشتقة ، نجد أن نقطة القيمة القصوى هي y1 = w2/(2*w1) و y2 = w1/(2*w2). وبأخذ w1 = 0.6 و w2 = 0.4، نحصل على y1 = 1/3 و y2 = 3/4.

إذن، مع w1=0.6 و w2=0.4، فإن النقطة (1/3، 3/4) تمثل استجابة مثلى متسقة للرفاهية الاجتماعية لجميع التحالفات في آن واحد. وبالتالي، يوجد توازن نيترو اجتماعي عند النقطة نفسها (1/3، 3/4).

فيما يلي مثالٌ يفشل فيه اتساق التحالف، ولا يوجد فيه بالفعل خوارزمية ناش-نيوز. ^{[ 3 ] : مثال 3.1:} يوجد لاعبان، ومساحة استراتيجياتهما هي [0،1]. دوال المنفعة الخاصة بهما هي:

• u1(x) = -x1 + 2*x2;
• u2(س) = 2*x1 - x2.

يوجد توازن ناش فريد عند النقطة (0,0)، مع متجه العائد (0,0). ومع ذلك، فهو ليس توازن ناش المستقر (SNE) لأن التحالف {1,2} يمكن أن ينحرف إلى النقطة (1,1)، مع متجه العائد (1,1). في الواقع، يتم انتهاك اتساق التحالف عند x = (0,0): بالنسبة للتحالف {1,2}، لأي متجه وزن w _{∈ S} ، فإن أفضل استجابة للرفاه الاجتماعي تقع إما على الخط (1,0) - (1,1) أو على الخط (0,1) - (1,1)؛ لكن أي نقطة من هذا القبيل لا تُعد أفضل استجابة للاعب الذي يلعب الدور 1.

كما يقدم نيسا وتيان ^{[ 3 ]} شرطًا ضروريًا وكافيًا لوجود SNE، إلى جانب خوارزمية تجد SNE إذا وفقط إذا كانت موجودة.

كل حالة توازن ناش أحادي هي حالة توازن ناش. ويمكن ملاحظة ذلك من خلال النظر في انحراف التحالفات الفردية n .

كل تحالف ناش - نيوكليوفيلي ضعيف الكفاءة وفقًا لمبدأ باريتو . ويمكن ملاحظة ذلك من خلال النظر في انحراف التحالف الكبير - تحالف جميع اللاعبين.

كل SNE يقع في النواة ألفا الضعيفة وفي النواة بيتا الضعيفة . ^{[ 3 ]}

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

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

من المثير للدهشة أن مفهوم توازن ناش القوي لا يرتبط بمفهوم توازن ناش الضعيف . أي أن توازن ناش يمكن أن يكون قوياً وضعيفاً في آن واحد، أو أحدهما، أو لا هذا ولا ذاك.