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

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

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

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

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

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

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

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

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

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