ליבה של משחק שיתופי

בתורת המשחקים, הליבה של משחק שיתופי היא קבוצה של חלוקות אפשריות של הרווח שמשיגה הקואליציה שכוללת את כל השחקנים, העונה על שתי דרישות:

• יעילות: הרווח מהמשחק מחולק כולו בין השחקנים, ללא עודף.
• סבירות קואליציונית: הרווח לכל קואליציה הוא לפחות הסכום אותו הייתה יכולה הקואליציה לקבל לו הייתה נפרדת מהקואליציה הכוללת את כל השחקנים.

ניסוח פורמלי

אם ${\displaystyle \!\,G=(N,v)}$ הוא משחק שיתופי עם n שחקנים, וקטור תשלומים (imputation) הוא וקטור ${\displaystyle {\vec {x}}\in \mathbb {R} ^{n}}$ המקיים:

• יעילות: ${\displaystyle \sum _{i=1}^{n}x_{i}=v(N)}$. זה בא לציין שכל הרווח מתחלק בין השחקנים, ללא עודף.
• סבירות פרטית: ${\displaystyle x_{i}\geq v(\left\{i\right\})}$ לכל שחקן ${\displaystyle i\in N}$. זה בא לציין שלכל שחקן כדאי להצטרף לקואליציית כל השחקנים, כי בה הוא ירוויח לפחות את מה שהוא יכול להרוויח לבדו.

קבוצת וקטורי התשלומים מסומנת ב-${\displaystyle \ X(N;v)}$.

וקטור תשלומים הוא בליבה אם הוא מקיים בנוסף:

• סבירות קואליציונית: ${\displaystyle \sum _{i\in S}x_{i}\geq v(S)}$ לכל קואליציה ${\displaystyle S\subseteq N}$. זה בא לציין שלכל קואליציה חלקית לקואליציה של כל השחקנים כדאי להשתתף בקואליציה של כל השחקנים, כי סך הרווחים שלהם בה יהיה גדול לפחות כמו זה שישיגו אם ילכו לבדם. לעיתים מסמנים ${\displaystyle x(S):=\sum _{i\in S}x_{i}}$.

הליבה של המשחק מסומנת ב-${\displaystyle {\mathcal {C}}(N;v)}$.

ליבה של משחק הוצאות

במשחק הוצאות ${\displaystyle \ (N,c)}$, הדרישות משתנות קמעה - תשלומי הצד משולמים על ידי השחקנים (ולא משולמים להם), ולכן כל שחקן רוצה למזער את הסכום שהוא צריך לשלם. לכן, אי השוויונים מתהפכים:

• סבירות פרטית: ${\displaystyle x_{i}\leq c(\left\{i\right\})}$ לכל שחקן ${\displaystyle i\in N}$.
• סבירות קואליציונית: ${\displaystyle \sum _{i\in S}x_{i}\leq c(S)}$ לכל קואליציה ${\displaystyle S\subseteq N}$.

מאפיינים

מאפיינים טופולוגיים

לכל קואליציה ${\displaystyle S\subseteq N}$, הקבוצה ${\displaystyle \{x\in \mathbb {R} ^{n}:x(S)\geq v(S)\}}$ היא קבוצה סגורה וקמורה. הליבה היא חיתוך של קבוצות מהצורה הזו, ושל הקבוצה ${\displaystyle \{x\in \mathbb {R} ^{n}:x(N)\leq v(N)\}}$ שגם היא סגורה וקמורה, ולכן גם הליבה היא קבוצה סגורה וקמורה.

ניתן לראות כי מתכונות היעילות והסבירות הפרטית, נובע שלכל וקטור x בליבה, כל הקואורדינטות של x חסומות על ידי הערך ${\displaystyle \sum _{i\in N}|v(\{i\})|}$, ולכן היא קבוצה קומפקטית.

קיום וקטורים בליבה

