استراتژی غلبه - ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه بازی‌ها راهبرد غالب برای یک بازیکن، راهبردی است که مستقل از این که بازیکن رقیب چه بازی انجام دهد، از یک راهبرد دیگر بهتر باشد.بسیاری از بازی‌های ساده با استفاده از راهبرد غلبه می‌توانند حل شوند. در مقابل غیر تراگذری در بازی‌هایی اتفاق می افتد که برای یک بازیکن بهتر یا بدتر بودن یک راهبرد نسبت به راهبرد دیگر وابسته به بازی بازیکن رقیب باشد.

هنگامی که یک بازیکن سعی دارد بهترین راهبرد را انتخاب کند، ممکن است دو راهبرد A و B را با هم مقایسه کند تا بفهمد کدام بهتر است.نتیجهٔ این مقایسه یکی از حالتهای زیر است:

• B بر A غلبه می‌کند : انتخاب B همیشه نتیجهٔ بهتر (یا مساوی) از A می‌دهد.در این حالت دو امکان وجود دارد:
  • B اکیداً بر A غلبه می‌کند: مستقل از بازی بازیکن (های) رقیب، انتخاب B همیشه از A بهتر است.
  • B ضعیفانه بر A غلبه می‌کند: دستکم یک راهبرد برای بازیکن رقیب وجود دارد که اگر آن را بازی کند، B از A بهتر است و برای سایر راهبردهای رقیب، نتیجهٔ B حداقل برابر نتیجهٔ A است.
• B و A غیرتراگذری هستند: در این حالت B بر A غلبه نمی‌کند و نسبت به A مغلوب هم نمی‌شود. به عبارت دیگر در بعضی از مواقع A، و در سایر مواقع B بهتر نتیجه می‌دهد.
• B توسط A مغلوب می‌شود: مستقل از بازی بازیکن (های) رقیب انتخاب B هیچ گاه نتیجهٔ بهتری نسبت به انتخاب A نمی‌دهد. در اینجا نیز دو امکان وجود دارد:
  • B ضعیفانه توسط A مغلوب می‌شود: حداقل به ازای یک راهبرد که رقیب انتخاب می‌کند، B نتیجهٔ بدتری از A می‌دهد و برای سایر راهبردهای رقیب، A حداقل مثل B نتیجه می‌دهد. (A ضعیفانه بر B غلبه می‌کند)
  • B اکیداً توسط A مغلوب می‌شود: انتخاب B همیشه نتیجه بدتری نسبت به A می‌دهد.(مستقل از بازی رقیب)

در حالت کلی می‌توان گفت:

• راهبرد B اکیداً غالب است اگر راهبردB بر همهٔ دیگر استراتژی‌ها اکیداً غلبه کند
• راهبرد B ضعیفانه غالب است اگر راهبردB بر همهٔ دیگر راهبردها غلبه کند در حالی که بر بعضی از آن‌ها ضعیفانه غالب شود.
• راهبرد B اکیداً مغلوب است اگر راهبرد دیگری پیدا شود که اکیداً بر B غلبه کند.
• راهبرد B ضعیفانه مغلوب است اگر راهبرد دیگری پیدا شود که ضعیفانه بر B غلبه کند.

برای هر بازیکن ${\displaystyle i}$ ،راهبرد ${\displaystyle s^{*}\in S_{i}}$ بر استراتژی ${\displaystyle s^{\prime }\in S_{i}}$ غلبه می‌کند اگر

${\displaystyle \forall s_{-i}\in S_{-i}\left[u_{i}(s^{*},s_{-i})\geq u_{i}(s^{\prime },s_{-i})\right]}$ (حداقل یک ${\displaystyle s_{-i}}$ وجود داشته باشد که نامساوی اکید را ارضا کند) 

${\displaystyle s^{*}}$ اکیداً بر ${\displaystyle s^{\prime }}$ غلبه می‌کند اگر

${\displaystyle \forall s_{-i}\in S_{-i}\left[u_{i}(s^{*},s_{-i})>u_{i}(s^{\prime },s_{-i})\right]}$

در حالی که ${\displaystyle S_{-i}}$ حاصلضری همهٔ استراتژی‌های بازیکن ${\displaystyle i}$ است.

