الاستراتيجية (نظرية اللعبة)

في نظرية الألعاب ، الحركة أو الفعل أو اللعب هو أي من الخيارات التي يمكن للاعب اختيارها في بيئة حيث تعتمد النتيجة المثلى ليس فقط على أفعاله الخاصة ولكن على أفعال الآخرين. ^[1] يتعلق الانضباط بشكل أساسي بتصرف اللاعب في لعبة تؤثر على سلوك أو أفعال اللاعبين الآخرين. تشمل بعض الأمثلة على "الألعاب" الشطرنج والبريدج والبوكر والاحتكار والدبلوماسية أو البارجة. ^[2]

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

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

ملف تعريف الاستراتيجية (يُطلق عليه أحيانًا مجموعة الاستراتيجيات ) هو مجموعة من الاستراتيجيات لجميع اللاعبين والتي تحدد بالكامل جميع الإجراءات في اللعبة. يجب أن يتضمن ملف تعريف الاستراتيجية استراتيجية واحدة فقط لكل لاعب.

تحدد مجموعة استراتيجيات اللاعب الاستراتيجيات المتاحة له للعب.

يمتلك اللاعب مجموعة محدودة من الاستراتيجيات إذا كان لديه عدد من الاستراتيجيات المنفصلة المتاحة له. على سبيل المثال، تتألف لعبة حجر ورقة مقص من حركة واحدة يقوم بها كل لاعب - ويتم تنفيذ حركة كل لاعب دون معرفة حركة الآخر، وليس كاستجابة - لذا فإن كل لاعب لديه مجموعة محدودة من الاستراتيجيات {حجر ورقة مقص}.

إن مجموعة الاستراتيجيات تكون غير محدودة بخلاف ذلك. على سبيل المثال، تحتوي لعبة تقطيع الكعكة على استمرارية محدودة للاستراتيجيات في مجموعة الاستراتيجيات {قطع أي جزء من الكعكة يتراوح بين صفر بالمائة و100 بالمائة}.

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

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

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

على سبيل المثال، بالمعنى الدقيق للكلمة في لعبة Ultimatum، يمكن للاعب أن يتبع استراتيجيات مثل: رفض عروض ($1، $3، $5، ...، $19)، وقبول عروض ($0، $2، $4، ...، $20) . يؤدي تضمين كل هذه الاستراتيجيات إلى توفير مساحة استراتيجية كبيرة جدًا ومشكلة صعبة إلى حد ما. قد يعتقد منظّر اللعبة بدلاً من ذلك أنه يمكنه تقييد مجموعة الاستراتيجية على: {رفض أي عرض ≤ x ، قبول أي عرض > x ؛ بالنسبة لـ x في ($0، $1، $2، ...، $20)}.

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

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

وبطبيعة الحال، يمكننا أن ننظر إلى الاستراتيجية النقية باعتبارها حالة منحطّة من الاستراتيجية المختلطة، حيث يتم اختيار تلك الاستراتيجية النقية المعينة باحتمال 1 وكل استراتيجية أخرى باحتمال 0 .

الاستراتيجية المختلطة تمامًا هي استراتيجية مختلطة حيث يعين اللاعب احتمالية إيجابية تمامًا لكل استراتيجية نقية. (الاستراتيجيات المختلطة تمامًا مهمة لتحسين التوازن مثل التوازن المثالي لليد المرتعشة .)

في ركلة جزاء كرة القدم، يجب على المسدد أن يختار ما إذا كان سيسدد إلى الجانب الأيمن أو الأيسر من المرمى، وفي الوقت نفسه يجب على حارس المرمى أن يقرر أي اتجاه سيمنعه. أيضًا، يكون للمسدد اتجاه يكون أفضل في التسديد فيه، وهو اليسار إذا كان يميني القدم. توضح مصفوفة لعبة كرة القدم هذا الموقف، وهو شكل مبسط للعبة درسه تشيابوري وليفيت وجروسكلوز (2002). ^[3] تفترض أنه إذا خمن حارس المرمى بشكل صحيح، فسيتم منع الركلة، والتي يتم ضبطها على المكافأة الأساسية 0 لكلا اللاعبين. إذا خمن حارس المرمى خطأ، فمن المرجح أن تدخل الركلة إذا كانت إلى اليسار (مكافآت +2 للمسدد و-2 لحارس المرمى) مما لو كانت إلى اليمين (المكافأة الأقل +1 للمسدد و-1 لحارس المرمى).

		حارس المرمى
		انحنى إلى اليسار	انحنى إلى اليمين
