משחק תומך

**משחק תומך** (באנגלית: **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 משחקים תומכים המהווים בסיס למרחב כל המשחקים.

### משחק <math>\alpha</math> תומך
תהי  \emptyset \neq T \subseteq N  קואליציה ו- \alpha \isin \mathbb {R} . משחק יקרא **<math>\alpha</math> - תומך** ויסומן  \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\ -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 . נחלק זאת לשני מצבים:
#  \,T \subseteq S  .
#  \,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} & \ \ \ \ \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} 


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

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

## לקריאה נוספת
*

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