משחק תומך

משחק תומך (באנגלית: Carrier Game) הוא מושג בתורת המשחקים בתחום המשחקים השיתופיים. משחק תומך הוא משחק פשוט ומונוטוני שמוגדר על ידי קואליציה מסוימת. כל משחק עם אותה קבוצת שחקנים יכול להיות מתואר על ידי צירוף ליניארי יחיד של כל המשחקים התומכים. למשחקים תומכים יש חשיבות באפיון של ערך שפלי של משחק כלשהו.

סימונים והגדרות בסיסיות במשחקים שיתופיים

נגדיר:

1. $\,N=\{1,2,\dots ,n\}$ - קבוצה לא ריקה וסופית של השחקנים.

2. $\,S\subseteq \,N=\{1,2,\dots ,n\}$ - תת-קבוצה של שחקנים תקרא קואליציה.

3. $\,v:2^{N}\rightarrow \mathbb {R}$ - פונקציית תשלום. פונקציה המשייכת לכל קואליציה מספר ממשי כלשהו, כאשר $\,v(\emptyset )=0$.

ייצוג מרחב המשחקים כמרחב ליניארי

בהינתן הקבוצה $\,N=\{1,2,\dots ,n\}$, כל משחק $\left(N,v\right)$ נקבע ביחידות על ידי הערכים $v\left(S\right)$ לכל קואליציה $\emptyset \neq \,S\subseteq \,N$. דהיינו, ניתן להתייחס למשחק כעל וקטור במרחב $\mathbb {R} ^{2^{n}-1}$.

כעת, ניתן להגדיר "חיבור" בין משחקים (עם אותה קבוצת שחקנים $\,N=\{1,2,\dots ,n\}$ ) ו"כפל משחק בסקלר" על ידי חיבור הווקטורים הללו והכפלתם בסקלר כפי שעושים במרחב $\mathbb {R} ^{2^{n}-1}$ ומכאן המסקנה שאפשר להתאים את קבוצת כל המשחקים (עם אותם השחקנים) עם המרחב הליניארי $\mathbb {R} ^{2^{n}-1}$.

נשאלת השאלה: "מה יכול להיות בסיס לכל אותם משחקים?".

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

הגדרה

משחק תומך

תהי $\emptyset \neq T\subseteq N$ קואליציה. המשחק התומך על $\,T$ הוא המשחק הפשוט והמונוטוני $\left(N;u_{T}\right)$ כאשר:

$u_{T}(S)=\left\{{\begin{array}{ll}1&\ \ \ \ \forall S:T\subseteq S\\0&\ \ \ \ else\end{array}}\right.$

יש בסה"כ $2^{\left|N\right|}-1$ משחקים תומכים המהווים בסיס למרחב כל המשחקים.

משחק $\alpha$ תומך

תהי $\emptyset \neq T\subseteq N$ קואליציה ו- $\alpha \in \mathbb {R}$. משחק יקרא $\alpha$ - תומך ויסומן $\left(N;u_{T,\alpha }\right)$ כאשר:

$u_{T,\alpha }(S)=\left\{{\begin{array}{ll}\alpha &\ \ \ \ \forall S:T\subseteq S\\0&\ \ \ \ else\end{array}}\right.$

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

פריסת מרחב המשחקים בעזרת משחקים תומכים

משפט: כל משחק בצורה קואליציונית $\left(N,v\right)$ ניתן להביע כצירוף ליניארי של משחקים $\left(N;u_{T}\right)$ . כלומר, לכל משחק $\left(N,v\right)$ קיימים קבועים $\left(\alpha _{T}\right)_{\emptyset \neq T\subseteq N}$ כך ש-

$$v(S)=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T}(S)\alpha _{T}=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T,\alpha }(S)\ \ \ \ \ \forall S\subseteq N$$

הוכחת המשפט

כאמור ישנן $\,2^{n}-1$ קואליציות $\emptyset \neq T\subseteq N$ ולכן ישנם $\,2^{n}-1$ משחקים תומכים $\left(N;u_{T}\right)$ . כאמור כל משחק שכזה מייצג וקטור במרחב $\mathbb {R} ^{2^{n}-1}$ וכל שנותר להראות הוא כי וקטורים אלו הם בלתי תלויים ליניארית (בת"ל).

נניח בשלילה כי וקטורים אלו תלויים ליניארית ולכן קיימים קבועים $\left(\alpha _{T}\right)_{\emptyset \neq T\subseteq N}$ כך שלא כולם שווים לאפס ו- $0=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T}(S)\alpha _{T}\ \ \ \ \forall S\subseteq N$ (נסמן זאת ב-[1]) ונוכל להסתכל בהתאמה על המשחקים $\left(N;u_{T,\alpha }\right)$, משמע - $0=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T,\alpha }(S)\ \ \ \ \forall S\subseteq N$ .

נסתכל על הקבוצה הבאה $\,A=\{\emptyset \neq T\subseteq N:\left(\alpha _{T}\right)\neq 0\}$ ונבחר קואליציה אחת כך ש- $|T|=min\{|T|:T\in A\}$ ונסמנה ב- $\,T_{*}$. כעת נוכל להסיק שתי מסקנות:

1. $\alpha _{T_{*}}\neq 0$ .
2. $\forall T\subsetneq T_{*}\ \ \ \ \alpha _{T}=0$ .

נציב $\,S=T_{*}$ ב-[1] ונקבל