לא לכל משחק יש וקטור שעונה על הדרישות של הליבה, ועל כן לפעמים הליבה של המשחק ריקה, כפי שניתן לראות בדוגמה בהמשך. לעיתים יש וקטורים רבים שעונים על התנאים הללו. קיימים סוגים מסוימים של משחקים שיתופיים בהם ניתן להראות כי תמיד הליבה אינה ריקה, כגון משחק שוק או משחק קמור.

תנאי כללי שהוא תנאי הכרחי ומספיק לאי-ריקות הליבה נוסח במשפט בונדרבה-שפלי.

קווריאנטיות תחת שקילות אסטרטגית

הליבה של משחק שיתופי היא קווריאנטית תחת שקילות אסטרטגית. כלומר, לכל ${\displaystyle \ a>0}$ ולכל ${\displaystyle b\in \mathbb {R} ^{n}}$ מתקיים:

${\displaystyle {\mathcal {C}}(N;av+b)=a{\mathcal {C}}(N;v)+b}$

כאשר הפונקציה ${\displaystyle \ av+b}$ מוגדרת ע"י

${\displaystyle (av+b)(S)=av(S)+\sum _{i\in S}b_{i}}$

לכל קואליציה ${\displaystyle S\subseteq N}$.

הוכחה

יהי נתון משחק ${\displaystyle \ (N;v)}$ ויהיו ${\displaystyle \ a>0}$ ו${\displaystyle b\in \mathbb {R} ^{n}}$. נגדיר משחק ${\displaystyle \ (N;u)}$ באופן הבא: ${\displaystyle \ u(S)=av(s)+b(S)}$ לכל קואליציה ${\displaystyle S\subseteq N}$. יש להוכיח כי ${\displaystyle {\mathcal {C}}(N;u)=a{\mathcal {C}}(N;v)+b}$. נוכיח כי כל אחד מהצדדים מוכל בשני.

בשלב הראשון נראה כי ${\displaystyle a{\mathcal {C}}(N;v)+b\subseteq {\mathcal {C}}(N;u)}$.

יהי ${\displaystyle x\in {\mathcal {C}}(N;v)}$. נראה כי ${\displaystyle ax+b\in {\mathcal {C}}(N;u)}$, על ידי כך שנראה שהוא מקיים את דרישות היעילות והסבירות הפרטית. כיוון ש-${\displaystyle x\in {\mathcal {C}}(N;v)}$, הוא מקיים:

1. ${\displaystyle \ x(N)=v(N)}$.
2. ${\displaystyle x(S)\geq v(S)}$ לכל קואליציה ${\displaystyle S\subseteq N}$.

מהנתון הראשון נובע

${\displaystyle \ ax(N)+b(N)=av(N)+b(N)=u(N)}$

כלומר ${\displaystyle \ ax+b}$ הוא וקטור יעיל במשחק ${\displaystyle \ (N;u)}$. מהנתון השני נובע

${\displaystyle ax(S)+b(S)\geq av(S)+b(X)=u(S)}$

לכל קואליציה S, כלומר ${\displaystyle \ ax+b}$ הוא סביר קואליציונית.

מכאן ש-${\displaystyle ax+b\in {\mathcal {C}}(N;u)}$, ולכן ${\displaystyle a{\mathcal {C}}(N;v)+b\subseteq {\mathcal {C}}(N;u)}$.

כדי להראות הכלה הפוכה מספיק לשים לב שלכל ${\displaystyle S\subseteq N}$ מתקיים

${\displaystyle v(S)={\tfrac {1}{a}}u(S)-{\tfrac {b}{a}}}$

לפי החלק הראשון מתקיים ${\displaystyle {\tfrac {1}{a}}{\mathcal {C}}(N;u)+{\tfrac {b}{a}}\subseteq {\mathcal {C}}(N;v)}$,. על ידי העברת אגפים מתקבל ${\displaystyle {\mathcal {C}}(N;u)\subseteq a{\mathcal {C}}(N;v)+b}$.

תכונת העקביות של הליבה

נתבונן במשחק עם שלושה שחקנים :

${\displaystyle \ v(1)=v(2)=v(3)=0}$

