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

בתורת המשחקים, משחק אפס-מונוטוני הוא משחק שיתופי מונוטוני שבו כל קואליציה המכילה שחקן בודד, מקבלת 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