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

בתורת המשחקים, שיווי משקל משוכלל הוא עידון של המושג שיווי משקל נאש שנהגה על ידי ריינהרד זלטן ב-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}$ וגם $\sum _{s_{i}\in S_{i}}v_{i}(s_{i})\leq 1$ לכל $i\in N$.

נסמן $v=(v_{i}),i\in N$ את וקטור האילוצים של כל השחקנים. המשחק עם v-הפרעות הוא המשחק $\Gamma (v)=(N,\Sigma _{i}(v_{i}),u_{i})$ שבו קבוצת האסטרטגיות של שחקן i היא $\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.

פורמלית: אסטרטגיה מעורבת $\sigma$ במשחק בצורה אסטרטגית $\ \ \left(N,S_{i},u_{i}\right)$ נקראת שיווי משקל משוכלל אם קיימת סדרה של וקטורי אילוצים $(v^{k})_{k\in \mathbb {N} }$ המקיימים ש- $\lim _{k\to \infty }max(v_{i}^{k}(s_{i}))=0$ ולכל $k\in \mathbb {N}$ קיימת נקודת שיווי משקל $\sigma ^{k}$ במשחק $\Gamma (v^{k})$ כך שמתקיים $\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 משחק באסטרטגיה המעורבת $(1-\epsilon ,\epsilon )$, כאשר $0<\epsilon <1$.

הרווח של שחקן 2 אם יבחר לשחק Left במקרה זה יהיה :$1(1-\epsilon ) 2\epsilon =1 \epsilon \$

במקרה ששחקן 2 ישחק Right הרווח הצפוי הוא :$0(1-\epsilon ) 2\epsilon =2\epsilon \$

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

לעומת זאת נראה (D,R) אינו שיווי משקל משוכלל: נניח ששחקן 1 משחק באסטרטגיה המעורבת $(\epsilon ,1-\epsilon )$.

הרווח הצפוי לשחקן 2 אם ישחק Left הוא: $1\epsilon 2(1-\epsilon )=2-\epsilon \$

הרווח הצפוי ל-2 ממשחק Right הוא: $0(\epsilon ) 2(1-\epsilon )=2-2\epsilon \$

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

תכונות

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

ראו גם

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

לקריאה נוספת

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