כיסוי מאוזן (של משחק)

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

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

מושגים רלוונטיים והגדרה

  • הליבה של משחק בצורה קואליציונית היא אוסף וקטורי התשלומים הסבירים קבוצתית (מתארים אפשרויות חלוקה של שווי הקואליציה שלא יעודדו תת-קבוצה של הקואליציה ליצור קואליציה משלהם).
  • יהי משחק בצורה קואליציונית. תת-משחק שלו הוא המשחק בצורה קואליציונית שבו קבוצת שחקנים לא ריקה ו- היא הפונקציה הקואליציונית המצומצמת לקואליציות המוכלות ב-
  • משחק מאוזן הוא משחק שהליבה שלו אינה ריקה
  • משחק מאוזן לחלוטין הוא משחק שהליבה של כל תת-משחק שלו אינה ריקה


מתעוררת המוטיבציה לשאלה הבאה - בהינתן משחק שאינו מאוזן (ליבתו ריקה), מהו השינוי/כיסוי המינימלי שנוכל לבצע בפונקציה הקואליציונית על מנת להפוך את המשחק למאוזן? או למאוזן לחלוטין?. שינוי/כיסוי זה מוגדר להיות הכיסוי המאוזן של המשחק

נוסחה לכיסוי המאוזן

תנאי כללי שהוא תנאי הכרחי ומספיק לאי-ריקות הליבה נוסח במשפט בונדרבה-שפלי.
מובא להלן תנאי בונדרבה-שפלי  : (ניתן לקרוא יותר בתוך הערך)

נסמן את אוסף הקואליציות הלא ריקות ב - . נסמן ב- את אוסף כל המשקלות המאזנים חלש את :

כאשר נשים לב כי הוא וקטור החילה של הקואליציה .

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

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

קיבלנו אם כן משחק חדש ומאוזן אך זה אינו מבטיח שהמשחק מאוזן לחלוטין,
בשביל להבטיח שאי השוויונים יתקיימו לכל תתי המשחקים, נפעיל את אותו שיקול שהפעלנו לגבי הקואליציה N עבור כל קואליציה S,
ונקבל שעל מנת שהמשחק יהיה מאוזן לחלוטין השווי של כל קואליציה צריך להיות לפחות:


המשחק נקרא הכיסוי המאוזן של המשחק

משפטים רלוונטיים ללא הוכחה

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

ראו גם

לקריאה נוספת