بازی ازدحامی

**بازی‌های ازدحامی** دسته‌ای در نظریهٔ بازی‌ها هستند که در سال ۱۹۷۳ توسط رزنتال مطرح شدند. در یک بازی ازدحامی بازیکنان و منابع را تعریف می‌کنیم و سود هر بازیکن به منابعی که انتخاب می‌کند و تعداد بازیکنانی که همان منابع را انتخاب می‌کنند بستگی دارد. بازی‌های ازدحامی حالت خاصی از بازی‌های پتانسیل می‌باشند. رزنتال ثابت کرد که هر بازی ازدحامی یک بازی پتانسیل نیز می‌باشد و بعدها مندرر و شاپلی (۱۹۹۶) عکس آن را اثبات کردند: به ازای هر بازی پتانسیلی، یک بازی ازدحامی با تابع پتانسیل یکسان موجود است.

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

## تعریف
بازی‌های ازدحامی گسسته دارای اجزای زیرند:
* یک مجموعه از عناصر ازدحام‌پذیر E
* n بازیکن
* یک مجموعه متناهی از استراتژی‌های S_i برای هر بازیکن بدین صورت که هر استراتژی P \in S_i زیرمجموعه‌ای از E می‌باشد.
* به‌ازای هر عنصر e و یک بردار از استراتژی‌های (P_1, P_2, \ldots, P_n) ، باری که این عنصر متحمل می‌شود به صورت x_e = \#\{ i : e \in P_i \} می‌باشد.
* به‌ازای هر عنصر e، یک تابع تأخیر به صورت d_e : \mathbb{N} \longrightarrow \mathbb{R}
* به‌ازای استراتژی P_i داده شده، بازیکن i تأخیری معادل  \textstyle \sum_{e \in P_i} d_e(x_e) متحمل می‌شود. فرض کنید که هر d_e مثبت و صعودی به صورت یکنواخت است.

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

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

## وجود تعادل نش
وجود تعادل نش را می‌توان با ساختن یک تابع پتانسیلی که به هر وضعیت خروجی یک مقدار نسبت می‌دهد اثبات کرد. علاوه بر این، ساختن این تابع نشان می‌دهد یافتن بهترین پاسخ به صورت تکرارشونده به تعادل نش منجر می‌شود. تابع ذکرشده را به صورت  \textstyle \Phi =\sum _\sum _^}d_{e}(k) تعریف می‌کنیم. توجه کنید که این تابع همان رفاه اجتماعی \textstyle \sum _x_{e}d_{e}(x_{e}) نیست؛ بلکه بیشتر یک نوع انتگرال گسسته محسوب می‌شود. ویژگی اصلی تابع پتانسیلی این است که اگر یک بازیکن استراتژی خود را تفییر دهد، تغییر تأخیر او برابر با تغییر در تابع پتانسیل باشد.حالتی را در نظر بگیرید که بازیکن i استراتژی خود را از P_{i} به Q_{i} تغییر می‌دهد. عناصری که در هر دو استراتژی هستند بدون تغییر باقی می‌مانند و عناصری که این بازیکن آن‌ها را رها می‌کند (به عبارت دیگر  e\in P_{i}-Q_{i}) تابع پتانسیل را به مقدار d_{e}(x_{e}) کاهش می‌دهند و همچنین عناصری که این بازیکن به آن‌ها می‌پیوندد (به عبارت دیگر e\in Q_{i}-P_{i}) تابع پتانسیلی را به اندازهٔ d_{e}(x_{e}+1) افزایش می‌دهند. این تغییر در پتانسیل دقیقاً با تغییر تأخیر برای این بازیکن برابر می‌باشد. در نتیجه تابع تعریف‌شده در حقیقت یک تابع پتانسیل می‌باشد.

