משחק מאוזן

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

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

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

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

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

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

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

אוסף קואליציות מאוזן[עריכת קוד מקור | עריכה]

נתבונן באוסף קואליציות , המכיל קואליציות:. נרצה לקבוע האם אוסף הוא אוסף מאוזן או לא.

הסבר 1[עריכת קוד מקור | עריכה]

אם קיים וקטור (באורך ) כך שיתקיים: (הכוונה ב היא הרכיב ה בווקטור ). נאמר שהאוסף הוא אוסף מאוזן והווקטור הוא וקטור מקדמים מאזנים.

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

הסבר 2[עריכת קוד מקור | עריכה]

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

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

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

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

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

  • אם במקום לדרוש , נדרוש רק אז נאמר שהוא וקטור מקדמים מאזנים חלש .

בהתאמה, נאמר שהאוסף הוא אוסף מאוזן חלש .

  • אוסף מאוזן של קואליציות יקרא מינימלי אם כל תת-אוסף שלו אינו מאוזן.

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

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