שיווי משקל מתואם

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

הסבר לא פורמלי

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

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

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

יהי $G=(N,(S_{i})_{i\in N},(u_{i})_{i\in N})$ משחק בצורה תכסיסית.

עבור כל ווקטור $S_{i}$ בגודל $n$ נגדיר ווקטור $S_{-i}$ כווקטור בגודל $n-1$, הזהה ל $S_{i}$, פרט לכך שאינו מכיל את התא $i$ שלו.

תהי $p$ התפלגות על קבוצת ווקטורי התכסיסים $S$, אזי $p$ הוא שיווי משקל מתואם אם לכל שחקן $i\in N$ מתקיים :

$\forall s_{i}^{\prime }\in S_{i}\sum _{s_{-i}\in S_{-i}}p(s_{i},s_{-i})u(s_{i},s_{-i})\geq \sum _{s_{-i}\in S_{-i}}p(s_{i},s_{-i})u(s_{i}^{\prime },s_{-i})$

במילים אחרות, $p$ הוא שיווי משקל מתואם אם אף שחקן לא יכול לשפר את תוחלת התשלומים שלו על ידי החלפת תכסיסיו.

דוגמה

משחק מלחמת המינים

	אופרה	כדורגל
אופרה	(2,1)	(0,0)
כדורגל	(0,0)	(1,2)

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

למשחק הנ"ל ישנם שלושה שיוויי משקל נאש, (כדורגל, כדורגל), (אופרה, אופרה) ושיווי משקל מעורב בו כל שחקן הולך לאן שהוא מעדיף בסיכוי 2/3 לאן שהשני מעדיף 1/3, בהם לאף אחד מהשחקנים לא משתלם להיות היחיד המשנה את בחירתו.

ניתן ליצור שיווי משקל מתואם במשחק הנ"ל על ידי הגרלה – שני השחקנים יטילו מטבע הוגן. ייקבע מראש כי אם תוצאת ההטלה היא פלי, שני השחקנים ילכו לאופרה, ואם התוצאה עץ, ילכו למשחק הכדורגל. תוחלת התשלומים של כל שחקן, במקרה זה, היא: 1.5=0.5(1+2). ניתן לשים לב כי תוחלת התשלומים בשיווי משקל זה זהה לשני השחקנים, בניגוד לשיווי המשקל במשחק המקורי.

נראה באופן פורמלי עבור השחקן הראשון (חובב הכדורגל) כי התנאי לשיווי משקל מתואם מתקיים.

נגדיר התפלגות $p$,

$p(o,o)=p(f,f)=1/2$ $p(o,f)=p(f,o)=0$

תחילה נחשב עבור התכסיס "הליכה לכדורגל":

$p(f,f)u_{1}(f,f)+p(f,o)u_{1}(f,o)=1/2*2+0*0=1\geq 0=1/2*0+0*1=p(f,f)u_{1}(o,f)+p(f,o)u_{1}(o,o)$

כעת עבור "הליכה לאופרה":

$p(o,f)u_{1}(o,f)+p(o,o)u_{1}(o,o)=0*0+1/2*1=1/2\geq 0=0*2+1/2*0=p(o,f)u_{1}(f,f)+p(o,o)u_{1}(f,o)$

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

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

משחק צ'יקן לדוגמה

	לסטות	לנסוע ישר
לסטות	(8,8)	(9,1)
לנסוע ישר	(1,9)	(0,0)

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

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

אם הגוף החדש אומר לשחקן לנסוע ישר אזי כמובן שאין לו סיבה לסטות כי הוא יודע שלשחקן השני נאמר לסטות והתועלת תהיה 9. אם הגוף אמר לשחקן לסטות אזי השחקן השני יסטה או ייסע בהסתברות 0.5 ואז תוחלת התועלת עבור אי קבלת העצה ונסיעה ישר תהיה:

$0.5\cdot 0+0.5\cdot 9=4.5$ ועבור סטייה כפי שנאמר תהיה $0.5\cdot 8+0.5\cdot 1=4.5$ לכן אין סיבה שלא להקשיב לצד השלישי.

שיווי משקל מתואם ומשחקים עם אינפורמציה לא מלאה

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

לקריאה נוספת

• ישראל אומן, תורת המשחקים, 1981.
• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, מאגנס, 2008