استراتژی غلبه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

اصطلاحات[ویرایش]

هنگامی که یک بازیکن سعی دارد بهترین راهبرد را انتخاب کند، ممکن است دو راهبرد 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 غلبه کند.

تعریف ریاضی[ویرایش]

برای هر بازیکن i ،راهبرد s^*\in S_i بر استراتژی s^\prime\in S_i غلبه میکند اگر

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

s^* اکیداً بر s^\prime غلبه میکند اگر

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

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

غلبه و تعادل نش[ویرایش]

C D
C 1, 1 0, 0
D 0, 0 0, 0

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

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

حذف کردن راهبرد های مغلوب[ویرایش]

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

منابع[ویرایش]

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]