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

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

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

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

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

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

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

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

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

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

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

ליבה של משחק הוצאות[עריכת קוד מקור | עריכה]

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

  • סבירות פרטית: x_i\le c(\left\{i\right\}) לכל שחקן i\in N.
  • סבירות קואליציונית: \sum_{i\in S} x_i\le c(S) לכל קואליציה S \subseteq N.

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

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

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

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

קיום וקטורים בליבה[עריכת קוד מקור | עריכה]

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

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

קווריאנטיות תחת שקילות אסטרטגית[עריכת קוד מקור | עריכה]

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

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

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

(av+b)(S) = av(S) + \sum_{i\in S} b_i

לכל קואליציה S \subseteq N.

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

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

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

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

  1. \ x(N) = v(N).
  2. x(S) \ge v(S) לכל קואליציה S \subseteq N.

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

\ ax(N) + b(N) = av(N) + b(N) = u(N)

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

ax(S) + b(S) \ge av(S) + b(X) = u(S)

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

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

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

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

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

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

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

\ v(1) = v(2) = v(3) = 0
\ v(1,2) = v(2,3) =1
\ v(1,3) =2
\ v(1,2,3) =3

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

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

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

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

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

משחק הכפפות[עריכת קוד מקור | עריכה]

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

\ v(1) = v(2) = v(3) = v(2,3) = 0
\ v(1,2) = v(1,3) = v(1,2,3) = 1

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

\ x_1 + x_2 + x_3 = 1

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

x_1, x_2, x_3, x_2 + x_3 \ge 0
x_1 + x_3 \ge 1
x_1 + x_2 \ge 1

מפתרון מערכת האי-שוויונים נקבל \ x_2 = x_3 = 0 , ולכן \ x_1 = 1.

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

משחק רוב עם ליבה ריקה[עריכת קוד מקור | עריכה]

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

\ v(1) = v(2) = v(3) = 0
\ v(1,2) = v(1,3) = v(2,3) = v(1,2,3) = 1

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

\ x_1 + x_2 + x_3 = 1

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

x_1 + x_3 \ge 1
x_1 + x_2 \ge 1
x_2 + x_3 \ge 1

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

\ 2(x_1 + x_2 + x_3) \ge 3

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

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