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

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

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

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

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

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

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

נסמן את אוסף הקואליציות הלא ריקות ב - $D^{*}:=\{S\subseteq N:S\ne \mathrm{\varnothing }\}$. נסמן ב-$P$ את אוסף כל המשקלות המאזנים חלש את $D^{*}$: $$P=\{\delta ={\left({\delta }_S\right)}_{S\in D^{*}}:{\delta }_S\ge 0\mathrm{\forall }S\in D^{*},\sum _{S\in D^{*}}{\delta }_S{\chi }^S={\chi }^N\}$$

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

משפט בונדרבה-שפלי: תנאי הכרחי ומספיק לכך שהליבה של המשחק $(N;v)$ איננה ריקה הוא שלכל $\delta \in P$ מתקיים: $\sum _{S\in D*}{\delta }_{S}v\left(S\right)\le v\left(N\right)$.

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

$\tilde{v}(S)=\{\begin{array}{ll}v(S)& \text{ S≠N }\\ Max\{\sum _{S\in D*}{\delta }_{S}v\left(S\right):\delta \in P\}& \text{S=N}\\ \end{array}$

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

$\hat{v}(S)=Max\left\{\sum _{\{S\subseteq N,R\ne \mathrm{\varnothing }\}}{\delta }_{R}v\left(R\right):\sum _{\{S\subseteq N,R\ne \mathrm{\varnothing }\}}{\delta }_R{\chi }^R={\chi }^S,{\delta }_R\ge 0,\mathrm{\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

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