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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

קואליציה מהותית (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).

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

תכונות[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]