اگر در بازی برای یک بازیکن راهبرد اکیداً غالب وجود داشته باشد، در بازی‌هایی که تعادل نش هستند آن بازیکن حتماً آن راهبرد را بازی می‌کند. اگر هر دو بازیکن راهبرد اکیداً غالب داشته باشند، بازی فقط دارای یک تعادل نش یکتاست.در حالی که تعادل نش لزوماً کارایی پارتو نیست. ممکن است نقاطی وجود داشته باشند که نقاط تعادل بازی نیستند ولی قرار گرفتن در آن نقاط برای هر دو بازیکن بهتر باشد. مانند مثال کلاسیک معمای زندانی‌ها. راهبردهای اکیداً مغلوب نمی‌توانند جزئی از تعادل نش باشند و در نتیجه غیرمنطقی است اگر بازیکنان آن‌ها را بازی کنند. ولی راهبردهای ضعیفانه مغلوب ممکن است جز تعادل نش باشند.به‌طور مثال ماتریس جزا شکل مقابل را در نظر بگیرید.

راهبرد C ضعیفانه بر راهبرد تژی D غلبه می‌کند. حال اگر هر دو بازیکن C را انتخاب کنند به تعادل رسیده و نمی‌خواهند موقعیت خود را تغییر دهند. پس (C,C) یک تعادل نش است. حال فرض کنید هر دو بازیکن D را بازی کنند، در این حالت نیز اگر یکی از بازیکن‌ها C را بازی کند چیزی بیشتر از صفر گیرش نمی‌آید پس می‌توان گفت نقطهٔ (D,D) نیز یک تعادل نش است. چون در صورتی که بازیکنان در این نقطه قرار گیرند حاضر به عوض کردن راهبرد خود نیستند. همانطور که گفته شد استراتژی‌هایی که ضعیفانه مغلوب هستند (D در این مثال) می‌توانند جزئی از تعادل نش باشند.

یکی از روش‌های متداول حل بازی ها، تکراری حذف کردن راهبردهای مغلوب است.در قدم اول هر بازیکن سعی می‌کند حداکثر یک راهبرد مغلوب از میان راهبردهایش پیدا کرده و از آنجایی که در هر شرایطی بازی آن راهبرد غیرعقلانی است، آن را حذف می‌کند. پس از حذف این راهبردها به بازی کوچکتری میرسیم و ممکن است در بازی کوچکتر راهبردهایی پیدا شوند که قبلاً مغلوب نبوده‌اند ولی حالا مغلوب شده و می‌توانند حذف شوند. به صورت تکراری عمل حذف راهبردهای مغلوب را انجام میدهیم تا جایی که در یک حلقهٔ تکرار هیچ بازیکنی هیچ یک از راهبردهایش را نتواند حذف کند. این روش حل بازی معتبر است چون فرض کرده ایم همهٔ بازیکن‌ها اطلاعات کامل دارند و همچنین همهٔ بازیکن‌ها عاقل هستند و هر بازیکن میداند که بازیکن دیگر عاقل بوده و هر بازیکن میداند که بازیکن‌های دیگر میدانند که او میداند سایر بازیکن‌ها عاقل هستند. حال دو نسخه برای انجام این فرایند وجود دارد. در نسخهٔ اول فقط راهبردهایی که اکیداً مغلوب هستند را حذف می‌کنیم. اگر پس از پایان فرایند فقط یک راهبرد برای هر دو بازیکن باقی‌مانده باشد، این مجموعه راهبرد یک تعادل نش یکتاست. در نسخهٔ دوم هر دوی راهبردهای اکیداً و ضعیفانه مغلوب را حذف می‌کنیم. در انتهای فرایند اگر برای هر دو بازیکن یک راهبرد باقی‌مانده باشد، این مجموعه راهبردها نیز یک تعادل نش است. ولی برخلاف حالت قبل ممکن است تنها نقطهٔ تعادل نش نباشد و با حذف استراتژی‌های ضعیفانه مغلوب، سایر تعادل‌های نش حذف شده باشند. به هر حال اگر با تکراری حذف کردن راهبردهای مغلوب در نهایت برای هر بازیکن یک راهبرد باقی بماند، آن بازی با روش راهبرد غلبه قابل حل است.

مشارکت‌کنندگان ویکی‌پدیا. «Strategic dominance». در دانشنامهٔ ویکی‌پدیای انگلیسی.