$$0=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T}(T_{*})\alpha _{T}=\sum _{\left\{\emptyset \neq T\subsetneq T_{*}\right\}}u_{T}(T_{*})\alpha _{T}+u_{T_{*}}(T_{*})\alpha _{T_{*}}+\sum _{\left\{\emptyset \neq T\nsubseteq T_{*}\right\}}u_{T}(T_{*})\alpha _{T}=0+u_{T_{*}}(T_{*})\alpha _{T_{*}}+0=\alpha _{T_{*}}\neq 0$$

ונשים לב שקיבלנו סתירה.

המעברים האחרונים בוצעו לפי:

1) הסכום הראשון $\sum _{\left\{\emptyset \neq T\subsetneq T_{*}\right\}}u_{T}(T_{*})\alpha _{T}=0$ משום ש- $\forall T\subsetneq T_{*}\ \ \ \ \alpha _{T}=0$ .

2) האיבר השני $u_{T_{*}}(T_{*})=1$ לפי הגדרת משחק תומך לעיל.

3) הסכום השלישי $\sum _{\left\{\emptyset \neq T\nsubseteq T_{*}\right\}}u_{T}(T_{*})\alpha _{T}=0$ לפי הגדרת משחק תומך לעיל.

משמע שהווקטורים בלתי תלויים ליניארית ולכן מהווים בסיס למרחב $\mathbb {R} ^{2^{n}-1}$ ולמרחב המשחקים בהתאם.

אפיון ערך שפלי על ידי משחקים תומכים

בהינתן משחק $\left(N,v\right)$, נרשום אותו כסכום של $2^{\left|N\right|}-1$ משחקים $\alpha$-תומכים: $v(S)=\sum _{\left\{\emptyset \neq T\subseteq N\right\}}u_{T,\alpha }(S)\ \ \ \ \ \forall S\subseteq N$. אזי ניתן להראות כי:

$Sh_{i}\left(N,v\right)=\sum _{\left\{T\subseteq N:i\in T\right\}}{\frac {\alpha _{T}}{\left|T\right|}}$

טענה: שחקנים סימטריים ושחקני אפס במשחק תומך

במשחק $\left(N;u_{T}\right)$ כל השחקנים ב- $\,T$ הם שחקנים סימטריים וכל השחקנים שאינם ב- $\,T$ הם שחקני אפס.

הוכחת הטענה

יהי שחקן $\,i\notin T$ ותהי קואליציה $\,S\subseteq N$. נחלק זאת לשני מצבים:

1. $\,T\subseteq S$ .
2. $\,T\nsubseteq S$ .

אם $T\subseteq S\cup \{i\}\Leftarrow T\subseteq S$ אז $u_{T}(S)=\,u_{T}(S\cup \{i\})=1$ .

אם $T\nsubseteq S\cup \{i\}\Leftarrow T\nsubseteq S$ כי $\,i\notin T$ ולכן $u_{T}(S)=\,u_{T}(S\cup \{i\})=0$ .

קיבלנו כי השחקן $\,i\notin T$ הוא שחקן אפס.

יהיו צמד שחקנים $\,i,\,j\in T$ וקואליציה $\,S\subseteq N$ כך ש- $\,i,\,j\notin \,S$. נשים לב ש $T\nsubseteq S\cup \{i\}$ כי $j\in T,j\notin S\cup \{i\}$ ובהתאם $T\nsubseteq S\cup \{j\}$ כי $i\in T,i\notin S\cup \{j\}$ ולכן מתקיים:

$\forall \,S\subseteq N:\,i,\,j\notin \,S\ \ \ \ v(S\cup \{i\})=v(S\cup \{j\})=0$ והשחקנים $\,i,\,j\in T$ סימטריים.

טענה: מושג פתרון של משחק תומך

אם $\phi$ מושג פתרון המקיים את תכונות: יעילות, שחקן אפס ו-סימטריה אזי:

$\phi _{i}(N;u_{T,\alpha })=\left\{{\begin{array}{ll}{\frac {\alpha }{|T|}}&\ \ \ \ \forall i\in T\\0&\ \ \ \ \forall i\notin T\end{array}}\right.$

הוכחת הטענה

לפי הטענה לעיל ידוע כי במשחק $\left(N;u_{T,\alpha }\right)$ כל השחקנים ב- $\,T$ הם שחקנים סימטריים וכל השחקנים שאינם ב- $\,T$ הם שחקני אפס ולכן מקיום תכונת שחקן האפס נובע ש- $\phi _{i}(N;u_{T,\alpha })=0\ \ \forall i\notin T$ . בנוסף ידוע כי כל השחקנים שכן ב-$\,T$ הם סימטריים ולכן - $\phi _{i}(N;u_{T,\alpha })=\phi _{j}(N;u_{T,\alpha })\ \ \forall i,j\in T$ ובנוסף מהיעילות נובע ש-

$\alpha =u_{T,\alpha }(N)=\sum _{\left\{i\in N\right\}}\phi _{i}(N;u_{T,\alpha })=\sum _{\left\{i\in T\right\}}\phi _{i}(N;u_{T,\alpha })+\sum _{\left\{i\notin T\right\}}\phi _{i}(N;u_{T,\alpha })=\sum _{\left\{i\in T\right\}}\phi _{i}(N;u_{T,\alpha })+0=|T|\times \phi _{i}(N;u_{T,\alpha })$

$\Rightarrow \phi _{i}(N;u_{T,\alpha })={\frac {\alpha }{|T|}}$

וההוכחה הושלמה.

ראו גם

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

לקריאה נוספת

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