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

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

تعریف

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

تعادل تقریبی (تعریف استاندارد)

در یک بازی با پارامتر نا منفی ${\displaystyle \varepsilon }$، یک استراتژی را اپسیلون-تعادل می‌نامیم در صورتی که هیچ بازیکنی وجود نداشته باشد که بتواند تنها با تغییر استراتژی خودش امید سودش را بیش از مقدار ${\displaystyle \varepsilon }$ افزایش دهد.[2] هر تعادل نش معادل یک اپسیلون-تعادل است که در آن ${\displaystyle \varepsilon =0}$ است.

به صورت رسمی فرض می‌کنیم ${\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})}$یک بازی ${\displaystyle N}$نفره باشد که مجموعه رفتارهای ${\displaystyle A_{i}}$ برای بازیکن ${\displaystyle i}$و تابع سود ${\displaystyle u}$ را دارد. فرض کنیم ${\displaystyle u_{i}(s)}$ نشان دهندهٔ سود نفر ${\displaystyle i}$است هنگامی که استراتژی ${\displaystyle s}$ انجام شده. فرض می‌کنیم ${\displaystyle \Delta _{i}}$فضای توزیع احتمال بر روی ${\displaystyle A_{i}}$باشد. بردار استراتژی ${\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}}$ یک اپسیلون-تعادل نش برای ${\displaystyle G}$ است اگر:

به ازای هر ${\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N}$داشته باشیم ${\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon }$

تعادل تقریبی پشتیبانی شده

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

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

${\displaystyle \sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j'}^{p}=0.}$

نتایج

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

مثال

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

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

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

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

ماتریس سود مسئله دوراهی زندانی

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

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

با این که هیچ‌کدام از این دو استراتژی تعادل نش برای این بازی نیستند، هر دوی آنها به ازای ${\displaystyle \epsilon >0}$، یک اپسیلون-تعادل برای این بازی محسوب می‌شوند. مقادیر قابل قبول برای اپسیلون بر حسب مقادیر ماتریس سود و تعداد دفعات بازی ${\displaystyle T}$ محاسبه می‌شود.

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

منابع

1. V. Bubelis (1979). "On equilibria in finite games". International Journal on Game Theory. 8 (2): 65–79. doi:10.1007/bf01768703.
2. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
3. P.W. Goldberg and C.H. Papadimitriou (2006). "Reducibility Among Equilibrium Problems". 38th Symposium on Theory of Computing. pp. 61–70. doi:10.1145/1132516.1132526.
4. C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou (2009). "The Complexity of Computing a Nash Equilibrium". SIAM Journal on Computing. 39 (3): 195–259. doi:10.1137/070699652.
5. H. Tsaknakis and Paul G. Spirakis (2008). "An optimisation approach for approximate Nash equilibria". Internet Mathematics. 5 (4): 365–382. doi:10.1080/15427951.2008.10129172.
6. Spyros C. Kontogiannis and Paul G. Spirakis (2010). "Well Supported Approximate Equilibria in Bimatrix Games". Algorithmica. 57 (4): 653–667. doi:10.1007/s00453-008-9227-6.

منابع

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.

Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 More than one of |ISBN= and |isbn= specified (help)More than one of |ISBN= and |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.

Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7 More than one of |ISBN= and |isbn= specified (help)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.