بازی ازدحامی

یک شبکهٔ ترافیکی را در نظر بگیرید که دو بازیکن از نقطهٔ O حرکت خود را آغاز می‌کنند و می‌خواهند به نقطهٔ T برسند. فرض کنید نقطهٔ O با مسیرهای ارتباطی A و B به نقطهٔ T متصل است، به صورتی که مسیر A کمی از مسیر B طول کمتری دارد (به عبارت دیگر مسیر A با احتمال بیشتری توسط هر بازیکن انتخاب می‌شود). اما هردو راه ارتباطی به سادگی شلوغ می‌شود؛ به این معنا که هر چه تعداد بازیکن بیشتری از یک مسیر عبور کنند تأخیر هر بازیکن بیشتر می‌شود. در نتیجه عبور هر دو بازیکن از مسیر یکسان باعث تأخیر اضافی خواهد شد. نتیجهٔ مطلوب در این بازی درصورتی کسب می‌شود که دو بازیکن همکاری کرده و از مسیرهای متفاوتی عبور کنند. آیا می‌توان چنین نتیجه‌ای گرفت؟ و اگر چنین است، هزینهٔ هر بازیکن چه خواهد بود؟

بازی‌های ازدحامی گسسته دارای اجزای زیرند:

• یک مجموعه از عناصر ازدحام‌پذیر ${\displaystyle E}$
• ${\displaystyle n}$
  بازیکن
• یک مجموعه متناهی از استراتژی‌های ${\displaystyle S_i}$
  برای هر بازیکن بدین صورت که هر استراتژی ${\displaystyle P\in S_i}$
  زیرمجموعه‌ای از ${\displaystyle E}$
  می‌باشد.
• به‌ازای هر عنصر ${\displaystyle e}$
  و یک بردار از استراتژی‌های ${\displaystyle (P_1,P_2,\dots ,P_n)}$
  ، باری که این عنصر متحمل می‌شود به صورت ${\displaystyle x_e=\mathrm{\#}\{i:e\in P_i\}}$
  می‌باشد.
• به‌ازای هر عنصر ${\displaystyle e}$
  ، یک تابع تأخیر به صورت ${\displaystyle d_e:\mathbb{N}⟶\mathbb{R}}$
• به‌ازای استراتژی ${\displaystyle P_i}$
  داده شده، بازیکن ${\displaystyle i}$
  تأخیری معادل ${\displaystyle \sum _{e\in P_i}{d}_e(x_e)}$
  متحمل می‌شود. فرض کنید که هر ${\displaystyle d_e}$
  مثبت و صعودی به صورت یکنواخت است.

گراف جهت‌دار زیر را در نظر بگیرید. هر بازیکن دو استراتژی برای انتخاب دارد تا از A به B برسد. در نتیجه در کل ۴ حالت برای رسیدن بازیکنان به مقصد موجود است. ماتریس زیر، هزینهٔ بازیکنان را به صورت تأخیری که بسته به انتخابشان متحمل می‌شوند، نشان می‌دهد.

در این بازی، استراتژی‌های (A,B) و (B,A) تعادل نش خالص هستند. این بدین دلیل است که هر تغییری توسط هر بازیکن باعث افزایش هزینهٔ او می‌شود (توجه کنید که اعداد جدول هزینه را نشان می‌دهند. در نتیجه بازیکنان مقادیر کوچکتر را ترجیح می‌دهند)

وجود تعادل نش را می‌توان با ساختن یک تابع پتانسیلی که به هر وضعیت خروجی یک مقدار نسبت می‌دهد اثبات کرد. علاوه بر این، ساختن این تابع نشان می‌دهد یافتن بهترین پاسخ به صورت تکرارشونده به تعادل نش منجر می‌شود. تابع ذکرشده را به صورت ${\displaystyle \mathrm{\Phi }=\sum _{e\in E}\sum _{k=1}^{xe}{d}_e(k)}$

بازی‌های ازدحامی پیوسته حالت حدی این نوع بازی‌ها به‌طوری‌که ${\displaystyle n\to \mathrm{\infty }}$

توجه کنید در این حالت استراتژی‌ها مجموعه استراتژی پروفایل‌های ${\displaystyle f_P}$

به عنوان تابع استراتژی، ${\displaystyle \mathrm{\Phi }}$

آخرین گام این است که نشان دهیم، کوچکترین مقدار ${\displaystyle \mathrm{\Phi }}$

بنابراین، تغییرات در پتانسیل تقریباً برابر با ${\displaystyle \delta (\sum _{e\in Q}{d}_e(x_e)-\sum _{e\in P}{d}_e(x_e))}$

به دلیل وجود تعادل نش در بازی‌های ادغامی پیوسته، طبعاً موضوع بعدی تجزیه و تحلیل کیفیت این تعادل‌ها می‌باشد. میزان کیفیت تعادل‌ها را به صورت نسبت مجموع تأخیر در تعادل نش و حالت بهینه که به هزینهٔ هرج و مرج معروف است، استخراج می‌کنیم. در ابتدا، با یک شرط بر روی توابع تأخیر کار را آغاز می‌کنیم:

تعریف تأخیر ${\displaystyle (\lambda ,\mu )}$

حال اگر تأخیر ${\displaystyle (\lambda ,\mu )}$

بازی پتانسیل

• یادداشت‌های سخنرانی از یشای منصور در مورد پتانسیل و تراکم بازی‌ها
• ּبازی‌های تخصیص منابع تا حدودی مربوط به بازی‌های ازدحامی می‌باشند.