משחק סטוכסטי

משחק סטוכסטי הוא מושג בתורת המשחקים אשר הוצג על ידי לויד שפלי בתחילת שנות ה-50 של המאה ה-20 לתיאור משחק דינמי עם מעברים הסתברותיים המשוחק על ידי שחקן אחד או יותר. המשחק משוחק ברצף של שלבים. בתחילת כל שלב המשחק הוא במצב מסוים. השחקנים בוחרים פעולות וכל שחקן משיג תגמול על-פי המצב הנוכחי והפעולות שנעשו עד לנקודה זו במשחק. לאחר מכן, המשחק עובר למצב אקראי חדש שההתפלגות שלו תלויה במצב הקודם והפעולות שנעשו על ידי השחקנים. התהליך חוזר על עצמו והמשחק ממשיך עד למספר סופי או אינסופי של שלבים. התגמול הכולל לשחקן מחושב לעיתים תכופות כסכום המנוכה של תגמולי השלב או כגבול התחתון של ממוצע תגמולי השלב.

משחקים סטוכסטיים מכלילים הן תהליכי החלטה מרקוביים והן משחקים חוזרים.

משחקי שני שחקנים

משחקי שני-שחקנים המשתמשים בגרפים ישירים נועדו במקרים רבים עבור מידול ואנליזה עבור מערכות בדידות הפועלות בסביבה (יריבה) בלתי ידועה. קונפיגורציות אפשריות של מערכת וסביבתה מוצגות כקודקודים, והמעברים מתואמים לפעולות של המערכת, לסביבתה או ל"טבע". הרצה של המערכת לאחר מכן תואמת למעבר אינסופי בגרף. כך, המערכת וסביבתה יכולות להיראות כשני שחקנים עם מטרות מנוגדות, כאשר שחקן אחד (המערכת) שואף למקסם את ההסתברות של ריצות "טובות", בזמן של השחקן האחר (הסביבה) בעל שאיפות מנוגדות.

במקרים רבים, מתקיים ערך שיווי-משקל של הסתברות זו, אך ייתכן כי אסטרטגיות אופטימליות עבור שני השחקנים לא יהיו קיימות.

אנו נציג קונספטים בסיסיים ושאלות אלגוריתמיות שנלמדו בתחום זה, ונציין כמה בעיות פתוחות ארוכות שנים. לאחר מכן, נציין תוצאות עדכניות נבחרות.

תאוריה

הרכיבים של משחק סטוכסטי הם:

• קבוצה סופית של שחקנים $I$
• מרחב מצב $M$ (אשר מהווה קבוצה סופית או מרחב הניתן למדידה $(M,{\mathcal {A}})$)
• עבור כל שחקן $i\in I$, קבוצת פעולה $S^{i}$$(S^{i},{\mathcal {S}}^{i})$)
• הסתברות מעבר $P$ מ- $M\times S$, כאשר $S=\times _{i\in I}S^{i}$ הוא פרופילי הפעולה, ל- $M$, כאשר $P(A\mid m,s)$ הנה ההסתברות שהמצב הבא יהיה $A$ בהינתן שהמצב הנוכחי הוא $m$ ופרופיל הפעולה הנוכחית הוא $s$.
• פונקציית תגמול $g$ מ-$M\times S$$R^{I}$, כאשר קואורדינטת ה- $i$של $g$, $g^{i}$, מייצגת את התגמול לשחקן $i$ כפונקציה של המצב $m$ ופרופיל הפעולה $s$.

