لعبة عشوائية

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 75 صور
الموسوعة الحرة

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

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

ألعاب ثنائية اللاعبين

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

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

لعبة مُعدّلة من لعبة حجر ورقة مقص، تُلعَب باستخدام النرد، موضحة بشكل عام في الرسم البياني الأول وبشكل أكثر تفصيلًا في الثاني. يمتلك كل لاعب مجموعة من 6 نرد، حيث يحمل 4 أوجه من كل نرد إما حجر أو ورقة أو مقص، بينما يحمل الوجهان الآخران أحد الخيارات الأخرى، بحيث تحتوي مجموعة النرد الستة على جميع الاحتمالات الممكنة. يُشير الرمز "RP" إلى نرد يحمل 4 حجر و2 ورقة، وعلى الرغم من أنه لا يجوز لكلا اللاعبين اختيار هذا النرد، فإن أي مجموعتين منه تُعادلان مجموعة من أي نرد أساسي ونرد آخر، لذا يُستخدم النرد الأساسي BR كأساس. في حالة التعادل، يُمكن للاعبين اختيار نرد جديد إذا رغبوا في ذلك. الرسم البياني الأكثر تفصيلًا ضروري لأن احتمالية فوز اللاعبين تتأثر بالنرد الذي يختارونه هم وخصومهم. وبالتالي، فإن احتمالية كل نتيجة هي دالة لخيارات اللاعبين خلال مرحلة "الاختيار والرمي".

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

نظرية

مكونات اللعبة العشوائية هي: مجموعة محدودة من اللاعبينأنا{\displaystyle I}فضاء الحالة ;S{\displaystyle S}(إما مجموعة منتهية أو فضاء قابل للقياس)(S،S){\displaystyle (S,{\mathcal {S}})}); لكل لاعبأنا∈أنا{\displaystyle i\in I}مجموعة إجراءاتأأنا{\displaystyle A^{i}} (إما مجموعة منتهية أو فضاء قابل للقياس)(أأنا،أأنا){\displaystyle (A^{i},{\mathcal {A}}^{i})}); احتمال الانتقالP{\displaystyle P}منS×أ{\displaystyle S\times A}، أينأ=×أنا∈أناأأنا{\displaystyle A=\times _{i\in I}A^{i}}هي ملفات تعريف الإجراءات، إلىS{\displaystyle S}، أينP(S|s،أ){\displaystyle P(S\mid s,a)}هي احتمالية أن تكون الحالة التالية فيS{\displaystyle S}بالنظر إلى الوضع الحاليs{\displaystyle s}والملف التعريفي الحالي للنشاطأ{\displaystyle a}ودالة العائدز{\displaystyle g}منS×أ{\displaystyle S\times A}لRأنا{\displaystyle R^{I}}، حيثأنا{\displaystyle i}الإحداثي رقم - منز{\displaystyle g}،زأنا{\displaystyle g^{i}}، هو العائد الذي يحصل عليه اللاعبأنا{\displaystyle i}كدالة للحالةs{\displaystyle s}وملف تعريف الإجراءأ{\displaystyle a}.

تبدأ اللعبة عند حالة أولية معينةs1{\displaystyle s_{1}}في المرحلةت{\displaystyle t}يراقب اللاعبون أولاًsت{\displaystyle s_{t}}ثم اختر الإجراءات في نفس الوقتأتأنا∈أأنا{\displaystyle a_{t}^{i}\in A^{i}}ثم راقب ملف تعريف الحركةأت=(أتأنا)أنا{\displaystyle a_{t}=(a_{t}^{i})_{i}}ثم تقوم الطبيعة بالاختيارsت+1{\displaystyle s_{t+1}}وفقًا للاحتماليةP(⋅|sت،أت){\displaystyle P(\cdot \mid s_{t},a_{t})}لعبة من ألعاب الاحتمالات،s1،أ1،...،sت،أت،...{\displaystyle s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots }، يحدد سلسلة من العوائدز1،ز2،...{\displaystyle g_{1},g_{2},\ldots }، أينزت=ز(sت،أت){\displaystyle g_{t}=g(s_{t},a_{t})}.

