קבוצת ידיעה

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

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

הגדרה

קבוצת ידיעה של שחקן i היא תת קבוצה Ui של קודקודי ההחלטה שלו כך שבכולם לשחקן אותם מהלכים אפשריים. פורמלית, אם נסמן בAx=a1,a2,...an את קבוצת המהלכים האפשריים בקודקוד x, ונסמן בL=xAx את איחוד קבוצות אלו. אזי קיימת חלוקה P של L, כך שבכל קבוצה lL יש בדיוק מהלך אחד מכל Ax.

תכונות

כל קודקוד החלטה של שחקן שייך לקבוצת ידיעה אחת ויחידה שלו.

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

דוגמאות

קינואה/פיצה

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

משחק 2

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

דילמת האסיר

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

משחק 4

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

ראו גם

לקריאה נוספת

קבוצת_ידיעה20870907Q6876246