משחק תומך

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

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

נגדיר:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,N = \{1,2,\dots,n\} } - קבוצה לא ריקה וסופית של השחקנים.

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

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

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

בהינתן הקבוצה הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \,N=\{1,2,\dots ,n\}} , כל משחק $\left(N,v\right)$ נקבע ביחידות על ידי הערכים $v\left(S\right)$ לכל קואליציה $\emptyset \neq \,S\subseteq \,N$. דהיינו, ניתן להתייחס למשחק כעל וקטור במרחב $\mathbb {R} ^{2^{n}-1}$.

כעת, ניתן להגדיר "חיבור" בין משחקים (עם אותה קבוצת שחקנים הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \,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. הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \alpha _{T_{*}}\neq 0} .
2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall T \subsetneq T_* \ \ \ \ \alpha_T = 0 } .

נציב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,S = T_* } ב-[1] ונקבל

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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) הסכום הראשון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{ \left\{ \emptyset \neq T \subsetneq T_* \right\} } u_T(T_*)\alpha_T = 0 } משום ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall T \subsetneq T_* \ \ \ \ \alpha_T = 0 } .

2) האיבר השני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_{T_*}(T_*) = 1} לפי הגדרת משחק תומך לעיל.

3) הסכום השלישי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{ \left\{ \emptyset \neq T \nsubseteq T_* \right\} } u_T(T_*)\alpha_T = 0 } לפי הגדרת משחק תומך לעיל.

משמע שהווקטורים בלתי תלויים לינארית ולכן מהווים בסיס למרחב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^{2^n -1}} ולמרחב המשחקים בהתאם.

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

בהינתן משחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(N,v\right)} , נרשום אותו כסכום של $2^{\left|N\right|}-1$ משחקים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} -תומכים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v(S)= \sum_{ \left\{ \emptyset \neq T \subseteq N \right\} } u_{T,\alpha}(S) \ \ \ \ \ \forall S \subseteq N } . אזי ניתן להראות כי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Sh_i \left(N,v\right) = \sum_{ \left\{ T \subseteq N: i \in T \right\} } \frac{\alpha_T}{ \left| T \right|}}

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

במשחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(N;u_T\right) } כל השחקנים ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T} הם שחקנים סימטריים וכל השחקנים שאינם ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T} הם שחקני אפס.

הוכחת הטענה

יהי שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i \notin T } ותהי קואליציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,S \subseteq N } . נחלק זאת לשני מצבים:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T \subseteq S } .
2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T \nsubseteq S } .

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T \subseteq S \cup \{i\} \Leftarrow T \subseteq S } אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_T(S) = \,u_T(S \cup \{i\}) = 1 } .

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T \nsubseteq S \cup \{i\} \Leftarrow T \nsubseteq S } כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i \notin T } ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_T(S) = \,u_T(S \cup \{i\}) = 0 } .

קיבלנו כי השחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i \notin T } הוא שחקן אפס.

יהיו צמד שחקנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i,\,j \in T } וקואליציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,S \subseteq N } כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i,\,j \notin \,S } . נשים לב ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T \nsubseteq S \cup \{i\} } כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j \in T, j \notin S \cup\{i\} } ובהתאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T \nsubseteq S \cup \{j\} } כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in T, i \notin S \cup\{j\} } ולכן מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall \,S \subseteq N : \,i,\,j \notin \,S \ \ \ \ v(S \cup \{i\}) = v(S \cup \{j\}) = 0 } והשחקנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,i,\,j \in T } סימטריים.

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

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi } מושג פתרון המקיים את תכונות: יעילות, שחקן אפס ו-סימטריה אזי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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. }

הוכחת הטענה

לפי הטענה לעיל ידוע כי במשחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(N;u_{T,\alpha}\right) } כל השחקנים ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T} הם שחקנים סימטריים וכל השחקנים שאינם ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T} הם שחקני אפס ולכן מקיום תכונת שחקן האפס נובע ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i(N;u_{T,\alpha}) = 0 \ \ \forall i \notin T } . בנוסף ידוע כי כל השחקנים שכן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,T} הם סימטריים ולכן - הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i(N;u_{T,\alpha}) = \phi_j(N;u_{T,\alpha}) \ \ \forall i,j \in T } ובנוסף מהיעילות נובע ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}) }

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \Rightarrow \phi _{i}(N;u_{T,\alpha })={\frac {\alpha }{|T|}}}

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

ראו גם

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

לקריאה נוספת

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

ערך זה הוא יתום, כלומר אין ערכים במכלול שמקשרים אליו. אתם מוזמנים לתרום למכלול ולקשר אליו מכמה מהערכים שמכילים את המונח "משחק תומך".