اپسیلون-تعادل

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

## تعریف
برای یک اپسیلون تعادل تعاریف مختلفی وجود دارد.

### تعادل تقریبی (تعریف استاندارد)
در یک بازی با پارامتر نا منفی \varepsilon، یک استراتژی را اپسیلون-تعادل می‌نامیم در صورتی که هیچ بازیکنی وجود نداشته باشد که بتواند تنها با تغییر استراتژی خودش امید سودش را بیش از مقدار \varepsilon افزایش دهد. هر تعادل نش معادل یک اپسیلون-تعادل است که در آن \varepsilon = 0 است.

به صورت رسمی فرض می‌کنیم G = (N, A=A_1 \times \dotsb \times A_N, u\colon A \to R^N)یک بازی Nنفره باشد که مجموعه رفتارهای A_i برای بازیکن iو تابع سود u را دارد. فرض کنیم u_i (s) نشان دهندهٔ سود نفر iاست هنگامی که استراتژی s انجام شده. فرض می‌کنیم \Delta_iفضای توزیع احتمال بر روی A_iباشد. بردار استراتژی \sigma \in \Delta = \Delta_1 \times \dotsb \times \Delta_N یک اپسیلون-تعادل نش برای G است اگر:

به ازای هر \sigma_i^' \in \Delta_i, i \in Nداشته باشیم u_i(\sigma)\geq u_i(\sigma_i^',\sigma_{-i})-\varepsilon

### تعادل تقریبی پشتیبانی شده
این تعریف شرط قوی‌تری را برای یک اپسیلون-تعادل در نظر می‌گیرد. در این تعریف یک بازیکن تنها زمانی به استراتژی خالص aیک احتمال مثبت نسبت می‌دهد که امید سودی که از این استراتژی کسب می‌کند حداکثر به مقدار \varepsilonاز سود بهترین جواب کمتر باشد.

فرض کنیم x_sاحتمال انجام استراتژی sباشد. برای بازیکن pفرض می‌کنیم S_{-p} مجموعه استراتژی‌های تمام بازیکنان به جز بازیکن p باشد. به ازای استراتژی s\in S_{-p}و استراتژی خالص j بازیکن pفرض می‌کنیم js استراتژی باشد که بازیکن pبازی j را انجام می‌دهد و بقیه بازیکنان بازیsرا انجام می‌دهند. تعریف می‌کنیم  u_p(s) سود بازی pمی‌باشد زمانی که استراتژی sاستفاده شده است. حال شرط تعادل تقریبی پشتیبانی شده را می‌توان به شکل زیر نوشت:

\sum_{s\in S_{-p}}u_p(js)x_s > \varepsilon+\sum_{s\in S_{-p}}u_p(j's)x_s \Longrightarrow x^p_{j'} = 0.

## نتایج
مسئله وجود یک الگوریتم تقریبی با زمان چندجمله‌ای برای یک اپسیلون-تعادل نش معادل مسئله وجود یک الگوریتم برای یک تعادل تقریبی پشتیبانی شده می‌باشد اما وجود چنین الگوریتمی همچنان یک مسئله حل نشده است. برای مقادیر ثابت اپسیلون، الگوریتم‌های چندجمله‌ای بهتری برای تعادل تقریبی نسبت به تعادل تقریبی پشتیبانی شده وجود دارد؛ یعنی مقدار اپسیلون در تعادل تقریبی کمتر از تعادل تقریبی پشتیبانی شده است. مثلاً برای بازی‌هایی که سودشان در بازه [0, 1]است و \epsilon = 0.3393 یک اپسیلون تعادل را می‌توان در زمان چند جمله‌ای محاسبه کرد اما برای محاسبه تعادل تقریبی پشتیبانی شده\epsilon = \frac{2}{3}است.

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

