שיווי משקל משוכלל

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

רקע

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

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

הגדרה

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

פורמלית: יהי $\ \ \left(N,S_{i},u_{i}\right)$ משחק בצורה אסטרטגית. לכל שחקן $i\in N$ נתון וקטור האילוצים $v_{i}=(v_{i}(s_{i}))_{s_{i}\in S_{i}}$ כך שמתקיים ש-$\ v_{i}(s_{i})>0$ לכל $\ s_{i}\in S_{i}$ וגם הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \sum _{s_{i}\in S_{i}}v_{i}(s_{i})\leq 1} לכל $i\in N$.

נסמן $v=(v_{i}),i\in N$ את וקטור האילוצים של כל השחקנים. המשחק עם v-הפרעות הוא המשחק הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \Gamma (v)=(N,\Sigma _{i}(v_{i}),u_{i})} שבו קבוצת האסטרטגיות של שחקן i היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma_i (v_i)=\{\sigma_i\in \Sigma_i: \sigma_i(s_i)\geq v_i(s_i), \forall s_i \in S_i\}} .

שיווי משקל משוכלל- שיווי משקל נאש המתקבל כגבול של שיוויי משקל במשחקים עם הפרעות כאשר גודל ההפרעה המרבית שואף ל-0.

פורמלית: אסטרטגיה מעורבת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} במשחק בצורה אסטרטגית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \ \left( N , S_i , u_i \right) } נקראת שיווי משקל משוכלל אם קיימת סדרה של וקטורי אילוצים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (v^k)_{k\in \mathbb{N}}} המקיימים ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{k \to \infty}max(v^k_i(s_i))= 0} ולכל $k\in \mathbb {N}$ קיימת נקודת שיווי משקל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^k} במשחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma (v^k)} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{k \to \infty}\sigma^k=\sigma} .

דוגמה

במשחק שני השחקנים המוצג בצורה אסטרטגית במטריצה קיימים שני שיוויי משקל נאש באסטרטגיות טהורות- (Up,Left),(Down,Right). נראה שרק (Up,Left) הוא שיווי משקל משוכלל:

משחק בצורה אסטרטגית

	Right	Left
Up	0, 2	1, 1
Down	2, 2	2, 0

נניח ששחקן 1 משחק באסטרטגיה המעורבת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-\epsilon, \epsilon)} , כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle 0<\epsilon <1} .

הרווח של שחקן 2 אם יבחר לשחק Left במקרה זה יהיה :הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1(1-\epsilon) + 2\epsilon = 1+\epsilon\ }

במקרה ששחקן 2 ישחק Right הרווח הצפוי הוא :הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0(1-\epsilon) + 2\epsilon = 2\epsilon\ }

אם ε מספיק קטן שחקן 2 ממקסם את תוחלת התועלת שלו על ידי בחירת האסטרטגיה Right במשקל המרבי האפשרי (במשחק מופרע משקל זה אינו יכול להיות 1). הטיעון הסימטרי לגבי הרווח הצפוי לשחקן 1 מוביל למסקנה ששחקן 1 ישחק Up בהסתברות הגבוהה ביותר האפשרית. אם ניקח סדרת משחקים מופרעים כמתואר לעיל עם ε השואף ל-0 נקבל בהתאם סדרה של שיוויי משקל נאש השואפים ל(U,L). לכן בהתאם להגדרה (U,L) הוא שיווי משקל משוכלל.

לעומת זאת נראה (D,R) אינו שיווי משקל משוכלל: נניח ששחקן 1 משחק באסטרטגיה המעורבת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\epsilon, 1-\epsilon)} .

הרווח הצפוי לשחקן 2 אם ישחק Left הינו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\epsilon + 2(1-\epsilon) = 2-\epsilon\ }

הרווח הצפוי ל-2 ממשחק Right הינו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0(\epsilon) + 2(1-\epsilon) = 2-2\epsilon\ }

לכל ערך (בתחום המוגדר) של ε שחקן 2 יעדיף לשחק Left בהסתברות הגבוהה ביותר האפשרית. לכן (D,R) אינו שיווי משקל משוכלל- בהינתן הפרעה במשחק שחקן 2 יעדיף לשנות את האסטרטגיה שלו מRight לLeft. טיעון סימטרי נכון גם לגבי שחקן 1.

תכונות

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

ראו גם

• שיווי משקל משוכלל לצורה הרחבה
• שיווי משקל תת-משחקי משוכלל
• שיווי משקל נאש

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946