משחק קמור

משפחת המשחקים הקמורים הוגדרה על ידי לויד שפלי (1971). משחק קמור הוא משחק קואליציוני בו התרומה השולית של כל שחקן גדלה ככל שהקואליציה אליה הוא מצטרף גדולה יותר, לכן במשחקים קמורים לשחקנים כדאי להצטרף לקואליציות גדולות ככל האפשר.

הגדרה פורמלית: משחק $\,(N;v)$ נקרא קמור (convex) אם לכל זוג קואליציות $\,S,\,T$ מתקיים: $v(S)+v(T)\leq v(S\cup T)+v(S\cap T)$.

כל משחק קמור הוא משחק סופר אדיטיבי, מכיוון שאם $\,S,\,T$ זרות, חיתוכן ריק ו $v(\emptyset )=0$ במשחק קואליציוני.

ההגדרה המתאימה עבור משחקי הוצאות היא: משחק $\,(N;c)$ נקרא קמור אם לכל זוג קואליציות $\,S,\,T$ מתקיים: $c(S)+c(T)\geq c(S\cup T)+c(S\cap T)$.

שקילות משחק קמור

משפט: הטענות הבאות שקולות:

1. המשחק $\,(N;v)$ קמור.

2. לכל $S\subseteq T\subseteq N$ ולכל $R\subseteq N\setminus T$ מתקיים: $v(S\cup R)-v(S)\leq v(T\cup R)-v(T)$.

3. לכל $S\subseteq T\subseteq N$ ולכל $i\in N\setminus T$ מתקיים: $v(S\cup \{i\})-v(S)\leq v(T\cup \{i\})-v(T)$.

כלומר, משחק $\,(N;v)$ הוא קמור אם ורק אם התרומה השולית של שחקן $\,i$ ($v(S\cup \{i\})-v(S)$) או של קבוצת שחקנים $\,R$ ($v(S\cup R)-v(S)$) לקואליציה $\,S$ גדולה יותר ככל שהקואליציה $\,S$ גדולה יותר.

הוכחת המשפט

$.2\Leftarrow .1$

נציב ב- $v(S)+v(T)\leq v(S\cup T)+v(S\cap T)$ את $R\cup S$ במקום $\,S$ ונקבל:

$\Leftarrow v(R\cup S)+v(T)\leq v(\{R\cup S\}\cup T)+v(\{R\cup S\}\cap T)$ $v(R\cup S)+v(T)\leq v(R\cup T)+v(S\cap T)$ (לפי- $S\subseteq T$ ו- $R\cap T=\emptyset$ ).

ולכן נובעת הטענה $v(S\cup R)+v(T)\leq v(R\cup T)+v(S)$.

$.3\Leftarrow .2$

נציב ב-2. את $\{i\}\subseteq N\setminus T$ במקום $\,R$ ונקבל: $v(S\cup \{i\})-v(S)\leq v(T\cup \{i\})-v(T)$ כנדרש.

$.1\Leftarrow .3$

תהיינה זוג קואליציות $\,S,\,T$. אם $S\subseteq T$ או $T\subseteq S$ אזי התנאי למשחק קמור $v(S)+v(T)\leq v(S\cup T)+v(S\cap T)$ מתקיים עם שוויון, ולכן נניח כי לא קיים יחס הכלה בין הקבוצות.

נסמן - $B=S\setminus T=\{i_{1},\ldots ,i_{r}\},A=S\cap T$.

כעת נשים לב ש- $A\subseteq T$ וגם $i_{1}\notin T$ ולכן בהינתן קיום של תנאי 3 נקבל: $v(A\cup \{i_{1}\})-v(A)\leq v(T\cup \{i_{1}\})-v(T)$ נסמן אי שוויון זה ב- $[1]$.

