משחק מאוזן

בתחום המשחקים השיתופיים ישנו נושא העוסק במשחקים בצורה קואליציונית. משחק בצורה קואליציונית יכול להיות (או לא להיות) משחק מאוזן. <br />
המשחק <math>\;\left( N;v \right) \;</math> יקרא משחק מאוזן אם לכל אוסף קואליציות מאוזן <math>\;D \;</math> ולכל וקטור מקדמים מאזנים של האוסף מתקיים: <math>\;\sum\limits_{S\in D}{\delta _{S}v\left( S \right)\le v\left( N \right)} \;</math>

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

==מושגים==
משחק בצורה קואליציונית <math>\;\left( N;v \right) \;</math> מוגדר על ידי קבוצת שחקנים <math>\;N=\left\{ 1,2,...,n \right\} \;</math> ופונקציה קואליציונית <math>\;v:2^{N}\to \mathbb{R} \;</math>. פונקציה זו "נותנת" רווח כלשהו לכל תת-קבוצה (קואליציה) של השחקנים. כך לדוגמה, אם שחקנים 1,2,3 יתאגדו לקואליציה, הרווח המשותף שלהם במשחק יהיה <math>\;v\left( \left\{ 1,2,3 \right\} \right) \;</math>. בהמשך גם יצטרכו להחליט איך לחלק את הרווח ביניהם. <br /> 
הסימון המקובל לקואליציה הוא <math>\;S \;</math>. (<math>\;S\in 2^{N} \;</math>).

===וקטור החילה===
לכל קואליציה <math>\;S \;</math>, נגדיר וקטור <math>\;\chi \;</math>, (<math>\;\chi \in \mathbb{R}^{n} \;</math>) באופן הבא: <math>\;\chi _{i}^{S}=\left\{ \begin{matrix}
 1 & i\in S \\
 0 & i\notin S \\
\end{matrix} \right. \;</math>. <br />
כלומר, וקטור החילה של הקואליציה <math>\;S \;</math> הוא וקטור שהקואורדינאטה ה <math>\;i \;</math>'ית שלו היא 1 אם שחקן <math>\;i \;</math> נמצא בקואליציה, ו 0 אחרת.

===אוסף קואליציות מאוזן===
נתבונן באוסף קואליציות <math>\;D \;</math>, המכיל <math>\;K \;</math> קואליציות:<math>\;D=\left\{ S_{1},...,S_{K} \right\} \;</math>. נרצה לקבוע האם אוסף <math>\;D \;</math> הוא אוסף מאוזן או לא.

====הסבר 1====
אם קיים וקטור <math>\;\delta >0 \;</math> (באורך <math>\;K \;</math>) כך שיתקיים: <math>\;\sum\limits_{S_{i}\in D}{\delta _{i}\chi ^{S_{i}}=\left( 1,...,1 \right)} \;</math>(הכוונה ב <math>\;\delta _{i} \;</math> היא הרכיב ה <math>\;i \;</math> בווקטור <math>\;\delta \;</math>).
נאמר שהאוסף הוא אוסף מאוזן והווקטור <math>\;\delta \;</math> הוא וקטור מקדמים מאזנים.

סכום זה הוא למעשה סכום של וקטורים, כאשר כל וקטור הוא כפל של הקבוע <math>\;\left( \delta _{i} \right) \;</math> בווקטור החילה המתאים לקואליציה <math>\;S_{i} \;</math>. אם סכום הווקטורים (חיבור "רכיב-רכיב") מסתכם לווקטור <math>\;\left( 1,...,1 \right) \;</math> נאמר שהאוסף הוא אוסף מאוזן והווקטור <math>\;\delta \;</math> הוא וקטור מקדמים מאזנים.
 
====הסבר 2====
לכל קואליציה <math>\;S_{i}\in D \;</math> נסמן את וקטור החילה שלה ב-<math>\;\chi ^{S_{i}} \;</math>. 
נתבונן במטריצה <math>\;A=\left( \begin{matrix}
 - & \chi ^{S_{1}} & - \\
 {} & \cdots & {} \\
 - & \chi ^{S_{K}} & - \\
\end{matrix} \right)_{K\times n} \;</math> (מספר העמודות הוא <math>\;n \;</math> - כמספר השחקנים). 

אם קיים וקטור <math>\;\delta >0 \;</math> (באורך <math>\;K \;</math>) כך ש 
<math>\;\delta \cdot A=\left( 1,...,1 \right) \;</math> (מכפלת מטריצות) אזי נאמר שהווקטור <math>\; \delta \;</math> הוא וקטור מקדמים מאזנים וגם נאמר על אוסף הקואליציות <math>\;D \;</math> שהוא אוסף מאוזן. 

נשים לב שמשני ההסברים נובע בקלות שכל חלוקה של <math>\;N \;</math> מהווה אוסף מאוזן עם וקטור מקדמים מאזנים <math>\;\left( 1,...,1 \right) \;</math>.

ניתן לראות במושג האוסף המאוזן הכללה של מושג החלוקה. נניח שהשחקנים יכולים לחלק את זמנם בין הקואליציות השונות: כל שחקן יכול לקבוע איזה חלק מזמנו יקדיש לכל קואליציה שאליה הוא שייך. למשל החלוקה <math>\;\{N\} \;</math> מתאימה למצב שבו כל השחקנים מקדישים את מלוא זמנם לקואליציה <math>\;N \;</math>. ב"אוסף מאוזן" כל שחקן מקדיש מזמנו לכל קואליציה בה הוא נמצא את המקדם של קואליציה זו, ומשמעות העובדה שהסכום הנ"ל הוא 1 לכל שחקן היא שאף שחקן לא יעבוד "שעות נוספות" או "יתבטל".

===הערות===
*אם במקום לדרוש <math>\;\delta >0 \;</math>, נדרוש רק <math>\;\delta \ge 0 \;</math> אז נאמר שהוא וקטור מקדמים מאזנים חלש .
בהתאמה, נאמר שהאוסף הוא אוסף מאוזן חלש .
*אוסף מאוזן של קואליציות <math>\;D \;</math> יקרא מינימלי אם כל תת-אוסף שלו אינו מאוזן.
לדוגמה - האוסף
<math>\; \left\{ \left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\} \right\} \;</math>
הוא מאוזן מינימלי, בעוד שהאוסף
<math>\; \left\{ \left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{1\right\} \right\} \;</math>
מאוזן אך אינו מאוזן מינימלי.<br>
במשפט בונדרבה-שפלי דורשים כי שהמשוואה
<math>\;\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\} \;</math>
(ראו כיסוי מאוזן) תתקיים לכל אוסף מאוזן. <br>
מסתבר שדי לדרוש שמשוואה זו תתקיים רק עבור אוספים מאוזנים מינימליים. משפט זה נקרא משפט בונדרבה-שפלי החזק.

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

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