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

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

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

נסמן את הגדלים הרלוונטיים: $\ p,q$ הן אסטרטגיות של שחקן 1 ו-2, ו $\ h(p,q)$ היא פונקציית התשלום ששחקן 1 משלם לשחקן 2. $\ p_{0},q_{0}$, יקראו אסטרטגיות אופטימליות, אם הן מקיימות את התנאי:

$\forall q\,,h(p_{0},q)\geq h(p,q)$

$\forall p\,,h(p,q)\leq h(p,q_{0})$

הערך $\ v=h(p_{0},q_{0})$ נקרא הערך של המשחק. מכיוון ש $\ h$ היא ליניארית בכל רכיב, קל להוכיח כי קבוצת כל האסטרטגיות האופטימליות של כל שחקן היא קבוצה קמורה.

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

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

כלומר, שחקן 1 יבדוק את כל האסטרטגיות שלו, כך שלכל אסטרטגיה $\ p$ יבדוק מהו הרווח המינימלי שלו על פני האסטרטגיות האפשריות של $\ q$, ואז יבחר אסטרטגיה $\ p_{0}$ כזו שהרווח המינימלי עליה היה גדול (או שווה) מכל הרווחים המינימליים של כל האסטרטגיות האחרות. בסימון מתמטי, נאמר כי שחקן 1 יבדוק לכל אסטרטגיה $\ p$ את $\ \min _{q}\{h(p,q)\}$, ואז יחפש את המקסימום מתוך קבוצה זו, כלומר את $\ \max _{p}\{\min _{q}\{h(p,q)\}\}$. אסטרטגיה שעליה מתקבל המקסימום תהייה אופטימלית לשחקן 1. כאן יש לציין נקודה עדינה: מבחינה פורמלית, צריך היה לחפש את הסופרמום והאינפימום, במקום את המינימום והמקסימום. אך מכיוון שקבוצת האסטרטגיות היא קומפקטית ופונקציית התשלום היא רציפה, המקסימום והמינימום חייבים להתקבל בתוך הקבוצה.

באופן שקול לגמרי, שחקן 2 יבדוק לכל אסטרטגיה $\ q$ את $\ \max _{p}\{h(p,q)\}$, ואז יבחר אסטרטגיה שנותנת מינימום על קבוצה זו, כלומר אסטרטגיה שנותנת מינימום על $\ \min _{q}\{\max _{p}\{h(p,q)\}\}$.

לפי משפט המינימקס, מתקיים שוויון $\ v=\min _{q}\{\max _{p}\{h(p,q)\}\}=\max _{p}\{\min _{q}\{h(p,q)\}\}$.

כמו כן, מקמירות $\ h$ ניתן להראות כי די לשחקן 1 [שחקן 2] לבדוק עבור אסטרטגיה מוצעת שלו את מינימום [מקסימום] הרווחים רק על פני האסטרטגיות הטהורות של שחקן 2 [שחקן 1].