הרחבת העירוב של משחק

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

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

מבחינה מתמטית, הרחבת העירוב מוגדרת כך: יהי הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle G=(S_{1},S_{2},\ldots ,S_{n},\pi _{1},\pi _{2},\ldots ,\pi _{n})} משחק n שחקנים בצורה תכסיסית. הרחבת העירוב של המשחק היא המשחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G^*=(P_1,P_2,\ldots,P_n,\pi^*_1,\pi^*_2,\ldots,\pi^*_n)} כאשר לכל i, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P_i} הוא תכסיס מעורב (בתורת המשחקים) של השחקן i, ופונקציית התשלום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi^*_i:P_1\times P_2 \times\ldots\times P_n\rarr \R} מתאימה לכל בחירת תכסיסים מעורבים על ידי השחקנים את הרווח שהשחקן i משיג מכך.