הצגת המקור של הדף "משחק רוב משוקלל"

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

== הגדרה פורמלית ==
'''משחק רוב משוקלל''' (weighted majority game) הוא [[משחקים בצורה קואליציונית|משחק בצורה קואליציונית]] הנתון ע"י:
* קבוצת שחקנים <math>\; N={1,2,...n} \;</math>
* '''מכסה''' (quata) <math>\; q \ge 0 \;</math>
* '''משקולות''' <math>\; w_1,w_2,...,w_n \;</math>. כאשר <math>\; w_i \;</math> - '''משקולת של שחקן i''' מקיימת: <math>\; w_i \ge 0 \;</math>
כאשר השווי של קואליציה <math>\; S \;</math> נתון ע"י:
:<math>v(s) =
\left\{\begin{matrix}
1 &\mbox{if}\ w(S) \geq q \\
0 &\mbox{if}\ w(S) < q
\end{matrix}\right.
</math>
כאשר <math>\; w(S)=\sum_{i \in S}w_i \;</math>

ונהוג לסמן את המשחק באופן הבא: <math>\; [q;w_1,w_2,...,w_n] \;</math> או בקיצור, כאשר ברור על איזה וקטור משקולות מדובר: <math>\; [q;w] \;</math>

== דוגמה ==
דוגמה טובה למשחק רוב משוקלל היא הבחירות לכנסת.
נניח שבכנסת ישראל- בה יושבים 120 חברי כנסת ובה על מנת להרכיב ממשלה יש צורך ברוב של יותר מ-61 חברים מתקבלות התוצאות הבאות:
* מפלגה 1 זכתה ב-47 מנדטים.
* מפלגה 2 זכתה ב-35 מנדטים.
* מפלגה 3 זכתה ב-20 מנדטים.
* מפלגה 4 זכתה ב-13 מנדטים.
* מפלגה 5 זכתה ב-5 מנדטים.

אזי תתקבל מערכת המשקולות הבאה:
*<math>\; w_1=47 \;</math>
*<math>\; w_2=35 \;</math>
*<math>\; w_3=20 \;</math>
*<math>\; w_4=13 \;</math>
*<math>\; w_5=5 \;</math>

המשחק יכתב כך: <math>\; [61;47,35,20,13,5] \;</math>
והפונקציה הקואליציונית תוגדר בצורה הבאה:
:<math>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.
</math>

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

==הצגה הומוגנית והצגה מנורמלת==
משחק פשוט ומונוטוני נקבע על ידי '''אוסף הקואליציות המינימליות הזוכות''' בו, המסומן ע"י: <math>\; \mathcal{W}^m \;</math>
<br>
הצגה <math>\; [q;w_1,w_2,...,w_n] \;</math> של משחק פשוט <math>\; (N;v)\;</math> נקראת '''הצגה הומוגנית''' אם <math>\;\textstyle \sum_{i \in S}w_i \;</math> שווה, לכל קואליציה מינימלית זוכה <math>\; S \subseteq \mathcal{W}^m \;</math>.
<br>
הצגה <math>\; [q;w_1,w_2,...,w_n] \;</math> של משחק פשוט <math>\; (N,v) \;</math> נקראת '''הצגה מנורמלת''' אם <math>\; w(N)= \textstyle \sum_{i=1}^n w_i =1 \;</math>.
<br>
משחק פשוט <math>\; (N;v) \;</math> נקרא '''משחק הומוגני''' אם יש לו הצגה הומוגנית.
<br>
<br>
כך למשל ההצגה <math>\; [3;2,2,2] \;</math> היא הצגה הומוגנית, <math>\; [\tfrac{2}{3};\tfrac{1}{3},\tfrac{1}{3},\tfrac{1}{3}] \;</math> הצגה הומוגנית מנורמלת ו-<math>\; [5;4,4,1] \;</math> הצגה לא הומוגנית (וכולן הצגות של אותו משחק רוב משוקלל!). <br> לעומת זאת, למשחק <math>\; [5;2,2,2,1,1,1] \;</math> אין הצגה הומוגנית כלל.

==גרעינון של משחק רוב משוקלל סכום קבוע==
===סימונים===
יהי <math>\; (N;v) \;</math> משחק פשוט ו-<math>\; y \in \mathbb{R}^n \;</math> וקטור כלשהו. נסמן:
<math>\; q(y)= \min_{S \in \mathcal{W}^m}y(S) \;</math>.
<br>
<br> ע"פ סימון זה, <math>\; [q(w),w] \;</math> היא הצגה של משחק הרוב המשוקלל <math>\; [q;w] \;</math>.
<br> <math>\; [q(w),w] \;</math> הצגה הומוגנית אם ורק אם לכל <math>\; S \subseteq \mathcal{W}^m \;</math> מתקיים <math>\; w(S)=q(w) \;</math>

===גרעינון של משחק רוב משוקלל סכום קבוע===
'''משפט:''' יהי <math>\; [q(w);w] \;</math> משחק רוב משוקלל [[משחקים בצורה קואליציונית|סכום קבוע]], ויהי <math>\; [q(w);w] \;</math> ה[[גרעינון]] של המשחק, אזי <math>\; [q(w);w] \;</math> היא הצגה מנורמלת של המשחק. <br>
<br>
'''הוכחת המשפט''' <br>
על מנת להוכיח את המשפט, להלן שתי טענות עזר:
<br> <br>
'''טענת עזר 1:''' יהי <math>\; x \in \mathbb{R}_+^n \;</math> וקטור המקיים <math>\; \textstyle \sum_{i=1}^n x_i =1 \;</math>. יהי <math>\; (N;v) \;</math> משחק פשוט מונוטוני סכום קבוע. <math>\; [q(x);x] \;</math> היא הצגה של <math>\; (N;v) \;</math> אם ורק אם <math>\; q(x)> \tfrac{1}{2} \;</math>.
<br>
'''הוכחת טענת עזר 1:''' <br>
בתחילה, נניח <math>\; [q(x);x] \;</math> הצגה של <math>\; (N;v) \;</math>. קואליציה מנצחת במשחק אם ורק אם סכום המשקולות של חבריה גדול או שווה ל-<math>\; q(x) \;</math>. [[הוכחה בדרך השלילה|נניח בשלילה]] <math>\; q(x) \le \tfrac{1}{2} \;</math>. כלומר, קיימת קואליציה מינימלית מנצחת <math>\; \hat{S} \;</math> כך ש: <br>
<math>\; x(N \smallsetminus \hat{S})=x(N)-x(\hat{S})=1-x(\hat{S})=1-q(x) \ge \tfrac{1}{2} \ge q(x) \;</math> <br>
כלומר, גם <math>\; N \smallsetminus \hat{S} \;</math> מנצחת, בסתירה לכך שהמשחק סכום קבוע (<math>\; v(\hat{S})+v(N \smallsetminus \hat{S})=2 > 1=v(N) \;</math>).
<br>
כעת, נניח <math>\; q(x)> \tfrac{1}{2} \;</math>. תהי קואליציה <math>\; S \;</math>.
<br>
אם <math>\; S \;</math> מנצחת אזי היא מכילה קואליציה זוכה מינימלית <math>\; \tilde{S} \;</math> ולכן <math>\; x(S) \ge x(\tilde{S}) \ge q(x) \;</math>.
<br>
אם <math>\; S \;</math> מפסידה אזי <math>\; N \smallsetminus S \;</math> מנצחת (שכן המשחק סכום קבוע) ומתקיים <math>\; x(N \smallsetminus S) \ge \tfrac{1}{2} \;</math>. כלומר <math>\; x(S)=x(N)-x(N \smallsetminus S)=1-x(N \smallsetminus S) \le 1-q(x) \le \tfrac{1}{2} < q(x) \;</math>
<br>
בסה"כ קיבלנו <math>\; v(S)=1 \;</math> (כלומר <math>\; S \;</math> זוכה) אם ורק אם <math>\; x(S) \ge q(x) \;</math>.
<br>
כלומר <math>\; [q(x);x] \;</math> היא הצגה של <math>\; (N;v) \;</math>
<br> <br>
'''טענת עזר 2:''' יהי <math>\; (N;v) \;</math> משחק פשוט מונוטוני סכום קבוע. ויהי <math>\; x^*= \mathcal{N} (N;v) \;</math> הגרעינון של המשחק. אזי לכל <math>\; x \in X(N;v) \;</math> מתקיים <math>\; q(x^*) \ge q(x) \;</math>. (הערה: <math>\; X(N;v) \;</math> היא קבוצת [[ליבה של משחק שיתופי|וקטורי התשלומים]] ב-<math>\; (N;v) \;</math>)
<br>
'''הוכחת טענת עזר 2:'''<br>
יהי <math>\; x \in X(N;v) \;</math> כלשהו. <math>\; x^* \;</math> הוא הגרעינון ולכן <math>\; \theta_1(x^*) \ge \theta_1(x) \;</math> כלומר:<br> <br> <math>\; \max_{S \subseteq N} e(S,x^*) \le \max_{S \subseteq N} e(S,x) \;</math>. <br>
כמו כן מתקיים: <br>

<math>\; \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) \;</math>
<br><br>

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

