שיווי משקל תת-משחקי משוכלל
בתורת המשחקים, המונח שיווי משקל תת-משחקי משוכלל מתייחס לגרסה חזקה של שיווי משקל נאש במשחקים סדרתיים. תכסיס במשחק בצורה רחבה נקרא שיווי משקל תת-משחקי משוכלל אם לכל תת-משחק, האסטרטגיות המצומצמות לתת המשחק הזה מהוות שיווי משקל נאש של תת-המשחק. במילים אחרות, שיווי משקל ייקרא תת-משחקי משוכלל אם השחקנים משתתפים בתתי-משחקים שגודלם קטן מגודל המשחק המקורי, ועבור כל תת-משחק כזה ההתנהגות המוגדרת על ידי התכסיס היא שיווי משקל נאש.
שיטה נפוצה לקביעת שיווי משקל תת-משחקי משוכלל במקרה של משחק בצורה רחבה סופי, היא בעזרת אינדוקציה לאחור. בשיטה זו מסתכלים תחילה על המהלך האחרון של המשחק וקובעים מה הפעולה שצריך השחקן שמשחק אחרון לעשות על מנת למקסם את התועלת שלו. לאחר שנקבע מהלך זה, מסתכלים על המהלך הלפני אחרון וקובעים מהו המהלך שממקסם את התועלת עבור השחקן שמשחק אותו. באופן דומה ממשיכים וקובעים מהלכים עד שמגיעים למהלך הראשון. כל האסטרטגיות שנקבעו בשיטה זו הן שיווי משקל תת-משחקי משוכלל. במהלך פעולה זו, מבטלים למעשה כל איום לא אמין של השחקנים, שכן פעולות לא אמינות אינן אופטימליות עבור אותו שחקן באותו תת-עץ.
ניתן להוכיח כי בכל משחק בצורה רחבה סופי עם מידע מלא קיים שיווי משקל תת-משחקי משוכלל באסטרטגיות טהורות. הוכחה זו מתבצעת באינדוקציה על תתי המשחק, מהקטנים (הצמודים לעלים) לגדולים (הצמודים לשורש).
דוגמה למשחק שבו לא כל שיווי משקל נאש הוא שיווי משקל תת-משחקי משוכלל הינו "משחק האולטימטום".
הרעיון של שיווי משקל תת-משחקי משוכלל פותח בשנות ה-60 על ידי ריינהרד סלטן. סלטן זכה בפרס נובל לכלכלה על תרומתו לתורת המשחקים בצוותא עם ג'ון נאש וג'ון הרסני ב-1994.
דוגמה - דילמת האסיר החוזרת
| פעולה | 1 | 2 |
|---|---|---|
| 1 | 1,1 | 3,0 |
| 2 | 0,3 | 2,2 |
בגרסה זו של דילמת האסיר, שני השחקנים משחקים את המשחק 100 פעמים, כאשר בסופו של כל שלב נודעים לשחקנים המהלכים של שניהם באותו שלב.
ננתח את המשחק באינדוקציה לאחור: במשחק האחרון, כל שחקן יבחר בשיווי משקל את הפעולה ה-1, ללא תלות במהלכים שהיו קודם לכן. זאת, שכן בכל בחירה אחרת היה ניתן להגדיל את התשלום על ידי מעבר ל-1. כיוון שלמהלך הקודם, בשלב 99, אין השפעה על המהלך בשלב ה-100, ניתן להסיק כי כל שחקן ישחק 1 גם במשחק ה-99. באופן דומה ישוחקו שאר המשחקים עד למשחק הראשון. כתוצאה מתהליך זה של אינדוקציה לאחור נסיק כי שיווי המשקל התת-משחקי המשוכלל היחיד הוא כאשר שני השחקנים משחקים 1 בכל השלבים.
ראו גם
לקריאה נוספת
- שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, עמ' 268 - 274, מסת"ב 9654932946
קישורים חיצוניים
- תוכנת ג'אווה המאפשרת למצוא שיווי משקל תת-משחקי משוכלל במשחק בצורה רחבה, מהאתר gametheory.net
- בנג'מין פולק, הרצאה מצולמת מקורס באוניברסיטת ייל, שיווי משקל תת-משחקי משוכלל: השקעות אסטרטגיות והתאמות