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

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

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

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

מבחינה מתמטית, הרחבת העירוב מוגדרת כך: יהי $G=(S_{1},S_{2},\ldots ,S_{n},\pi _{1},\pi _{2},\ldots ,\pi _{n})$ משחק n שחקנים בצורה תכסיסית. הרחבת העירוב של המשחק היא המשחק $G^{*}=(P_{1},P_{2},\ldots ,P_{n},\pi _{1}^{*},\pi _{2}^{*},\ldots ,\pi _{n}^{*})$ כאשר לכל i, $\ P_{i}$ הוא תכסיס מעורב (בתורת המשחקים) של השחקן i, ופונקציית התשלום $\pi _{i}^{*}:P_{1}\times P_{2}\times \ldots \times P_{n}\rightarrow \mathbb {R}$ מתאימה לכל בחירת תכסיסים מעורבים על ידי השחקנים את הרווח שהשחקן i משיג מכך.