הצגת המקור של הדף "אסטרטגיה אופטימלית"

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

==הגדרה פורמלית==
נסמן את הגדלים הרלוונטיים: <math>\ p, q </math> הן אסטרטגיות של שחקן 1 ו-2, ו <math>\ h(p,q)</math> היא פונקציית התשלום ששחקן 1 משלם לשחקן 2. <math>\ p_0, q_0</math>, יקראו אסטרטגיות אופטימליות, אם הן מקיימות את התנאי:

<math>\forall q\,, h(p_0,q)\ge h(p,q)</math>

<math>\forall p\,, h(p,q)\le h(p,q_0)</math>

הערך <math>\ v=h(p_0,q_0)</math> נקרא ה[[ערך של משחק|ערך של המשחק]]. מכיוון ש <math>\ h</math> היא ליניארית בכל רכיב, קל להוכיח כי קבוצת כל האסטרטגיות האופטימליות של כל שחקן היא [[קבוצה קמורה]].

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

כלומר, שחקן 1 יבדוק את כל האסטרטגיות שלו, כך שלכל אסטרטגיה <math>\ p</math> יבדוק מהו הרווח המינימלי שלו על פני האסטרטגיות האפשריות של <math>\ q</math>, ואז יבחר אסטרטגיה <math>\ p_0</math> כזו שהרווח המינימלי עליה היה גדול (או שווה) מכל הרווחים המינימליים של כל האסטרטגיות האחרות. בסימון מתמטי, נאמר כי שחקן 1 יבדוק לכל אסטרטגיה <math>\ p</math> את <math>\ \min_q \{h(p,q)\}</math>, ואז יחפש את המקסימום מתוך קבוצה זו, כלומר את  <math>\ \max_p\{\min_q \{h(p,q)\}\}</math>. אסטרטגיה שעליה מתקבל המקסימום תהייה אופטימלית לשחקן 1. כאן יש לציין נקודה עדינה: מבחינה פורמלית, צריך היה לחפש את ה[[סופרמום]] וה[[אינפימום]], במקום את המינימום והמקסימום. אך מכיוון שקבוצת האסטרטגיות היא [[קבוצה קומפקטית|קומפקטית]] ופונקציית התשלום היא [[פונקציה רציפה|רציפה]], המקסימום והמינימום חייבים להתקבל בתוך הקבוצה.

באופן שקול לגמרי, שחקן 2 יבדוק לכל אסטרטגיה <math> \ q</math> את <math>\ \max_p\{h(p,q)\}</math>, ואז יבחר אסטרטגיה שנותנת מינימום על קבוצה זו, כלומר אסטרטגיה שנותנת מינימום על <math>\ \min_q\{ \max_p\{h(p,q)\}\}</math>.

לפי [[משפט המינימקס]], מתקיים שוויון <math>\ v= \min_q\{ \max_p\{h(p,q)\}\}=\max_p\{\min_q \{h(p,q)\}\}</math>. 

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

[[קטגוריה:תורת המשחקים]]
[[קטגוריה:אסטרטגיה]]