משחק סכום אפס

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

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

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

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

משחק שני שחקנים נקרא משחק סכום אפס אם לכל תוצאה אפשרית של המשחק, סכום ערכי פונקציית התשלומים עבור אותה תוצאה, לכל השחקנים, הוא 0. אם המשחק נתון בצורה אסטרטגית, התנאי הוא: $\forall s_{1}\in S_{1},s_{2}\in S_{2}.u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2})=0$, כאשר $S_{i}$ הוא קבוצת האסטרטגיות של שחקן $i$, ו- $u_{i}$ הוא פונקציית התשלומים של שחקן $i$. משחק שני שחקנים סכום-אפס בצורה אסטרטגית ניתן לייצוג באמצעות מטריצה, כפי שניתן לראות בדוגמה הבאה:

בכחול: האסטרטגיות והתשלומים של שחקן 1. באדום: האסטרטגיות והתשלומים של שחקן 2. ו

	L	C	R
T	3,-3	0,0	4,-4
M	6,-6	5,-5	7,-7
B	9,-9	2,-2	4,-4

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

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

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

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

מושגי המקסמין והמינמקס משמשים לתת פתרון של משחק שבו השחקן מעוניין להגדיל כמה שיותר את התשלום שיקבל, ללא תלות באסטרטגיות השחקנים האחרים. אסטרטגיית מקסמין תבטיח לו את התשלום הגדול ביותר מבין התשלומים הכי נמוכים ששחקנים אחרים יוכלו לכפות עליו. ערך המקסמין הוא התשלום המינימלי המתקבל מנקיטת אסטרטגיה זו. בכתיב מתמטי, ערך המקסמין של שחקן i הוא: ${\underline {v_{i}}}={\underset {s_{i}\in S_{i}}{\max }}{\underset {s_{-i}\in S_{-i}}{\min }}u_{i}(s_{i},s{-i})$

מושג המינמקס הוא מושג סימטרי למושג המקסמין שנועד לתאר את התשלום שנכפה על שחקן j: ${\overline {v_{j}}}={\underset {s_{j}\in S_{j}}{\min }}{\underset {s_{-j}\in S_{-j}}{\max }}u_{j}(s_{j},s{-j})$

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

את המושגים הללו ניתן להרחיב גם לאסטרטגיות מעורבות. באסטרטגיות מעורבות, התשלום לשחקן הוא תוחלת התשלום ביחס להסתברויות המיוחסות לכל אסטרטגיה טהורה בווקטור האסטרטגיות, ומכאן שערך המקסמין של שחקן i יוגדר באופן הבא: ${\underline {v_{i}}}={\underset {\sigma _{i}\in \Sigma _{i}}{\max }}{\underset {\sigma _{-i}\in \Sigma _{-i}}{\min }}U_{i}(\sigma _{i},\sigma _{-i})$

במשחק שני-שחקנים ניתן לפשט את הנוסחה. מלינאריות התוחלת, ומהיותה של קבוצת האסטרטגיות $\Sigma$ קבוצה קומפקטית וקמורה (הסימפלקס הסטנדרטי ה-n ממדי, המייצגים הסתברויות ל-n האסטרטגיות השונות של שחקן 2), נובע כי $U$ תקבל מינימום ומקסימום בנקודות קיצון של $\Sigma$, שהן האסטרטגיות הטהורות $S$, ולכן עבור i=1: ${\underline {v_{1}}}={\underset {\sigma _{1}\in \Sigma _{1}}{\max }}{\underset {s_{2}\in S_{2}}{\min }}U_{1}(\sigma _{1},s_{2})$

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

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

כך למשל במשחקים הבאים:

משחק 1 (אותו משחק מהדוגמה לעיל)	משחק 2
L C R T 3,-3 0,0 4,-4 M 6,-6 5,-5 7,-7 B 9,-9 2,-2 4,-4	L R T 0.7,-0.7 1,-1 B 1,-1 0,-0

ננסה לפתור את משחק 1 בעזרת המושג של שיווי משקל נאש. וקטור האסטרטגיות (M,C) מהווה שיווי משקל, משום שבהינתן ששחקן 2 בחר באסטרטגיה C, אין לשחקן 1 אינטרס לסטות מהאסטרטגיה M, שבה הרווח שלו הוא הגדול ביותר. מאידך, בהינתן ששחקן 1 בחר באסטרטגיה M, לשחקן 2 אין אינטרס לסטות מהאסטרטגיה C, שהרי אז הפסדו יהיה גדול מ -5.

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

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

בדוגמה זו, 5 (שהתקבל מהתוצאה 5,-5) הוא הערך של המשחק.

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

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

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

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

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

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

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

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

