משחק מאוזן

בתחום המשחקים השיתופיים ישנו נושא העוסק במשחקים בצורה קואליציונית. משחק בצורה קואליציונית יכול להיות (או לא להיות) **משחק מאוזן**. 
המשחק \;\left( N;v \right) \; יקרא **משחק מאוזן** אם לכל **אוסף קואליציות מאוזן** \;D \; ולכל **וקטור מקדמים מאזנים** של האוסף מתקיים: \;\sum\limits_{S\in D}{\delta _{S}v\left( S \right)\le 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 \ge 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} \ge 0 , \forall R} \right\} \;
(ראו כיסוי מאוזן) תתקיים לכל אוסף מאוזן. 
מסתבר שדי לדרוש שמשוואה זו תתקיים רק עבור אוספים מאוזנים מינימליים. משפט זה נקרא **משפט בונדרבה-שפלי החזק**.

## ראו גם
* מונחים בתורת המשחקים
* משפט בונדרבה שפלי

קטגוריה:תורת המשחקים