كيكر	ركلة يسار	0, 0	+2, -2
	ركلة يمينية	+1, -1	0, 0
المكافأة على لعبة كرة القدم (المسدد، حارس المرمى)

لا تتمتع هذه اللعبة بتوازن إستراتيجي بحت، لأن أحد اللاعبين أو الآخر سوف ينحرف عن أي نمط من الإستراتيجيات - على سبيل المثال، (يسار، يسار) ليس توازنًا لأن اللاعب الذي يسدد الكرة سوف ينحرف إلى اليمين ويزيد مكافأته من 0 إلى 1.

يتم إيجاد توازن الاستراتيجية المختلطة للمسدد من حقيقة أنه سوف ينحرف عن العشوائية ما لم تكن مكافآته من الركلة اليسرى والركلة اليمنى متساوية تمامًا. إذا انحنى حارس المرمى إلى اليسار باحتمالية g، فإن المكافأة المتوقعة للمسدد من الركلة اليسرى هي g(0) + (1-g)(2)، ومن الركلة اليمنى هي g(1) + (1-g)(0). معادلة هذه تعطي g= 2/3. وبالمثل، يكون حارس المرمى على استعداد للتوزيع العشوائي فقط إذا اختار المسدد احتمالية الاستراتيجية المختلطة k بحيث تكون مكافأة الميل إلى اليسار k(0) + (1-k)(-1) مساوية لمكافأة الميل إلى اليمين k(-2) + (1-k)(0)، لذا k = 1/3. وبالتالي، فإن توازن الاستراتيجية المختلطة هو (Prob(Kick Left) = 1/3, Prob(Lean Left) = 2/3).

في حالة التوازن، يسدد الرامي الكرة إلى جانبه الأفضل بنسبة 1/3 فقط من المرات. وذلك لأن حارس المرمى يحرس هذا الجانب أكثر. وأيضًا، في حالة التوازن، لا يبالي الرامي بالطريقة التي يسدد بها الكرة، ولكن لكي يكون الوضع متوازنًا، يجب أن يختار احتمالًا بنسبة 1/3 بالضبط.

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

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

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

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

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

يقدم Piccione و Rubinstein (1997) مثالاً مشهورًا لسبب ضرورة التذكر المثالي للتكافؤ ^{من خلال لعبتهما} Absent -Minded Driver .

يجمع تكافؤ النتائج بين الاستراتيجية المختلطة والسلوكية للاعب i فيما يتعلق بالاستراتيجية البحتة لخصم اللاعب i. يتم تعريف تكافؤ النتائج على أنه الموقف الذي يجب أن يكون فيه توزيع نتائج الاستراتيجية المختلطة والسلوكية متساويًا لأي استراتيجية مختلطة وسلوكية يتخذها اللاعب i، استجابةً لأي استراتيجية نقية يلعبها خصم اللاعب I. يمكن وصف هذا التكافؤ بالصيغة التالية: (Q^(U(i), S(-i)))(z) = (Q^(β(i), S(-i)))(z)، حيث تصف U(i) الاستراتيجية المختلطة للاعب i، وتصف β(i) الاستراتيجية السلوكية للاعب i، وS(-i) هي استراتيجية الخصم. ^[8]

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

بدون معلومات كاملة (أي معلومات غير كاملة)، يتخذ اللاعبون خيارًا عند كل عقدة قرار دون معرفة القرارات التي سبقتها. لذلك، يمكن لاستراتيجية اللاعب المختلطة أن تنتج نتائج لا تستطيع استراتيجيته السلوكية إنتاجها، والعكس صحيح. يتضح هذا في لعبة السائق شارد الذهن . مع التذكر والمعلومات المثالية، يكون لدى السائق استراتيجية نقية واحدة، وهي [الاستمرار، الخروج]، حيث يكون السائق على دراية بالتقاطع (أو عقدة القرار) الذي يوجد عنده عندما يصل إليها. من ناحية أخرى، بالنظر إلى مرحلة التخطيط الأمثل فقط، يتم تحقيق أقصى قدر من المكافأة من خلال الاستمرار عند التقاطعين، مع تعظيم p = 2/3 (مرجع). توضح هذه اللعبة البسيطة التي يلعبها لاعب واحد أهمية التذكر المثالي لتكافؤ النتائج، وتأثيره على الألعاب ذات الشكل الطبيعي والممتد. ^[9]

• توازن ناش
• هافن (نظرية الرسم البياني)
• استراتيجية مستقرة تطوريا