بازی‌های مجموع صفر؛ ماکسی‌مین و راهبرد مختلط

از درس دکتری

این یادداشت از درس «نظریه بازی‌ها» دوره‌ی دکتری من نوشته شده است. توضیح‌ها را به زبان خودم بازنویسی و مثال‌های عددی را دوباره حساب کرده‌ام.

مجموع صفر

در بازی مجموع صفر، پیامد بازیکن ۱ منهای پیامد بازیکن ۲ است؛ برای همین یک ماتریس کافی است (پیامد بازیکن سطر). مثال درس: دو مؤسسه‌ی آموزش عالی هر کدام باید برای جذب دانشجو رشته‌ی جدیدی راه بیندازند؛ درایه‌ها «درصد افزایش سهم جذب دانشجو برای مؤسسه‌ی الف» است. سطر = راهبردهای الف، ستون = راهبردهای ب.

ماکسی‌مین و مینیمکس

• بازیکن سطر محتاط است: برای هر راهبرد کمینه‌ی سطر را می‌یابد (بدترین حالت) و بیشترین آن کمینه‌ها را انتخاب می‌کند: ماکسی‌مین.
• بازیکن ستون هم‌چنین برای هر ستون بیشینهی ستون را می‌یابد و کمترین آن‌ها را انتخاب می‌کند: مینیمکس.

اگر این دو عدد برابر شوند، نقطه‌ی زینی داریم: ارزش بازی. هیچ‌کدام تمایلی به تغییر ندارند (تعادل نش). در مثال درس: برای مؤسسه‌ی الف کمینه‌ی سطرها $(14,18,13)$ بود و ماکسی‌مین ۱۳؛ یعنی راهبرد سوم.

راهبرد مختلط

اگر نقطه‌ی زینی نباشد، پیش‌بینی‌پذیربودن بازی را می‌بازد. راه‌حل: تصادفی بازی کنیم (انتخاب هر راهبرد با یک احتمال). قضیه‌ی مینیمکس فون نویمان (۱۹۲۸) تضمین می‌کند که در هر بازی دونفره‌ی مجموع‌صفر محدود، ارزش بازی در راهبردهای مختلط وجود دارد.

مثال ۲×۲:

	ستون ۱	ستون ۲
سطر ۱	۳	۱−
سطر ۲	۲−	۴

ماکسی‌مین خالص: $\max (-1,-2)=-1$؛ مینیمکس خالص: $\min (3,4)=3$؛ برابر نیستند → نقطه‌ی زینی نداریم. بازیکن سطر با احتمال $p$ سطر ۱ را انتخاب می‌کند؛ باید دو ستون برایش بی‌تفاوت شوند: $3p-2(1-p)=-p+4(1-p)$ → $5p-2=4-5p$ → $p=0.6$ و ارزش بازی $=1$. یعنی در بلندمدت بازیکن سطر به‌طور متوسط ۱ واحد می‌برد، و حریف نمی‌تواند با پیش‌بینی او کاری کند.

کاربرد

مسئله‌ی تقابل مستقیم بر سر منبع ثابت: رقابت قیمتی دو شرکت بر سر سهم بازار، بازی‌های نظامی، مسائل امنیتی. در رابطه‌های همکارانه کمتر کارساز است (بیشتر موقعیت‌های سازمانی «مجموع ناصفر» است).

مرتبط: بازی‌های ایستا؛ دوراهی زندانی و تعادل نش.

مجموع_صفرراهبرد_مختلط