تعادل همبسته

در تئوری بازی، تعادل همبسته یک مفهوم راه حل است که عمومی تر از تعادل شناخته شده نش است. این تعادل اولین بار توسط ریاضیدان رابرت آومان در سال ۱۹۷۴ بررسی شد.[1][2] در این تعادل هر بازیکن حرکت خود را بر اساس مشاهده اش از یک سیگنال عمومی (متغیر تصادفی مشترک) ، انتخاب می‌کند. هر استراتژی یک عمل را به هر مشاهده احتمالی بازیکن از سیگنال نسبت می‌دهد. اگر هیچ بازیکنی تمایل به انحراف از استراتژی توصیه شده نداشته باشد (با فرض عدم انحراف دیگران)، توزیع را تعادل همبسته می‌نامند.

تعریف رسمی

یک بازی استراتژیک با ${\displaystyle N}$ بازیکن ${\displaystyle \displaystyle (N,A_{i},u_{i})}$ با یک مجموعه استراتژی ${\displaystyle A_{i}}$ و یک تابع مطلوبیت ${\displaystyle u_{i}}$ برای هر بازیکن ${\displaystyle i}$ تعریف می‌شود. وقتی بازیکن ${\displaystyle i}$ استراتژی${\displaystyle a_{i}\in A_{i}}$ را انتخاب و باقی بازیکنان استراتژی ${\displaystyle a_{-i}}$ را انتخاب می‌کنند، مطلوبیت بازیکن ${\displaystyle i}$ برابر با ${\displaystyle \displaystyle u_{i}(a_{i},a_{-i})}$ خواهد بود.

تغییر استراتژی برای بازیکن ${\displaystyle i}$ با تابع: ${\displaystyle \phi _{i}\colon A_{i}\to A_{i}}$ تعریف می‌شود. تابع ${\displaystyle \phi _{i}}$ به بازیکن ${\displaystyle i}$ می‌گوید تا رفتار خود را با عمل ${\displaystyle \phi _{i}(a_{i})}$ هنگامی که دستور بازی ${\displaystyle a_{i}}$ داده می‌شود تعویض کند.

فرض کنید که ${\displaystyle (\Omega ,\pi )}$ یک فضای احتمال شمارا باشد. برای هر بازیکن ${\displaystyle i}$ ، ${\displaystyle P_{i}}$ پارتیشن اطلاعات این بازیکن ، ${\displaystyle q_{i}}$ احتمال بسین ${\displaystyle i}$ و ${\displaystyle s_{i}\colon \Omega \rightarrow A_{i}}$ همان مقدار موجود در ${\displaystyle P_{i}}$ که متناسب با هر رخداد است را اختصاص می‌دهد. در این صورت ${\displaystyle ((\Omega ,\pi ),P_{i},s_{i})}$ یک تعادل همبسته برای بازی استراتژیک${\displaystyle (N,A_{i},u_{i})}$ است اگر برای هر بازیکن ${\displaystyle i}$ و هر تغییر استراتژی ${\displaystyle \phi _{i}}$ نامساوی زیر برقرار باشد:

${\displaystyle \sum _{\omega \in \Omega }q_{i}(\omega )u_{i}(s_{i}(\omega ),s_{-i}(\omega ))\geq \sum _{\omega \in \Omega }q_{i}(\omega )u_{i}\left(\phi _{i}\left(s_{i}(\omega )\right),s_{-i}(\omega )\right)}$

به عبارت دیگر، ${\displaystyle ((\Omega ,\pi ),P_{i})}$ یک تعادل همبسته است اگر هیچ بازیکنی نتواند مطلوبیت مورد انتظار خود را از طریق تغییر استراتژی بهبود بخشد.

یادگیری تعادل همبسته

یکی از مزایای تعادل‌های همبسته این است که از نظر محاسباتی از تعادل نش هزینه کمتری دارند. یک روش توجیه این مزیت این است که محاسبه یک تعادل همبسته فقط به حل یک برنامه‌ریزی خطی نیاز دارد در حالی که حل تعادل نش مساوی با یافتن یک نقطه ثابت است.[3]

منابع

1. 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.
2. 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.
3. 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.

منابع