ثمن الفوضى

معضلة السجين

وفي هذا الصدد، بما أن اللعبة لها توازن ناش فريد، فإن PoS يساوي PoA وهو 5 كذلك.

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

في هذا الإطار، لنفترض لعبة 2x2 المسماة معضلة السجين، والتي يتم تحديدها بواسطة مصفوفة التكلفة التالية:

جدولة العمل

علاوةً على ذلك، ومن الأمثلة الأكثر طبيعية جدولة العمل (Job Scheduling). لدينا: لاعبًا، ولكلٍّ منهم مهمّة يريد تشغيلها. يمكن لكلٍّ منهم اختيار إحدى: آلة لتشغيل مهمّته. يقارن ثمن الفوضى بين الحالة التي يكون فيها اختيار الآلات موجَّهًا/مُدارًا مركزيًّا، والحالة التي يختار فيها كل لاعب الآلة التي ستُشغّل مهمّته بأسرع ما يمكن.

وعلى صعيد آخر، التكلفة بالنسبة للاعب هي ، أي حِمل الآلة التي اختارها. ونعتبر دالة التكلفة المساواتية (Egalitarian) ، وتُسمّى هنا زمن الإنجاز الكلّي (Makespan).

كذلك، كل آلة لها سرعة ، وكل مهمّة لها وزن ، ويختار كل لاعب آلةً لتشغيل مهمّته عليها، وبالتالي فإن استراتيجيات كل لاعب هي ، ونُعرّف الحِمل (Load) على الآلة بأنه:

التعريف الرياضي

في هذا الإطار، هناك مفهوم ذو صلة هو ثمن الاستقرار (POS) حيث يقيس النسبة بين الحلّ "المركزي" الأمثل و"أفضل توازن

أمثلة

وفي هذا السياق، لِنَعتَبِر لعبة ، مُعرَّفة بمجموعة من اللاعبين ، مجموعة إستراتيجيات لكل لاعب، ودالة منفعة (حيث تُسمّى مجموعة النتائج). يمكننا تعريف مقياس لكفاءة كل نتيجة نسمّيه دالة الرفاهية . ومن الأمثلة الطبيعية التي يمكن اختيارها لتعريف دالة الرفاهية: أن نأخذ مجموع منافع جميع اللاعبين (وهذا ما يُسمّى الهدف النفعي / Utilitarian)

ومن جهة أخرى، ، أو أدنى منفعة (هدف العدالة أو المساواتية) . ..، أو أي دالة ذات معنى للعبة المُحلَّلة ويُرغَب في تعظيمها.

وفي هذا السياق، نعلم أنه: بحكم التعريف. ومن المتوقّع أن تكون الخسارة في الكفاءة الناتجة عن قيود نظرية الألعاب واقعةً في مكانٍ ما بين ثمن الاستقرار و ثمن الفوضى.

في حالة دالة التكلفة:

من جانب آخر، يمكننا تعريف مجموعة جزئية أن تكون مجموعة الاستراتيجيات في حالة توازن (مثلًا، مجموعة توازنات ناش ). ويُعرَّف ثمن الفوضى بأنه النسبة بين الحل الأمثل "المركزي" و"أسوأ توازن":

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