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

הגדרות

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

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

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

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

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

ייתכן כי עבור משחק מסוים $(N;v)\in U$ יתקיים $\phi (N;v)=\mathrm{\varnothing }$.

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

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

משחקים בצורה קואליציונית $(N;w)$, $(N;v)$ שקולים אסטרטגית אם קיימים מספרים $a>0$ ו-$b_1,\cdots ,b_n\in ℝ$ כך שלכל $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)$ יקרא משחק סכום קבוע אם $\mathrm{\forall }S\subseteq N.v(S)+v(N\setminus S)=v(N)$.

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

משחק $(N;v)$ יקרא משחק רוב משוקלל אם הוא משחק פשוט וקיימים משקלות חיוביים $(w_1,w_2\mathrm{...}{w}_n)$ (אחד לכל שחקן) ומיכסה $q\ge 0$ כך שלכל $S\subseteq N$ מתקיים:

$V(s)=\{\begin{array}{cc}1& \text{if}\sum _{i\in S}{w}_i\ge q\\ 0& \text{if}\sum _{i\in S}{w}_i<q\end{array}$

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

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

משחק קמור

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

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

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

משחק שוק

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

משפטים

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

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

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

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

ערך שפלי

${\phi }_i(N;v)=\frac{1}{|N|!}\sum _R[v(P_i^R\cup \left\{i\right\})-v(P_i^R)]$

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

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

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

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

ראו גם

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

לקריאה נוספת

• תבנית:צ-ספר