משפט המינימקס

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

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

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

• תכסיס/אסטרטגיה הכוללת הגרלה בין מספר תכסיסים נקרא תכסיס מעורב.
• תכסיס/אסטרטגיה ללא הגרלות נקרא גם תכסיס טהור.

ניסוח מתמטי

תהי $\ A=a_{ij}$ מטריצה מסדר $\ m\times n$ המייצגת את התשלומים של שחקן העמודות לשחקן השורות במשחק סכום אפס. אזי קיים קבוע $\ v$, ושני וקטורי הסתברות $\ p\in \mathbb {R} ^{m},q\in \mathbb {R} ^{n}$ כך ש:

• לכל $\ 1\leq j\leq n$ מתקיים $\sum _{i=1}^{m}a_{ij}p_{i}\geq v$ (כששחקן השורות משחק $\ p$, לכל אסטרטגיה טהורה של שחקן העמודות, התשלום גדול או שווה לערך)

• לכל $\ 1\leq i\leq m$ מתקיים $\sum _{j=1}^{n}a_{ij}q_{j}\leq v$ (כששחקן העמודות משחק $\ q$, לכל אסטרטגיה טהורה של שחקן השורות, התשלום קטן או שווה לערך)

$\ v$ הנקרא הערך של המשחק, והווקטורים $\ p,q$ נקראים אסטרטגיות אופטימליות.

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

ניסוח שקול

קיים למשפט ניסוח חשוב נוסף, המתווה אלגוריתם למציאת האסטרטגיות האופטימליות. נסמן ב $\ \Delta ^{n}$ את הסימפלקס ה n ממדי, שהוא קבוצת האסטרטגיות של שחקן העמודות, ובאופן דומה את הסימפלקס ה m ממדי $\ \Delta ^{m}$ שהוא קבוצת האסטרטגיות של שחקן השורות. בנוסף, נסמן את פונקציית התשלום על ידי $\ h(p,q)$. אזי

$\ v=\max _{p\in \Delta ^{m}}\min _{q\in \Delta ^{n}}\{h(p,q)\}=\min _{q\in \Delta ^{n}}\max _{p\in \Delta ^{m}}\{h(p,q)\}$

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

הוכחה

בהוכחת המשפט יהיה שימוש במשפט ההפרדה שלקוח מתחום הטופולוגיה:

תהיינה $\ K,L\subset \mathbb {R} ^{n}$ קבוצות קמורות, סגורות, לא ריקות וזרות. נניח ש- $\ K$ חסומה, אז קיים על-מישור שמשוואתו $\ {\overrightarrow {a}}\cdot {\overrightarrow {z}}=\alpha$ כאשר: ${\overrightarrow {0}}\neq {\overrightarrow {a}}\in \mathbb {R} ^{n},\alpha \in \mathbb {R}$

המפריד בין $\ L$ ל $\ K$ . כלומר לכל: $\ {\overrightarrow {x}}\in K$ מתקיים: ${\overrightarrow {a}}\cdot {\overrightarrow {x}}<\alpha$ ולכל $\ {\overrightarrow {y}}\in L$ מתקיים: ${\overrightarrow {a}}\cdot {\overrightarrow {y}}>\alpha$.

$\$

נניח בשלילה כי עבור:

$\ v_{1}=\max _{p\in \Delta ^{m}}\min _{q\in \Delta ^{n}}\{h(p,q)\}$

$\ v_{2}=\min _{q\in \Delta ^{n}}\max _{p\in \Delta ^{m}}\{h(p,q)\}$

מתקיים האי-שוויון הבא: $\sum _{i=1}^{m}a_{ij}p_{i}\geq v_{2}>v_{1}\geq \sum _{j=1}^{n}a_{ij}p_{i}$. עבור הייצוג של $\ A$ בצורה הבאה:

$\ A={\begin{bmatrix}{\overrightarrow {a^{1}}}\\{\overrightarrow {a^{2}}}\\\vdots \\{\overrightarrow {a^{m}}}\end{bmatrix}};{\overrightarrow {a^{i}}}\in \mathbb {R} ^{n}$

