بازی پتانسیل

بازی پتانسیل (به انگلیسی: Potential game) در نظریه بازی ها به بازی ای گفته می‌شود که در آن انگیزه بازیکنان برای تغییر استراتژی در بازی را می‌توان تنها توسط یک تابع، که به آن تابع پتانسیل گقته می‌شود، نشان داد.

داو ماندرر و لوید شپلی در سال 1996 مفهوم بازی پتانسیل را برای اولین بار ارائه کردند. قبل از آن‌ها رابرت روزنتال در مقاله خود در سال 1973 بازی ازدحامی را معرفی کرد که خود حالت خاصی از بازی پتانسیل می‌باشد.

از آنجا که در این بازی سود (یا هزینه) هر بازیکن با تابع پتانسیل بیان می‌شود، ویژگی‌های بازی از جمله ویژگی‌های نقطه تعادل را می‌توان با تحلیل تابع پتانسیل تحلیل کرد. تحلیل بازی توسط تابع پتانسیل موجب شده تا بازی پتانسیل علاوه بر اقتصاد، کاربردهای فراوانی در علوم مهندسی از جمله تخصیص منابع، بهینه‌سازی توزیع شده و طراحی سازوکار داشته باشد.

تعریف

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

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

در اینصورت بازی $G$

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

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

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

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

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

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

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

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

$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) در بازی است. در این روش بازی به صورت تکراری انحام می‌شود و در هر تکرار فقط یک بازیکن می‌تواند حرکت خود را تغییر دهد. هر بازیکن $i\in {\mathcal {N}}$ در هر تکرار، حرکت $a_{i}$ را به نحوی انتخاب می‌کند که سود خود را در نسبت به حرکت انتخاب شده توسط دیگران ($a_{-i}$) در تکرار قبل بیشینه کند، یعنی $a_{i}=\arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})$.

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

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

جستارهای وابسته

بازی ازدحامی