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

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

סימונים:

• $N=\{1,2,\cdots ,n\}$ קבוצה סופית של שחקנים.
• $v:2^{N}\rightarrow \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\geq 2$

כך שמתקיים $v(S)\leq \sum _{j=1}^{r}v(S_{j})$.

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

תכונות

1. כל קואליציה הכוללת שחקן בודד הינה מהותית, מאחר שכל חלוקה כוללת את הקואליציה עצמה ותו לא. כלומר $\!r=1$.
2. כל קואליציה לא מהותית $\!S$ ניתנת לחלוקה לקואליציות מהותיות $\!S_{1},S_{2},...,S_{r}$ כך שמתקיים $v(S)\leq \sum _{j=1}^{r}v(S_{j})$. אכן, תהי $\!S$ קואליציה שאינה מהותית. נבצע חלוקה כלשהי של $\!S$, אם קיבלנו בחלוקה קואליציה שאינה מהותית נמשיך ונחלק גם אותה. תהליך זה הוא בהכרח סופי לפי תכונה 1.
3. הקואליציה $\!N$ לאו דווקא מהותית. ממשפט שפלי-בונדרבה מסיקים כי כדי שהליבה לא תהיה ריקה, יש לדרוש כי לכל חלוקה של $\!N$ יתקיים $v(N)\geq \sum _{j=1}^{r}v(S_{j})$.

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

חשיבות בחישוב הליבה

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

$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}$ אינן ריקות אז הן שוות זו לזו. קיבלנו כי לשני המשחקים הנ"ל יש את אותן הקואליציות המהותיות ואת אותה הליבה, כנדרש.

ראו גם

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

לקריאה נוספת

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