תוגדרנה שתי הקבוצות הבאות: $\ K=Conv({\overrightarrow {a^{1}}},{\overrightarrow {a^{2}}},...,{\overrightarrow {a^{m}}})$ הקמור של הווקטורים ${\overrightarrow {a^{1}}}...{\overrightarrow {a^{m}}}$ והקבוצה $\ L=\{(y_{1},...y_{n})\in \mathbb {R} ^{n}:y_{i}\geq v_{2}\}$

לפי ההנחה, שחקן השורות יכול להבטיח לעצמו לכל היותר $\ v_{1}$ על ידי כל תכסיס מעורב שלו, ולכן לפי האי-שוויון $\ v_{1}<v_{2}$, לא יכולות להיות ל K ו- L נקודות משותפות במרחב $\ \mathbb {R} ^{n}$, כלומר מתקיים: $\ K\cap L=\emptyset$. כל שאר תנאי משפט ההפרדה מתקיימים גם כן, ולכן קיים על-מישור כפי שהוגדר במשפט. כלומר קיים וקטור $\ {\overrightarrow {q}}=(q_{1},...q_{n})$ וסקלר $\ \alpha \in \mathbb {R} ^{n}$ המקיימים לכל $\ {\overrightarrow {x}}\in K$ ולכל $\ {\overrightarrow {y}}\in L$:

• $\ {\overrightarrow {q}}\cdot {\overrightarrow {x}}<\alpha$
• $\ {\overrightarrow {q}}\cdot {\overrightarrow {y}}>\alpha$

מתקיים $\ q_{i}\geq 0$ כי אם היה $\ q_{i}<0$ הגבול של המכפלה של: $\ {\overrightarrow {y^{*}}}=(v_{2},v_{2},...,y_{i},v_{2},...,v_{2})$ עם $\ {\overrightarrow {q}}$ כאשר $\ y_{i}\rightarrow \infty$ היה מקיים:

$\ {\overrightarrow {q}}\cdot {\overrightarrow {y^{*}}}\rightarrow -\infty$ וזו סתירה לנאמר לעיל.

כמו כן מתקיים $\sum _{i=1}^{n}q_{i}>0$ ולכן נוכל לכפול את $\ {\overrightarrow {q}}$ ואת $\ \alpha$ בסקלר כך ש: $\sum _{i=1}^{n}q_{i}=1$ וההפרדה תישאר ללא שינוי.

מצד אחד: הווקטור $\ {\overrightarrow {y}}=(v_{2},v_{2},...v_{2})\in L$ מראה ש: $\ {\overrightarrow {q}}\cdot {\overrightarrow {y}}=v_{2}>\alpha$.

מצד שני: עבור כל $\ {\overrightarrow {x}}\in K$ מתקיים: $\ {\overrightarrow {q}}\cdot {\overrightarrow {x}}<\alpha$.

כל תכסיס טהור של שחקן השורות הוא בעצם אחת השורות במטריצה A, וכל אחת מהשורות נמצאת בתוך הקבוצה K, ולכן לכל אחד מהתכסיסים הטהורים של שחקן השורות מתקיים: $\ {\overrightarrow {q}}\cdot {\overrightarrow {a^{i}}}<\alpha <v_{2}$. המשמעות היא שאם מתייחסים לוקטור $\ {\overrightarrow {q}}$ בתור תכסיס של שחקן העמודות, תכסיס זה מבטיח לו שישלם פחות מ $\ v_{2}$ על כל תכסיס טהור של שחקן השורות, אבל אם זה נכון, אז זה מבטיח לשחקן העמודות לשלם פחות גם עבור כל תכסיס מעורב של שחקן השורות, וזו סתירה להגדרה של $\ v_{2}$. לכן ההנחה שממנה יצאנו איננה נכונה, ולכן $\ v_{1}=v_{2}$.