משחק אפס-מונוטוני

בתורת המשחקים, משחק אפס-מונוטוני הוא משחק שיתופי מונוטוני שבו כל קואליציה המכילה שחקן בודד, מקבלת 0. כלומר משחק $\ \left(N;v\right)$ כאשר $\ v\left(i\right)=0$ לכל $\ i\in N$. משחק מונוטוני הוא משחק שבו שוויה של כל קואליציה עולה או נשאר ללא שינוי כאשר מתווספים אליה שחקנים נוספים, כלומר אם לכל שתי קואליציות $\ S,T\subset N$ המקיימות $\ S\subset T$ מתקיים $\ v\left(S\right)\leq v\left(T\right)$.

הגדרה

קיימות שתי הגדרות שקולות:
(1) משחק נקרא אפס-מונוטוני אם נורמליזציית אפס שלו היא משחק מונוטוני. נורמליזציית-אפס של משחק $\ \left(N;v\right)$ הוא משחק $\ \left(N;w\right)$ השקול אסטרטגית ל $\ \left(N;v\right)$ ומתקיים $\ w\left(i\right)=0$ לכל שחקן $\ i\in N$.

(2) משחק נקרא אפס-מונוטוני אם $\ v\left(S\cup \left\{i\right\}\right)\geq v\left(S\right)+v\left(i\right)$ לכל קואליציה $\ S\subset N$ ולכל שחקן $\ i$ שלא נמצא בקואליציה $\ S$. $\ \left(\forall i\notin S\right)$.

תכונות

• במשחק אפס-מונוטוני הגרעינון והקדם גרעינון מתלכדים.

• במשחק מיקוח אפס-מונוטוני עם שלושה שחקנים, קבוצת המיקוח עבור המבנה הקואליציוני $\ \left\{N\right\}$ מתלכדת עם הליבה כאשר הליבה אינה ריקה, והיא מכילה נקודה אחת כאשר הליבה ריקה.

• בכל בעיית פשיטת רגל $\ \left[E;d_{1},d_{2},...,d_{n}\right]$ ניתן להגדיר משחק אפס-מונוטני $\ \left(N;v\right)$ בצורה הבאה:

• $\ N$ קבוצת הנושים.
• $\ v$ הפונקציה הקואליציונית המוגדרת על ידי $\ v\left(S\right)=\max \left\{E-\sum \limits _{i\in S}{d_{i}},0\right\}$. הגודל $\ v\left(S\right)$ מסמל את החלק של $\ E$ שאינו שנוי במחלוקת.

ראו גם

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

לקריאה נוספת

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