משחק רוב משוקלל

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

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

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

משחק רוב משוקלל (weighted majority game) הוא משחק בצורה קואליציונית הנתון ע"י:

  • קבוצת שחקנים
  • מכסה (quata)
  • משקולות . כאשר - משקולת של שחקן i מקיימת:

כאשר השווי של קואליציה נתון ע"י:

כאשר

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

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

דוגמה טובה למשחק רוב משוקלל היא הבחירות לכנסת. נניח שבכנסת ישראל- בה יושבים 120 חברי כנסת ובה על מנת להרכיב ממשלה יש צורך ברוב של יותר מ-61 חברים מתקבלות התוצאות הבאות:

  • מפלגה 1 זכתה ב-47 מנדטים.
  • מפלגה 2 זכתה ב-35 מנדטים.
  • מפלגה 3 זכתה ב-20 מנדטים.
  • מפלגה 4 זכתה ב-13 מנדטים.
  • מפלגה 5 זכתה ב-5 מנדטים.

אזי תתקבל מערכת המשקולות הבאה:

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

ניתן לשים לב שישנן מספר קואליציות שונות המסוגלות ליצור רוב משוקלל. כך למשל: אבל

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

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

כך למשל ההצגה הינה הצגה הומוגנית, הצגה הומוגנית מנורמלת ו- הצגה לא הומוגנית (וכולן הצגות של אותו משחק רוב משוקלל!).
לעומת זאת, למשחק אין הצגה הומוגנית כלל.

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

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

יהי משחק פשוט ו- וקטור כלשהו. נסמן: .

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

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

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

הוכחת המשפט
על מנת להוכיח את המשפט, להלן שתי טענות עזר:

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

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

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

.
כמו כן מתקיים:



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

לפיכך מתקיים:


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

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

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


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


כלומר: . ולכן הצגה הומוגנית של המשחק.

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

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

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


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



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

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

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

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