משחק בייסיאני

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

מודל למשחק בייסיאני

תיאור המודל

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

מודל מתמטי

משחק בייסיאני מוגדר באמצעות $G=\langle N,\Omega ,\langle A_{i},u_{i},T_{i},\tau _{i},p_{i},C_{i}\rangle _{i\in N}\rangle$ כאשר:

$N$ הוא אוסף השחקנים.
$\Omega$ הוא אוסף המצבים ששחקן הטבע יכול לבחור מביניהם.
$A_{i}$ הוא אוסף הפעולות ששחקן $i$ יכול לפעול; $A=A_{1}\times A_{2}\times ...A_{N}$ הוא אוסף הפעולות הכללי במשחק
$T_{i}$ הוא הסוג של שחקן $i$ ; סוג זה נקבע על ידי הפונקציה $\tau _{i}:\Omega \rightarrow T_{i}$ (כלומר, לכל מצב ששחקן הטבע בחר יהיו סוגים שונים של השחקנים)
$C_{i}\subseteq A_{i}\times T_{i}$ אוסף הפעולות ששחקן $i$ מסוג $T_{i}$ יכול לבצע.
$u_{i}:\Omega \times A\rightarrow R$ היא פונקציית התועלת של שחקן $i$ .
$p_{i}$ היא ההתפלגות של שחקן $i$ על פני $\Omega$ ; כלומר לכל שחקן ישנה התפלגות שונה הקובעת מהי ההסתברות שלו להיות כל אחד מהסוגים.

ולפי הגדרות אלו:

אסטרטגיה טהורה במשחק היא $s_{i}:T_{i}\rightarrow A_{i}$ כך ש $(s_{i}(t_{i}),t_{i})\in C_{i}$ ; כלומר שחקן מסוג $t_{i}$ יכול לבחור רק מתוך הפעולות שמותרות לו לפי הסוג שלו, ובחירתו לא יכולה להסתמך על הסוג של השחקנים האחרים שכן הוא לא יודע מה הסוג של השחקנים האחרים.
התועלת הצפויה לשחקן $i$ מפרופיל אסטרטגיות $S$ היא $u_{i}(S)=E_{\omega \sim p_{i}}[u_{i}(\omega ,s_{1}(\tau _{1}(\omega )),...,s_{N}(\tau _{N}(\omega )))]$
שיווי משקל בייסיאני על משחק $G$ מוגדר כשווי משקל נאש על המשחק ${\hat {G}}=\langle N,{\hat {A}}=S_{1}\times S_{2}...S_{N},{\hat {u}}=u\rangle$ , ומכאן שלפי משפט נאש לכל משחק בייסיאני סופי קיים שווי משקל בייסיאני.

דוגמאות

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

איתות

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

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

האיתות ונוסחת בייס

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

שיווי משקל נאש בייסיאני

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

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