משחק מאוזן
בתחום המשחקים השיתופיים ישנו נושא העוסק במשחקים בצורה קואליציונית. משחק בצורה קואליציונית יכול להיות (או לא להיות) משחק מאוזן.
המשחק $ \;\left(N;v\right)\; $ יקרא משחק מאוזן אם לכל אוסף קואליציות מאוזן $ \;D\; $ ולכל וקטור מקדמים מאזנים של האוסף מתקיים: $ \;\sum \limits _{S\in D}{\delta _{S}v\left(S\right)\leq v\left(N\right)}\; $
משחק מאוזן הוא משחק אשר עונה על תנאי בונדרבה שפלי, לכן נוכל לתת ניסוח שקול למשפט זה – "הליבה של משחק איננה ריקה אם ורק אם המשחק הוא משחק מאוזן".
מושגים
משחק בצורה קואליציונית $ \;\left(N;v\right)\; $ מוגדר על ידי קבוצת שחקנים $ \;N=\left\{1,2,...,n\right\}\; $ ופונקציה קואליציונית $ \;v:2^{N}\to \mathbb {R} \; $. פונקציה זו "נותנת" רווח כלשהו לכל תת-קבוצה (קואליציה) של השחקנים. כך לדוגמה, אם שחקנים 1,2,3 יתאגדו לקואליציה, הרווח המשותף שלהם במשחק יהיה $ \;v\left(\left\{1,2,3\right\}\right)\; $. בהמשך גם יצטרכו להחליט איך לחלק את הרווח ביניהם.
הסימון המקובל לקואליציה הוא $ \;S\; $. ($ \;S\in 2^{N}\; $).
וקטור החילה
לכל קואליציה $ \;S\; $, נגדיר וקטור $ \;\chi \; $, ($ \;\chi \in \mathbb {R} ^{n}\; $) באופן הבא: $ \;\chi _{i}^{S}=\left\{{\begin{matrix}1&i\in S\\0&i\notin S\\\end{matrix}}\right.\; $.
כלומר, וקטור החילה של הקואליציה $ \;S\; $ הוא וקטור שהקואורדינאטה ה $ \;i\; $'ית שלו היא 1 אם שחקן $ \;i\; $ נמצא בקואליציה, ו 0 אחרת.
אוסף קואליציות מאוזן
נתבונן באוסף קואליציות $ \;D\; $, המכיל $ \;K\; $ קואליציות:$ \;D=\left\{S_{1},...,S_{K}\right\}\; $. נרצה לקבוע האם אוסף $ \;D\; $ הוא אוסף מאוזן או לא.
הסבר 1
אם קיים וקטור $ \;\delta >0\; $ (באורך $ \;K\; $) כך שיתקיים: $ \;\sum \limits _{S_{i}\in D}{\delta _{i}\chi ^{S_{i}}=\left(1,...,1\right)}\; $(הכוונה ב $ \;\delta _{i}\; $ היא הרכיב ה $ \;i\; $ בווקטור $ \;\delta \; $). נאמר שהאוסף הוא אוסף מאוזן והווקטור $ \;\delta \; $ הוא וקטור מקדמים מאזנים.
סכום זה הוא למעשה סכום של וקטורים, כאשר כל וקטור הוא כפל של הקבוע $ \;\left(\delta _{i}\right)\; $ בווקטור החילה המתאים לקואליציה $ \;S_{i}\; $. אם סכום הווקטורים (חיבור "רכיב-רכיב") מסתכם לווקטור $ \;\left(1,...,1\right)\; $ נאמר שהאוסף הוא אוסף מאוזן והווקטור $ \;\delta \; $ הוא וקטור מקדמים מאזנים.
הסבר 2
לכל קואליציה $ \;S_{i}\in D\; $ נסמן את וקטור החילה שלה ב-$ \;\chi ^{S_{i}}\; $. נתבונן במטריצה $ \;A=\left({\begin{matrix}-&\chi ^{S_{1}}&-\\{}&\cdots &{}\\-&\chi ^{S_{K}}&-\\\end{matrix}}\right)_{K\times n}\; $ (מספר העמודות הוא $ \;n\; $ - כמספר השחקנים).
אם קיים וקטור $ \;\delta >0\; $ (באורך $ \;K\; $) כך ש $ \;\delta \cdot A=\left(1,...,1\right)\; $ (מכפלת מטריצות) אזי נאמר שהווקטור $ \;\delta \; $ הוא וקטור מקדמים מאזנים וגם נאמר על אוסף הקואליציות $ \;D\; $ שהוא אוסף מאוזן.
נשים לב שמשני ההסברים נובע בקלות שכל חלוקה של $ \;N\; $ מהווה אוסף מאוזן עם וקטור מקדמים מאזנים $ \;\left(1,...,1\right)\; $.
ניתן לראות במושג האוסף המאוזן הכללה של מושג החלוקה. נניח שהשחקנים יכולים לחלק את זמנם בין הקואליציות השונות: כל שחקן יכול לקבוע איזה חלק מזמנו יקדיש לכל קואליציה שאליה הוא שייך. למשל החלוקה $ \;\{N\}\; $ מתאימה למצב שבו כל השחקנים מקדישים את מלוא זמנם לקואליציה $ \;N\; $. ב"אוסף מאוזן" כל שחקן מקדיש מזמנו לכל קואליציה בה הוא נמצא את המקדם של קואליציה זו, ומשמעות העובדה שהסכום הנ"ל הוא 1 לכל שחקן היא שאף שחקן לא יעבוד "שעות נוספות" או "יתבטל".
הערות
- אם במקום לדרוש $ \;\delta >0\; $, נדרוש רק $ \;\delta \geq 0\; $ אז נאמר שהוא וקטור מקדמים מאזנים חלש .
בהתאמה, נאמר שהאוסף הוא אוסף מאוזן חלש .
- אוסף מאוזן של קואליציות $ \;D\; $ יקרא מינימלי אם כל תת-אוסף שלו אינו מאוזן.
לדוגמה - האוסף
$ \;\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\}\right\}\; $
הוא מאוזן מינימלי, בעוד שהאוסף
$ \;\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{1\right\}\right\}\; $
מאוזן אך אינו מאוזן מינימלי.
במשפט בונדרבה-שפלי דורשים כי שהמשוואה
$ \;{\hat {v}}(S)=Max\left\{\sum \limits _{\left\{S\subseteq N,R\neq \emptyset \right\}}{\delta _{R}v\left(R\right):\sum \limits _{\left\{S\subseteq N,R\neq \emptyset \right\}}{\delta _{R}\chi ^{R}}=\chi ^{S},\delta _{R}\geq 0,\forall R}\right\}\; $
(ראו כיסוי מאוזן) תתקיים לכל אוסף מאוזן.
מסתבר שדי לדרוש שמשוואה זו תתקיים רק עבור אוספים מאוזנים מינימליים. משפט זה נקרא משפט בונדרבה-שפלי החזק.