بازی پتانسیل

فرض کنیم یک بازی غیر همکارانه ${\displaystyle G=(N,A=A_1\times \dots \times A_N,u:A\to \mathbb{R})}$

• مجموعه‌ای از ${\displaystyle N}$
  بازیکن: ${\displaystyle \mathcal{N}=\{1,\dots ,N\}}$
• فضای حرکت بازی: ${\displaystyle A=A_1\times \cdots \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 \mathrm{\Phi }:A\to \mathbb{R}}$
  وجود داشته باشد به نحوی که ${\displaystyle \mathrm{\forall }{a}_{-i}\in A_{-i},\mathrm{\forall }{a}_i,a_i^{\prime }\in A_i}$
  آنگاه:

${\displaystyle \mathrm{\Phi }(a_i,a_{-i})-\mathrm{\Phi }(a_i^{\prime },a_{-i})=u_i(a_i,a_{-i})-u_i(a_i^{\prime },a_{-i})}$

یعنی مقدار تغییر در سود بازیکن ${\displaystyle i}$

در صورت عوض کردن استراتژی از ${\displaystyle a_i}$

به ${\displaystyle a_i^{\prime }}$

، دقیقاً برابر میزان تغییر در تابع پتانسیل به ازای این دو استراتژی باشد.

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

${\displaystyle \mathrm{\Phi }(a_i,a_{-i})-\mathrm{\Phi }(a_i^{\prime },a_{-i})=w_i(u_i(a_i,a_{-i})-u_i(a_i^{\prime },a_{-i}))}$

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

${\displaystyle u_i(a_i,a_{-i})-u_i(a_i^{\prime },a_{-i})>0\iff \mathrm{\Phi }(a_i,a_{-i})-\mathrm{\Phi }(a_i^{\prime },a_{-i})>0}$

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

${\displaystyle u_i(a_i,a_{-i})-u_i(a_i^{\prime },a_{-i})>0\Rightarrow \mathrm{\Phi }(a_i^{\prime },a_{-i})-\mathrm{\Phi }(a_i^{\prime },a_{-i})>0}$

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

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

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

بازی ازدحامی