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

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

זה הוא משחק שיתופי המוגדר על ידי הזוג <math>\left(N ; v\right)</math> כך שמתקיים:
* <math>N =\{1,2,\cdots,n\}</math> הוא קבוצה סופית של שחקנים.
* <math>v:2^N \rarr \mathbb{R}</math> היא פונקציה המתאימה לכל תת-קבוצה <math>S</math> של שחקנים מספר ממשי <math>v(S)</math> ומקיימת <math>v(\emptyset)=0</math>. <math>\! v</math> נקראת הפונקציה הקואליציונית של המשחק.

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

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

ייתכן כי עבור משחק מסוים <math>(N;v)\in U</math> יתקיים <math>\varphi(N;v)=\empty</math>.

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

<big>שקילות אסטרטגית</big>

משחקים בצורה קואליציונית <math>\left(N;w\right)</math>, <math>\left(N;v\right)</math> שקולים אסטרטגית אם קיימים מספרים <math>a>0</math> ו-<math>b_1,\cdots,b_n\in\mathbb{R}</math> כך שלכל <math>S\subseteq N</math> מתקיים: <math>w\left(S\right)=av\left(S\right)+\sum_{i\in S}b_i</math>.

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

<big>משחק פשוט</big>

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

<big>משחק סכום קבוע</big> <br>
משחק <math>\ (N;v)</math> יקרא משחק סכום קבוע אם <math>\ \forall S \subseteq N \; . \; v(S)+v(N \smallsetminus S)=v(N)</math>. 

<big>משחק רוב משוקלל</big>

משחק <math>\ (N;v)</math> יקרא משחק רוב משוקלל אם הוא משחק פשוט וקיימים משקלות חיוביים <math> \left(w_1,w_2...w_n\right) </math> (אחד לכל שחקן) ומיכסה <math> q \geq 0</math> כך שלכל <math>\ S \subseteq N</math> מתקיים:
:<math>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.
</math>

<big>משחק סופר אדיטיבי</big>

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

<big>משחק קמור</big>

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

<big>משחק מונוטוני</big>

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

<big>משחק שוק</big>

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

== משפטים==

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

<big>משפט</big> 
כל משחק <math>\ (N;v)</math> שקול אסטרטגית למשחק מונוטוני.

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

<big>פתרונות נקודתיים</big>

<big>ערך שפלי</big>

:<math>\varphi_i(N;v)= \frac{1}{|N|!}\sum_R\left [\ v(P_i^R \cup \left \{ i \right \}) - \ v(P_i^R) \right ]\,\!</math>
כאשר R הוא יחס סדר על השחקנים, הסכום רץ על כל יחסי הסדר האפשריים (קיימים !n כאלה) ו-<math>P_i^R</math> היא קבוצת כל השחקנים שמקדימים את i ביחס הסדר R.
להרחבה ניתן לקרוא בערך שפלי.

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

<big>פתרונות קבוצתיים</big>

<big>הליבה</big> <br>
להרחבה ניתן לקרוא בליבה של משחק שיתופי

== ראו גם ==
* משחק שיתופי
* מונחים בתורת המשחקים

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

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