קואליציה מהותית

**קואליציה מהותית** (Essential Coalition) הוא מושג בתורת המשחקים בתחום המשחקים השיתופיים המגדיר תכונה של קואליציה במשחק בצורה קואליציונית. חשיבות הקואליציות המהותיות בא לידי ביטוי בחישוב הליבה של המשחק.

סימונים:
*N =\{1,2,\cdots,n\} קבוצה סופית של שחקנים.
*v:2^N \rarr \mathbb{R} היא פונקציה המתאימה לכל תת-קבוצה \! S של שחקנים מספר ממשי \! v(S) ומקיימת v(\emptyset)=0.
*\! v נקראת הפונקציה הקואליציונית.
*נסמן ב- \! G את המשחק:  G=\left( N,v \right) .

## הגדרה
נתחיל מהגדרת המושג **קואליציה לא מהותית**.

יהי \! G  משחק בצורה קואליציונית. קואליציה \! S נקראת **לא מהותית** (inessential) במשחק G אם קיימת חלוקה \!S_1,S_2,...,S_r של S שבה r\geq2

כך שמתקיים v(S)\leq \sum_{j=1}^r v(S_j).

**קואליציה מהותית** היא קואליציה שאינה לא מהותית.

## תכונות
# כל קואליציה הכוללת שחקן בודד היא מהותית, מאחר שכל חלוקה כוללת את הקואליציה עצמה ותו לא. כלומר \! r=1.
# כל קואליציה לא מהותית \! S ניתנת לחלוקה לקואליציות **מהותיות** \! S_1,S_2,...,S_r כך שמתקיים v(S)\leq \sum_{j=1}^r v(S_j). אכן, תהי \! S קואליציה שאינה מהותית. נבצע חלוקה כלשהי של \! S, אם קיבלנו בחלוקה קואליציה שאינה מהותית נמשיך ונחלק גם אותה. תהליך זה הוא בהכרח סופי לפי תכונה 1.
# הקואליציה \! N  לאו דווקא מהותית. ממשפט שפלי-בונדרבה מסיקים כי כדי שהליבה לא תהיה ריקה, יש לדרוש כי לכל חלוקה של \! N יתקיים v(N)\geq \sum_{j=1}^r v(S_j).

לכן, במשחקים בהם הליבה איננה ריקה ו-\! N איננה מהותית, בהכרח מתקיים שוויון בנוסחא לעיל לכל חלוקה של \! N.

## חשיבות בחישוב הליבה
**1.** לצורך חישוב הליבה של משחק \! G, יש למצוא את כל וקטורי התשלומים x\in\mathbb{R}^ כך ש:

 x(N)=v\left(N\right)  וגם \forall S \subseteq N: x(S)\geq v\left(S\right). 

מדובר ב- 
 2^{\left|N\right|}  
אי שוויונים ושוויון אחד שיש לפתור כדי למצוא את הליבה. 

ניתן לראות כי אפשר להסתפק אך ורק באי השוויונים עבור **הקואליציות המהותיות**.
כלומר וקטור \! X נמצא בליבה של \! G אם ורק אם:

 x(N)=v\left(N\right)  וגם  x(S)\geq v\left(S\right) לכל \! S **מהותית** ב \! N. 

**2.** יהיו  G_1=(N,v) , G_2=\left(N,u\right)  שני משחקים בצורה קואליציונית המקיימים
ש  v(S)=u\left(S\right)  לכל קואליציה **מהותית** ב-\! G_1 או ב- \! G_2.

אז לשני המשחקים יש את אותן **קואליציות מהותיות** ואת אותה **הליבה**.

נוכיח זאת במספר שלבים:

**א.** נראה כי קואליציה \! S היא קואליציה מהותית ב-\! G_1 אם ורק אם היא קואליציה מהותית ב-\! G_2. 

נניח שהטענה לא נכונה. תהי \! S קואליציה מינימלית שהיא מהותית באחד המשחקים, \! G_1 ולא מהותית בשני \! G_2.

 u(S)=v\left(S\right)\ \leq \sum_{j=1}^r v(S_j) =\sum_{j=1}^r u(S_j)  

כאשר המעבר האחרון נובע מההנחה ומכך ש \! S_j מהותית לפי \! v 
(מסעיף א נובע כי ניתן להציג את הסכום כך ש \! S_j מהותיות לפי \! v).

כל הקואליציות \! S_j הן תת-קואליציות ממש של \! S, בסתירה. 

**ב.** מכאן נסיק שאם u(N)=v\left(N\right) אז הליבה של \! G_1 שווה לליבה של \! G_2. 

**ג.** נראה כי אם הליבות של \! G_1 ושל \! G_2 אינן ריקות אז u(N)=v\left(N\right).

יהי \! x בליבה של \! G_1, \! y בליבה של \! G_2. 

- אם \! N מהותית לפי \! u או לפי \! v אז מהתנאי u(N)=v\left(N\right).

- אם \! N אינה מהותית לפי \! u ולפי \! v אז:

x(N)=v\left(N\right)\leq \sum_{j=1}^r v(S_j)\ = \sum_{j=1}^r u(S_j)\ \leq \sum_{j=1}^r y(S_j)\ = y(N) .

קיבלנו  x(N)\leq y(N). 
באופן סימטרי נקבל y(N)\leq x(N) ולכן בסה"כ 
\! y(N)= x(N). 

מכך שהווקטורים יעילים נקבל ש \! u(N)= v(N). 

נשים לב שמטענות ב ו-ג נובע כי אם הליבות של \! G_1 ושל \! G_2 אינן ריקות אז הן שוות זו לזו. קיבלנו כי לשני המשחקים הנ"ל יש את אותן הקואליציות המהותיות ואת אותה הליבה, כנדרש.

## ראו גם
* תורת המשחקים - מונחים
* פתרון (תורת המשחקים)
* ליבה של משחק שיתופי
* קואליציה (תורת המשחקים)

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

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