נסתכל כעת על הקבוצות - $A\cup \{i_{1}\}\subseteq T\cup \{i_{1}\}$ וגם $i_{2}\notin T\cup \{i_{1}\}$ וגם לגביהן נוכל להשתמש ב-3 ולקבל: $v(A\cup \{i_{1},i_{2}\})-v(A\cup \{i_{1}\})\leq v(T\cup \{i_{1},i_{2}\})-v(T\cup \{i_{1}\})$ נסמן זאת ב- $[2]$.

נמשיך בתהליך זה $\,r-1$ פעמים עבור איברי הקבוצה $B\setminus \{i_{r}\}=\{i_{1},\ldots ,i_{r-1}\}$ ונשאר עם $A\cup B\setminus \{i_{r}\}\subseteq T\cup B\setminus \{i_{r}\}$. נשתמש שוב בטענה 3 כדי לקבל את אי השוויון הבא: $v(A\cup B)-v(A\cup B\setminus \{i_{r}\})\leq v(T\cup B)-v(T\cup B\setminus \{i_{r}\})$ יסומן ב- $[\,r]$ .

קיבלנו $\,r$ אי שיוויונים חלשים שנוכל לסכום יחדיו (כל אגפי ימין וכל אגפי שמאל בנפרד):

${\begin{array}{cl}+{\underline {\left\{{\begin{array}{cl}v(A\cup \{i_{1}\})-v(A)\leq v(T\cup \{i_{1}\})-v(T)\\v(A\cup \{i_{1},i_{2}\})-v(A\cup \{i_{1}\})\leq v(T\cup \{i_{1},i_{2}\})-v(T\cup \{i_{1}\})\\\vdots \\v(A\cup B)-v(A\cup B\setminus \{i_{r}\})\leq v(T\cup B)-v(T\cup B\setminus \{i_{r}\})\end{array}}\right.}}\\v(A\cup B)-v(A\cup B\setminus \{i_{r}\})+\dots +v(A\cup \{i_{1}\})-v(A))\leq v(T\cup B)-v(T\cup B\setminus \{i_{r}\})+\dots +v(T\cup \{i_{1}\})-v(T)\end{array}}$

בכל אחד מהאגפים קיבלנו טור טלסקופי ולכן לאחר צמצום האיברים המתאימים: $v(A\cup B)-v(A)\leq v(T\cup B)-v(T)$

משום ש-$T\cup B=S\cup T,A\cup B=S\Leftarrow A=S\cap T,B=S\setminus T$

נציב זאת באי השוויון האחרון: $v(S)-v(S\cap T)\leq v(S\cup T)-v(T)$ כנדרש.

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

משפט: הליבה של משחק קמור אינה ריקה.

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

הנקודה החשובה היא לכל סידור של השחקנים יהיה קיים וקטור כזה בליבה.

הוכחת המשפט

הערה: לאורך כל ההוכחה נשתמש בסימון המקובל הבא: $X(S):=\sum _{i\in S}X_{i}$

יהי $\,(N,v)$ משחק קמור. ויהי וקטור $\,x$ וקטור התשלומים הבא:

$x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\\\end{pmatrix}}={\begin{pmatrix}v(\{1\})\\v(\left\{1,2\right\})-v(\{1\})\\\vdots \\v(N)-v(\left\{1,2,\dots ,n-1\right\})\\\end{pmatrix}}$

את ההוכחה נבצע באינדוקציה על מספר השחקנים ב- $(\left|N\right|=n)N$.

עבור $\left|N\right|=1$:

$x={\begin{pmatrix}x_{1}\\\end{pmatrix}}={\begin{pmatrix}v(\{1\})\\\end{pmatrix}}$ , נבדוק כי וקטור זה אכן שייך לליבה:

1. $\sum _{i=1}^{n=1}X_{i}=x_{1}=v(\{1\})=v(N)$ (תנאי היעילות מתקיים).

2. $\,X(S)=x_{1}=v(\{1\})=v(S)$ (תנאי הסבירות מתקיים לכל קואליציה משום שקיימת רק קואליציה אחת לא ריקה והיא השחקן $\,x_{1}$ עצמו).

לכן $\,x$ נמצא בליבה.

