بازی پتانسیل

فرض کنیم یک بازی غیر همکارانه ${\displaystyle G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} )}$ با مشخصات زیر تعریف شود:

• مجموعه‌ای از ${\displaystyle N}$ بازیکن: ${\displaystyle {\mathcal {N}}=\{1,\dots ,N\}}$
• فضای حرکت بازی: ${\displaystyle A=A_{1}\times \dots \times A_{N}}$ که در آن ${\displaystyle A_{i}}$ مجموعه حرکت بازیکن ${\displaystyle i}$ است. فضای حرکت بازی بسته به نوع بازی می‌تواند فضایی گسسته یا پیوسته باشد.
• استراتژی (حرکت) هر بازیکن: ${\displaystyle a_{i}\in A_{i}}$. استراتژی بازیکنان به غیر از ${\displaystyle i}$ با${\displaystyle a_{-i}}$ نشان داده می‌شود و .... ${\displaystyle (a_{i},a_{-i})}$ نمایه حرکتی بازی را نمایش می‌دهد.
• تابه سود بازیکن ${\displaystyle i}$: ${\displaystyle u_{i}(a_{i},a_{-i})}$.

در اینصورت بازی ${\displaystyle G}$

• یک بازی پتانسیل دقیق است اگر تابع پتانیسیلی مانند ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ وجود داشته باشد به نحوی که ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a_{i},\ a'_{i}\in A_{i}}}$ آنگاه:

${\displaystyle \Phi (a_{i},a_{-i})-\Phi (a'_{i},a_{-i})=u_{i}(a_{i},a_{-i})-u_{i}(a'_{i},a_{-i})}$

یعنی مقدار تغییر در سود بازیکن ${\displaystyle i}$ در صورت عوض کردن استراتژی از ${\displaystyle a_{i}}$ به ${\displaystyle a'_{i}}$ ، دقیقاً برابر میزان تغییر در تابع پتانسیل به ازای این دو استراتژی باشد.

• یک بازی پتانسیل وزن دار است اگر تابع پتانیسیلی مانند ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ وجود داشته باشد به نحوی که ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a_{i},\ a'_{i}\in A_{i}}}$ آنگاه:

${\displaystyle \Phi (a_{i},a_{-i})-\Phi (a'_{i},a_{-i})=w_{i}(u_{i}(a_{i},a_{-i})-u_{i}(a'_{i},a_{-i}))}$

• یک بازی پتانسیل ترتیبی است اگر تابع پتانیسیلی مانند ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ وجود داشته باشد به نحوی که ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a_{i},\ a'_{i}\in A_{i}}}$ آنگاه:

${\displaystyle u_{i}(a_{i},a_{-i})-u_{i}(a'_{i},a_{-i})>0\Leftrightarrow \Phi (a_{i},a_{-i})-\Phi (a'_{i},a_{-i})>0}$

• یک بازی پتانسیل تعمیم یافته است اگر تابع پتانیسیلی مانند ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ وجود داشته باشد به نحوی که ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a_{i},\ a'_{i}\in A_{i}}}$ آنگاه:

${\displaystyle u_{i}(a_{i},a_{-i})-u_{i}(a'_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a'_{i},a_{-i})>0}$

هر نمایه حرکتی که تابع پتانسیل را بیشینه کند, یک نقطه تعادل نش است. این نقطه تعادل می‌تواند بیشینه محلی یا بیشینه مطلق باشد. یکی از روش‌های رسیدن به نقطه تعادل نش اجرای بهترین پاسخ پویا (Best response dynamics) در بازی است. در این روش بازی به صورت تکراری انحام می‌شود و در هر تکرار فقط یک بازیکن می‌تواند حرکت خود را تغییر دهد. هر بازیکن ${\displaystyle i\in {\mathcal {N}}}$ در هر تکرار، حرکت ${\displaystyle a_{i}}$ را به نحوی انتخاب می‌کند که سود خود را در نسبت به حرکت انتخاب شده توسط دیگران (${\displaystyle a_{-i}}$) در تکرار قبل بیشینه کند، یعنی ${\displaystyle a_{i}=\arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})}$.

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

یکی از معیارهای سنجش کیفیت تعادل نش، مقایسه آن با بیشینه مطلق (Global optimum) تابع رفاه اجتماعی است. این معیارها هزینه بی نظمی (Price of Anarchy) و هزینه پایداری (Price of Stability) نامیده می‌شوند.

بازی ازدحامی