באופן כללי, לא בהכרח קיים ערך למשחק סכום-אפס באסטרטגיות טהורות, כפי שמראה הדוגמה של משחק 2. אסטרטגיית המקסמין של שחקן 1 היא T, עם ערך מקסמין 0.7, ואסטרטגיית המינמקס של שחקן 2 היא L או R, עם ערך מינמקס 1. לכן, במשחק זה לא קיים ערך באסטרטגיות טהורות.
לכן, לא לכל משחק שני שחקנים סכום-אפס קיים ערך באסטרטגיות טהורות, אך מה שכן מתקיים תמיד במשחק כזה, הוא שערך המינמקס גדול או שווה לערך המקסמין. אי-שוויון זה נובע מכך, שאם שחקן 1 יכול להבטיח לעצמו רווח כלשהו, אז שחקן 2 לא יכול להבטיח לעצמו לשלם פחות מערך זה (למשל במקרה ששחקן 1 משחק את אסטרטגיית המקסמין שלו). ניתן לראות שתכונה זו אכן מתקיימת במשחק 2: ערך המינמקס 1 של שחקן 2 גדול מערך המקסמין 0.7 של שחקן 1.
אחת העובדות החשובות ביותר לגבי ערך במשחק סכום-אפס ניתנת על ידי משפט המינימקס של פון-נוימן: לכל משחק שני שחקנים סכום-אפס, אשר בו מספר האסטרטגיות הטהורות של כל שחקן הוא סופי, קיים ערך המתקבל בעזרת אסטרטגיות מעורבות. יתרה מכך, ערך זה יהיה גם שיווי משקל.
קיימות הכללות של משפט המינימקס גם למקרים בהן קבוצות האסטרטגיות של השחקנים אינן בהכרח סופיות, אך מקיימות תכונות אחרות.
הערך יכול להתקבל גם באסטרטגיות טהורות: למשל, כך מתרחש במשחק 1.גם את האסטרטגיות הטהורות ניתן להציג כאסטרטגיות מעורבות, על ידי כך שאסטרטגיה מסוימת מקבלת הסתברות 1 והשאר הסתברות 0.
ישנן מספר שיטות למציאת שיווי משקל באסטרטגיות מעורבות במשחקים כלליים, ובמקרה של משחקי סכום-אפס, מציאת הערך או שיווי המשקל של המשחק קשורה לבעיות תכנון ליניארי.
משחק שני שחקנים סכום אפס ותכנון ליניארי.
במידה ומספר האסטרטגיות הטהורות של שחקן במשחק שני שחקנים סכום אפס הוא סופי, ניתן להציג את בעיית חישוב ערך המשחק סכום אפס על ידי בעיית תכנון ליניארי. בנוסף, ניתן לחשב את ערך המשחק סכום אפס באמצעות אלגוריתמים, המשמשים לפתרון בעיות תכנון ליניארי.
להלן הצגת בעיית התכנון הליניארי המתאימה לבעיית חישוב ערך המשחק :
יהי formula_14 משחק שני שחקנים סכום אפס. קבוצת השחקנים היא {1,2} = formula_15
ו-formula_16 היא ההרחבה המולטי-ליניארית של formula_17.
ערך פונקציית המטרה בפתרון האופטימלי לבעיית התכנון הבאה יסומן ב-formula_18 :
formula_19
תחת האילוצים :
formula_20
formula_21
formula_22
אזי formula_18 הוא ערך המשחק באסטרטגיות מעורבות.
רעיון ההוכחה מתמקד בכך שאם נסמן ב- formula_24 את ערך המשחק באסטרטגיות מעורבות, נוכל להראות כי formula_25. הדבר מתקיים מכיוון ש- formula_26 ו- formula_27.
ראשית, formula_26 מתקיים, מכיוון שבמידה ו-formula_24 הוא ערך המשחק, אזי ישנה לשחקן 1 אסטרטגיה אופטימלית formula_30, המבטיחה כי תוחלת התשלום תהיה לפחות formula_24 לכל אסטרטגיה טהורה של שחקן 2, ולכן גם לכל אסטרטגיה מעורבת שלו. מכיוון ש-formula_18 הוא המספר הממשי הגדול ביותר, שעבורו קיימת אסטרטגיה מעורבת לשחקן 1, כל עוד האילוצים מתקיימים, אנו נסיק כי formula_26.
שנית, נראה כי formula_27 מתקיים. לצורך כך, נסביר מדוע מתקיים formula_35. אם האילוצים שלנו אכן מתקיימים, נקבל :
formula_36.
מכיוון שלכל אחד מהשחקנים יש מספר סופי של אסטרטגיות טהורות, הביטוי הרשום מעלה סופי. formula_18 הוא הפתרון האופטימלי, ועל כן קיים וקטור formula_38 המקיים את האילוצים. האילוצים דורשים כי האסטרטגיה של שחקן 1 תהיה מעורבת, וכי התועלת תהיה גדולה מ-formula_18 לכל אסטרטגיה טהורה של שחקן 2. מכאן, נוכל לראות כי לשחקן 1 יש אסטרטגיה מעורבת המבטיחה תשלום מינימלי של formula_18, ועל כן ערך המשחק הוא לפחות formula_18.
משמעות הפתרון של משחק סכום-אפס.
חשיבותו המתמטית של משחק סכום-אפס היא שהוא מאחד שני מושגי פתרון של משחקים: מושג היציבות (פתרון בעזרת מציאת שיווי משקל נאש), ומושג הביטחון (פתרון בעזרת מציאת אסטרטגיות מקסמין ומינמקס).
יציבות, משמעה שהציפייה של השחקנים לגבי האסטרטגיה שאותה ינקטו יריביהם, יוצרת מצב שבו לאף אחד מהשחקנים לא משתלם להחליף אסטרטגיה, ובכך תוצאת המשחק נקבעת. אין זה בהכרח פתרון של המשחק, אלא תכונה שמצופה שפתרון של המשחק יקיים.
בהינתן ששחקן 1 יודע (או מאמין) ששחקן 2 ינקוט באסטרטגיה מסוימת formula_42 שלו, ויבחר לפיכך באסטרטגיה formula_43, גם שחקן 2 לא ירצה לסטות מאסטרטגיה formula_42, ולהפך. זוהי בדיוק ההגדרה של שיווי משקל – אף אחד מהשחקנים לא ירוויח אם יסטה ממנו, בעוד שאר השחקנים ידבקו בו.
ביטחון, משמעו שהשחקן מתעלם מהשפעות חיצוניות כדוגמת תיאום בין השחקנים, ומסתכל אך ורק על מה שהוא יכול להבטיח לעצמו בוודאות, בהינתן מה שהוא יודע על המשחק. הוא בוחן את האפשרויות הגרועות ביותר מבחינתו, ובוחר את הרעה במיעוטה.
תכונות.
במשחק שני שחקנים סכום-אפס מתקיימות התכונות הבאות:
לפיכך, במשחק סכום-אפס, השחקן מסוגל להשיג את הטוב שבשני העולמות – הן יציבות, המבוטאת בעזרת שיווי משקל נאש, והן ביטחון, המבוטא בעזרת ערך המקסמין. ואכן, אם שחקן 1 ינקוט באסטרטגיית המקסמין שלו formula_53, הרי שיבטיח לעצמו את הערך של המשחק formula_45, וייתכן שיקבל יותר מ- formula_45 רק אם שחקן 2 יסטה משיווי המשקל formula_46. אבל, במידה ושני השחקנים רציונליים, ויודעים או מאמינים שיריבם גם רציונלי, אז שני השחקנים לא יסטו משיווי המשקל ויקבלו לא יותר ולא פחות מערך המשחק, formula_45.
יתרה מזו, במשחק שני שחקנים סכום אפס כל שיווי משקל של המשחק ייתן תשלום זהה. כמו כן כל ערבוב של אסטרטגיות אופטימליות הוא גם כן אסטרטגיה אופטימלית ולכן במשחק שני שחקנים סכום אפס כל ערבוב של שיוויי משקל הוא גם כן שיווי משקל.
משחק n-שחקנים סכום אפס.
ניתן להכליל את ההגדרה של משחק שני שחקנים סכום-אפס למשחק n שחקנים סכום-אפס. שאלה טבעית היא מה הוא היחס בין משחקי סכום-אפס עם יותר משני שחקנים לעומת משחקי סכום-אפס עם בדיוק שני שחקנים, וכן כיצד נראה פתרון של משחקים כאלו. פון נוימן, שהיה ממפתחיה הראשונים של תורת המשחקים, מיקד את הדיון במשחקי סכום-אפס, ובפרט במשחקי שני שחקנים סכום-אפס. היסוד להתמקדותו במקרה פרטי זה הייתה שמשחקים רבים ניתן לבטא כמשחק סכום אפס, כך:
א. עבור משחק n שחקנים כללי, לאו דווקא סכום-אפס או אפילו סכום-קבוע, נגדיר שחקן מס' n+1, כך שעבור כל וקטור תשלומים במשחק המקורי formula_58 נגדיר את התשלום של השחקן ה- n+1 (המדומה) להיות formula_59, וכך מתקבל משחק n+1 שחקנים סכום-אפס.
ב. עבור משחק n שחקנים סכום-אפס כלשהו, אם נוכל לחלק את קבוצת השחקנים לשתי קבוצות, שתיקראנה קואליציות, כך שבתוך כל קואליציה שיתוף הפעולה של השחקנים הוא מוחלט, ובין שתי הקואליציות ניגוד אינטרסים גמור, אזי ניתן להסתכל על משחק 2 השחקנים המתקבל משתי קואליציות אלה כעל משחק שני שחקנים סכום-אפס.
משחק סכום קבוע.
במשחק סכום-קבוע, סכום ערכי פונקציות התשלומים של כל השחקנים הוא קבוע מספרי כלשהו, אך לאו דווקא אפס. משחק סכום קבוע שקול אסטרטגית למשחק סכום-אפס על ידי טרנספורמציה אפינית של פונקציית התשלומים שבה אנו מוסיפים או מחסירים קבוע. למעשה, כל שני משחקים בצורה אסטרטגית (לא בהכרח משחקי סכום-אפס), הנבדלים אך ורק בטרנספורמציה אפינית של פונקציית התשלומים שקולים אסטרטגית זה לזה. השקילות מתאפיינת בכך שקבוצת שיווי המשקל בשני המשחקים זהה.
בר מניה
רוג'ר זילאזני
רוג'ר ג'וזף זילאזני (באנגלית: Roger Joseph Zelazny; 13 במאי 1937 - 14 ביוני 1995) היה סופר מדע בדיוני ופנטזיה אמריקאי. כתיבתו מתבססת על פולקלור של תרבויות רבות. נודע בעיקר בשל סיפורים קצרים ובשל סדרת אמבר ובה עשרה ספרים. היה מועמד 14 פעמים לפרס הוגו וזכה בו שש פעמים. כמו כן, היה מועמד 14 פעמים לפרס נבולה וזכה בו שלוש פעמים. על שמו של רוג'ר זילאזני נקרא הצדפונאי Sclerocypris zelaznyi.
קורות חיים.
זילאזני נולד בעיירה אוקליד, מדינת אוהיו. היה ילד יחיד לג'וזף פרנק זילאזני, מהגר פולני, וג'וזפין פלורה סוויט, ילידת ארצות הברית ממוצא אירי.
זילאזני התחיל את קריירת הכתיבה שלו בגיל מוקדם. הוא הצטרף לחוג לכתיבה יוצרת וערך את עיתון בית הספר בעת לימודים בתיכון. בסתיו 1955 החל את לימודיו באוניברסיטת וסטרן ריזרב בחוג לפסיכולוגיה, אך בהמשך שינה את כיוון לימודיו עם תואר ראשון בספרות אנגלית. עם סיום התואר הראשון בשנת 1959, המשיך ללימודי התואר השני באוניברסיטת קולומביה בניו יורק וסיים את לימודיו בשנת 1962.
בין 1962 ל-1969 עבד בביטוח לאומי בקליבלנד ולאחר מכן בבולטימור, תוך כדי הקדשת ערביו הפנויים לכתיבה. לאחר מכן התפטר מעבודתו והקדיש את כל זמנו לכתיבה.
זילאזני היה נשוי פעמיים: ב-1964 נישא לשרון סטברל, והזוג התגרש ללא ילדים. ב-1966 נישא לג'ודית (ג'ודי) אלין קאלאהאן. כמו כן היה מאורס לזמרת הפולק הדי ווסט במשך 6 חודשים בשנים 1962-1961. לזילאזני ולג'ודי נולדו שני בנים, דבין וטרנט (כותב רומני פשע), ובת בשם שאנון.
זילאזני חונך כקתולי על ידי הוריו, בהמשך הגדיר את עצמו כ"קתולי שהדרדר": "אכן היה לי רקע קתולי משמעותי, אבל אינני קתולי. מתישהו בעבר אני מאמין שעניתי בחיוב פעם אחת מסיבות מוזרות ומסובכות, אבל אינני חבר בשום דת מאורגנת".