لعبة محتملة

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

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

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

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

يترك${\displaystyle N}$ليكن عدد اللاعبين،${\displaystyle A}$مجموعة ملفات تعريف الإجراءات على مجموعات الإجراءات${\displaystyle A_{i}}$لكل لاعب و${\displaystyle u_{i}:A\to \mathbb {R} }$تكون دالة المكافأة للاعب${\displaystyle 1\leq i\leq N}$.

لعبة معينة${\displaystyle G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$نقول ذلك${\displaystyle G}$هي لعبة محتملة ذات دالة محتملة دقيقة (مرجحة، ترتيبية، ترتيبية معممة، أفضل استجابة) إذا${\displaystyle \Phi :A\rightarrow \mathbb {R} }$هي دالة جهد دقيقة (مرجحة، ترتيبية، ترتيبية معممة، أفضل استجابة، على التوالي) لـ${\displaystyle G}$سنعرّف هذه المفاهيم أدناه.

• ${\displaystyle \Phi }$تُسمى دالة جهد دقيقة إذا ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$،

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})}$

أي: عندما يلعب اللاعب${\displaystyle i}$يتحول من وضع التشغيل${\displaystyle a'}$إلى العمل${\displaystyle a''}$، التغير في الإمكانات${\displaystyle \Phi }$يساوي التغير في فائدة ذلك اللاعب.

• ${\displaystyle \Phi }$تُسمى دالة الجهد الموزون إذا كان هناك متجه${\displaystyle w\in \mathbb {R} _{++}^{N}}$بحيث${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$،

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))}$أي: عندما يغير اللاعب دوره، فإن التغيير في${\displaystyle \Phi }$يساوي التغير في منفعة اللاعب، مضروبًا في وزن موجب خاص باللاعب. كل دالة احتمالية دقيقة هي دالة احتمالية موزونة حيث wᵢ = 1 لجميع _قيم i .

• ${\displaystyle \Phi }$تُسمى دالة الجهد الترتيبي إذا ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$،

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Leftrightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$أي: عندما يغير اللاعب دوره، فإن إشارة التغيير في${\displaystyle \Phi }$يُساوي إشارة التغير في منفعة اللاعب، بينما قد يختلف مقدار التغير. كل دالة احتمالية مُرجّحة هي دالة احتمالية ترتيبية.

• ${\displaystyle \Phi }$يُطلق عليها اسم دالة الجهد الترتيبي المعمم إذا${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$،

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$بمعنى آخر: عندما يُغيّر اللاعب مساره، إذا زادت منفعته، فإن الإمكانات تزداد (لكن العكس ليس صحيحًا بالضرورة). كل احتمال ترتيبي هو احتمال ترتيبي مُعمّم.

• ${\displaystyle \Phi }$يُطلق عليها اسم دالة جهد الاستجابة المثلى إذا ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$،

${\displaystyle \arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$أي: بالنسبة لكل لاعب i ، فإن تعظيم دالة الإمكانات المشتركة يؤدي إلى نفس النتيجة التي يؤدي إليها تعظيم منفعته الخاصة.

• ${\displaystyle \Phi }$تُسمى دالة الجهد الزائف ^{[ 3 ]} إذا ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$،

${\displaystyle \arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})\supseteq \arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$أي: بالنسبة لكل لاعب i ، فإن تعظيم دالة الإمكانات المشتركة يؤدي إلى أفضل استجابة.

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

في لعبة ثنائية اللاعبين ذات حركتين مع تأثيرات خارجية، تُعطى عوائد كل لاعب بالدالة uᵢ ₍ aᵢ _, aⱼ ₎ = bᵢaᵢ ₊ wⱼaᵢaⱼ _، حيث _{يُمثل aᵢ} حركة اللاعب i، _و aⱼ حركة الخصم، و w تأثيرًا خارجيًا إيجابيًا ناتجًا عن اختيار الحركة نفسها. خيارات الحركة هي +1 و -1 ، كما هو موضح في مصفوفة _{العوائد في} الشكل 1 .

لهذه اللعبة دالة محتملة P( a ₁ , a ₂ ) = b ₁ a ₁ + b ₂ a ₂ + w a ₁ a ₂ .

إذا تحرك اللاعب 1 من -1 إلى +1، فإن فرق العائد هو Δ u ₁ = u ₁ (+1, a ₂ ) – u ₁ (–1, a ₂ ) = 2 b ₁ + 2 w a ₂ .

التغير في الجهد هو ΔP = P(+1, a ₂ ) – P(–1, a ₂ ) = ( b ₁ + b ₂ a ₂ + w a ₂ ) – (– b ₁ + b ₂ a ₂ – w a ₂ ) = 2 b ₁ + 2 w a ₂ = Δ u ₁ .

الحل للاعب الثاني مكافئ. باستخدام القيم العددية b₁ = 2، b₂ = _-1 ،   w = 3 ،   يتحول  هذا  المثال إلى معركة بسيطة بين الجنسين ، كما هو موضح في الشكل 2. تحتوي اللعبة على نقطتي توازن ناش بحتتين، (+1،  ₊₁ ) و ( -1 ، -1 )  . وهما أيضًا القيم القصوى المحلية لدالة الجهد (الشكل 3). نقطة التوازن الوحيدة المستقرة عشوائيًا هي (+1،  +1) ، وهي القيمة القصوى المطلقة لدالة الجهد.

لا يمكن اعتبار لعبة ثنائية اللاعبين وثنائية الحركة لعبة محتملة إلا إذا

${\displaystyle [u_{1}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1,-1)]=[u_{2}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(-1,-1)]}$

