לדלג לתוכן

משחק תומך

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

משחק תומךאנגלית: Carrier Game) הוא מושג בתורת המשחקים בתחום המשחקים השיתופיים. משחק תומך הוא משחק פשוט ומונוטוני שמוגדר על ידי קואליציה מסוימת. כל משחק עם אותה קבוצת שחקנים יכול להיות מתואר על ידי צירוף ליניארי יחיד של כל המשחקים התומכים. למשחקים תומכים יש חשיבות באפיון של ערך שפלי של משחק כלשהו.

סימונים והגדרות בסיסיות במשחקים שיתופיים

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

נגדיר:

1. - קבוצה לא ריקה וסופית של השחקנים.

2. - תת-קבוצה של שחקנים תקרא קואליציה.

3. - פונקציית תשלום. פונקציה המשייכת לכל קואליציה מספר ממשי כלשהו, כאשר .

ייצוג מרחב המשחקים כמרחב ליניארי

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

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

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

נשאלת השאלה: "מה יכול להיות בסיס לכל אותם משחקים?".

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

תהי קואליציה. המשחק התומך על הוא המשחק הפשוט והמונוטוני כאשר:

יש בסה"כ משחקים תומכים המהווים בסיס למרחב כל המשחקים.

משחק תומך

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

תהי קואליציה ו- . משחק יקרא - תומך ויסומן כאשר:

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

פריסת מרחב המשחקים בעזרת משחקים תומכים

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

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

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

כאמור ישנן קואליציות ולכן ישנם משחקים תומכים . כאמור כל משחק שכזה מייצג וקטור במרחב וכל שנותר להראות הוא כי וקטורים אלו הם בלתי תלויים ליניארית (בת"ל).

נניח בשלילה כי וקטורים אלו תלויים ליניארית ולכן קיימים קבועים כך שלא כולם שווים לאפס ו- (נסמן זאת ב-[1]) ונוכל להסתכל בהתאמה על המשחקים , משמע - .

נסתכל על הקבוצה הבאה ונבחר קואליציה אחת כך ש- ונסמנה ב- . כעת נוכל להסיק שתי מסקנות:

  1. .
  2. .

נציב ב-[1] ונקבל

ונשים לב שקיבלנו סתירה.

המעברים האחרונים בוצעו לפי:

1) הסכום הראשון משום ש- .

2) האיבר השני לפי הגדרת משחק תומך לעיל.

3) הסכום השלישי לפי הגדרת משחק תומך לעיל.

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

אפיון ערך שפלי על ידי משחקים תומכים

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

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

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

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

יהי שחקן ותהי קואליציה . נחלק זאת לשני מצבים:

  1. .
  2. .

אם אז .

אם כי ולכן .

קיבלנו כי השחקן הוא שחקן אפס.

יהיו צמד שחקנים וקואליציה כך ש- . נשים לב ש כי ובהתאם כי ולכן מתקיים:

והשחקנים סימטריים.

טענה: מושג פתרון של משחק תומך
[עריכת קוד מקור | עריכה]

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

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

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

וההוכחה הושלמה.

לקריאה נוספת

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