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

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

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

در یک بازی با پارامتر نا منفی ${\displaystyle \varepsilon }$، یک استراتژی را اپسیلون-تعادل می‌نامیم در صورتی که هیچ بازیکنی وجود نداشته باشد که بتواند تنها با تغییر استراتژی خودش امید سودش را بیش از مقدار ${\displaystyle \varepsilon }$ افزایش دهد.^[۲] هر تعادل نش معادل یک اپسیلون-تعادل است که در آن ${\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 }$

این تعریف^[۳] شرط قوی‌تری را برای یک اپسیلون-تعادل در نظر می‌گیرد. در این تعریف یک بازیکن تنها زمانی به استراتژی خالص ${\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.}$

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

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

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

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

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

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

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

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