קבוצת ידיעה

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

הגדרה

קבוצת ידיעה של שחקן $i$ היא תת קבוצה $U_{i}$ של קודקודי ההחלטה שלו כך שבכולם לשחקן אותם מהלכים אפשריים. פורמלית, אם נסמן ב$A_{x}=a^{1},a^{2},...a^{n}$ את קבוצת המהלכים האפשריים בקודקוד $x$, ונסמן ב$L=\bigcup _{x}A_{x}$ את איחוד קבוצות אלו. אזי קיימת חלוקה $P$ של $L$, כך שבכל קבוצה $l\in L$ יש בדיוק מהלך אחד מכל $A_{x}$.

תכונות

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

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

דוגמאות

קינואה/פיצה

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

משחק 2

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

דילמת האסיר

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

משחק 4

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

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

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