تعادل نش - ویکی‌پدیا، دانشنامهٔ آزاد

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

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

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

جنبه مهم تعادل نش این است که سود هر بازیکن نه تنها به راهبرد برگزیده خود بلکه به راهبرد برگزیده دیگر بازیکنان نیز ارتباط دارد.

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

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

یک نسخه از مفهوم تعادل نش برای اولین بار توسط آنتونی آگوستین کورنو در نظریه خود در انحصار چند جانبه مورد استفاده قرار گرفت (۱۸۳۸). در تئوری کورنو آمده که بنگاه‌ها برای بیشینه کردن سود خود چگونه میزان محصول بیشتر برای تولید را انتخاب می‌کنند. با این حال، بهترین محصول برای یک شرکت بستگی به محصولات دیگران دارد. تعادل کورنو هنگامی که هر بنگاه سود هر محصول خود را با توجه به محصول‌های شرکت‌های دیگر حداکثر می‌کند رخ می‌دهد.

مفهوم نوین تئوری بازی از تعادل نش بر حسب راهبرد‌های ترکیبی تعریف شده‌است. جایی که بازیکنان یک توزیع احتمال از اقدامات امکان‌پذیر را انتخاب می‌کنند. مفهوم راهبرد ترکیبی تعادل نش توسط جان فون نویمان و اسکار مورگسترن در کتاب سال ۱۹۴۴ خود با عنوان نظریه بازی‌ها و رفتار اقتصادی معرفی شده‌است. با این حال، تجزیه و تحلیل آن‌ها برای حالت خاصی از بازی با مجموع صفر محدود بود. آن‌ها نشان دادند که راهبرد ترکیبی تعادل نش برای هر بازی مجموع صفر مجموعه متناهی از اقدامات وجود خواهد داشت. نقش جان فوربز نش در مقاله خود در سال ۱۹۵۱ با عنوان بازی‌های غیر مشارکتی به تعریف یک راهبرد مختلط تعادل نش برای هر گونه بازی با یک مجموعه متناهی از اقدامات پرداخت و ثابت کرد که حداقل یک (راهبرد مختلط) تعادل نش باید در چنین بازی وجود داشته باشد.

از آنجایی که توسعه مفهوم تعادل نش را نظریه پردازان تئوری بازی کشف کرده‌اند در شرایط معینی پیش‌بینی‌های گمراه‌کننده‌ای ایجاد می‌کند؛ بنابراین راه حل بسیاری از مفاهیم مرتبط پیشنهاد شده (همچنین اصلاحات تعادل نش) طراحی شده که برای غلبه بر نقص درک مفهوم نش می‌باشد. یک موضوع خیلی مهم این است که برخی از تعادل‌های نش ممکن است مبتنی بر خطراتی باشد که معتبر نیست؛ بنابراین، در سال ۱۹۶۵ توسط راینهارد سلتن پیشنهاد شده که تعادل کامل با بازی فرعی به عنوان یک بهبود که به تعادل در تهدیدهای غیر معتبر بستگی دارد را حذف کند. ضمیمه‌های دیگر از مفهوم تعادل نش به این پرداخته که اگر یک بازی تکرار شده‌است یا چه چیزی اتفاقی می‌افتد اگر یک بازی در نبوداطلاعات کامل بازی شده باشد، با این حال پس از آن اصلاحات و ضمیمه‌ها از مفهوم تعادل نش سهم دیدگاه اصلی مفهوم نش استوار بر همهٔ مفاهیم تعادل تجزیه و تحلیل گزینه‌هایی خواهد شد که هر بازیکن به اعتبار تصمیم سازی‌های دیگران می‌گیرد.

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

مجموعه ${\displaystyle (S,F)}$ را به عنوان بازی با ${\displaystyle n}$ بازیکن در نظر بگیرید، که در آن ${\displaystyle S_{i}}$ مجموعه راهبرد‌ها برای بازیکن ${\displaystyle i}$ است، ${\displaystyle S=S_{1}*S_{2}...*S_{n}}$ مجموعه‌ای از فضای راهبرد آن است و ${\displaystyle F(x)}$ تابع بهره‌مندی آن است${\displaystyle X_{-i}}$ را به عنوان فضای راهبرد همهٔ بازیکنان به جز بازیکن${\displaystyle i}$در نظر بگیرید. هر بازیکن به ازای هر ${\displaystyle i}$ عضو مجموعه اعداد صحیح، راهبرد ${\displaystyle X_{i}}$ را انتخاب کند، پروفایل راهبرد آن به صورت ${\displaystyle x={x_{1},...,x_{n}}}$ و تابع بهره‌مندی آن به صورت ${\displaystyle F(x_{i})}$ نتیجه داده می‌شود. قابل ذکر است که تابع بهره‌مندی به نمای راهبرد انتخابی وابسته است. به عنوان مثال، در راهبرد انتخاب شده توسط بازیکن i و همچنین راهبرد‌های انتخاب شده توسط تمام بازیکنان دیگر. نمای راهبرد ${\displaystyle x^{*}\in S}$ یک تعادل نش (NE) است اگر هیچ انحراف یک سویی در راهبرد توسط هر بازیکن واحد با یکی دیگر از بازیکنان سودآور نمی‌باشد.