اللعبة المخفضةΓλ{\displaystyle \Gamma _{\lambda }}مع عامل الخصمλ{\displaystyle \lambda }(0<λ≤1{\displaystyle 0<\lambda \leq 1}) هي اللعبة التي يكون فيها العائد للاعبأنا{\displaystyle i}يكونλ∑ت=1∞(1-λ)ت-1زتأنا{\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}. الن{\displaystyle n}لعبة المراحل هي اللعبة التي يحصل فيها اللاعب على مكافأة.أنا{\displaystyle i}يكونز¯نأنا:=1ن∑ت=1نزتأنا{\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}.

القيمةvن(s1){\displaystyle v_{n}(s_{1})}، على التوالىvλ(s1){\displaystyle v_{\lambda }(s_{1})}، من لعبة عشوائية ذات مجموع صفري لشخصينΓن{\displaystyle \Gamma _{n}}، على التوالىΓλ{\displaystyle \Gamma _{\lambda }}توجد حالة ذات عدد محدود من الحالات والأفعال، وقد أثبت ترومان بيولي وإيلون كولبرغ (1976) ذلك.vن(s1){\displaystyle v_{n}(s_{1})}يتقارب إلى حد معين عندمان{\displaystyle n}يتجه إلى ما لا نهاية وهذاvλ(s1){\displaystyle v_{\lambda }(s_{1})}يتقارب إلى نفس النهاية مثلλ{\displaystyle \lambda }يذهب إلى0{\displaystyle 0}.

لعبة "غير مخفضة" Γ∞{\displaystyle \Gamma _{\infty }}هي اللعبة التي يحصل فيها اللاعب على مكافأةأنا{\displaystyle i}يمثل "الحد" الأقصى لمتوسطات عوائد المرحلة. يلزم اتخاذ بعض الاحتياطات عند تحديد قيمة لعبة مجموعها صفر لشخصينΓ∞{\displaystyle \Gamma _{\infty }}وفي تحديد عوائد التوازن لمجموع غير صفريΓ∞{\displaystyle \Gamma _{\infty }}القيمة الموحدةv∞{\displaystyle v_{\infty }}لعبة عشوائية ذات مجموع صفري لشخصينΓ∞{\displaystyle \Gamma _{\infty }}يوجد إذا كان لكلε>0{\displaystyle \varepsilon >0}يوجد عدد صحيح موجبشمال{\displaystyle N} وزوج استراتيجيσε{\displaystyle \sigma _{\varepsilon }}اللاعب 1 وτε{\displaystyle \tau _{\varepsilon }}من اللاعب 2 بحيث يكون لكلσ{\displaystyle \sigma }وτ{\displaystyle \tau }وكلن≥شمال{\displaystyle n\geq N} توقعاتز¯نأنا{\displaystyle {\bar {g}}_{n}^{i}}فيما يتعلق باحتمالية اللعبات المحددة بواسطةσε{\displaystyle \sigma _{\varepsilon }}وτ{\displaystyle \tau }هو على الأقلv∞-ε{\displaystyle v_{\infty }-\varepsilon }وتوقعز¯نأنا{\displaystyle {\bar {g}}_{n}^{i}}فيما يتعلق باحتمالية اللعبات المحددة بواسطةσ{\displaystyle \sigma }و τε{\displaystyle \tau _{\varepsilon }}هو على الأكثرv∞+ε{\displaystyle v_{\infty }+\varepsilon }أثبت جان فرانسوا ميرتنز وأبراهام نيمان (1981) أن كل لعبة عشوائية ذات مجموع صفري لشخصين مع عدد محدود من الحالات والإجراءات لها قيمة موحدة. [ 3 ]

وجود حالة توازن

توازن ناش

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

