لعبة متكررة

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

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

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

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

يمكن تقسيم الألعاب المتكررة بشكل عام إلى فئتين، محدودة وغير محدودة، وذلك اعتمادًا على المدة التي يتم فيها لعب اللعبة.

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

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

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

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

• حدود الإمكانيات - إذا أسفرت اللعبة عن سلسلة من النتائج${\displaystyle x_{t}}$واللاعب i لديه وظيفة الأدوات الأساسية للعبة${\displaystyle u_{i}}$، فائدة اللاعب i هي:

${\displaystyle U_{i}=\lim _{T\to \infty }\inf {\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})}$

• الخصم - إذا انخفضت قيمة اللعبة لدى اللاعب (أ) بمرور الوقت تبعًا لعامل الخصم${\displaystyle \delta <1}$إذن، فائدة اللاعب i هي:

${\displaystyle U_{i}=\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t})}$

بالنسبة للاعبين الصبورين بما فيه الكفاية (على سبيل المثال، أولئك الذين لديهم قيم عالية بما فيه الكفاية من${\displaystyle \delta }$)، يمكن إثبات أن كل استراتيجية لها عائد أكبر من عائد الحد الأدنى الأقصى يمكن أن تكون توازن ناش - مجموعة كبيرة جدًا من الاستراتيجيات.

تتيح الألعاب المتكررة دراسة التفاعل بين المكاسب الفورية والحوافز طويلة الأجل. اللعبة المتكررة بشكل محدود هي لعبة تُعاد فيها نفس المرحلة المكونة من جولة واحدة بشكل متكرر على مدى عدد من الفترات الزمنية المنفصلة، ​​أو الجولات. يُرمز لكل فترة زمنية بـ 0 < t ≤ T، حيث T هو العدد الإجمالي للفترات. ويُحسب العائد النهائي للاعب بجمع عوائده من كل جولة. ^{[ 1 ]}

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

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

أما الألعاب ذات التكرار المحدود والتي يكون عدد فتراتها الزمنية غير معروف أو غير محدد، فتُعتبر بمثابة لعبة ذات تكرار لا نهائي. ولا يمكن تطبيق الاستقراء العكسي على هذه الألعاب.

مثال 1: لعبة متكررة من مرحلتين مع توازنات ناش متعددة

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

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

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

المثال الثاني: لعبة متكررة من مرحلتين مع توازن ناش فريد

يُظهر المثال 2 لعبة متكررة من مرحلتين مع توازن ناش فريد. ولأن هناك توازنًا واحدًا فقط، فلا توجد آلية لأي من اللاعبين للتهديد بالعقاب أو الوعد بالمكافأة في الجولة الثانية. وبالتالي، فإن الاستراتيجية الوحيدة التي يمكن اعتبارها توازن ناش مثاليًا في اللعبة الفرعية هي لعب استراتيجية توازن ناش الفريدة (D, N) في كل جولة. في هذه الحالة، يعني ذلك لعب (D, N) في كل مرحلة لمرحلتين (n=2)، ولكن هذا ينطبق على أي عدد محدود من المراحل n . ^{[ 3 ]} تفسير ذلك: تعني هذه النتيجة أن وجود أفق زمني معروف ومحدود يُعيق التعاون في كل جولة من جولات اللعبة. لا يكون التعاون ممكنًا في الألعاب المتكررة إلا عندما يكون عدد الجولات غير محدود أو غير معروف.

بشكل عام، يسهل حل الألعاب المتكررة باستخدام الاستراتيجيات التي توفرها النظريات الشائعة . أما الألعاب المتكررة المعقدة، فيمكن حلها باستخدام تقنيات متنوعة، يعتمد معظمها بشكل كبير على الجبر الخطي والمفاهيم الواردة في اللعب الافتراضي . ويمكن استنتاج أنه بالإمكان تحديد خصائص عوائد التوازن في الألعاب المتكررة بلا حدود. ومن خلال التناوب بين عائدين، ولنقل a و f، قد يكون متوسط ​​العائد عبارة عن متوسط ​​مرجح بين a و f.

قد تتضمن الألعاب المتكررة بعض المعلومات غير الكاملة. وقد كان أومان وماشلر من الرواد في مجال الألعاب المتكررة ذات المعلومات غير الكاملة . ^{[ 4 ]} في حين أنه من الأسهل التعامل مع حالة يكون فيها أحد اللاعبين على علم بالمعلومات والآخر غير مُطلع عليها، وعندما تكون المعلومات التي يتلقاها كل لاعب مستقلة، فإنه من الممكن التعامل مع ألعاب المحصلة الصفرية ذات المعلومات غير الكاملة لدى كلا الجانبين والإشارات غير المستقلة. ^{[ 5 ]}

• فودنبرج، درو؛ تيرول، جان (1991). نظرية اللعبة . كامبريدج: مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 0-262-06141-4.
• مايلات، ج. وسامويلسون، ل. (2006). الألعاب المتكررة والسمعة: علاقات طويلة الأمد . نيويورك: مطبعة جامعة أكسفورد. ISBN 0-19-530079-3.
• أوزبورن، مارتن جيه؛ روبنشتاين، أرييل (1994). دورة في نظرية الألعاب . كامبريدج: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-15041-7.
• سورين، سيلفان (2002). مدخل إلى الألعاب المتكررة ذات المجموع الصفري . برلين: سبرينغر. ISBN 3-540-43028-8.

• حلٌّ لمسألة البوكر باستخدام نظرية الألعاب مع اللعب الافتراضي ( مؤرشف بتاريخ ١١ مارس ٢٠٠٧ في أرشيف الإنترنت)
• ملاحظات حول نظرية الألعاب المتعلقة بالألعاب المتكررة ، مؤرشفة بتاريخ 4 نوفمبر 2016 في أرشيف الإنترنت (Wayback Machine).
• حول الألعاب المتكررة ومفارقة سلسلة المتاجر