המשחק מתחיל במצב התחלתי מסוים $m_{1}$. בשלב $t$, השחקנים צופים ב- $m_{t}$קודם כל. לאחר מכן הם בוחרים בו-זמנית פעולות $s_{t}^{i}\in S^{i}$, לאחר מכן הם צופים בפרופיל הפעולה $s_{t}=(s_{t}^{i})_{i}$, ואז הטבע בוחר $m_{t+1}$לפי הסתברות $P(\cdot \mid m_{t},s_{t})$. מהלך של המשחק הסטוכסטי, $m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots$, מגדיר זרם של תגמולים $g_{1},g_{2},\ldots$, כאשר $g_{t}=g(m_{t},s_{t})$.המשחק המנוכה Γ_λ עם מקדם הניכיון הוא המשחק אשר התגמול לשחקן i הוא משחק שלב ה-n הוא המשחק אשר התגמול לשחקן i הוא.הערך (v_n(m₁, ו- ( v_λ(m₁ בהתאמה, של משחק סטוכסטי סכום-אפס של שני שחקנים _nΓ, ו- Γ_λ בהתאמה, עם מצבים ופעולות סופיים רבים. טרומן בוולי ואילון קולברג (1967) הוכיחו כי ( v_λ(m₁ מתכנס לגבול כאשר n שואף לאינסוף. כמו כן, הם הוכיחו כי ( v_λ(m₁ מתכנס לאותו הגבול כאשר λ שואף ל-0. המשחק "הבלתי מנוכה", $\Gamma _{\infty }$הוא משחק אשר התגמול לשחקן $i$הוא ה-"גבול" של ממוצע תגמולי השלב. ישנם אמצעי זהירות הצריכים להינקט בהגדרת הערך של $\Gamma _{\infty }$של שני-שחקנים בעל סכום-אפס, ובהגדרת תגמולים שיווי-משקליים של $\Gamma _{\infty }$שאינו בעל סכום-אפס. הערך האחיד $v_{\infty }$של משחק סטוכסטי סכום-אפס בעל שני-שחקנים $\Gamma _{\infty }$ מתקיים אם עבור כל $\varepsilon >0$ ישנו מספר חיובי ושלם $N$וזוג אסטרטגי: $\sigma _{\varepsilon }$ של שחקן מס' 1 ו- $\tau _{\varepsilon }$של שחקן מס' 2, כך שעבור כל $\sigma$ ן- $\tau$ וכל $n\geq N$ התוחלת של ${\bar {g}}_{n}^{i}$המתייחסת להסתברות במהלכים שמוגדרים על ידי $\sigma _{\varepsilon }$ ו- $\tau$ הנה לפחות $v_{\infty }-\varepsilon$, והתוחלת של ${\bar {g}}_{n}^{i}$ המתייחסת להסתברות במהלכים המוגדרים על ידי $\sigma$ ו- $\tau _{\varepsilon }$ היא לכל היותר $v_{\infty }+\varepsilon$. ז'אן פרנסואה מרטנס ואברהם נוימן (1981) הוכיחו שכל משחק סטוכסטי סכום-אפס בעל שני-שחקנים עם מצבים ופעולות סופיים רבים לבעל ערך אחיד. אם ישנו מספר סופי של שחקנים וקבוצות הפעולה וקבוצת המצבים הם סופיים, אזי למשחק סטוכסטי עם מספר סופי של שלבים תמיד יהיה שיווי משקל נאש. אותו הדבר נכון עבור משחק עם אינסוף שלבים אם התגמול הכולל הוא הסכום המנוכה.למשחק הסטוכסטי $\Gamma _{\infty }$ שאינו בעל סכום-אפס יש תגמול שיווי-משקלי אחיד $v_{\infty }$ אם עבור כל $\varepsilon >0$ישנו מספר חיובי ושלם $N$ ופרופיל אסטרטגי $\sigma$כך שעבור כל סטייה חד-צדדית הנעשית על ידי שחקן $i$, (כלומר, פרופיל אסטרטגי $\tau$ עם $\sigma ^{j}=\tau ^{j}$ עבור כל $j\neq i$, וכל $n\geq N$ התוחלת של ${\bar {g}}_{n}^{i}$המתייחסת להסתברות במהלכים המוגדרים על ידי $\sigma$ הנה לפחות $v_{\infty }^{i}-\varepsilon$, והתוחלת של ${\bar {g}}_{n}^{i}$המתייחסת להסתברות במהלכים המוגדרים על ידי $\tau$ הנה לכל היותר $v_{\infty }^{i}+\varepsilon$ וייל הראה שמשחקים סטוכסטיים בעלי שני-שחקנים עם מצב סופי ומרחבי פעולה יש תגמול שיווי משקל אחיד.

למשחק הסטוכסטי שאינו בעל סכום-אפס יש תגמול שיווי-משקלי ממוצע מוגבל אם עבור כל $\varepsilon >0$ יש פרופיל אסטרטגי $\sigma$ כך שעבור כל סטייה חד-צדדית הנעשית על ידי שחקן $i$, התוחלת של הגבול התחתון של ממוצע תגמולי השלב המתייחסת להסתברות במהלכים המוגדרים על ידי $\sigma$היא לפחות $v_{\infty }^{i}-\varepsilon$, והתוחלת של הגבול העליון של תגמול ממוצע השלב המתייחסת להסתברות במהלכים המוגדרים על ידי $\tau$הנה לכל היותר $v_{\infty }+\varepsilon$. ז'אן פרנסואה מרטנס ואברהם נוימן הוכיחו (1981) כי לכל משחק סטוכסטי שהוא סכום-אפס בעל שני שחקנים עם מצבים ופעולות סופיים רבים ישנו ערך ממוצע מוגבל, וניקולה וייל הראה שלכל המשחקים הסטוכסטיים בעלי שני שחקנים עם מצב ומרחבי פעולה סופיים יש תגמול שיווי-משקלי ממוצע מוגבל. במיוחד, התוצאות הללו מביעות שלמשחקים הללו יש ערך ותגמול שיווי-משקל מקורב, הנקרא תגמול שיווי-משקלי בעל ממוצע גבול-תחתון (ובהתאמה, בעל ממוצע גבול-עליון), כשאר התגמול הכולל הוא הגבול התחתון (או הגבול העליון) של ממוצע תגמולי השלב. שאלה שנותרה פתוחה היא האם לכל משחק סטוכסטי עם מס' שחקנים, מצבים ופעולות רבים וסופיים ישנו תגמול שיווי-משקל אחיד, או תגמול שיווי-משקל ממוצע מגדל, או אפילו תגמול שיווי-משקל בעל ממוצע גבול-תחתון. שיווי המשקל המושלם של מרקוב הוא עיבוד תת-משחקי משוכלל של הקונספט של שיווי משקל נאש עבור משחקים סטוכסטיים.

יישומים

למשחקים סטוכסטיים יש יישומים בכלכלה, ביולוגיה אבולוציונית ורשתות מחשבים. הם מהווים הכללות של משחקים חוזרים שמתאימים למקרה מיוחד שבו יש מצב אחד בלבד.

ראו גם

• תהליך סטוכסטי

לקריאה נוספת

• Condon, A. (1992). "The complexity of stochastic games". Information and Computation. 96: 203–224. doi:10.1016/0890-5401(92)90048-K.
• H. Everett (1957). "Recursive games". In Melvin Dresher, Albert William Tucker, Philip Wolfe (ed.). Contributions to the Theory of Games, Volume 3. Annals of Mathematics Studies. Princeton University Press. pp. 67–78. ISBN 978-0-691-07936-3. (Reprinted in Harold W. Kuhn, ed. Classics in Game Theory, Princeton University Press, 1997. מסת"ב 978-0-691-01192-9).{{cite book}}: תחזוקה - ציטוט: multiple names: editors list (link)
• Filar, J.; Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag. ISBN 0-387-94805-8.
• Mertens, J. F.; Neyman, A. (1981). "Stochastic Games". International Journal of Game Theory. 10 (2): 53–66. doi:10.1007/BF01769259.
• Neyman, A.; Sorin, S. (2003). "Stochastic Games and Applications". Kluwer Academic Press. Dordrecht. ISBN 1-4020-1492-9.
• Shapley, L. S. (1953). "Stochastic games". PNAS. pp. 1095–1100. doi:10.1073/pnas.39.10.1095.
• Vieille, N. (2002). "Stochastic games: Recent results". Handbook of Game Theory. Amsterdam: Elsevier Science. pp. 1833–1850. ISBN 0-444-88098-4.
• Yoav Shoham; Kevin Leyton-Brown (2009). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7. (suitable for undergraduates; main results, no proofs)

קישורים חיצוניים

• הרצאה על משחקים סטוכסטיים עם שני שחקנים מאת אנטונין קוסרה

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

משחק סטוכסטי33800628Q1074380