כיסוי מאוזן (של משחק)

כיסוי מאוזן הוא מושג בתורת המשחקים השיתופיים. <br>
הגדרה : יהי <math>\!\,(N;v)</math> משחק בצורה קואליציונית, הכיסוי המאוזן של המשחק הוא המשחק <math>\!\,(N;\hat{v})</math> כך ש-<math>\hat{v}(s)</math> הוא המינימלי המקיים <math>v(s)\le\hat{v}(s)</math> לכל s וכן שהמשחק <math>\!\,(N;\hat{v})</math> הוא משחק מאוזן לחלוטין.

==מושגים רלוונטיים והגדרה==
*הליבה של משחק בצורה קואליציונית היא אוסף וקטורי התשלומים הסבירים קבוצתית (מתארים אפשרויות חלוקה של שווי הקואליציה שלא יעודדו תת-קבוצה של הקואליציה ליצור קואליציה משלהם).
*יהי <math>\!\,(N;v)</math> משחק בצורה קואליציונית. תת-משחק שלו <math>\!\,(T;v)</math> הוא המשחק בצורה קואליציונית שבו <math>T \subseteq N</math> קבוצת שחקנים לא ריקה ו-<math>\!\,v</math> היא הפונקציה הקואליציונית המצומצמת לקואליציות המוכלות ב-<math>\!\,T</math>
*משחק מאוזן הוא משחק שהליבה שלו אינה ריקה
*משחק מאוזן לחלוטין הוא משחק שהליבה של כל תת-משחק שלו אינה ריקה

מתעוררת המוטיבציה לשאלה הבאה - בהינתן משחק שאינו מאוזן (ליבתו ריקה), מהו השינוי/כיסוי המינימלי שנוכל לבצע בפונקציה הקואליציונית <math>\!\,v(S)</math> על מנת להפוך את המשחק למאוזן? או למאוזן לחלוטין?.
שינוי/כיסוי זה מוגדר להיות הכיסוי המאוזן של המשחק
== נוסחה לכיסוי המאוזן ==
תנאי כללי שהוא תנאי הכרחי ומספיק לאי-ריקות הליבה נוסח במשפט בונדרבה-שפלי.<br>
מובא להלן תנאי בונדרבה-שפלי : (ניתן לקרוא יותר בתוך הערך) <br><br>
נסמן את אוסף הקואליציות הלא ריקות ב - <math> D^* := \left\{S \subseteq N : S \ne \emptyset \right\} </math>. נסמן ב-<math>\;P \;</math> את אוסף כל המשקלות המאזנים חלש את <math>\;D^* \;</math>:
<math display="block"> P = \left\{\delta = \left(\delta_{S} \right)_{S \in D^*} : \delta_{S} \ge 0 \quad \forall S \in D^*, \sum_{S \in D^*}{\delta_{S}{\chi^{S}}} = {\chi^{N}} \right\} </math>

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

תנאי בונדרבה-שפלי הרשום לעיל הוא אוסף של אי שוויונים, ניתן לראות שאם נגדיל את שווי הקואליציה N דיה, אי השוויונים יתקיימו ונקבל משחק חדש ומאוזן שליבתו אינה ריקה. <br>
ממשפט בונדרבה-שפלי ניתן לראות שלכל משחק <math>\!\,(N;v)</math> ניתן להגדיר משחק <math>\!\,(N; \tilde{v})</math> באופן הבא :
:<math>
\tilde{v}(S) =
\begin{cases}
 v(S) & \mbox{ S≠N }\\
 \;Max\left\{\sum\limits_{S\in D*}{\delta _{S}v\left(S \right)} : \delta \in P\right\} & \mbox{S=N}\\
\end{cases}
</math>

קיבלנו אם כן משחק חדש ומאוזן אך זה אינו מבטיח שהמשחק מאוזן לחלוטין,<br>
בשביל להבטיח שאי השוויונים יתקיימו לכל תתי המשחקים, נפעיל את אותו שיקול שהפעלנו לגבי הקואליציה N עבור כל קואליציה S, <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>

המשחק <math>\!\,(N;\hat{v})</math> נקרא הכיסוי המאוזן של המשחק <math>\!\,(N;v)</math>

==משפטים רלוונטיים ללא הוכחה==
*למשחק <math>\!\,(N;v)</math> בצורה קואליציונית ליבה לא ריקה אם ורק אם <math>\tilde{v}(N) = v(N)</math>
*משחק <math>\!\,(N;v)</math> הוא מאוזן לחלוטין אם ורק אם <math>\hat{v}(N)= v(N)</math> לכל קואליציה <math>S \subseteq N</math>כאשר הפונקציה <math>\hat{v}</math> מוגדרת בהגדרה לעיל

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

==לקריאה נוספת==
*

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