משתמש:Ortalsimana/משחק סטוכסטי

משחק סטוכסטי

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

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

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

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

משחקי שתי-שחקנים

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

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

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

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

תיאוריה

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

קבוצה סופית של שחקנים I

מרחב מצב M (אשר מהווה קבוצה סופית או מרחב הניתן למדידה (M,A) )

עבור כל שחקן i∈I ,קבוצת פעולה Si ( קבוצה סופית או מרחב הניתן למדידה (Si, Si).

הסתברות מעבר P מ-M x S ,כאשר S= ×_(i∈I ) S^i הינו פרופילי הפעולה, ל- M,כאשר (P(A┤m,s הנה ההסתברות שהמצב הבא יהיה A בהינתן שהמצב הנוכחי הנו m ופרופיל הפעולה הנוכחית הנו s. פונקציית תגמול g מ – M x S ל- RI ,כאשר קואורדינטת ה-i של gⁱ g מייצגת את התגמול לשחקן i כפונקציה של המצב m ופרופיל הפעולה s .

המשחק מתחיל במצב התחלתי מסוים, mi. בשלב t ,השחקנים צופים ב- mt קודם כל. לאחר מכן הם בוחרים בו-זמנית פעולות s_t^i∈S^i ,לאחר מכן הם צופים בפרופיל הפעולה

s_t=〖(s_t^i)〗_i,ואז טבע בוחר mt+1 לפי ההסתברות P(∙┤|  m_t  ,s_t) . מהלך של המשחק הסטוכסטי,  m_1  ,s_1……,m_t  ,s_t,…, מגדיר זרם של תגמולים g_1  ,g_2,…. , כאשר 
g_t=g(m_t  ,s_t).

המשחק המנוכה Γλ ,עם מקדם הניכיון λ(0<λ≤1) הנו המשחק אשר התגמול לשחקן i הנו :λ∑_(t=1)^∞▒〖(1-λ)〗^(t-1) g_t^i . משחק שלב ה-n הינו המשחק אשר התגמול לשחקן i הינו g ̅_n^i≔1/n ∑_(t=1)^n▒g_t^i הערך vn(m1), ו- ( vλ(m1 בהתאמה, של משחק סטוכסטי סכום-אפס של שני-שחקנים,nΓ, ו- Γλ בהתאמה, עם מצבים ופעולות סופיים רבים קיימים. טרומן בוולי ואלון קוהלברג (1976) הוכיחו כי vn(m1) מתכנס לגבול כאשר n שואף לאינסוף .כמו כן, הם הוכיחו כי ( vλ(m1מתכנס לאותו הגבול כאשר λ שואף ל-0. המשחק "הבלתי מנוכה", Γ_∞ ,הינו המשחק אשר התגמול לשחקן i הוא ה-"גבול" של ממוצעי תגמולי השלב. כמה אמצעי זהירות צריכים להינקט בהגדרת הערך של Γ_∞ של שני-שחקנים בעל סכום-אפס, ובהגדרת תגמולים שיווי-משקליים של Γ_∞ שאינו בעל סכום-אפס. הערך האחיד v_∞ של משחק סטוכסטי סכום-אפס בעל שני-שחקנים, Γ_∞ ,מתקיים אם עבור כל ε>0 ישנו מספר חיובי ושלם N וזוג אסטרטגי: σ_ε של שחקן מס' 1 ו-τ_ε של שחקן מס' 2 , כך שעבור כל σ ו- τ וכל n≥N התוחלת של g ̅_n^i המתייחסת להסתברות במהלכים שמוגדרים ע"י σ_ε ו- τ הינה לפחות v_∞-ε , והתוחלת של g ̅_n^i המתייחסת להסתברות במהלכים המוגדרים ע"י σ ו- τ_ε הינה לכל היותר v_∞+ε . ג'ין-פרנסיס מרטנס ואברהם ניימן (1981) הוכיחו שכל משחק סכום-אפס סטוכסטי בעל שני-שחקנים עם מצבים ופעולות סופיים רבים ישנו ערך אחיד. אם ישנו מספר סופי של שחקנים וקבוצות הפעולה וקבוצת המצבים הם סופיים, אזי למשחק סטוכסטי עם מספר סופי של שלבים תמיד יהיה שיווי-משקל נאש. אותו הדבר נכון עבור משחק עם אינסוף שלבים אם התגמול הכולל הינו הסכום המנוכה. למשחק הסטוכסטי Γ_∞ שאינו בעל סכום-אפס יש תגמול שיווי-משקלי אחיד v_∞ אם עבור כל ε>0 ישנו מספר חיובי ושלם N ופרופיל אסטרטגי σ כך שעבור כל סטייה חד-צדדית הנעשית ע"י שחקן i (כלומר, פרופיל אסטרטגי τ עם σ^j=τ^j עבור כל j≠i),וכל n≥N התוחלת של g ̅_n^i המתייחסת להסתברות במהלכים המוגדרים ע"י σ הינה לפחות v_∞^i-ε , והתוחלת של g ̅_n^i המתייחסת להסתברות במהלכים המוגדרים ע"י τ הינה לכל היותר v_∞^i+ε . ניקולס ויאלה הראה שמשחקים סטוכסטיים בעלי שני-שחקנים עם מצב סופי ומרחבי פעולה יש תגמול שיווי משקל אחיד. למשחק הסטוכסטי Γ_∞ שאינו בעל סכום-אפס יש תגמול שיווי-משקלי מוגבל ממוצע v_∞ אם עבור כל ε>0 ישנו פרופיל אסטרטגי σ כך שעבור כל סטייה חד-צדדית הנעשית ע"י שחקן i , התוחלת של הגבול התחתון של ממוצעי תגמולי השלב המתייחסת להסתברות במהלכים המוגדרים ע"י σ הינה לפחות v_∞^i-ε , והתוחלת של הגבול העליון של ממוצעי תגמולי השלב המתייחסת להסתברות במהלכים המוגדרים ע"י τ הינה לכל היותר v_∞^i+ε . ג'ין-פרנסיס מרטנס ואברהם ניימן הוכיחו כי כל משחק סכום-אפס סטוכסטי בעל שני שחקנים עם מצהים ופעולות סופיים רבים ישנו ערך מוגבל ממוצע, וניקולס ויאלה הראה שכל המשחקים הסטוכסטיים בעלי שני שחקנים עם מצב ומרחבי פעולה סופיים יש תגמול שיווי-משקלי מוגבל ממוצע. במיוחד, התוצאות הללו מביעות שהמשחקים הללו יש ערך ותגמול שיווי-משקל מקורב, הנקרא תגמול שיווי-משקלי בעל ממוצע גבול-תחתון (ובהתאמה, בעל ממוצע גבול-עליון), כשאר התגמול הכולל הוא הגבול התחתון (או הגבול העליון) של ממוצעי תגמולי השלב. שאלה שנותרה פתוחה היא האם כל משחק סטוכסטי עם מס' שחקנים ,מצבים ופעולות רבים וסופיים ישנו תגמול שיווי-משקלי אחיד, או תגמול שיווי-משקלי מוגבל-ממוצע, או אפילו תגמול שיווי-משקלי בעל ממוצע גבול-תחתון. שיווי משקל מרקובי מושלם הינו עיבוד של הקונספט של שיווי משקל תת-משחקי משוכלל למשחקים סטוכסטיים.

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