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

הגדרות

משחק בצורה קואליציונית עם תשלומי צד (games in coalitional form with side payments(TU) games)

זה הוא משחק שיתופי המוגדר על ידי הזוג $\left(N;v\right)$ כך שמתקיים:

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

פתרון של משחק קואליציוני עם תשלומי צד

תהי U משפחת משחקים בצורה קואליציונית (על קבוצה כלשהי של שחקנים). מושג פתרון (עבור המשפחה U) הוא פונקציה $\varphi$ המתאימה לכל משחק $(N;v)\in U$ תת-קבוצה $\varphi (N;v)$ של R^N.

ייתכן כי עבור משחק מסוים $(N;v)\in U$ יתקיים $\varphi (N;v)=\emptyset$.

מושג הפתרון נקרא נקודתי אם לכל משחק $(N;v)\in U$ הקבוצה $\varphi (N;v)$ בת איבר אחד.

שקילות אסטרטגית

משחקים בצורה קואליציונית $\left(N;w\right)$, $\left(N;v\right)$ שקולים אסטרטגית אם קיימים מספרים $a>0$ ו-$b_{1},\cdots ,b_{n}\in \mathbb {R}$ כך שלכל $S\subseteq N$ מתקיים: $w\left(S\right)=av\left(S\right)+\sum _{i\in S}b_{i}$.

דוגמאות וסוגים של משחקים בצורה קואליציונית

משחק פשוט

משחק $\ (N;v)$ יקרא משחק פשוט אם הוא משחק בצורה קואליציונית ולכל תת-קבוצה S של N מתקיים $\ v(S)=0$ או $\ v(S)=1$. להרחבה ניתן לקרוא ב משחק פשוט .

משחק סכום קבוע
משחק $\ (N;v)$ יקרא משחק סכום קבוע אם $\ \forall S\subseteq N\;.\;v(S)+v(N\smallsetminus S)=v(N)$.

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

משחק $\ (N;v)$ יקרא משחק רוב משוקלל אם הוא משחק פשוט וקיימים משקלות חיוביים $\left(w_{1},w_{2}...w_{n}\right)$ (אחד לכל שחקן) ומיכסה $q\geq 0$ כך שלכל $\ S\subseteq N$ מתקיים:

$V(s)=\left\{{\begin{matrix}1&{\mbox{if}}\ \sum _{i\in S}w_{i}\geq q\\0&{\mbox{if}}\ \sum _{i\in S}w_{i}<q\end{matrix}}\right.$

משחק סופר אדיטיבי

משחק $\ (N;v)$ יקרא משחק סופר אדיטיבי אם הוא משחק בצורה קואליציונית ולכל שתי קבוצות זרות $\ T,S\subseteq N$ מתקיים: $\ v(\ T\cup S)\geq v(S)+v(T)$

משחק קמור

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

משחק מונוטוני

משחק $\ (N;v)$ יקרא משחק מונוטוני אם הוא משחק בצורה קואליציונית ולכל שתי קואליציות $\ S,T$ כך ש- $S\subseteq T$, מתקיים: $v(S)\leq v(T)$

משחק שוק

להרחבה ניתן לקרוא במשחק שוק.

משפטים

משפט אם משחק $\ (N;v)$ הוא סופר אדיטיבי ומשחק $\ (N;w)$ שקול לו אסטרטגית אזי, המשחק $\ (N;w)$ הוא סופר אדטיבי .

משפט כל משחק $\ (N;v)$ שקול אסטרטגית למשחק מונוטוני.

דוגמאות לפתרונות למשחקים בצורה קואליציונית

פתרונות נקודתיים

ערך שפלי

$\varphi _{i}(N;v)={\frac {1}{|N|!}}\sum _{R}\left[\ v(P_{i}^{R}\cup \left\{i\right\})-\ v(P_{i}^{R})\right]\,\!$

כאשר R הוא יחס סדר על השחקנים, הסכום רץ על כל יחסי הסדר האפשריים (קיימים !n כאלה) ו-$P_{i}^{R}$ היא קבוצת כל השחקנים שמקדימים את i ביחס הסדר R. להרחבה ניתן לקרוא בערך שפלי.

גרעינון
להרחבה ניתן לקרוא בגרעינון (משחק שיתופי).

פתרונות קבוצתיים

הליבה
להרחבה ניתן לקרוא בליבה של משחק שיתופי

ראו גם

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

לקריאה נוספת

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