לפיכך מתקיים: <br>
<math>\; q(x^*)=1 - \max_{S \subseteq N} e(S,x^*) \ge \ 1-max_{S \subseteq N} e(S,x)=q(x) \;</math>
<br><br>

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

===גרעינון של משחק רוב משוקלל סכום קבוע הומוגני===
'''טענה:''' יהי <math>\; (N;v) \;</math> משחק רוב משוקלל הומוגני. אז יש לו הצגה הומוגנית שבה [[שחקן אפס|שחקני אפס]] מקבלים 0.<br>
'''הוכחה:''' תהי <math>\; [q;w] \;</math> הצגה הומוגנית של המשחק. לכל קואליציה זוכה מינימלית <math>\; S \in \mathcal{W}^m \;</math> מתקיים <math>\; q(w)=w(S) \;</math> . תהי <math>\; D \;</math> קבוצת שחקני האפס. נגדיר:
<br>
<math>\; \hat{q} = \tfrac{q(w)}{\sum_{j \notin D} w_j} \;</math>
<br>
<math>\; \hat{w}_i = \begin{cases} \tfrac{w_i}{\sum_{j \notin D} w_j} & i \notin D \\ 0 & i \in D \end{cases} \;</math>
<br>
נותר לראות כי <math>\; [\hat{q};\hat{w}] \;</math> היא הצגה הומוגנית של המשחק: <br>
תהי קואליציה זוכה מינימלית <math>\; S \in \mathcal{W}^m \;</math>. ממינימליות <math>\; S \;</math>, נקבל כי <math>\; S \;</math> לא מכילה שחקני אפס, ולכן מתקיים: <br>
<br>
<math>\; \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} \;</math>
<br>
כלומר: <math>\; \forall S \in \mathcal{W}^m \; . \; \hat{w}(S)=\hat{q} \;</math>. ולכן <math>\; [\hat{q};\hat{w}] \;</math> הצגה הומוגנית של המשחק.
<br>
<br>
'''משפט:''' יהי <math>\; [q(w);w] \;</math> משחק רוב משוקלל סכום קבוע הומוגני. הגרעינון הוא ההצגה המנורמלת ההומוגנית היחידה שבה המשקל של כל שחקן אפס הוא 0.

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

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

== ראו גם ==
* [[תורת המשחקים - מונחים]]

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

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