הצגת המקור של הדף "משחק מאוזן"

בתחום ה[[משחק שיתופי|משחקים השיתופיים]] ישנו נושא העוסק במשחקים בצורה קואליציונית. משחק בצורה קואליציונית יכול להיות (או לא להיות) '''משחק מאוזן'''. <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>
מסתבר שדי לדרוש שמשוואה זו תתקיים רק עבור אוספים מאוזנים מינימליים. משפט זה נקרא '''משפט בונדרבה-שפלי החזק'''.

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

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