تعادل همبسته
در تئوری بازی، تعادل همبسته یک مفهوم راه حل است که عمومی تر از تعادل شناخته شده نش است. این تعادل اولین بار توسط ریاضیدان رابرت آومان در سال ۱۹۷۴ بررسی شد.[۱][۲] در این تعادل هر بازیکن حرکت خود را بر اساس مشاهده اش از یک سیگنال عمومی (متغیر تصادفی مشترک) ، انتخاب میکند. هر راهبرد یک عمل را به هر مشاهده احتمالی بازیکن از سیگنال نسبت میدهد. اگر هیچ بازیکنی تمایل به انحراف از راهبرد توصیه شده نداشته باشد (با فرض عدم انحراف دیگران)، توزیع را تعادل همبسته مینامند.
تعریف رسمی
[ویرایش]یک بازی راهبردی با بازیکن با یک مجموعه راهبرد و یک تابع مطلوبیت برای هر بازیکن تعریف میشود. وقتی بازیکن راهبرد را انتخاب و باقی بازیکنان راهبرد را انتخاب میکنند، مطلوبیت بازیکن برابر با خواهد بود.
تغییر راهبرد برای بازیکن با تابع: تعریف میشود. تابع به بازیکن میگوید تا رفتار خود را با عمل هنگامی که دستور بازی داده میشود تعویض کند.
فرض کنید که یک فضای احتمال شمارا باشد. برای هر بازیکن ، پارتیشن اطلاعات این بازیکن ، احتمال بسین و همان مقدار موجود در که متناسب با هر رخداد است را اختصاص میدهد. در این صورت یک تعادل همبسته برای بازی راهبردک است اگر برای هر بازیکن و هر تغییر راهبرد نامساوی زیر برقرار باشد:
به عبارت دیگر، یک تعادل همبسته است اگر هیچ بازیکنی نتواند مطلوبیت مورد انتظار خود را از طریق تغییر راهبرد بهبود بخشد.
یادگیری تعادل همبسته
[ویرایش]یکی از مزایای تعادلهای همبسته این است که از نظر محاسباتی از تعادل نش هزینه کمتری دارند. یک روش توجیه این مزیت این است که محاسبه یک تعادل همبسته فقط به حل یک برنامهریزی خطی نیاز دارد در حالی که حل تعادل نش مساوی با یافتن یک نقطه ثابت است.[۳]
منابع
[ویرایش]- ↑ Aumann, Robert (1974). "Subjectivity and correlation in randomized strategies". Journal of Mathematical Economics. 1 (1): 67–96. CiteSeerX 10.1.1.120.1740. doi:10.1016/0304-4068(74)90037-8.
- ↑ Aumann, Robert (1987). "Correlated Equilibrium as an Expression of Bayesian Rationality". Econometrica. 55 (1): 1–18. CiteSeerX 10.1.1.295.4243. doi:10.2307/1911154. JSTOR 1911154.
- ↑ Papadimitriou, Christos H.; Roughgarden, Tim (2008). "Computing correlated equilibria in multi-player games". J. ACM. 55 (3): 14:1–14:29. CiteSeerX 10.1.1.335.2634. doi:10.1145/1379759.1379762.