تعادل نش
- معرفیشده توسط
- John Nash
- سال
- 1950
- نوع
- algorithm
- خانواده
- Game-theoretic
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
تعادل نش (Nash Equilibrium) یک مفهوم راهحل در نظریه بازیهاست که در آن هیچ بازیکنی نمیتواند با انحراف یکجانبه، سود خود را بهبود بخشد. این مفهوم که توسط جان نش در سال ۱۹۵۰ فرمولبندی شد، از طریق الگوریتم لمکه-هاوسون (Lemke-Howson) به صورت محاسباتی تعادلها را در بازیهای بیماتریس با شناسایی جفتهای رأس کاملاً برچسبگذاری شده در چندوجهیهای استراتژی پیدا میکند.
شهود پشت روش
در یک تعادل نش، استراتژی هر بازیکن بهترین پاسخ به استراتژی سایر بازیکنان است. وضعیتی را تصور کنید که هر دو بازیکن از استراتژی دیگری آگاه هستند: هیچکدام تمایلی به تغییر نخواهند داشت، زیرا انجام این کار فقط به ضررشان خواهد بود. الگوریتم لمکه-هاوسون از هندسه چندوجهیهای بازی بهره میبرد و با ردیابی برچسبها (محدودیتهای ارضا نشده) و چرخش از طریق رئوس، تا زمانی که یک جفت کاملاً برچسبگذاری شده یافت شود، پیش میرود—پیکربندیای که در آن هیچ بازیکنی انحراف سودآوری ندارد.
تاریخ
جان نش در رساله دکترای خود در سال ۱۹۵۰ ثابت کرد که هر بازی متناهی حداقل یک تعادل نش با استراتژی ترکیبی دارد. در سال ۱۹۶۴، لمکه و هاوسون اولین الگوریتم سازنده را برای یافتن این تعادلها منتشر کردند و اثبات وجود نش را به یک روش محاسباتی عملی تبدیل کردند. کار آنها برای نظریه بازیهای محاسباتی و اقتصاد الگوریتمی بنیادی شد.
چه زمانی استفاده شود
هنگام مطالعه بازیها با دو بازیکن و فضاهای استراتژی گسسته، یا هنگام جستجوی تعادلهای کاملاً ترکیبی، از تحلیل تعادل نش استفاده کنید. این روش برای مدلسازی رقابت، مذاکره، و مسائل هماهنگی که در آنها تعامل استراتژیک از اهمیت بالایی برخوردار است، مناسب است. روش لمکه-هاوسون برای بازیهای بیماتریس غیرتباهیده بهترین عملکرد را دارد؛ موارد تباهیده ممکن است به محاسبات نمادین یا اغتشاش نیاز داشته باشند.
محدودیتها و ملاحظات
- محدود به بازیهای بیماتریس (دو بازیکن)؛ تعمیم به بازیهای n-بازیکن NP-hard است
- در بازیهای تباهیده که چندین محور ورودی ممکن است، شکست میخورد یا ناکارآمد میشود
- ممکن است تنها یک تعادل را پیدا کند؛ تعادلهای متعدد اغلب در بازیهای با مجموع غیرصفر وجود دارند
- بدون بازفرمولبندی، بازیهای پویا یا با فرم گسترده را مستقیماً مدیریت نمیکند
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- کارایی محاسباتی برای یافتن تعادلهای نش در بازیهای بیماتریس متناهی
- تضمین همگرایی به یک جفت رأس کاملاً برچسبگذاری شده برای بازیهای غیرتباهیده
- ارائه مبنای نظری که هندسه ترکیبیاتی را به نظریه بازیها پیوند میدهد
- قابل اطلاق به تعادلهای استراتژی ترکیبی، که اغلب واقعبینانهتر از نتایج استراتژی محض هستند
کاربردها
- اقتصاد: مدلسازی رقابت الیگوپولیستی و رفتار قیمتگذاری در بازارها
- مزایدهها و طراحی مکانیزم: تحلیل استراتژیهای پیشنهاد قیمت در مزایدههای قیمت اول و مزایدههای پاکتی
- امنیت سایبری: پیشبینی تعادلهای مهاجم-مدافع در بازیهای امنیت شبکه
- زیستشناسی حیات وحش: تحلیل استراتژیهای پایدار تکاملی در تعاملات شکارچی-شکار
چگونه کار میکند
چگونه کار میکند
بازی بیماتریس را به دو مسئله مکمل خطی (LCP) تبدیل کنید، یکی برای هر بازیکن، که شرایط بهترین پاسخ آنها را نشان میدهد.
برچسبهایی را به یالها و رئوس چندوجهیهای استراتژی بر اساس اینکه کدام یک از محدودیتهای انگیزشی بازیکن نقض شده است، اختصاص دهید.
با شروع از رأس همه-یکها (کاملاً برچسبگذاری شده)، چرخشهای سیمپلکسمانند را برای پیمایش چندوجهی انجام دهید، برچسبها را حذف و اضافه کنید تا یک جفت کاملاً برچسبگذاری شده کشف شود.
با بررسی اینکه هیچکدام از بازیکنان نمیتوانند سود خود را با توجه به استراتژی دیگری بهبود بخشند، تأیید کنید که استراتژیهای هر دو بازیکن پاسخهای متقابل بهینه را تشکیل میدهند.
دامهای رایج
- فرض وجود یک تعادل منحصر به فرد؛ بسیاری از بازیها دارای چندین تعادل نش با پیامدهای سود متفاوت هستند
- اشتباه گرفتن تعادلهای استراتژی ترکیبی (بازی احتمالی) با تعادلهای استراتژی محض، که منجر به تفسیر نادرست رفتار عامل میشود
- نادیده گرفتن تمایز بین شرایط لازم و کافی برای تعادل؛ یک جفت کاملاً برچسبگذاری شده بهینگی را ارضا میکند اما ممکن است اگر بازیکنان نتوانند هماهنگ شوند، محقق نشود
پرسشهای متداول
آیا یک بازی میتواند هیچ تعادل نشی نداشته باشد؟
تعادلهای نش با استراتژی محض ممکن است وجود نداشته باشند (مثلاً سنگ-کاغذ-قیچی)، اما هر بازی متناهی حداقل یک تعادل با استراتژی ترکیبی دارد که در آن بازیکنان با احتمالات مشخصی بر روی اقدامات تصادفی عمل میکنند.
تعادل استراتژی ترکیبی چه تفاوتی با تعادل استراتژی محض دارد؟
در یک تعادل استراتژی محض، هر بازیکن با اطمینان به یک اقدام خاص متعهد میشود. در یک تعادل استراتژی ترکیبی، هر بازیکن از یک توزیع احتمال بر روی اقدامات استفاده میکند. تعادلهای ترکیبی اغلب کلیتر هستند و زمانی وجود دارند که تعادلهای محض وجود ندارند.
چرا الگوریتم لمکه-هاوسون به جستجوی جامع (brute-force) ترجیح داده میشود؟
این الگوریتم از ساختار چندوجهی فضاهای استراتژی بهره میبرد، فضای جستجو را به صورت نمایی کاهش میدهد و برای بازیهای غیرتباهیده در زمان چندجملهای همگرا میشود، در حالی که شمارش جامع با افزایش فضای استراتژی غیرعملی میشود.
روشهای مرتبط
منابع
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
باز کردن مرجع DOIکپی شد.Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
باز کردن مرجع DOIکپی شد.