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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת המשחקים, שיווי משקל משוכלל הוא עידון של המושג שיווי משקל נאש שנהגה על ידי ריינהרד זלטן ב-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^k_i(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 ממקסם את תוחלת התועלת שלו על ידי בחירת האסטרטגיה Right במשקל המרבי האפשרי (במשחק מופרע משקל זה אינו יכול להיות 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.

תכונות[עריכת קוד מקור | עריכה]

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

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