שיווי משקל תת-משחקי משוכלל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
איור שמתאר את ההבדל בין שיווי משקל נאש לבין שיווי משקל תת-משחקי משוכלל. המשבצת הכחולה הינה שיווי משקל נאש, אך אינה שיווי משקל תת-משחקי משוכלל. הסיבה לכך היא שבתת העץ הימני, לשחקן 2 עדיף לשחק את K ולא את U.

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

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

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

דוגמה למשחק שבו לא כל שיווי משקל נאש הוא שיווי משקל תת-משחקי משוכלל הינו "משחק האולטימטום".

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

דוגמה - דילמת האסיר החוזרת[עריכת קוד מקור | עריכה]

פעולה 1 2
1 1,1 3,0
2 0,3 2,2

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

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

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

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

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