משחק מונוטוני

בתורת המשחקים, משחק מונוטוני מתאר משחק שיתופי בו שוויה של כל קואליציה עולה או נשאר ללא שינוי כאשר מתווספים אליה שחקנים נוספים.

הגדרה פורמלית

משחק $(N,v)$ נקרא מונוטוני אם לכל שתי קואליציות $S$ ו-$T$, $S\subseteq T$, מתקיים: $v(S)\leq v(T)$

מן ההגדרה משתמע שככל שקואליציה היא גדולה יותר, כך שוויה גדול יותר (או לפחות אינו קטן). בפרט, מתקיים כי $v(S)\leq v(N)$ לכל קואליצה $S$.

דוגמה

יהי $(N,v)$ משחק פשוט הנתון על ידי: $N=\left\{1,2,...,10\right\}$

$v(S)=\left\{{\begin{matrix}1&S=N\\0&o.w\end{matrix}}\right.$

זהו משחק בו שוויה של כל קואליציה שאינה $N$ הוא '0', ורק כאשר כולם מתאגדים יחדיו שוויה הוא '1'.

בפרט, תנאי הגדרת המונוטוניות מתקיימים ולכן זהו משחק מונוטוני.

שקילות אסטרטגית

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

לדוגמה, יהי משחק $(N,w)$ השקול אסטרטגית ל$(N,v)$:

  $w(S)=v(S)+\sum _{i\in S}b_{i}$ כאשר $b_{i}=-1$ לכל $i\in \mathbb {N}$

נראה כי $(N,w)$ אינו משחק מונוטוני.

ניקח למשל את הקואליציה {S={1,2,3,...,8, עבורה מתקיים $w(S)=-8$, וניקח את הקואליציה N עבורה $w(N)=-9$.

קיבלנו כי במשחק $(N,w)$ קיימת קואליציה S קטנה ממש מ-N כך ש: $w(N)\leq w(S)$ וזה כאמור מעיד כי המשחק אינו מונוטוני.

לקריאה נוספת

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