یکی از ساده‌ترین مثال‌ها مدل خاص ارائه شده از بازی سکه‌های مطابق توسط Everett می‌باشد. در این حالت بازیکن اول سکه را قایم می‌کند و بازیکن دوم باید حدس بزند که سکه شیر است یا خط. اگر بازیکن دوم درست حدس بزند، سکه را از بازیکن اول می‌برد و بازی تمام می‌شود. اگر بازیکن دوم اشتباهاً حدس بزند که سکه شیر است، بازی با سود صفر برای هر دو نفر به اتمام می‌رسد. اگر بازیکن دوم به اشتباه حدس بزند که سکه خط است بازی تکرار می‌شود. اگر بازی تا ابد ادامه داشته باشد، سود هر دو بازیکن صفر است.

به ازای پارامتر *ε*> ۰ هر استراتژی که بازیکن دوم در آن با احتمال ε حدس بزند که شیر است و با احتمال 1 - \varepsilonحدس بزند که خط است (در هر مرحله از بازی و مستقل از مراحل قبلی) یک استراتژی اپسیلون-تعادل برای بازی می‌باشد. امید میزان سود بازیکن دوم در این استراتژی حداقل 1 - \varepsilon است. همچنین واضح است که هیچ استراتژی برای نفر دوم وجود ندارد که بتواند تضمین کند سود آن دقیقاً ۱ است، بنابراین این بازی تعادل نش ندارد.

یک مثال ساده دیگر مسئلهٔ دوراهی زندانی است که T بار تکرار می‌شود و سود بازیکنان در این T دوره میانگین گرفته می‌شود. تنها تعادل نش این بازی این است که در هر دوره از بازی عدم همکاری انتخاب شود. حال دو استراتژی زیر را در نظر بگیرید:

* استراتژی این به آن در: بازیکن همان کاری را انجام می‌دهد که حریف در دور قبل انجام داده است.
* استراتژی نابخشودنی: بازیکن تا زمانی که حریف همکاری کند، همکاری می‌کند اما به محض این که حریف گزینه عدم همکاری را انتخاب کرد، تمام بازی‌های بعدی با گزینه عدم همکاری انجام می‌شود.
با این که هیچ‌کدام از این دو استراتژی تعادل نش برای این بازی نیستند، هر دوی آنها به ازای \epsilon > 0، یک اپسیلون-تعادل برای این بازی محسوب می‌شوند. مقادیر قابل قبول برای اپسیلون بر حسب مقادیر ماتریس سود و تعداد دفعات بازی T محاسبه می‌شود.

در اقتصاد، مفهوم اپسیلون-تعادل با استراتژی خالص زمانی کاربرد دارد که استراتژی میکس غیرواقعی به نظر برسد. در یک اپسیلون-تعادل با استراتژی خالص هر بازیکن یک استراتژی خالص که حداکثر به میزان اپسیلون از بهترین استراتژی خالص تفاوت دارد انتخاب می‌کند. برای مثال در مدل Bertrand–Edgeworth که هیچ تعادلی با استراتژی خالص وجود ندارد ممکن است یک تعادل-اپسیلون با استراتژی خالص وجود داشته باشد.

## منابع

 منابع H Dixon Approximate Bertrand Equilibrium in a Replicated Industry, Review of Economic Studies, 54 (1987), pages 47–62.
 H. Everett. "Recursive Games". In H.W. Kuhn and A.W. Tucker, editors. *Contributions to the theory of games*, vol. III, volume 39 of *Annals of Mathematical Studies*. Princeton University Press, 1957.
 More than one of |ISBN= and &#x7C;isbn= specified (help)

. An 88-page mathematical introduction; see Section 3.7. Free online at many universities.
 R. Radner. *Collusive behavior in non-cooperative epsilon equilibria of oligopolies with long but finite lives*, Journal of Economic Theory, **22**, 121–157, 1980.
 More than one of |ISBN= and |isbn= specified (help)
. A comprehensive reference from a computational perspective; see Section 3.4.7. Downloadable free online.
 S.H. Tijs. *Nash equilibria for noncooperative *n*-person games in normal form*, Siam Review, **23**, 225–237, 1981.

رده:ایده‌های تعادل تئوری بازی
رده:صفحه‌های دارای ارجاع با متغیر تکراری
رده:نظریه بازی‌ها