لعبة عشوائية ذات مجموع غير صفريΓ∞{\displaystyle \Gamma _{\infty }}له عائد توازن منتظمv∞{\displaystyle v_{\infty }}إذا لكلε>0{\displaystyle \varepsilon >0}يوجد عدد صحيح موجبشمال{\displaystyle N} وملف تعريف استراتيجيσ{\displaystyle \sigma }بحيث أنه مقابل كل انحراف أحادي الجانب من جانب اللاعبأنا{\displaystyle i}أي، ملف تعريف استراتيجي τ{\displaystyle \tau }معσج=τج{\displaystyle \sigma ^{j}=\tau ^{j}}للجميعج≠أنا{\displaystyle j\neq i}وكلن≥شمال{\displaystyle n\geq N} توقعاتز¯نأنا{\displaystyle {\bar {g}}_{n}^{i}}فيما يتعلق باحتمالية اللعبات المحددة بواسطةσ{\displaystyle \sigma }هو على الأقلv∞أنا-ε{\displaystyle v_{\infty }^{i}-\varepsilon }وتوقعز¯نأنا{\displaystyle {\bar {g}}_{n}^{i}}فيما يتعلق باحتمالية اللعبات المحددة بواسطة τ{\displaystyle \tau }هو على الأكثرv∞أنا+ε{\displaystyle v_{\infty }^{i}+\varepsilon }أظهر نيكولاس فييل أن جميع الألعاب العشوائية ذات الشخصين والتي تحتوي على مساحات حالة وفعل محدودة لها عائد توازن موحد. [ 4 ]

لعبة عشوائية ذات مجموع غير صفريΓ∞{\displaystyle \Gamma _{\infty }}له عائد توازن متوسط ​​محدودv∞{\displaystyle v_{\infty }}إذا لكلε>0{\displaystyle \varepsilon >0}يوجد ملف تعريف استراتيجيσ{\displaystyle \sigma }بحيث أنه مقابل كل انحراف أحادي الجانب من جانب اللاعبأنا{\displaystyle i}، وهو توقع الحد الأدنى لمتوسطات عوائد المرحلة بالنسبة للاحتمالية في اللعبات المحددة بواسطةσ{\displaystyle \sigma }هو على الأقلv∞أنا-ε{\displaystyle v_{\infty }^{i}-\varepsilon }وتوقع الحد الأعلى لمتوسطات عوائد المرحلة بالنسبة للاحتمالية في اللعبات المحددة بواسطة τ{\displaystyle \tau }هو على الأكثرv∞أنا+ε{\displaystyle v_{\infty }^{i}+\varepsilon }أثبت جان فرانسوا ميرتنز وأبراهام نيمان (1981) أن كل لعبة عشوائية ثنائية اللاعبين ذات مجموع صفري وعدد محدود من الحالات والإجراءات لها قيمة متوسطة حدية، [ 3 ] كما بيّن نيكولاس فييل أن جميع الألعاب العشوائية ثنائية اللاعبين ذات فضاءات الحالات والإجراءات المحدودة لها عائد توازن متوسط ​​حدي. [ 4 ] وعلى وجه الخصوص، تشير هذه النتائج إلى أن هذه الألعاب لها قيمة وعائد توازن تقريبي، يُسمى عائد التوازن المتوسط ​​الحدي (على التوالي، المتوسط ​​الأعلى الحدي)، عندما يكون إجمالي العائد هو الحد الأدنى (أو الحد الأعلى) لمتوسطات عوائد المراحل.

إن ما إذا كانت كل لعبة عشوائية ذات عدد محدود من اللاعبين والحالات والإجراءات، لها عائد توازن موحد، أو عائد توازن متوسط ​​محدود، أو حتى عائد توازن متوسط ​​محدود، هو سؤال مفتوح صعب.

الملفات الشخصية المقبولة من حيث الحد الأدنى والحد الأقصى

نبذة عن الاستراتيجيةs*{\displaystyle s^{*}}يُطلق عليه اسم minmax-acceptable [ 5 ] [ 6 ] إذا كانت منفعة كل لاعب فيs*{\displaystyle s^{*}}هو على الأقل قيمة الحد الأدنى والحد الأقصى للاعب:

uأنا(s*)≥مينs-أناالأعلىsأناuأنا(s-أنا،sأنا){\displaystyle u_{i}(s^{*})\geq \min _{s_{-i}}\max _{s_{i}}u_{i}(s_{-i},s_{i})}.

كل توازن ناش مقبول من نوع minmax، حيث يتم استيفاء الخاصية الأقوى التالية في توازن ناش:

uأنا(s*)=الأعلىsأناuأنا(s-أنا*،sأنا){\displaystyle u_{i}(s^{*})=\max _{s_{i}}u_{i}(s_{-i}^{*},s_{i})}.

