הצגת המקור של הדף "כיסוי מאוזן (של משחק)"

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

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

==לקריאה נוספת==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946}}

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