موضوع مقاله: اپسیلون-تعادل | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اپسیلون-تعادل | مقدمه: در نظریه بازی‌ها یک اپسیلون-تعادل یا یک تعادل نزدیک به نش یک استراتژی است که شرایط تعادل نش به صورت تقریبی در آن برقرار است. | ## بخش 1: اپسیلون-تعادل | در یک تعادل نش هیچ بازیکنی تمایل به عوض کردن رفتارش ندارد اما در تعادل نزدیک به نش این شرط ضعیف شده است؛ یعنی می‌توان بازیکنانی وجود داشته باشند که تمایل کمی به تغییر رفتارشان دارند. این حالت در شرایطی می‌تواند یک راه حل مطلوب از نظریه‌بازی‌ها باشد، مثلاً با فرض وجود سوگیری حفظ وضعیت موجود. این راه حل می‌تواند نسبت به راه حل تعادل نش ترجیح داده شود زیرا می‌توان آن را راحت‌تر محاسبه کرد و در بازی‌های با بیش از دو بازیکن ممکن است احتمالات موجود در یک تعادل نش اعداد گویا نباشند. تعادل تقریبی (تعریف استاندارد) در یک بازی با پارامتر نا منفی ، یک استراتژی را اپسیلون-تعادل می‌نامیم در صورتی که هیچ بازیکنی وجود نداشته باشد که بتواند تنها با تغییر استراتژی خودش امید سودش را بیش از مقدار افزایش دهد. به صورت رسمی فرض می‌کنیم یک بازی نفره باشد که مجموعه رفتارهای برای بازیکن و تابع سود را دارد. بردار استراتژی یک اپسیلون-تعادل نش برای است اگر: به ازای هر داشته باشیم تعادل تقریبی پشتیبانی شده این تعریف شرط قوی‌تری را برای یک اپسیلون-تعادل در نظر می‌گیرد. در این تعریف یک بازیکن تنها زمانی به استراتژی خالص یک احتمال مثبت نسبت می‌دهد که امید سودی که از این استراتژی کسب می‌کند حداکثر به مقدار از سود بهترین جواب کمتر باشد. به ازای استراتژی و استراتژی خالص بازیکن فرض می‌کنیم استراتژی باشد که بازیکن بازی را انجام می‌دهد و بقیه بازیکنان بازیرا انجام می‌دهند. | ## بخش 2: اپسیلون-تعادل | حال شرط تعادل تقریبی پشتیبانی شده را می‌توان به شکل زیر نوشت: نتایج مسئله وجود یک الگوریتم تقریبی با زمان چندجمله‌ای برای یک اپسیلون-تعادل نش معادل مسئله وجود یک الگوریتم برای یک تعادل تقریبی پشتیبانی شده می‌باشد اما وجود چنین الگوریتمی همچنان یک مسئله حل نشده است. برای مقادیر ثابت اپسیلون، الگوریتم‌های چندجمله‌ای بهتری برای تعادل تقریبی نسبت به تعادل تقریبی پشتیبانی شده وجود دارد؛ یعنی مقدار اپسیلون در تعادل تقریبی کمتر از تعادل تقریبی پشتیبانی شده است. مثلاً برای بازی‌هایی که سودشان در بازه است و یک اپسیلون تعادل را می‌توان در زمان چند جمله‌ای محاسبه کرد اما برای محاسبه تعادل تقریبی پشتیبانی شدهاست. مثال مفهوم اپسیلون-تعادل در نظریه بازی‌های تصادفی که می‌توانند تا ابد ادامه داشته باشند از اهمیت بالایی برخوردار است. مثال‌هایی از بازی‌های تصادفی وجود دارد که هیچ تعادل نشی ندارند، امابازای هر اپسیلون بزرگتر از صفر یک اپسیلون-تعادل دارند. در این حالت بازیکن اول سکه را قایم می‌کند و بازیکن دوم باید حدس بزند که سکه شیر است یا خط. اگر بازیکن دوم اشتباهاً حدس بزند که سکه شیر است، بازی با سود صفر برای هر دو نفر به اتمام می‌رسد. به ازای پارامتر ε> ۰ هر استراتژی که بازیکن دوم در آن با احتمال ε حدس بزند که شیر است و با احتمال حدس بزند که خط است (در هر مرحله از بازی و مستقل از مراحل قبلی) یک استراتژی اپسیلون-تعادل برای بازی می‌باشد. | ## بخش 3: اپسیلون-تعادل | همچنین واضح است که هیچ استراتژی برای نفر دوم وجود ندارد که بتواند تضمین کند سود آن دقیقاً ۱ است، بنابراین این بازی تعادل نش ندارد. یک مثال ساده دیگر مسئلهٔ دوراهی زندانی است که بار تکرار می‌شود و سود بازیکنان در این دوره میانگین گرفته می‌شود. حال دو استراتژی زیر را در نظر بگیرید: +ماتریس سود مسئله دوراهی زندانیهمکاریعدم همکاریهمکاری۳ و ۳۰ و ۵عدم همکاری۵ و ۰۱ و ۱ استراتژی این به آن در: بازیکن همان کاری را انجام می‌دهد که حریف در دور قبل انجام داده است. استراتژی نابخشودنی: بازیکن تا زمانی که حریف همکاری کند، همکاری می‌کند اما به محض این که حریف گزینه عدم همکاری را انتخاب کرد، تمام بازی‌های بعدی با گزینه عدم همکاری انجام می‌شود. با این که هیچ‌کدام از این دو استراتژی تعادل نش برای این بازی نیستند، هر دوی آنها به ازای ، یک اپسیلون-تعادل برای این بازی محسوب می‌شوند. مقادیر قابل قبول برای اپسیلون بر حسب مقادیر ماتریس سود و تعداد دفعات بازی محاسبه می‌شود. در اقتصاد، مفهوم اپسیلون-تعادل با استراتژی خالص زمانی کاربرد دارد که استراتژی میکس غیرواقعی به نظر برسد. | ## جمع‌بندی | در یک اپسیلون-تعادل با استراتژی خالص هر بازیکن یک استراتژی خالص که حداکثر به میزان اپسیلون از بهترین استراتژی خالص تفاوت دارد انتخاب می‌کند.