משחק מאוזן

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

ראו גם

• מונחים בתורת המשחקים
• משפט בונדרבה שפלי