אסטרטגיה אופטימלית

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

נסמן p ו-q כאסטרטגיות של שחקן 1 ושל שחקן 2. נח denote את h(p,q) כפונקציית התשלום, כלומר כמה שחקן 1 משלם לשחקן 2 בתוצאה הנתונה. אסטרטגיות p0 ו-q0 נקראות אופטימליות אם עבור כל q מתקיים h(p0,q) ≥ h(p,q), ועבור כל p מתקיים h(p,q0) ≤ h(p,q). הערך v של המשחק הוא h(p0,q0). מכיוון ש-h ליניארית בכל רכיב, קבוצת כל האסטרטגיות האופטימליות של כל שחקן היא קבוצה קמורה.

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

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

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

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

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