یعنی

${\displaystyle \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 را انتخاب کنند هنوز هم در تعادل نش قرار دارند. اگر چه به هر بازیکن کمتر از بهره‌وری بهینه تعلق می‌گیرد، هیچ‌یک از بازیکنان انگیزه‌ای برای تغییر راهبرد به دلیل کاهش در پرداخت فوری ندارند (از ۳ به ۱). نمونه‌ای از بازی هماهنگ تنظیم دو فناوری موجود برای دو شرکت با محصولات سازگار است، و آن‌ها حق انتخاب یک راهبرد برای تبدیل شدن به استاندارد بازار دارند. اگر هر دو شرکت موافق به فناوری انتخاب شده باشند، فروش بالا برای هر دو شرکت انتظار می‌رود. اگر شرکت‌ها در انجام این فناوری استاندارد را قبول نکنند نتیجه کمی نتیجه فروش می‌باشد. هر دو روش تعادل نش از بازی . در جاده در حال رانندگی کردن هستید، و دارای انتخاب برای رانندگی در سمت چپ یا به رانندگی در سمت راست جاده باشید همچنین این هم یک بازی هماهنگ است. برای مثال بهره‌مندی ۱۰۰ به معنی بدون تصادف و ۰ به معنی تصادف است، این بازی هماهنگ را می‌توان با ماتریس پرداخت زیر تعریف کرد:

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

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

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

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

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

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

اگر این موارد هر دو را ملاقات نمود، سپس بازیکن با تغییر کوچک در راهبرد ترکیبی خود فوراً به تعادل نش باز خواهد گشت. تعادل گفته شده با ثبات می‌باشد. اگر شرط اول برقرار نباشد سپس تعادل ناپایدار است. اگر فقط شرط نخست برقرار باشد سپس احتمالاً تعداد نامحدود از راهبرد‌های بهینه برای بازیکنی که تغییر کرده وجود دارد. جان نش نشان داد که وضعیت دوم که در طیف وسیعی از بازی به خوبی تعریف شده نمی‌تواند به وجود بیاید. در بازی «رانندگی» مثال بالا هر دو تعادل پایدار و ناپایدار وجود دارد. تعادل شامل راهبرد‌های ترکیبی با احتمال ۱۰۰ ٪ پایدار می‌باشند. اگر هر دو بازیکن کمی احتمالات خودشان را تغییر بدهند، و حریف خود هیچ دلیلی برای تغییر راهبرد خود در عوض نداشته باشد. تعادل (۵۰ ٪، ۵۰ ٪) ناپایدار است. اگر هر دو بازیکن احتمالات خود را تغییر بدهند و سپس دیگر بازیکنان بلافاصله یک راهبرد بهتر را از بین (۰ ٪، ۱۰۰ ٪) یا (۱۰۰ ٪، ۰ ٪) می‌گیرند. پایداری در کاربردهای عملی از تعادل نش بسیار مهم است، زمانی که راهبرد ترکیبی از هر بازیکن کاملاً ناشناخته است، اما باید از توزیع آماری در اقدامات خود در بازی استنتاج کرد. در این حالت تعادل ناپایدارند بسیار بعید است که در عمل به وجود آیند، از آنجا که در هر دقیقه تغییر در سهم هر راهبرد دیده می‌شود منجر به تغییر در راهبرد و شکست تعادل می‌شود. تعادل نش تنها بر حسب انحرافات یک جانبه، پایداری را تعریف می‌کند. در بازی‌های مشارکتی ایده قانع‌کننده کافی نیست. تعادل قوی نش برای انحرافات با هر اتحاد امکان‌پذیری اجازه می‌دهد. بعبارت دیگر، تعادل قوی نش هنگامی تعادل نش است که در آن هیچ اتحادی نمی‌باشد، در نظر گرفتن اقداماتی که خود به عنوان مکمل داده می‌شود، با همکاری می‌توان منافع تمام اعضا را منحرف ساخت. با این حال، مفهوم نش قوی، گاهی خیلی قوی تصور شده‌است که در محیط برای برقراری ارتباط خصوصی نامحدود اجازه می‌دهد. در حقیقت، تعادل قوی نش می‌توان بهینه پارتو باشد. در نتیجه این شرایط، نش قوی تقریباً هرگز وجود ندارد. تعادل نش اصلاح شده معروف به تعادل نش ضد اتحاد (CPNE) هنگامی رخ می‌دهد که بازیکن نمی‌تواند بهتر عمل کند حتی اگر به آن‌ها اجازه برقراری ارتباط و ایجاد «خود اجرا درآوردن» توافق برای منحرف شدن را بدهند. هر راهبرد مرتبط با حمایت شده توسط تسلط همه‌جانبه تکرار شده که بر روی مرز پارتو می‌باشد (CPNE) است. علاوه بر این، ممکن است برای یک بازی داشتن تعادل نش که انعطاف در برابر ائتلاف‌ها کمتر از یک اندازه مشخص شده باشند. (CPNE) مرتبط با تئوری مرکزی است.

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

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

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

• مشارکت‌کنندگان ویکی‌پدیا. «Nash equilibrium». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۲ مه ۲۰۱۱.

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