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

הגדרות

משחק בצורה קואליציונית עם תשלומי צד (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