تعادل همبسته

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

تعریف رسمی

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

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

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

$\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)$

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

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

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