ערך המקסמין

בתורת המשחקים הלא-שיתופיים, ערך המקסמין (Maxmin value) הוא התשלום המקסימלי, ששחקן יכול להבטיח לעצמו במשחק, בצורה אסטרטגית. נקיטה באסטרטגיה המבטיחה ערך זה, הנקראת אסטרטגית מקסמין, משקפת שחקן שהתנהגותו מתאפיינת בחוסר ביטחון או שמרנות.

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

ניסוח פורמלי

עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} קבוצה סופית כלשהי, ווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=(x_1,...,x_n) \in A^n} , נסמן את הווקטור המתקבל מהשמטת הקואורדינטה ה-$i$: $x_{-i}=(x_{1},...,x_{i-1},x_{i+1},...,x_{n})$. כמו כן, עבור קבוצה $X\subset A^{n}$, נסמן: $X_{-i}=\{x_{-i}|x\in X\}$.

עבור שחקן $i$ במשחק לא שיתופי בצורה אסטרטגית, $v_{i}=\max _{s_{i}\in S_{i}}\min _{t_{-i}\in S_{-i}}u_{i}(s_{i},t_{-i})$ נקרא ערך המקסמין של שחקן $i$ (מכאן מקור השם "מקסמין"). כאן, $u_{i}$ היא פונקציית התועלת של השחקן ה-$i$, ו-$S_{i}$ קבוצת האסטרטגיות שלו. אסטרטגיה $s^{*}$ הממקסמת את הביטוי הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \min _{t_{-i}\in S_{-i}}u_{i}(s_{i}^{*},t_{-i})} נקראת אסטרטגית מקסמין, וקטור מהצורה $s^{*}=(s_{1}^{*},...,s_{n}^{*})$, שבו כל $s_{i}^{*}$ היא אסטרטגית מקסמין, נקרא וקטור אסטרטגיות מקסמין.

ניתן להכליל את מושג המקסמין למשחק אינסופי, על ידי החלפת המקסימום והמינימום באינפימום ובסופרמום. ערך מקסמין של שחקן תמיד קיים; אסטרטגית מקסמין קיימת אף היא, כאשר שהמשחק סופי (אחרת, הסופרמום והאינפימום בהגדרה לאו דווקא מתקבלים). אסטרטגית מקסמין לא חייבת להיות יחידה, אפילו אם המשחק סופי: למשל בדוגמה הבאה, שחקן 2 יכול להבטיח לעצמו רווח של 7 על ידי אסטרטגיה c או d.

דוגמה

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

	שחקן 2 בוחר באסטרטגיה c	שחקן 2 בוחר באסטרטגיה d
שחקן 1 בוחר באסטרטגיה A	10, 40	1000-, 7
שחקן 1 בוחר באסטרטגיה B	2, 7	5, 8

כל שחקן לא יודע באיזו אסטרטגיה יריבו ינקוט. אם השחקן הראשון יבחר באסטרטגיה A, קיימת סבירות שיצא בהפסד גדול של 1000-, וסבירות זו עשויה לגרום לו להחליט להימנע מאסטרטגיה זו (אף כי היא מאפשרת את הרווח הגדול ביותר). אם יבחר באסטרטגיה B, לעומת זאת, הרווח הקטן ביותר שישיג הוא 2. רווח זה גדול מהרווח הקטן ביותר במקרה שיבחר את אסטרטגיה אחת, ולכן זהו ערך המקסמין של שחקן 1. אסטרטגיה B היא אסטרטגית מקסמין, ונראה "סביר" כי שחקן חסר ביטחון ינקוט בה.

קשר עם אסטרטגיות נשלטות

משפט: אסטרטגיה של שחקן השולטת על כל האסטרטגיות האחרות היא אסטרטגית מקסמין של השחקן הזה.

הוכחה: נניח כי $s_{i}^{*}$ אסטרטגיה שולטת של שחקן $i$, כלומר $u_{i}(s_{i}^{*},s_{-i})\geq u_{i}(s_{i},s_{-i})$ לכל אסטרטגיה אחרת $s_{i}\in S_{i}$. נקח מינימום על שני האגפים ונקבל $\min _{t_{-i}\in S_{-i}}u_{i}(s_{i}^{*},t_{-i})\geq \min _{t_{-i}\in S_{-i}}u_{i}(s_{i},t_{-i})$ לכל אסטרטגיה אחרת $s_{i}\in S_{i}$. כלומר, האסטרטגיה $s_{i}^{*}$ ממקסמת את הביטוי $\min _{t_{-i}\in S_{-i}}u_{i}(s_{i},t_{-i})$ ולכן היא אסטרטגית מקסמין.

השוואה מול שיווי משקל נאש

שיווי משקל נאש הוא מושג פתרון נוסף המייצג תכונות התנהגות אחרות של השחקנים: כל אסטרטגיה מהווה את התשובה הטובה ביותר לשאר האסטרטגיות.

במשחק המתואר בדוגמה, (40,10) הוא שיווי משקל נאש אך לא אסטרטגית מקסמין, ואסטרטגית מקסמין היא לא שיווי משקל נאש. בדוגמה זו נראה כי יותר "סביר" לנקוט באסטרטגית המקסמין על פני עקרון שיווי משקל נאש.

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

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

ראו גם

• עץ מינימקס

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, הוצאת הספרים ע"ש י"ל מאגנס, 2008.