تعادل نش

برای دیگر کاربردها، تعادل (ابهام‌زدایی) را ببینید.

تعادل نش (به انگلیسی: Nash equilibrium)‏. مفهومی در نظریه بازی‌ها که کاربرد فراوانی در اقتصاد پیدا کرده است و نام آن از نش گرفته شده است.

تعادل نش

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

کاربردها

مفهوم تعادل نش برای تجزیه و تحلیل نتایج اثر متقابل استراتژیک چندین تصمیم گیرنده استفاده شده است. به عبارت دیگر، این راهی برای پیش بینی اینکه اگر چند نفر یا چندین موسسه که در تصمیم گیری های همزمان هستند و اگر پیامد های آن وابسته به تصمیم های دیگران است چه نتایجی را خواهد داشت . نگرش ساده و ایده اساسی جان نش این است که اگر ما تصمیم های تصمیم گیرندگان مختلف را به صورت جداگانه تحلیل کنیم در نتیجه نمی توانیم نتیجه انتخاب های آنان را پیش بینی کنیم. در عوض، ما باید بپرسیم آنچه که هر کدام از بازیکنان انجام میدهد، با در نظر گرفتن تصمیم گیری های دیگران است. تعادل نش برای تجزیه و تحلیل شرایط خصمانه شبیه جنگ و مسابقات مسلحانه به کار گرفته شده است ( معمای زندانی). همچنین نحوه درگیری ممکن است از طریق اثر متقابل تکرار شده تعدیل داده شود( این به جای آن). همچنین این تئوری برای مطالعه آنچه که اندازه افراد با ترجیحات متفاوت می تواند همکاری کنند استفاده شده است(Battle of the sexes). و اینکه آیا آنها خطراتی را برای دستیابی به نتایج مشارکتی خواهد گرفت(Stag hunt). این تئوری برای مطالعه تصمیم گیری در مورد استانداردهای فنی گرفته شده است، و همچنین رخداد اجرایی بانک و بحران های ارزی ( بازی هماهنگ). برنامه های کاربردی دیگر شامل جریان ترافیک (Wardrop's principle ).، نحوه سازماندهی مزایده ها (تئوری مزایده)، نتیجه اقدامات وارد شده توسط احزاب مختلف در فرایند آموزشی و حتی ضربات پنالتی در فوتبال (سکه های مطابق)

تاریخچه

یک نسخه از مفهوم تعادل نش برای اولین بار توسط آنتونی آگوستین کورنو در نظریه خود در انحصار چند جانبه مورد استفاده قرار گرفت (1838).در تئوری کورنو آمده که بنگاه ها چگونه محصول بیشتر برای تولید حداکثر کردن سود خود انتخاب میکنند. با این حال، بهترین محصول برای یک شرکت بستگی به محصولات دیگران دارد. تعادل کورنو هنگامی که هر بنگاه سود هر محصول خود را با توجه به محصول های شرکت های دیگر حداکثر می کند رخ میدهد. مفهوم نوین تئوری بازی از تعادل نش بر حسب استراتژی های ترکیبی تعریف شده است. جایی که بازیکنان یک توزیع احتمال از اقدامات امکان پذیر را انتخاب می کنند. مفهوم استراتژی ترکیبی تعادل نش توسط جان فون نویمان و اسکار مورگسترن در کتاب سال 1944 خود با عنوان نظریه بازی ها و رفتار اقتصادی معرفی شده است. با این حال، تجزیه و تحلیل آنها برای حالت خاصی از بازی با مجموع صفر محدود بود. آنها نشان دادند که استراتژی ترکیبی تعادل نش برای هر بازی مجموع صفر با یک مجموعه متناهی از اقدامات وجود خواهد داشت. نقش جان فوربز نش در مقاله خود در سال 1951 با عنوان بازی های غیر مشارکتی به تعریف یک استراتژی مختلط تعادل نش برای هر گونه بازی با یک مجموعه متناهی از اقدامات پرداخت و ثابت کرد که حداقل یک (استراتژی مختلط) تعادل نش باید در چنین بازی وجود داشته باشد. از آنجایی که توسعه مفهوم تعادل نش را نظریه پردازان تئوری بازی کشف کرده اند در شرایط معینی پیش بینی های گمراه کننده ای ایجاد می کند. بنابراین راه حل بسیاری از مفاهیم مرتبط پیشنهاد شده (همچنین اصلاحات تعادل نش) طراحی شده که برای غلبه بر نقص در درک مفهوم نش می باشد.یک موضوع خیلی مهم این است که برخی از تعادلهای نش ممکن است مبتنی برآن خطراتی باشد که معتبر نیست. بنابراین، در سال 1965 توسط راینهارد سلتن پیشنهاد شده که تعادل کامل با بازی فرعی به عنوان یک بهبود که به تعادل در تهدیدهای غیر معتبر بستگی دارد را حذف می کند. ضمیمه های دیگر از مفهوم تعادل نش به این پرداخته که اگر یک بازی تکرار شده است و یا چه چیزی اتفاقی می افتد اگر یک بازی در فقدان اطلاعات کامل بازی شده باشد . با این حال، پس از آن اصلاحات و ضمیمه ها از مفهوم تعادل نش سهم دیدگاه اصلی مفهوم نش استوار به همه ی مفاهیم تعادل تجزیه و تحلیل گزینه هایی خواهد شد که هر بازیکن به اعتبار تصمیم سازی های دیگران می گیرد.

تعاریف

تعریف غیر رسمی

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

تعریف رسمی

مجموعه $(S,F)$ را به عنوان بازی با $n$ بازیکن در نظر بگیرید، که در آن $S_i$ مجموعه استراتژی ها برای بازیکن $i$ است، $S=S_1*S_2... *S_n$ مجموعه ای از فضای استراتژی آن است و $F(x)$ تابع بهره مندی آن است$X_{-i}$ را به عنوان فضای استراتژی همه ی بازیکنان به جز بازیکن$i$در نظر بگیرید .هر بازیکن به ازای هر $i$ عضو مجموعه اعداد صحیح، استراتژی $X_i$ را انتخاب کند، پروفایل استراتژی آن به صورت $x={x_1,...,x_n}$ و تابع بهره مندی آن به صورت $F(x_i)$ نتیجه داده می شود.قابل ذکر است که تابع بهره مندی به نمای استراتژی انتخابی وابسته است.به عنوان مثال، در استراتژی انتخاب شده توسط بازیکن i و همچنین استراتژی های انتخاب شده توسط تمام بازیکنان دیگر. نمای استراتژی $x^*\in S$ یک تعادل نش (NE) است اگر هیچ انحراف یک سویی در استراتژی توسط هر بازیکن واحد با یکی دیگر از بازیکنان سودآور نمی باشد.

یعنی 

$\forall i,x_i\in S_i, x_i \neq x^*_{i} : f_i(x^*_{i}, x^*_{-i}) \geq f_i(x_{i},x^*_{-i}).$

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

نمونه‌ها

بازی هماهنگ

	بازیکن ۲، پذیرش استراتژی A	بازیکن ۲، پذیرش استراتژی B
بازیکن ۱، پذیرش استراتژی A	۴٬۴	۱٬۳
بازیکن ۱، پذیرش استراتژی B	۳٬۱	۳٬۳

مثال بازی هماهنگ نسبت بازیکن ۱ به بازیکن ۲ با هر ترکیبی را نشان می‌دهد. بازی هماهنگ(متقارن) معمول دو بازیکن یا دو استراتژی بازی است، به عنوان مثال ماتریس بهره وری در سمت راست نشان داده شده‌است. بازیکنان باید در نتیجه هماهنگ، هر دو استراتژی A را اتخاذ کنند. به عنوان مثال، ۴. اگر هر دو بازیکن استراتژی B را انتخاب کنند هنوز هم در تعادل نش قرار دارند. اگر چه به هر بازیکن کمتر از بهره وری بهینه تعلق می‌گیرد، هیچ یک از بازیکنان انگیزه‌ای برای تغییر استراتژی به دلیل کاهش در پرداخت فوری ندارند (از ۳ به 1). نمونه‌ای از بازی هماهنگ تنظیم دو فن آوری موجود برای دو شرکت با محصولات سازگار است، و آنها حق انتخاب یک استراتژی برای تبدیل شدن به استاندارد بازار دارند. اگر هر دو شرکت موافق به فن آوری انتخاب شده باشند، فروش بالا برای هر دو شرکت انتظار می‌رود. اگر شرکت‌ها در انجام این فن آوری استاندارد را قبول نکنند نتیجه کمی نتیجه فروش می‌باشد. هر دو روش تعادل نش از بازی هاهستند. در جاده در حال رانندگی کردن هستید، و دارای انتخاب برای رانندگی در سمت چپ و یا به رانندگی در سمت راست جاده باشید همچنین این هم یک بازی هماهنگ است. برای مثال بهره مندی ۱۰۰ به معنی بدون تصادف و ۰ به معنی تصادف است، این بازی هماهنگ را می توان با ماتریس پرداخت زیر تعریف کرد:

	رانندگی در سمت چپ	رانندگی در سمت راست
رانندگی در سمت چپ	۱۰۰٬۱۰۰	۰٬۰
رانندگی در سمت راست	۰٬۰	۱۰۰٬۱۰۰

در این حالت دو استراتژی محض تعادل نش، هنگامی که هر دو به یکی از دو حالت رانندگی در سمت چپ و یا در سمت راست را انتخاب کنند وجود دارد، اگر ما اعتراف استراتژی‌های مختلط که در آن استراتژی محض تعادل نش است به تصادف انتخاب شده(موضوع برای بعضی احتمالات ثابت)، سپس سه تعادل نش برای موارد مشابه وجود دارد: ما برای هر دو استراتژی محض را به ترتیب در نظر می‌گیریم که در آن احتمالات (۰%,۱۰۰%) برای بازیکن نخست، (۰%,۱۰۰%) برای بازیکن دو،(۱۰۰%و۰%) برای بازیکن نخست و (۱۰۰%و۰%) برای بازیکن دوم. یکی دیگر از احتمالاتی که برای هر بازیکن مشخص می‌کنیم (۵۰%و۵۰%) است.

معمای زندانی

معمای زندانی مشابه ماتریس بهره وری است که به منظور نشان دادن بازی هماهنگ به کار می‌رود، اما اکنون در نظر بگیرید که< C > A > D > B. چونکه C>A و D>A، هر بازیکن موقعیت خودش را با تغییر استراتژی از از استراتژی ۱ به ۲ بهبود می‌بخشد. بدون توجه به آنکه بازیکن دیگر چه تصمیمی می‌گیرد. بنابراین معمای زندانی یک تعادل نش است: هر دو بازیکن استراتژی ۲ (خیانت) را انتخاب می‌کنند. این مورد جذاب مدت زیادی ساخته شده‌است برای مطالعه این حقیقت که D>A است، (به عنوان مثال، "هر دو خیانت" است در سطح جهانی پایین تر از "هر دو وفاداری باقی می‌ماند "). استراتژی بهینه به طور کلی ناپایدار است، بلکه در تعادل نیست. مثال ماتریس بهره وری معمای زندانی

	همکاری	عدم
همکاری	۳٬۳	۰٬۵
عدم	۵٬۰	۱٬۱

تعادل نش در ماتریس پرداخت

یک راه آسان عددی برای شناسایی تعادل نش در ماتریس بهره مندی وجود دارد. این امر به ویژه کمک کننده در بازی‌های دو نفره که در آن بازیکنان بیش از دو استراتژی می‌گیرند می باشد. در این مورد تجزیه و تحلیل رسمی ممکن است بیش از حد طولانی شود. این قانون برای جایی که حالت مختلط است (تصادفی) استراتژی‌های مورد علاقه صدق نمی‌کند. قانون آن به شرح زیر است: اگر شماره اولین بهره وری، در سلول‌های دوتایی، حداکثر ستون ازهر سلول است و اگر عدد دوم حداکثر ازمیان ردیف سلول باشد، سپس آن سلول نشان دهنده تعادل نش است. ما می‌توانیم این قاعده برای یک ماتریس ۳ × ۳ به کار بگیریم

	انتخاب A	انتخاب B	انتخاب C
انتخاب A	۰٬۰	۲۵٬۴۰	۵٬۱۰
انتخاب B	۴۰٬۲۵	۰٬۰	۵٬۱۵
انتخاب C	۱۰٬۵	۱۵٬۵	۱۰٬۱۰

با استفاده از این قانون، ما خیلی سریع (خیلی سریع تر از تجزیه و تحلیل رسمی) می‌توانیم ببینیم که سلول‌های تعادل نش (B,A) ، (A,B) و (C,C) هستند. درواقع، برای سلول (B,A) امتیاز ۴۰ درستون اول و امتیاز ۲۵ برای ردیف دوم حداکثر است. برای سلول (A,B) امتیاز ۲۵ درستون دوم و امتیاز ۴۰ برای ردیف اول حداکثر است. مشابه برای سلول (C,C). برای سلول‌های دیگر، یا یکی یا هردوی اعضای دوتایی حداکثر در سطر و ستون مربوطه نیستند.

پایداری

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

1. بازیکنی که تغییری نکرد هیچ استراتژی بهتری در شرایط مالی جدید ندارد ;
   
2. بازیکنی که تغییر انجام می دهد در حال حاضر با استراتژی به شدت بدتر بازی می کند ;
   

اگر این موارد هر دو را ملاقات نمود، سپس بازیکن با تغییر کوچک در استراتژی ترکیبی خود فورا به تعادل نش باز خواهد گشت. تعادل گفته شده با ثبات می باشد.اگر شرط اول برقرار نباشد سپس تعادل ناپایدار است. اگر فقط شرط نخست برقرار باشد سپس احتمالا تعداد نامحدود از استراتژی های بهینه برای بازیکنی که تغییر کرده وجود دارد. جان نش نشان داد که وضعیت دوم که در طیف وسیعی از بازی به خوبی تعریف شده نمی تواند بوجود بیاید. در بازی "رانندگی" مثال بالا هر دو تعادل پایدار و ناپایدار وجود دارد. تعادل شامل استراتژی های ترکیبی با احتمال 100 ٪ پایدار میباشند. اگر هر دو بازیکن کمی احتمالات خودشان را تغییر بدهند، و حریف خود هیچ دلیلی برای تغییر استراتژی خود در عوض نداشته باشد. تعادل (50 ٪، 50 ٪) ناپایدار است. اگر هر دو بازیکن احتمالات خود را تغییر بدهند و سپس دیگر بازیکنان بلافاصله یک استراتژی بهتر را از بین (0 ٪، 100 ٪) یا (100 ٪، 0 ٪) می گیرند. پایداری در کاربرد های عملی از تعادل نش بسیار مهم است، زمانی که استراتژی ترکیبی از هر بازیکن کاملا ناشناخته است، اما باید از توزیع آماری در اقدامات خود در بازی استنتاج کرد. در این حالت تعادل ناپایدارند بسیار بعید است که در عمل بوجود آیند، از آنجا که در هر دقیقه تغییر در سهم هر استراتژی دیده می شود منجر به تغییر در استراتژی و شکست تعادل میشود. تعادل نش تنها بر حسب انحرافات یک جانبه، پایداری را تعریف می کند. در بازی های مشارکتی ایده قانع کننده کافی نیست. تعادل قوی نش برای انحرافات با هر اتحاد امکان پذیری اجازه می دهد. بعبارت دیگر، تعادل قوی نش هنگامی تعادل نش است که در آن هیچ اتحادی نمی باشد، در نظر گرفتن اقداماتی که خود به عنوان مکمل داده می شود، با همکاری می توان منافع تمام اعضا را منحرف ساخت. با این حال، مفهوم نش قوی، گاهی خیلی قوی تصور شده است که در محیط برای برقراری ارتباط خصوصی نامحدود اجازه می دهد. در حقیقت، تعادل قوی نش می توان بهینه پارتو باشد. در نتیجه این شرایط، نش قوی تقریبا هرگز وجود ندارد. تعادل نش اصلاح شده معروف به تعادل نش ضد اتحاد (CPNE) هنگامی رخ میدهد که بازیکن نمی تواند بهتر عمل کند حتی اگر به آنها اجازه برقراری ارتباط و ایجاد "خود اجرا درآوردن" توافق برای منحرف شدن را بدهند. هر استراتژی مرتبط با حمایت شده توسط تسلط همه جانبه تکرار شده که بر روی مرز پارتو می باشد (CPNE) است. علاوه بر این، ممکن است برای یک بازی داشتن تعادل نش که انعطاف در برابر ائتلاف ها کمتر از یک اندازه مشخص شده باشند. (CPNE) مرتبط با تئوری مرکزی است.

پیش آمد

اگر بازی دارای یک تعادل نش منحصر به فرد است و در میان بازیکنان تحت شرایط خاصی انجام میشود، بنابراین مجموعه استراتژی تعادل نش تصویب شده خواهد بود. شرایط کافی برای تضمین اینکه تعادل نش در حال بازی شدن است عبارت اند از :

1. بازیکنان تمام قدرت خود برای حداکثر کردن بهره وری مورد انتظار خود در بازی های مورد انتظار انجام می دهند ;
   
2. بازیکن بی نقص در اجرای بازی هستند ;
   
3. بازیکنان هوش کافی برای استنتاج راه حل دارند ;
   
4. بازیکنان از استراتژی تعادلی برنامه ریزی شده توسط بازیکنهای دیگر با خبرند ;
   
5. بازیکنان بر این باورند که انحراف در استراتژی خود باعث انحراف هر بازیکن دیگر نخواهد شد ;
   
6. شناخت مشترک که همه بازیکنان با این شرایط مواجه اند وجود دارد ;
   

جستارهای وابسته

• نظریهٔ بازیها

منابع

برگردان فارسی از 

[Nash equilibrium http://en.wikipedia.org/w/index.php?title=Nash_equilibrium&oldid=428749636]

مطالعه بیشتر

• ویدیوی کوتاه توضیح تعریف غیررسمی تعادل نش
• ویدیوی کوتاه توضیح تعریف رسمی تعادل نش