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

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

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

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

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

  • קבוצת שחקנים \; N={1,2,...n} \;
  • מכסה (quata) \; q \ge 0 \;
  • משקולות \; w_1,w_2,...,w_n \;. כאשר \; w_i \; - משקולת של שחקן i מקיימת: \; w_i \ge 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) \le \tfrac{1}{2} \;. כלומר, קיימת קואליציה מינימלית מנצחת \; \hat{S} \; כך ש:
\; x(N \smallsetminus \hat{S})=x(N)-x(\hat{S})=1-x(\hat{S})=1-q(x) \ge \tfrac{1}{2} \ge 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) \ge x(\tilde{S}) \ge q(x) \;.
אם \; S \; מפסידה אזי \; N \smallsetminus S \; מנצחת (שכן המשחק סכום קבוע) ומתקיים \; x(N \smallsetminus S) \ge \tfrac{1}{2} \;. כלומר \; x(S)=x(N)-x(N \smallsetminus S)=1-x(N \smallsetminus S) \le 1-q(x) \le \tfrac{1}{2} < q(x) \;
בסה"כ קיבלנו \; v(S)=1 \; (כלומר \; S \; זוכה) אם ורק אם \; x(S) \ge q(x) \;.
כלומר \; [q(x);x] \; היא הצגה של \; (N;v) \;

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

\; \max_{S \subseteq N} e(S,x^*) \le \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)) \ge 0 \; (כי למשל \; N \; היא קואליציה זוכה עם עודף 0),
השוויון (2) מתקיים שכן \; \max_{S \; lose}e(S,x) \le 0 \; (עבור קואליציה מפסידה \; v(S)=0 \; ו- \; x(S) \ge 0 \;, מכיוון ש- \; x \in X(N;v) \;).
השוויון (3) מתקיים שכן \; x_i \ge 0 \; לכל השחקנים ( \; x \in X(N;v) \;) ולכן על מנת למקסם את \; 1-x(S) \; יש למזער את \; x(S) \; על פני הקואליציות הזוכות המינימליות (וניתן למקסם עליהן בלבד, שכן המשחק מונוטוני).

לפיכך מתקיים:
\; q(x^*)=1 - \max_{S \subseteq N} e(S,x^*) \ge \ 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^*) \ge 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 \ne 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 \ge v(i) \;\; ; \;\; x(N)=v(N) \;\; ; \;\; \forall S \in \mathcal{W}^m \; . \; x(S) \ge 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) \ge q(x^*) \;.
מטענת עזר ב' (שבהוכחת המשפט הקודם), \; y \in X(N;v) \; גורר \; q(x^*) \ge q(y) \;, ולכן לכל \; S \subseteq \mathcal{W}^m \; מתקיים \; x^*(S) \ge q(y) \;.
כלומר, \; x^* \in P \;.
נניח בשלילה \; y \ne x^* \;. כלומר ב-\; P \; יש לפחות שתי נקודות קיצון: \; y \; ו-\; z \; כך ש-\; z \ne y \;. כלומר, קיים אי שוויון בהגדרת \; P \; שמקבל שוויון עבור \; z \; אך מתקיים אי שוויון חזק עבור \; y \;. עבור \; y \; כל האי-שיוויונים \; x(S) \ge q(y) \; מתקיימים כשוויון (שכן \; [q(y),y] \; הצגה הומוגנית, כלומר: \; \forall S \in \mathcal{W}^m \; . \; y(S) = q(y) \;). לכן בהכרח \; \exists i \; . \; (z_i=0=v(i)) \, \and \, (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)}{\le} z(N \smallsetminus S_0) = 1-z(S_0) = 1-z(S_0 \cup {j}) \underset{(2)}{\le} 1-q(y) \;

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

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

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

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