لكن العكس ليس صحيحًا بالضرورة. فقد أثبت سولان [ 5 ] وفليش وسولان [ 6 ] نتائج عامة لوجود ملفات تعريف مقبولة من نوع مينماكس في الألعاب العشوائية. وهذا على النقيض من توازنات ناش، التي لا يُعرف وجودها بشكل عام.

مفاهيم أخرى للتوازن

يُعد التوازن المثالي لماركوف تحسينًا لمفهوم توازن ناش المثالي للألعاب الفرعية في الألعاب العشوائية.

ألعاب بايزية عشوائية

تم دمج الألعاب العشوائية مع الألعاب البايزية لنمذجة عدم اليقين بشأن استراتيجيات اللاعبين. [ 7 ] يتم حل نموذج اللعبة البايزية العشوائية الناتج من خلال دمج متكرر لمعادلة توازن ناش البايزية ومعادلة بلمان الأمثلية .

إيقاف الألعاب

قدم إي بي دينكين [ 8 ] المشكلة التالية في نظرية الألعاب المتعلقة بإيقاف العمليات العشوائية. لنفترضFن،ن=0،1،...{\displaystyle {\mathcal {F}}_{n},n=0,1,\ldots }، لتكن متتالية متزايدة من جبر سيجما في فضاء احتمالي ما(Ω،F،P){\displaystyle (\Omega ,{\mathcal {F}},{\mathbf {P} })}، أينF{\displaystyle {\mathcal {F}}}يحتوي على كلFن{\displaystyle {\mathcal {F}}_{n}}يراقب لاعبان متواليات عشوائية{Xن}ن=1∞{\displaystyle \{X_{n}\}_{n=1}^{\infty }}،{Φن}ن=1∞{\displaystyle \{\varPhi _{n}\}_{n=1}^{\infty }}أي الدوال القابلة للقياس بالنسبة إلى{Fن}ن=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}يمكن إيقاف اللعبة عند الزمن ن من قبل اللاعب الأول إذاΦن≥0{\displaystyle \varPhi _{n}\geq 0}وبواسطة اللاعب الثاني إذاΦن<0{\displaystyle \varPhi _{n}<0}إذا توقفت اللعبة عند الزمن ن، فإن اللاعب الأول يتلقى من اللاعب الثانيxن{\displaystyle x_{n}}يسعى اللاعب الأول إلى تحقيق أقصى عائد متوقع، بينما يسعى اللاعب الثاني إلى تقليله.