## بازی‌های ازدحامی پیوسته
بازی‌های ازدحامی پیوسته حالت حدی این نوع بازی‌ها به‌طوری‌که n \rightarrow \infty هستند. در این حالت، بازیکنان را بی‌نهایت کوچک در نظر می‌گیریم. همچنان E را مجموعهٔ متناهی از عناصر ازدحام‌پذیر تعریف می‌کنیم. درعوض به‌جای مشخص کردن nبازیکن در حالت گسسته، n نوع بازیکن داریم به صورتی که هر نوع بازیکن iبه r_i که نشان‌دهندهٔ نرخ ترافیک برای آن نوع است، مرتبط است. هر نوع بازیکن یک استراتژی از مجموعه S_i که مجزا در نظر گرفته می‌شوند،را انتخاب می‌کند. همانند قبل، فرض کنید که d_e یکنوا و مثبت می‌باشد اما فرض پیوسته بودن را هم به آن‌ها اضافه می‌کنیم. درنهایت، به بازیکنان از یک نوع اجازه می‌دهیم به‌طور نسبی بین مجموعهٔ استراتژی‌شان توزیع شوند. بدین صورت که به ازای استراتژی P \in S_i مقدار f_P برابر با کسری از بازیکنان نوع i که از استراتژی P استفاده می‌کنند، می‌باشد. فرض کنید داریم: \textstyle \sum_{P\in S_i} f_P = r_i.

## وجود تعادل در حالت پیوسته
توجه کنید در این حالت استراتژی‌ها مجموعه استراتژی پروفایل‌های f_{P} می‌باشند. برای یک مجموعه استراتژی S_{i}  با اندازهٔ n ، مجموعهٔ تمام پروفایل‌های معتبر زیرمجموعهٔ فشرده‌ای از [0,r_{i}]^{n} می‌باشد. همانند قبل، تابع پتانسیل را به صورت \textstyle \Phi =\sum _\int _{0}^}d_{e}(z)\,dz با جایگزینی انتگرال گسسته با نوع استاندارد آن، تعریف می‌کنیم.

به عنوان تابع استراتژی، \Phiبه دلیل پیوسته بودن d_eو x_e، نیز پیوسته است. در نتیجه با توجه به قضیهٔ ارزش فوق‌العاده، \Phiمقدار کمینهٔ سراسری خود را می‌گیرد.

آخرین گام این است که نشان دهیم، کوچکترین مقدار \Phi همان تعادل نش می‌باشد. فرض کنید برخلاف این، یک مجموعه f_P موجود است به صورتی که مقدار \Phiرا کمینه می‌کند اما تعادل نش نیست. سپس برای یک نوع iمی‌توان Q برای انتخاب کنونی P بهبود داد. به عبارت دیگر داریم: \textstyle \sum_{e \in P} d_e(x_e) > \sum_{e \in Q} d_e(x_e). حال مقدار کوجک \delta  را از بازیکنانی که استراتژی P را دارند، می‌گیریم و آن‌ها را به استراتژی Q تغییر می‌دهیم. حال، برای هر x_e \in Q، بار آن را با اندازهٔ \deltaافزایش داده‌ایم. در نتیجه مقدار آن در \Phi ، در این حالت برابر \textstyle \int _{0}^d_{e}(z)dz می‌باشد. با مشتق گرفتن از از این انتگرال، تغییرات تقریباً برابر با \delta \cdot d_e(x_e) با خطای \delta^2 خواهد بود. همین تحلیل تغییرات برای زمانی که به یال‌های داخل P نگاه کنیم صادق خواهد بود.

بنابراین، تغییرات در پتانسیل تقریباً برابر با \textstyle \delta (\sum _d_{e}(x_{e})-\sum _d_{e}(x_{e})) که مقداری منفی است، می‌باشد. این تناقض بوده و نتیجه می‌گیریم \Phi  کمینه نشده‌است. در نتیجه، کمینهٔ \Phi  باید یک تعادل نش باشد.

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

**تعریف** تأخیر (\lambda ,\mu )ملایم است در صورتی که به ازای هر x,y>0 داریم: yd(x)\leq \lambda yd(y)+\mu xd(x)

حال اگر تأخیر  (\lambda ,\mu )ملایم بود، fیک تعادل نش می‌باشد و f^{*}یک اختصاص بهینه منابع است و سپس داریم: \textstyle \sum _{e}x_{e}d_{e}(x_{e})\leq {\frac {\lambda }{1-\mu }}\sum _{e}x_{e}^{*}d_{e}(x_{e}^{*}) . به عبارت دیگر، هزینهٔ هرج و مرج برابر با  \textstyle {\frac {\lambda }{1-\mu }}می‌باشد. برای اثبات این مطلب می‌توانید به این نوشته مراجعه کنید.

## جستارهای وابسته
بازی پتانسیل

## منابع

* 
*.

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

رده:کلاس‌های بازی نظریه بازی‌ها
رده:نظریه بازی‌ها