נפלאות אי התבונה (חלק ג')

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

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

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

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

$latex \max_x\min_y f(x,y)$

עבור שחקן 2 המצב הפוך: מכיוון שככל שערך הפונקציה f גדול יותר, כך שחקן 2 מרוויח פחות, המקסמין הופך אצלו למינמקס: $latex \min_y\max_x f(x,y)$

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

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

כעת אפשר לחזור לעניין המרכזי שלפנינו - שיווי משקל נאש - ונותרה רק שאלה אחת לפענח לפני כן: למה דווקא מינמקס ולא מקסמין? ולמה "מינימקס" ולא"מינמקס"?


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com