يتركτ{\displaystyle \tau }ليكن زمن ماركوف بالنسبة لعملية الترشيح{Fن}ن=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}وχأ{\displaystyle \chi _{A}}لتكن الدالة المميزة للحدثأ{\displaystyle A}. يدلتي{\displaystyle {\mathcal {T}}}مجموعة جميع أوقات التوقف فيما يتعلق بالترشيح{Fن}ن=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}،Λ={λ=τχΦτ⩾0،τ∈تي}{\textstyle \Lambda =\{\lambda =\tau \chi _{\varPhi _{\tau }\geqslant 0},\tau \in {\mathcal {T}}\}}، وم={μ=τχΦτ<0،τ∈تي}{\textstyle \mathrm {M} =\{\mu =\tau \chi _{\varPhi _{\tau }<0},\tau \in {\mathcal {T}}\}}. يتركλ{\displaystyle \lambda }ليكن وقت التوقف الذي اختاره الأول (μ{\displaystyle \mu }(أو من قبل اللاعب الثاني). ثم يتم تحديد العائد، أي المبلغ الذي يدفعه اللاعب الثاني للأول.R(λ،μ)=هـXλ∧μ{\displaystyle R(\lambda ,\mu )={\mathbf {E} }X_{\lambda \land \mu }}.

بشرط أنهـ(رشفةن|Xن|)<∞{\displaystyle {\mathbf {E} }(\sup _{n}|X_{n}|)<\infty }أثبت دينكين [ 8 ] أن قيمة اللعبةv=رشفةλ∈Λمعلوماتμ∈مR(λ،μ){\displaystyle v=\sup _{\lambda \in \Lambda }\inf _{\mu \in \mathrm {M} }R(\lambda ,\mu )}موجود. قام ببناء استراتيجيات ε-المثلى، وقدم عدة شروط لوجود الاستراتيجيات المثلى (للتوسع انظر Neveu [ 9 ] وYasuda [ 10 ] ).

التطبيقات

تُستخدم الألعاب العشوائية في الاقتصاد وعلم الأحياء التطوري وشبكات الحاسوب. [ 11 ] [ 12 ] وهي تعميمات للألعاب المتكررة التي تُمثل الحالة الخاصة التي توجد فيها حالة واحدة فقط.

انظر أيضاً

ملحوظات

  1. ↑ شابلي، إل إس (1953). "الألعاب العشوائية" . وقائع الأكاديمية الوطنية للعلوم . 39 ( 10): 1095-1100 . رمز Bibcode : 1953PNAS...39.1095S . doi : 10.1073/pnas.39.10.1095 . PMC 1063912. PMID 16589380 .  
  2. ↑ سولان، إيلون؛ فييل، نيكولا (2015). "الألعاب العشوائية" . وقائع الأكاديمية الوطنية للعلوم . 112 ( 45): 13743-13746 . doi : 10.1073/pnas.1513508112 . PMC 4653174. PMID 26556883 .  
  3. 1 2 ميرتنز، جيه إف ونيمان، أ. (1981). "الألعاب العشوائية". المجلة الدولية لنظرية الألعاب . 10 (2): 53-66 . doi : 10.1007/BF01769259 . S2CID 189830419 . 
  4. 1 2 فييل، ن. (2002). "الألعاب العشوائية: نتائج حديثة". دليل نظرية الألعاب . أمستردام: إلسيفير ساينس. ص 1833-1850 . ISBN  0-444-88098-4.
  5. 1 2 سولان، إيلون (مارس 2018). "ملامح الاستراتيجية المقبولة في الألعاب العشوائية" . الألعاب والسلوك الاقتصادي . 108 : 523-540 . arXiv : 1608.05272 . doi : 10.1016/j.geb.2017.01.011 . ISSN 0899-8256 . مؤرشف من الأصل في 30 يونيو 2020. 
  6. 1 2 فليش، يانوس؛ سولان، إيلون (أغسطس 2024). "الألعاب العشوائية ذات دوال العائد العامة" . رياضيات بحوث العمليات . 49 (3): 1349-1371 . doi : 10.1287/moor.2023.1385 . ISSN 0364-765X . 
  7. ↑ ألبريشت، ستيفانو؛ كراندال، جاكوب؛ رامامورثي، سوبرامانيان (2016). "الاعتقاد والحقيقة في السلوكيات المفترضة". الذكاء الاصطناعي . 235 : 63-94 . arXiv : 1507.07688 . doi : 10.1016/j.artint.2016.02.004 . S2CID 2599762 . 
  8. 1 2 دينكين، إي بي (1969). "نسخة نظرية الألعاب لمسألة التوقف الأمثل" (ملف PDF) . دوكل. أكاد. ناوك إس إس إس آر . 185 (1): 16-19 – عبر ru .
  9. ↑ نيفو، ج. (1975). مارتينجالات ذات المعاملات المنفصلة (باللغتين الفرنسية والإنجليزية) (مكتبة نورث هولاند الرياضية، المجلد 10 ). أمستردام: أكسفورد: شركة نورث هولاند للنشر؛ نيويورك: شركة أمريكان إلسيفير للنشر، الصفحات 8+236، الفصل 3.  
  10. ↑ ياسودا، م. (1985-12-01). "حول استراتيجية عشوائية في مسألة توقف نيفو" . العمليات العشوائية وتطبيقاتها . 21 (1): 159-166 . doi : 10.1016/0304-4149(85)90384-9 . ISSN 0304-4149 . 
  11. ↑ الألعاب العشوائية المقيدة في الشبكات اللاسلكية ، بقلم إي. ألتمان، ك. أفراتشنكوف، ن. بونو، م. ديباه، ر. العزوزي، د. س. ميناش
  12. ↑ دجهيش، بوعلام؛ تشوكام، آلان؛ تمبين، حميدو (27-09-2017). "ألعاب من نوع المجال المتوسط ​​في الهندسة". مجلة AIMS للإلكترونيات والهندسة الكهربائية . 1 : 18-73 . arXiv : 1605.03281 . doi : 10.3934/ElectrEng.2017.1.18 . S2CID 16055840 . 

للمزيد من القراءة