משחק סטוכסטי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
Gnome-edit-clear.svg ערך זה זקוק לעריכה: הסיבה לכך היא: ויקיזציה.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

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

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

משחקי שני שחקנים[עריכת קוד מקור | עריכה]

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

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

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

תאוריה[עריכת קוד מקור | עריכה]

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

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

המשחק מתחיל במצב התחלתי מסוים . בשלב , השחקנים צופים ב- קודם כל. לאחר מכן הם בוחרים בו-זמנית פעולות , לאחר מכן הם צופים בפרופיל הפעולה , ואז הטבע בוחר לפי הסתברות  . מהלך של המשחק הסטוכסטי, , מגדיר זרם של תגמולים  , כאשר .המשחק המנוכה Γλ  עם מקדם הניכיון () הנו המשחק אשר התגמול לשחקן i הנו  משחק שלב ה-n הינו המשחק אשר התגמול לשחקן i  הוא .הערך (vn(m1, ו- (  vλ(m1 בהתאמה, של משחק סטוכסטי סכום-אפס של שני שחקנים nΓ, ו- Γλ  בהתאמה, עם מצבים ופעולות סופיים רבים. טרומן בוולי ואילון קולברג (1967) הוכיחו כי (  vλ(m1 מתכנס לגבול כאשר n שואף לאינסוף .  כמו כן, הם הוכיחו כי (  vλ(m1 מתכנס לאותו הגבול כאשר λ שואף ל-0. המשחק "הבלתי מנוכה", הנו משחק אשר התגמול לשחקן הוא ה-"גבול" של ממוצע תגמולי השלב. ישנם אמצעי זהירות הצריכים להינקט בהגדרת הערך של של שני-שחקנים בעל סכום-אפס, ובהגדרת תגמולים שיווי-משקליים של שאינו בעל סכום-אפס. הערך האחיד של משחק סטוכסטי סכום-אפס בעל שני-שחקנים מתקיים אם עבור כל ישנו מספר חיובי ושלם וזוג אסטרטגי: של שחקן מס' 1 ו- של שחקן מס' 2, כך שעבור כל ן-  וכל  התוחלת של המתייחסת להסתברות במהלכים שמוגדרים על ידי ו-  הנה לפחות , והתוחלת של המתייחסת להסתברות במהלכים המוגדרים על ידי ו-   הינה לכל היותר .  ז'אן פרנסואה מרטנס ואברהם נוימן (1981) הוכיחו שכל משחק סטוכסטי סכום-אפס בעל שני-שחקנים עם מצבים ופעולות סופיים רבים לבעל ערך אחיד. אם ישנו מספר סופי של שחקנים וקבוצות הפעולה וקבוצת המצבים הם סופיים, אזי למשחק סטוכסטי עם מספר סופי של שלבים תמיד יהיה שיווי משקל נאש. אותו הדבר נכון עבור משחק עם אינסוף שלבים אם התגמול הכולל הנו הסכום המנוכה. למשחק הסטוכסטי שאינו בעל סכום-אפס יש תגמול שיווי-משקלי אחיד אם עבור כל ישנו מספר חיובי ושלם   ופרופיל אסטרטגי כך שעבור כל סטייה חד-צדדית הנעשית על ידי שחקן  , (כלומר, פרופיל אסטרטגי עם  עבור כל , וכל  התוחלת של המתייחסת להסתברות במהלכים המוגדרים על ידי הנה לפחות , והתוחלת של המתייחסת להסתברות במהלכים המוגדרים על ידי הנה לכל היותר  וייל הראה שמשחקים סטוכסטיים בעלי שני-שחקנים עם מצב סופי ומרחבי פעולה יש תגמול שיווי משקל אחיד.

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

יישומים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Constrained Stochastic Games in Wireless Networks by E.Altman, K.Avratchenkov, N.Bonneau, M.Debbah, R.El-Azouzi, D.S.Menasche