משחק סכום אפס

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

פתרון של משחק סכום-אפס

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

מושג המקסמין והמינמקס

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

משחק שני שחקנים סכום אפס ותכנון ליניארי

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

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

משמעות הפתרון של משחק סכום-אפס

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

משחק n-שחקנים סכום אפס

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

משחק סכום קבוע

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