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

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

הגדרה

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

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

תכונות

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

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

ראו גם

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

לקריאה נוספת

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