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

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

הגדרה פורמלית

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

• קבוצת שחקנים $\;N={1,2,...n}\;$
• מכסה (quata) $\;q\geq 0\;$
• משקולות $\;w_{1},w_{2},...,w_{n}\;$. כאשר $\;w_{i}\;$ - משקולת של שחקן i מקיימת: $\;w_{i}\geq 0\;$

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

$v(s)=\left\{{\begin{matrix}1&{\mbox{if}}\ w(S)\geq q\\0&{\mbox{if}}\ w(S)<q\end{matrix}}\right.$

כאשר $\;w(S)=\sum _{i\in S}w_{i}\;$

ונהוג לסמן את המשחק באופן הבא: $\;[q;w_{1},w_{2},...,w_{n}]\;$ או בקיצור, כאשר ברור על איזה וקטור משקולות מדובר: $\;[q;w]\;$

דוגמה

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

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

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

• $\;w_{1}=47\;$
• $\;w_{2}=35\;$
• $\;w_{3}=20\;$
• $\;w_{4}=13\;$
• $\;w_{5}=5\;$

המשחק יכתב כך: $\;[61;47,35,20,13,5]\;$ והפונקציה הקואליציונית תוגדר בצורה הבאה:

$v(s)=\left\{{\begin{matrix}1&{\mbox{if}}\ \sum _{i\in S}w_{i}\geq 61\\0&{\mbox{if}}\ \sum _{i\in S}w_{i}<61\end{matrix}}\right.$

ניתן לשים לב שישנן מספר קואליציות שונות המסוגלות ליצור רוב משוקלל. כך למשל: $\;v(1,2)=v(1,3,5)=v(2,3,4)=1\;$ אבל $\;v(1,4)=v(2,3,5)=0\;$

הצגה הומוגנית והצגה מנורמלת

משחק פשוט ומונוטוני נקבע על ידי אוסף הקואליציות המינימליות הזוכות בו, המסומן ע"י: $\;{\mathcal {W}}^{m}\;$
הצגה $\;[q;w_{1},w_{2},...,w_{n}]\;$ של משחק פשוט $\;(N;v)\;$ נקראת הצגה הומוגנית אם $\;\textstyle \sum _{i\in S}w_{i}\;$ שווה, לכל קואליציה מינימלית זוכה $\;S\subseteq {\mathcal {W}}^{m}\;$.
הצגה $\;[q;w_{1},w_{2},...,w_{n}]\;$ של משחק פשוט $\;(N,v)\;$ נקראת הצגה מנורמלת אם $\;w(N)=\textstyle \sum _{i=1}^{n}w_{i}=1\;$.
משחק פשוט $\;(N;v)\;$ נקרא משחק הומוגני אם יש לו הצגה הומוגנית.

כך למשל ההצגה $\;[3;2,2,2]\;$ הינה הצגה הומוגנית, $\;[{\tfrac {2}{3}};{\tfrac {1}{3}},{\tfrac {1}{3}},{\tfrac {1}{3}}]\;$ הצגה הומוגנית מנורמלת ו-$\;[5;4,4,1]\;$ הצגה לא הומוגנית (וכולן הצגות של אותו משחק רוב משוקלל!).
לעומת זאת, למשחק $\;[5;2,2,2,1,1,1]\;$ אין הצגה הומוגנית כלל.

גרעינון של משחק רוב משוקלל סכום קבוע

סימונים

יהי $\;(N;v)\;$ משחק פשוט ו-$\;y\in \mathbb {R} ^{n}\;$ וקטור כלשהו. נסמן: $\;q(y)=\min _{S\in {\mathcal {W}}^{m}}y(S)\;$.

ע"פ סימון זה, $\;[q(w),w]\;$ היא הצגה של משחק הרוב המשוקלל $\;[q;w]\;$.
$\;[q(w),w]\;$ הצגה הומוגנית אם ורק אם לכל $\;S\subseteq {\mathcal {W}}^{m}\;$ מתקיים $\;w(S)=q(w)\;$

גרעינון של משחק רוב משוקלל סכום קבוע

משפט: יהי $\;[q(w);w]\;$ משחק רוב משוקלל סכום קבוע, ויהי $\;[q(w);w]\;$ הגרעינון של המשחק, אזי $\;[q(w);w]\;$ היא הצגה מנורמלת של המשחק.

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

טענת עזר 1: יהי $\;x\in \mathbb {R} _{+}^{n}\;$ וקטור המקיים $\;\textstyle \sum _{i=1}^{n}x_{i}=1\;$. יהי $\;(N;v)\;$ משחק פשוט מונוטוני סכום קבוע. $\;[q(x);x]\;$ היא הצגה של $\;(N;v)\;$ אם ורק אם $\;q(x)>{\tfrac {1}{2}}\;$.
הוכחת טענת עזר 1:
בתחילה, נניח $\;[q(x);x]\;$ הצגה של $\;(N;v)\;$. קואליציה מנצחת במשחק אם ורק אם סכום המשקולות של חבריה גדול או שווה ל-$\;q(x)\;$. נניח בשלילה $\;q(x)\leq {\tfrac {1}{2}}\;$. כלומר, קיימת קואליציה מינימלית מנצחת $\;{\hat {S}}\;$ כך ש:
$\;x(N\smallsetminus {\hat {S}})=x(N)-x({\hat {S}})=1-x({\hat {S}})=1-q(x)\geq {\tfrac {1}{2}}\geq q(x)\;$
כלומר, גם $\;N\smallsetminus {\hat {S}}\;$ מנצחת, בסתירה לכך שהמשחק סכום קבוע ($\;v({\hat {S}})+v(N\smallsetminus {\hat {S}})=2>1=v(N)\;$).
כעת, נניח $\;q(x)>{\tfrac {1}{2}}\;$. תהי קואליציה $\;S\;$.
אם $\;S\;$ מנצחת אזי היא מכילה קואליציה זוכה מינימלית $\;{\tilde {S}}\;$ ולכן $\;x(S)\geq x({\tilde {S}})\geq q(x)\;$.
אם $\;S\;$ מפסידה אזי $\;N\smallsetminus S\;$ מנצחת (שכן המשחק סכום קבוע) ומתקיים $\;x(N\smallsetminus S)\geq {\tfrac {1}{2}}\;$. כלומר $\;x(S)=x(N)-x(N\smallsetminus S)=1-x(N\smallsetminus S)\leq 1-q(x)\leq {\tfrac {1}{2}}<q(x)\;$
בסה"כ קיבלנו $\;v(S)=1\;$ (כלומר $\;S\;$ זוכה) אם ורק אם $\;x(S)\geq q(x)\;$.
כלומר $\;[q(x);x]\;$ היא הצגה של $\;(N;v)\;$

טענת עזר 2: יהי $\;(N;v)\;$ משחק פשוט מונוטוני סכום קבוע. ויהי $\;x^{*}={\mathcal {N}}(N;v)\;$ הגרעינון של המשחק. אזי לכל $\;x\in X(N;v)\;$ מתקיים $\;q(x^{*})\geq q(x)\;$. (הערה: $\;X(N;v)\;$ היא קבוצת וקטורי התשלומים ב-$\;(N;v)\;$)
הוכחת טענת עזר 2:
יהי $\;x\in X(N;v)\;$ כלשהו. $\;x^{*}\;$ הוא הגרעינון ולכן $\;\theta _{1}(x^{*})\geq \theta _{1}(x)\;$ כלומר:

$\;\max _{S\subseteq N}e(S,x^{*})\leq \max _{S\subseteq N}e(S,x)\;$.
כמו כן מתקיים:

$\;\max _{S\subseteq N}e(S,x){\underset {(1)}{=}}\max {\big \{}\max _{S\;win}e(S,x),\max _{S\;lose}e(S,x){\big \}}{\underset {(2)}{=}}\max _{S\;win}e(S,x)=\max _{S\;win}(1-x(S))=\max _{S\in {\mathcal {W}}^{m}}(1-x(S)){\underset {(3)}{=}}1-\min _{S\in {\mathcal {W}}^{m}}(1-x(S))=1-q(x)\;$

כאשר שוויון (1) מתקיים, שכן $\;\max _{S\;win}e(S,x)=\max _{S\;win}(v(S)-x(S))\geq 0\;$ (כי למשל $\;N\;$ היא קואליציה זוכה עם עודף 0),
השוויון (2) מתקיים שכן $\;\max _{S\;lose}e(S,x)\leq 0\;$ (עבור קואליציה מפסידה $\;v(S)=0\;$ ו- $\;x(S)\geq 0\;$, מכיוון ש- $\;x\in X(N;v)\;$).
השוויון (3) מתקיים שכן $\;x_{i}\geq 0\;$ לכל השחקנים ( $\;x\in X(N;v)\;$) ולכן על מנת למקסם את $\;1-x(S)\;$ יש למזער את $\;x(S)\;$ על פני הקואליציות הזוכות המינימליות (וניתן למקסם עליהן בלבד, שכן המשחק מונוטוני).

לפיכך מתקיים:
$\;q(x^{*})=1-\max _{S\subseteq N}e(S,x^{*})\geq \ 1-max_{S\subseteq N}e(S,x)=q(x)\;$

הוכחת המשפט:
תהי $\;[{\hat {q}};{\hat {w}}]\;$ הצגה מנורמלת של $\;[q;w]\;$. ע"פ טענת עזר 1 מתקיים $\;q({\hat {w}})>{\tfrac {1}{2}}\;$. מטענת עזר 2, מתקיים $\;q(x^{*})\geq q({\hat {w}})\;$, כלומר $\;q(x^{*})>{\tfrac {1}{2}}\;$.
מכיוון ש- $\;x^{*}(N)=v(N)=1\;$, ע"פ טענת עזר 1 נקבל $\;[q(x^{*});x^{*}]\;$ היא הצגה מנורמלת של המשחק.

גרעינון של משחק רוב משוקלל סכום קבוע הומוגני

טענה: יהי $\;(N;v)\;$ משחק רוב משוקלל הומוגני. אז יש לו הצגה הומוגנית שבה שחקני אפס מקבלים 0.
הוכחה: תהי $\;[q;w]\;$ הצגה הומוגנית של המשחק. לכל קואליציה זוכה מינימלית $\;S\in {\mathcal {W}}^{m}\;$ מתקיים $\;q(w)=w(S)\;$ . תהי $\;D\;$ קבוצת שחקני האפס. נגדיר:
$\;{\hat {q}}={\tfrac {q(w)}{\sum _{j\notin D}w_{j}}}\;$
$\;{\hat {w}}_{i}={\begin{cases}{\tfrac {w_{i}}{\sum _{j\notin D}w_{j}}}&i\notin D\\0&i\in D\end{cases}}\;$
נותר לראות כי $\;[{\hat {q}};{\hat {w}}]\;$ היא הצגה הומוגנית של המשחק:
תהי קואליציה זוכה מינימלית $\;S\in {\mathcal {W}}^{m}\;$. ממינימליות $\;S\;$, נקבל כי $\;S\;$ לא מכילה שחקני אפס, ולכן מתקיים:

$\;{\hat {w}}(S)=\sum _{i\in S}{\tfrac {w_{i}}{\sum _{j\notin D}w_{j}}}={\tfrac {\sum _{i\in S}w_{i}}{\sum _{j\notin D}w_{j}}}={\tfrac {q(w)}{\sum _{j\notin D}w_{j}}}={\hat {q}}\;$
כלומר: $\;\forall S\in {\mathcal {W}}^{m}\;.\;{\hat {w}}(S)={\hat {q}}\;$. ולכן $\;[{\hat {q}};{\hat {w}}]\;$ הצגה הומוגנית של המשחק.

משפט: יהי $\;[q(w);w]\;$ משחק רוב משוקלל סכום קבוע הומוגני. הגרעינון הוא ההצגה המנורמלת ההומוגנית היחידה שבה המשקל של כל שחקן אפס הוא 0.

הוכחת המשפט:
מקרה א': קיים שחקן i עבורו $\;v(i)=1\;$.
$\;(N;v)\;$ משחק סכום קבוע ולכן $\;1+v(N\smallsetminus {i})=v(i)+v(N\smallsetminus {i})=v(N)=1\;$, כלומר $\;v(N\smallsetminus {i})=0\;$. המשחק מונוטוני ולכן: $\;\forall S\subseteq N\smallsetminus {i}=0\;$,
וסה"כ נקבל $\;v(S)={\begin{cases}1&i\in S\\0&i\notin S\end{cases}}\;$,
כלומר i דיקטטור.
במקרה זה, ההצגות ההומוגניות המנורמלות של המשחק נתונות על ידי $\;[q;w]\;$ עבור כל $\;q\in ({\tfrac {1}{2}},1]\;$ ועבור וקטור משקולות $\;w=(w_{j})_{j=1}^{n}\;$ המקיים $\;w_{i}=q\;$ ו-$\;\textstyle \sum _{j=1}^{n}w_{j}=1\;$.
ההצגה המנורמלת היחידה בה משקל כל שחקן אפס הוא 0, היא זו בה $\;q=1\;$ ו-וקטור המשקולות הוא: $\;w_{j}={\begin{cases}1&j=i\\0&j\neq i\end{cases}}\;$.
וקטור משקולות זה הוא הגרעינון של המשחק (וגם ערך שפלי), מכיוון ששחקני אפס מקבלים 0 בגרעינון.

מקרה ב': לכל שחקן i מתקיים $\;v(i)=0\;$.
נסמן את קבוצת שחקני האפס במשחק ב-$\;D\;$. מהטענה שהוכחנו - יש למשחק הצגה הומוגנית שבה המשקל של כל שחקן אפס הוא 0. נסמן את ההצגה ב-$\;[q(y),y]\;$, ומתקיים $\;\forall S\subseteq N\;.\;y(S)=q(y)\;$. נגדיר את הפאון (פוליטופ) $\;P\;$ הבא:
$\;P={\big \{}x\in \mathbb {R} ^{n}\;{\big |}\;\forall i\in N\;.\;x_{i}\geq v(i)\;\;;\;\;x(N)=v(N)\;\;;\;\;\forall S\in {\mathcal {W}}^{m}\;.\;x(S)\geq q(y)\;\;;\;\;\forall i\in D\;.\;x_{i}=0{\big \}}\;$

הווקטורים ב-$\;P\;$ יעילים וסבירים פרטית, כלומר $\;P\subseteq X(N;v)\;$.
$\;[q(y);y]\;$ היא הצגה הומוגנית שבה משקל כל שחקן אפס הוא 0 ולכן $\;y\in P\;$, כלומר $\;y\in X(N;v)\;$.
מהמשפט הקודם (אודות גרעינון של משחק רוב משוקלל סכום קבוע), הגרעינון, נסמנו ב-$\;x^{*}\;$, הוא הצגה מנורמלת של המשחק, ולכן לכל $\;S\in {\mathcal {W}}^{m}\;$ מתקיים $\;x^{*}(S)\geq q(x^{*})\;$.
מטענת עזר ב' (שבהוכחת המשפט הקודם), $\;y\in X(N;v)\;$ גורר $\;q(x^{*})\geq q(y)\;$, ולכן לכל $\;S\subseteq {\mathcal {W}}^{m}\;$ מתקיים $\;x^{*}(S)\geq q(y)\;$.
כלומר, $\;x^{*}\in P\;$.
נניח בשלילה $\;y\neq x^{*}\;$. כלומר ב-$\;P\;$ יש לפחות שתי נקודות קיצון: $\;y\;$ ו-$\;z\;$ כך ש-$\;z\neq y\;$. כלומר, קיים אי שוויון בהגדרת $\;P\;$ שמקבל שוויון עבור $\;z\;$ אך מתקיים אי שוויון חזק עבור $\;y\;$. עבור $\;y\;$ כל האי-שיוויונים $\;x(S)\geq q(y)\;$ מתקיימים כשוויון (שכן $\;[q(y),y]\;$ הצגה הומוגנית, כלומר: $\;\forall S\in {\mathcal {W}}^{m}\;.\;y(S)=q(y)\;$). לכן בהכרח $\;\exists i\;.\;(z_{i}=0=v(i))\,\land \,(y_{i}>0=v(i))\;$.
בפרט $\;\exists i\notin D\;.\;z_{i}=0=v(i)\;$ (שכן לכל $\;i\in D\;$ מתקיים $\;y_{i}=0=v(0)\;$).
נסמן ב-j את השחקן שמקיים $\;j\notin D\;$ ו- $\;z_{j}=0\;$.
j אינו שחקן 0 ולכן קיימת קואליציה $\;S\;$ כך ש-$\;v(S)=0\;$ אך $\;v(S\cup {i})=1\;$. תהי $\;S_{0}\;$ קואליציה מינימלית שעבורה מתקיים הדבר. מתקיים אפוא: $\;S\cup {j}\in {\mathcal {W}}^{m}\;$.
$\;S_{0}\;$ מפסידה, ולכן, $\;N\smallsetminus S_{0}\;$ מנצחת (שכן המשחק סכום קבוע) ומתקיים: $\;j\in N\smallsetminus S_{0}\;$. לכן:

$\;q(y){\underset {(1)}{\leq }}z(N\smallsetminus S_{0})=1-z(S_{0})=1-z(S_{0}\cup {j}){\underset {(2)}{\leq }}1-q(y)\;$

אי שוויון (1) מתקיים כיוון ש-$\;z(T)\geq q(y)\;$ לכל קואליציה $\;T\;$ מנצחת, ו-$\;N\smallsetminus S_{0}\;$ היא קואליציה מנצחת
אי שוויון (2) מתקיים מסיבה דומה, עבור הקואליציה המנצחת $\;S_{0}\cup {j}\;$.

סה"כ מתקיים $\;q(y)\leq {\tfrac {1}{2}}\;$, וזוהי סתירה לטענת עזר 1 (שבהוכחת המשפט הקודם).
לפיכך מתקבל: $\;y=x^{*}\;$. כלומר הגרעינון הוא ההצגה ההומוגנית היחידה שבה המשקל של כל שחקן אפס הוא 0.

ראו גם

• תורת המשחקים - מונחים

לקריאה נוספת

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