${\displaystyle \ v(1,2)=v(2,3)=1}$

${\displaystyle \ v(1,3)=2}$

${\displaystyle \ v(1,2,3)=3}$

הווקטור ${\displaystyle \ \ (2,0.5,0.5)\ }$ נמצא בליבה.

השחקנים החליטו לחלק את שווי הקואליציה הגדולה, 3, על פי וקטור זה ושחקן 3 עזב עם חלקו 0.5. כעת, שחקנים 1 ו-2 מסתכלים על החלוקה של 2.5 ותוהים האם החלוקה המקורית (לפני העזיבה של השחקן השלישי) טובה גם עכשו, אחרי העזיבה. ניתן להגדיר משחק חדש זה כמשחק המצומצם לפי דייוויס ומשלר.

השחקנים יכולים להגדיר משחק בצורה קואליציונית שבו משתתפים רק 2 השחקנים שנשארו, זהו בעצם המשחק המצומצם, ולבדוק האם הפתרון במשחק הזה זהה לסכום שכל אחד מהם היה מקבל במשחק המקורי. אם הפתרון זהה לכל משחק בצורה קואליציונית ולכל קבוצה של שחקנים שתעזוב את המשחק, נאמר שמושג הפתרון מקיים את תכונת העקביות. ולאחר שהשחקנים יבחנו את המשחק המצומצם, שום קבוצה שלהם לא תהיה מעוניינת לסטות מהפתרון המקורי משום שאם יסטו לא ירוויחו מלהימצא בפתרון של המשחק המצומצם שכן יקבלו בדיוק אותו הסכום כמו בפתרון המקורי.

הליבה מקיימת את תכונת העקביות.

דוגמה

משחק הכפפות

במשחק עם שלושה שחקנים, לשחקן 1 יש כפפה ימנית, ולשחקנים 2,3 יש כפפה שמאלית (לכל אחד). קואליציה מנצחת אם יש לה זוג כפפות, כלומר

${\displaystyle \ v(1)=v(2)=v(3)=v(2,3)=0}$

${\displaystyle \ v(1,2)=v(1,3)=v(1,2,3)=1}$

על מנת שווקטור ${\displaystyle \ x}$ יהיה בליבה, יעילות דורשת

${\displaystyle \ x_{1}+x_{2}+x_{3}=1}$

וסבירות קבוצתית דורשת

${\displaystyle x_{1},x_{2},x_{3},x_{2}+x_{3}\geq 0}$

${\displaystyle x_{1}+x_{3}\geq 1}$

${\displaystyle x_{1}+x_{2}\geq 1}$

מפתרון מערכת האי-שוויונות נקבל ${\displaystyle \ x_{2}=x_{3}=0}$, ולכן ${\displaystyle \ x_{1}=1}$.

מכאן שהליבה היא הקבוצה ${\displaystyle \ \{(1,0,0)\}}$ .

משחק רוב עם ליבה ריקה

יהי משחק רוב עם שלושה שחקנים, בו קואליציה היא מנצחת אם היא מכילה שני שחקנים לפחות, כלומר

${\displaystyle \ v(1)=v(2)=v(3)=0}$

${\displaystyle \ v(1,2)=v(1,3)=v(2,3)=v(1,2,3)=1}$

על מנת שווקטור ${\displaystyle \ x}$ יהיה בליבה, יעילות דורשת

${\displaystyle \ x_{1}+x_{2}+x_{3}=1}$

וסבירות קבוצתית דורשת, בין השאר:

${\displaystyle x_{1}+x_{3}\geq 1}$

${\displaystyle x_{1}+x_{2}\geq 1}$

${\displaystyle x_{2}+x_{3}\geq 1}$

אם נסכום את שלושת אי השוויונים הללו נקבל

${\displaystyle \ 2(x_{1}+x_{2}+x_{3})\geq 3}$

וזה בסתירה ליעילות. מכאן שלא קיים וקטור המקיים את דרישות הליבה, ולכן היא ריקה.

ראו גם

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