שיווי משקל משוכלל לצורה הרחבה

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

דוגמה

במשחק המתואר משמאל ישנו תת-משחק יחיד (המשחק עצמו), ולכן כל שיווי משקל נאש הוא גם שיווי משקל תת-משחקי משוכלל. שני שיוויי המשקל נאש במשחק זה הינם: $(B,R)$ ו- $(C,L)$. אבל, אם נשים את עצמנו בנעליו של שחקן 1, הבחירה בפעולה $C$ נראית לא סבירה, שכן אם שחקן 1 ישחק את הפעולה $B$ לא סביר להניח כי שחקן 2 יעדיף את הפעולה $L$ על-פני הפעולה $R$ הנשלטת על ידה. שיווי המשקל $(B,R)$ נראה לכן תוצאה סבירה יותר של המשחק.

הגדרה פורמלית

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

פורמלית: נסמן ב-$A(U_{i}^{j})$ את קבוצת הפעולות האפשריות בכל קבוצת ידיעה $U_{i}^{j}\in U_{i}$ של שחקן $i$. וקטור הפרעות $\delta _{i}$ של שחקן $i$ הוא וקטור המתאים מספר חיובי לכל פעולה $a_{i}\in \cup A(U_{i}^{j})$ של שחקן $i$, כך שלכל קבוצת ידיעה שלו $U_{i}^{j}\in U_{i}$ מתקיים $\sum _{a_{i}\in A(U_{i})}\delta _{i}(a_{i})\leq 1$.

שיווי משקל משוכלל לצורה הרחבה: יהי $\Gamma$ משחק בצורה רחבה, נסמן ב-$\Gamma (\delta )$ את המשחק עם ההפרעות שבו על כל שחקן i, בכל קבוצת ידיעה $U_{i}^{j}$ שלו, לבחור כל פעולה $a_{i}$ אפשרית לו באותה קבוצת ידיעה בהסתברות גדולה מ- או שווה ל-$\delta (a_{i})$. לווקטור $\delta$ נקרא וקטור הפרעות, ואת הקואורדינטה המקסימלית שלו נסמן ב-$M(\delta )$.

וקטור אסטרטגיות התנהגות $\sigma$ במשחק בצורה הרחבה יהווה שיווי משקל משוכלל לצורה הרחבה אם קיימת סדרה של וקטורי הפרעות $(\delta ^{k})$ המקיימת $\lim _{k\to \infty }M(\delta ^{k})=0$ ולכל $k\in \mathbb {N}$ קיימת נקודת שיווי משקל (באסטרטגיות התנהגות) $\sigma ^{k}$ במשחק $\Gamma (\delta ^{k})$ כך שמתקיים $\lim _{k\to \infty }\sigma ^{k}=\sigma$.

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

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

קיום שיווי משקל משוכלל לצורה הרחבה

משפט: בכל משחק עם זיכרון שלם קיים שיווי משקל משוכלל לצורה הרחבה.

הוכחה: יהי $\Gamma$ משחק בצורה רחבה עם זיכרון שלם ותהי $(\delta ^{k})$ סדרה של וקטורי הפרעות המקיימת $\lim _{k\to \infty }M(\delta ^{k})=0$. נסתכל על המשחק המופרע $\Gamma (\delta ^{k})$. כיוון שלכל השחקנים זיכרון שלם, כל אסטרטגיה מעורבת שקולה לאסטרטגיית התנהגות כלשהי. לכן ממשפט נאש (קיום שיווי משקל לאסטרטגיות מעורבות) קיים גם שיווי משקל באסטרטגיות התנהגות ב- $\Gamma (\delta ^{k})$. מכיוון שמרחב וקטורי אסטרטגיית ההתנהגות הוא מרחב קומפקטי, לסדרה $(\sigma ^{k})$ קיימת תת-סדרה מתכנסת. בלי הגבלת הכלליות נניח כי זו הסדרה $(\sigma ^{k})$ עצמה. נסמן את גבול סדרה זו ב-$\sigma ^{*}$. אזי $\sigma ^{*}$ שיווי משקל משוכלל לצורה הרחבה.

המשך הדוגמה

נראה כי במשחק המתואר למעלה רק $(B,R)$ הוא שיווי משקל משוכלל לצורה הרחבה. יהי $\Gamma (\delta )$ המשחק המופרע המתאים למשחק זה, בו כל אחת מהפעולות: $A,B,C,R,L$ חייבת להיות משוחקת בהסתברות $\epsilon >0$ לפחות.

מכיוון שהפעולה $L$ שולטת על הפעולה $R$, בכל שיווי משקל במשחק עם ההפרעות שחקן 2 ישחק את אסטרטגיית ההתנהגות $((1-\epsilon )R,\epsilon L)$. נניח כי $\epsilon >0$ קטן מספיק - כלומר במידה כזו ש:$2(1-\epsilon )>1$. צרוף האסטרטגיה הקודמת של שחקן 2 עם האסטרטגיה $(\epsilon A,(1-2\epsilon )B,\epsilon C)$ של שחקן 1 מהוות שיווי משקל. נסמנו $\sigma ^{\epsilon }$. מתקיים: $\lim _{\epsilon \to 0}\sigma ^{\epsilon }=(B,R)$. כמו כן, כיוון שראינו כי בתנאים אלו שחקן 2 משחק את האסטרטגיה $C$ בהסתברות מינימלית לא ייתכן כי $(C,L)$ יהווה גם כן שיווי משקל משוכלל לצורה הרחבה.

ראו גם

• שיווי משקל תת-משחקי משוכלל
• אסטרטגית התנהגות
• שיווי משקל משוכלל
• שיווי משקל נאש

לקריאה נוספת

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