נניח כי המשפט מתקיים עבור $\left|N\right|=n-1$ ונוכיח אותו עבור $\left|N\right|=n$ :

1. $\sum _{i=1}^{n}X_{i}=\sum _{i=1}^{n-1}X_{i}+x_{n}=x(N\setminus \{n\})+x_{n}=v(\left\{1,2,\dots ,n-1\right\})+v(N)-v(\left\{1,2,\dots ,n-1\right\})=v(N)$ (תנאי היעילות מתקיים, כאשר בוצע שימוש ביעילות הווקטור באורך $\,n-1$ מהנחת האינדוקציה).

2. תהי קואליציה כלשהי $\,S\subseteq N$ , נבדיל בין שני מצבים אפשריים: $\,n\in S$ ו- $\,n\notin S$ .

$S\subseteq N\setminus \{n\}\Leftarrow \,n\notin S$ ולכן נקבל: $\,X(S)\geq v(S)$ ישירות מהנחת האינדוקציה עבור כל קואליצה, בשל קיום תנאי הסבירות במשחק בגודל $\left|N\right|=n-1$ . $S\setminus \{n\}\subseteq N\setminus \{n\}\Leftarrow S\subseteq N,n\in S$ כעת נוכל להשתמש בשקילות של משחק קמור לפי הטענה שהוכחה לעיל (תנאי 3) עבור השחקן ה- $\,n$ ולקבל: $v(S)-v(S\setminus \{n\})\leq v(N)-v(N\setminus \{n\})\Leftarrow v(S\setminus \{n\}\cup \{n\})-v(S\setminus \{n\})\leq v(N\setminus \{n\}\cup \{n\})-v(N\setminus \{n\})$ .

מכאן נובע ש- $v(S)-v(S\setminus \{n\})\leq x_{n}$

מהנחת האינדוקציה ידוע שתנאי הסבירות מתקיים עבור המשחק עם $\,n-1$ שחקנים, ולכן $-x(S\setminus \{n\})\leq -v(S\setminus \{n\})\Leftarrow v(S\setminus \{n\})\leq x(S\setminus \{n\})$ .

נציב זאת באי השיווין שהתקבל קודם לכן $v(S)\leq x_{n}+x(S\setminus \{n\})\Leftarrow v(S)-x(S\setminus \{n\})\leq v(S)-v(S\setminus \{n\})\leq x_{n}$.

$v(S)\leq x(S)\Leftarrow$ ולכן גם תנאי הסבירות מתקיים. אז $\,x$ נמצא בליבה והמשפט מוכח לכל $\,n$ טבעי.

ערך שפלי של משחק קמור

ערך שפלי של משחק קמור אף הוא נמצא בליבה.

בהוכחה שהליבה של משחק קמור אינה ריקה, הגדרנו את וקטור התשלומים $\ x$ לפי סדר שרירותי של השחקנים במשחק. למעשה, לכל תמורה על אוסף השחקנים $\pi :N\to N$ ניתן להגדיר באופן דומה וקטור תשלומים $\ x_{\pi }$:

$x_{\pi }={\begin{pmatrix}v(\{\pi (i)\})\\v(\left\{\pi (1),\pi (2)\right\})-v(\{\pi (1)\})\\\vdots \\v(N)-v(\left\{\pi (1),\pi (2),\dots ,\pi (n-1)\right\})\\\end{pmatrix}}$

משום שבהוכחה על הליבה של משחק קמור סידרנו את השחקנים באופן שרירותי, ההוכחה תקפה לכל וקטור תשלומים $\ x_{\pi }$ כזה, ולכן גם הוא בליבה.

הנוסחה לחישוב ערך שפלי היא הממוצע המשוקלל של הווקטורים הללו: $\ Sh(N,v)={\frac {1}{|N|!}}\sum _{\pi }x_{\pi }$. הליבה היא קבוצה קמורה, ומזה נובע שגם ערך שפלי נמצא בה.

דוגמה למשחק קמור

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

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946