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

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

מושגים רלוונטיים והגדרה

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

מתעוררת המוטיבציה לשאלה הבאה - בהינתן משחק שאינו מאוזן (ליבתו ריקה), מהו השינוי/כיסוי המינימלי שנוכל לבצע בפונקציה הקואליציונית $\!\,v(S)$ על מנת להפוך את המשחק למאוזן? או למאוזן לחלוטין?. שינוי/כיסוי זה מוגדר להיות הכיסוי המאוזן של המשחק

נוסחה לכיסוי המאוזן

תנאי כללי שהוא תנאי הכרחי ומספיק לאי-ריקות הליבה נוסח במשפט בונדרבה-שפלי.
מובא להלן תנאי בונדרבה-שפלי  : (ניתן לקרוא יותר בתוך הערך)

נסמן את אוסף הקואליציות הלא ריקות ב - $D^{*}:=\left\{S\subseteq N:S\neq \emptyset \right\}$. נסמן ב-$\;P\;$ את אוסף כל המשקלות המאזנים חלש את $\;D^{*}\;$:

$$P=\left\{\delta =\left(\delta _{S}\right)_{S\in D^{*}}:\delta _{S}\geq 0\quad \forall S\in D^{*},\sum _{S\in D^{*}}{\delta _{S}{\chi ^{S}}}={\chi ^{N}}\right\}$$

כאשר נשים לב כי $\;\chi ^{S}$ הוא וקטור החילה של הקואליציה $\;S$.

משפט בונדרבה-שפלי: תנאי הכרחי ומספיק לכך שהליבה של המשחק $\;\left(N;v\right)\;$ איננה ריקה הוא שלכל הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \;\delta \in P} מתקיים: $\;\sum \limits _{S\in D*}{\delta _{S}v\left(S\right)\leq v\left(N\right)}\;$.

תנאי בונדרבה-שפלי הרשום לעיל הוא אוסף של אי שיוויונים, ניתן לראות שאם נגדיל את שווי הקואליציה N דיה, אי השוויונים יתקיימו ונקבל משחק חדש ומאוזן שליבתו אינה ריקה.
ממשפט בונדרבה-שפלי ניתן לראות שלכל משחק $\!\,(N;v)$ ניתן להגדיר משחק $\!\,(N;{\tilde {v}})$ באופן הבא :

${\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}}$

קיבלנו אם כן משחק חדש ומאוזן אך זה אינו מבטיח שהמשחק מאוזן לחלוטין,
בשביל להבטיח שאי השוויונים יתקיימו לכל תתי המשחקים, נפעיל את אותו שיקול שהפעלנו לגבי הקואליציה N עבור כל קואליציה S,
ונקבל שעל מנת שהמשחק יהיה מאוזן לחלוטין השווי של כל קואליציה צריך להיות לפחות:

$\;{\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\}\;$

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

משפטים רלוונטיים ללא הוכחה

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

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946