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

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

## הגדרה פורמלית
**משחק רוב משוקלל** (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) 
כאשר \; 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 

ניתן לשים לב שישנן מספר קואליציות שונות המסוגלות ליצור רוב משוקלל. כך למשל: \; 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} 

בסך הכול קיבלנו \; 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)) \, \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)}{\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.

## ראו גם
* תורת המשחקים - מונחים

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

קטגוריה:תורת המשחקים