ألعاب الإمكانات الدقيقة تعادل ألعاب الازدحام : أثبت روزنتال ^{[ 4 ]} أن كل لعبة ازدحام لها إمكانات دقيقة؛ أثبت موندرر وشابلي ^{[ 1 ]} الاتجاه المعاكس: كل لعبة ذات دالة إمكانات دقيقة هي لعبة ازدحام .

إن فئة ألعاب الإمكانات الترتيبية أكبر بكثير. وقد أثبت فابريكانت وباباديميتريو وتالوار ^{[ 5 ] : النظرية 6} أنه لكل مسألة في فئة التعقيد PLS (أي كل مسألة بحث محلي بشكل أساسي)، توجد لعبة إمكانات ترتيبية بعدد متعدد الحدود من اللاعبين، بحيث تكون مجموعة توازنات ناش البحتة مساوية لمجموعة الحلول المثلى المحلية.

مسار التحسين (ويُسمى أيضًا ديناميكيات ناش ) هو سلسلة من متجهات الاستراتيجية، حيث يتم الوصول إلى كل متجه من المتجه السابق عن طريق قيام لاعب واحد بتغيير استراتيجيته إلى استراتيجية تزيد من منفعته بشكل صارم. إذا كانت اللعبة تحتوي على دالة جهد ترتيبي معممة${\displaystyle \Phi }$، ثم${\displaystyle \Phi }$تتزايد الدالة بشكل صارم في كل مسار تحسين، لذا فإن كل مسار تحسين غير دوري. إذا كانت اللعبة تحتوي على عدد محدود من الاستراتيجيات، فإن كل مسار تحسين يكون محدودًا. تُسمى هذه الخاصية خاصية التحسين المحدود (FIP) . لقد أثبتنا للتو أن كل لعبة ذات جهد ترتيبي معمّم محدود تمتلك خاصية التحسين المحدود. والعكس صحيح أيضًا: كل لعبة محدودة ذات خاصية التحسين المحدود تقبل دالة جهد ترتيبي معمّم. ^{[ 6 ]} الحالة النهائية في كل مسار تحسين محدود هي توازن ناش، لذا فإن خاصية التحسين المحدود تعني وجود توازن ناش ذي استراتيجية خالصة. علاوة على ذلك، فإنها تعني أنه يمكن حساب توازن ناش بواسطة عملية موزعة، حيث يتعين على كل وكيل تحسين استراتيجيته فقط.

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

تُعدّ خاصية التكرارية الضعيفة (WA) خاصيةً أضعف . ^{[ 7 ]} وتعني أنه لأي متجه استراتيجية أولي، يوجد مسار استجابة أمثل محدود يبدأ من ذلك المتجه. لا تكفي خاصية التكرارية الضعيفة لوجود دالة كامنة (لأن بعض مسارات التحسين قد تكون دورية)، ولكنها كافية لوجود توازن ناش للاستراتيجية البحتة. وهذا يعني أنه يمكن حساب توازن ناش بشكل شبه مؤكد من خلال عملية موزعة عشوائية، حيث يتم اختيار لاعب عشوائيًا في كل نقطة، ويختار هذا اللاعب استراتيجية أمثل عشوائيًا. ^{[ 6 ]}

دوبي وهايمانكو وزابيشيلنيوك ^{[ 3 ] : إثبات Thm.1} :

• أي لعبة من البدائل الاستراتيجية الضعيفة أو المكملات الاستراتيجية مع التجميع هي لعبة ذات إمكانات زائفة.
• أي لعبة ذات إمكانات زائفة لها توازن ناش للاستراتيجية البحتة.

درس أبراهام نيمان ^{[ 8 ]} ألعاب الإمكانات التي تكون فيها (أ) الإمكانات دالة سلسة ومقعرة ، (ب) مجموعات الاستراتيجيات محدبة، (ج) المنافع محدودة. وقد أثبت أنه في مثل هذه الألعاب، يكون أي توازن مترابط مزيجًا من أنماط استراتيجيات خالصة تُعظّم الإمكانات.

إذا كان، بالإضافة إلى ذلك، (د) مجموعات الاستراتيجيات مضغوطة، (هـ) الإمكانات عبارة عن دالة مقعرة تمامًا، فإن التوازن المرتبط يكون فريدًا.

• لعبة الازدحام
• الاقتصاد الفيزيائي
• توصيف لألعاب الإمكانات الترتيبية. ^{[ 9 ]}

• ملاحظات محاضرة يشاي منصور حول ألعاب الجهد والازدحام
• القسم 19 في: فازيراني، فيجاي ف .؛ نيسان, نعوم ; روغاردن, تيم ; تاردوس، إيفا (2007). نظرية اللعبة الخوارزمية (PDF) . كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج. رقم ISBN 0-521-87282-0.
• عرض غير تقني من قبل هو ديكسون حول حتمية التواطؤ، الفصل 8، عالم الدونات وأرخبيل الاحتكار الثنائي ، اقتصاديات ركوب الأمواج .