יהי $(N,(\mathbf {S} _{i})_{i\in {\mathcal {N}},\ u\ })$ משחק שני שחקנים סכום אפס. קבוצת השחקנים היא {1,2} = $N$ ו-$U$ היא ההרחבה המולטי-לינארית של $u$.

ערך פונקציית המטרה בפתרון האופטימלי לבעיית התכנון הבאה יסומן ב-$Zp$ :

$Zp:=\max z$ 

תחת האילוצים : 
$\sum s_{1}\in s_{1}X(S_{1})=1$ 

$\sum s_{1}\in s_{1}X(S_{1})U(s_{1},s_{2})\geq \ Z,\forall s_{2}\in S_{2}$

$X(S_{1})\geq \ 0,\forall s_{1}\in S_{1}$

אזי $Zp$ הוא ערך המשחק באסטרטגיות מעורבות.

רעיון ההוכחה מתמקד בכך שאם נסמן ב- $v$ את ערך המשחק באסטרטגיות מעורבות, נוכל להראות כי $Zp=v$. הדבר מתקיים מכיוון ש- $Zp\geq \ v$ ו- $Zp\leq \ v$.

ראשית, $Zp\geq \ v$ מתקיים, מכיוון שבמידה ו-$v$ הוא ערך המשחק, אזי ישנה לשחקן 1 אסטרטגיה אופטימלית ${\boldsymbol {\sigma }}$, המבטיחה כי תוחלת התשלום תהיה לפחות $v$ לכל אסטרטגיה טהורה של שחקן 2, ולכן גם לכל אסטרטגיה מעורבת שלו. מכיוון ש-$Zp$ הוא המספר הממשי הגדול ביותר, שעבורו קיימת אסטרטגיה מעורבת לשחקן 1, כל עוד האילוצים מתקיימים, אנו נסיק כי $Zp\geq \ v$.

שנית, נראה כי $Zp\leq \ v$ מתקיים. לצורך כך, נסביר מדוע מתקיים $Zp<\infty \$. אם האילוצים שלנו אכן מתקיימים, נקבל :

$z\leq \ \sum _{s_{1}\in s_{1}}X(S_{1})U(s_{1},s_{2})\leq \ \max _{s_{1}\in S_{1}}\max _{s_{2}\in s_{2}}|U(s_{1},s_{2})|<\infty \$.

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

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

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

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

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

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

תכונות

במשחק שני שחקנים סכום-אפס מתקיימות התכונות הבאות:

• אם למשחק קיים ערך $v$, והאסטרטגיות $s_{1}^{*},s_{2}^{*}$ הן אסטרטגיות אופטימליות (כלומר אסטרטגיות מקסמין ומינמקס), אז וקטור האסטרטגיות ${\overline {s^{*}}}=(s_{1}^{*},s_{2}^{*})$ הוא שיווי משקל שבו התשלום לשחקן 1 הוא $v$, ולשחקן 2 הוא $-v$.
• אם במשחק וקטור האסטרטגיות ${\overline {s^{*}}}=(s_{1}^{*},s_{2}^{*})$ מהווה שיווי משקל, אז ערך המשחק קיים, והוא שווה $v=u(s_{1}^{*},s_{2}^{*})$, והאסטרטגיות $s_{1}^{*},s_{2}^{*}$ הן אסטרטגיות אופטימליות.

לפיכך, במשחק סכום-אפס, השחקן מסוגל להשיג את הטוב שבשני העולמות – הן יציבות, המבוטאת בעזרת שיווי משקל נאש, והן ביטחון, המבוטא בעזרת ערך המקסמין. ואכן, אם שחקן 1 ינקוט באסטרטגיית המקסמין שלו $s_{1}^{*}$, הרי שיבטיח לעצמו את הערך של המשחק $v$, וייתכן שיקבל יותר מ- $v$ רק אם שחקן 2 יסטה משיווי המשקל $s_{1}^{*},s_{2}^{*}$. אבל, במידה ושני השחקנים רציונלים, ויודעים או מאמינים שיריבם גם רציונלי, אז שני השחקנים לא יסטו משיווי המשקל ויקבלו לא יותר ולא פחות מערך המשחק, $v$.

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

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

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

א. עבור משחק n שחקנים כללי, לאו דווקא סכום-אפס או אפילו סכום-קבוע, נגדיר שחקן מס' n+1, כך שעבור כל וקטור תשלומים במשחק המקורי $(u_{1},...,u_{n})$ נגדיר את התשלום של השחקן ה- n+1 (המדומה) להיות $-u_{1}-...-u_{n}$, וכך מתקבל משחק n+1 שחקנים סכום-אפס.

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

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

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

ראו גם

• מונחים בתורת המשחקים
• פון נוימן פוקר
• המשחק של גנרל בלוטו

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946

קישורים חיצוניים

• עמי גינזבורג, הצפת ערך | משחק סכום אפס, באתר TheMarker‏, 11 ביוני 2017