بازی ازدحامی
بازی‌های ازدحامی دسته‌ای در نظریهٔ بازی‌ها هستند که در سال ۱۹۷۳ توسط رزنتال مطرح شدند. در یک بازی ازدحامی بازیکنان و منابع را تعریف می‌کنیم و سود هر بازیکن به منابعی که انتخاب می‌کند و تعداد بازیکنانی که همان منابع را انتخاب می‌کنند بستگی دارد. بازی‌های ازدحامی حالت خاصی از بازی‌های پتانسیل می‌باشند. رزنتال ثابت کرد که هر بازی ازدحامی یک بازی پتانسیل نیز می‌باشد و بعدها مندرر و شاپلی (۱۹۹۶) عکس آن را اثبات کردند: به ازای هر بازی پتانسیلی، یک بازی ازدحامی با تابع پتانسیل یکسان موجود است.
یک شبکهٔ ترافیکی را در نظر بگیرید که دو بازیکن از نقطهٔ O حرکت خود را آغاز می‌کنند و می‌خواهند به نقطهٔ T برسند. فرض کنید نقطهٔ O با مسیرهای ارتباطی A و B به نقطهٔ T متصل است، به صورتی که مسیر A کمی از مسیر B طول کمتری دارد (به عبارت دیگر مسیر A با احتمال بیشتری توسط هر بازیکن انتخاب می‌شود). اما هردو راه ارتباطی به سادگی شلوغ می‌شود؛ به این معنا که هر چه تعداد بازیکن بیشتری از یک مسیر عبور کنند تأخیر هر بازیکن بیشتر می‌شود. در نتیجه عبور هر دو بازیکن از مسیر یکسان باعث تأخیر اضافی خواهد شد. نتیجهٔ مطلوب در این بازی درصورتی کسب می‌شود که دو بازیکن همکاری کرده و از مسیرهای متفاوتی عبور کنند. آیا می‌توان چنین نتیجه‌ای گرفت؟ و اگر چنین است، هزینهٔ هر بازیکن چه خواهد بود؟
بازی‌های ازدحامی گسسته دارای اجزای زیرند:
گراف جهت‌دار زیر را در نظر بگیرید. هر بازیکن دو استراتژی برای انتخاب دارد تا از A به B برسد. در نتیجه در کل ۴ حالت برای رسیدن بازیکنان به مقصد موجود است. ماتریس زیر، هزینهٔ بازیکنان را به صورت تأخیری که بسته به انتخابشان متحمل می‌شوند، نشان می‌دهد. در این بازی، استراتژی‌های (A,B) و (B,A) تعادل نش خالص هستند. این بدین دلیل است که هر تغییری توسط هر بازیکن باعث افزایش هزینهٔ او می‌شود (توجه کنید که اعداد جدول هزینه را نشان می‌دهند. در نتیجه بازیکنان مقادیر کوچکتر را ترجیح می‌دهند)
وجود تعادل نش را می‌توان با ساختن یک تابع پتانسیلی که به هر وضعیت خروجی یک مقدار نسبت می‌دهد اثبات کرد. علاوه بر این، ساختن این تابع نشان می‌دهد یافتن بهترین پاسخ به صورت تکرارشونده به تعادل نش منجر می‌شود. تابع ذکرشده را به صورت formula_15 تعریف می‌کنیم. توجه کنید که این تابع همان رفاه اجتماعی formula_16 نیست؛ بلکه بیشتر یک نوع انتگرال گسسته محسوب می‌شود. ویژگی اصلی تابع پتانسیلی این است که اگر یک بازیکن استراتژی خود را تفییر دهد، تغییر تأخیر او برابر با تغییر در تابع پتانسیل باشد.حالتی را در نظر بگیرید که بازیکن formula_12 استراتژی خود را از formula_18 به formula_19 تغییر می‌دهد. عناصری که در هر دو استراتژی هستند بدون تغییر باقی می‌مانند و عناصری که این بازیکن آن‌ها را رها می‌کند (به عبارت دیگر formula_20) تابع پتانسیل را به مقدار formula_21 کاهش می‌دهند و همچنین عناصری که این بازیکن به آن‌ها می‌پیوندد (به عبارت دیگر formula_22) تابع پتانسیلی را به اندازهٔ formula_23 افزایش می‌دهند. این تغییر در پتانسیل دقیقاً با تغییر تأخیر برای این بازیکن برابر می‌باشد. در نتیجه تابع تعریف‌شده در حقیقت یک تابع پتانسیل می‌باشد.
بازی‌های ازدحامی پیوسته حالت حدی این نوع بازی‌ها به‌طوری‌که formula_24 هستند. در این حالت، بازیکنان را بی‌نهایت کوچک در نظر می‌گیریم. همچنان formula_1 را مجموعهٔ متناهی از عناصر ازدحام‌پذیر تعریف می‌کنیم. درعوض به‌جای مشخص کردن formula_2بازیکن در حالت گسسته، formula_2 نوع بازیکن داریم به صورتی که هر نوع بازیکن formula_12به formula_29 که نشان‌دهندهٔ نرخ ترافیک برای آن نوع است، مرتبط است. هر نوع بازیکن یک استراتژی از مجموعه formula_3 که مجزا در نظر گرفته می‌شوند،را انتخاب می‌کند. همانند قبل، فرض کنید که formula_14 یکنوا و مثبت می‌باشد اما فرض پیوسته بودن را هم به آن‌ها اضافه می‌کنیم. درنهایت، به بازیکنان از یک نوع اجازه می‌دهیم به‌طور نسبی بین مجموعهٔ استراتژی‌شان توزیع شوند. بدین صورت که به ازای استراتژی formula_4 مقدار formula_33 برابر با کسری از بازیکنان نوع formula_12 که از استراتژی formula_35 استفاده می‌کنند، می‌باشد. فرض کنید داریم: formula_36.
توجه کنید در این حالت استراتژی‌ها مجموعه استراتژی پروفایل‌های formula_37 می‌باشند. برای یک مجموعه استراتژی formula_38 با اندازهٔ formula_2 ، مجموعهٔ تمام پروفایل‌های معتبر زیرمجموعهٔ فشرده‌ای از formula_40 می‌باشد. همانند قبل، تابع پتانسیل را به صورت formula_41 با جایگزینی انتگرال گسسته با نوع استاندارد آن، تعریف می‌کنیم.
به عنوان تابع استراتژی، formula_42به دلیل پیوسته بودن formula_14و formula_44، نیز پیوسته است. در نتیجه با توجه به قضیهٔ ارزش فوق‌العاده، formula_42مقدار کمینهٔ سراسری خود را می‌گیرد.
آخرین گام این است که نشان دهیم، کوچکترین مقدار formula_42 همان تعادل نش می‌باشد. فرض کنید برخلاف این، یک مجموعه formula_33 موجود است به صورتی که مقدار formula_42را کمینه می‌کند اما تعادل نش نیست. سپس برای یک نوع formula_12می‌توان formula_50 برای انتخاب کنونی formula_35 بهبود داد. به عبارت دیگر داریم: formula_52. حال مقدار کوجک formula_53 را از بازیکنانی که استراتژی formula_35 را دارند، می‌گیریم و آن‌ها را به استراتژی formula_50 تغییر می‌دهیم. حال، برای هر formula_56، بار آن را با اندازهٔ formula_57افزایش داده‌ایم. در نتیجه مقدار آن در formula_58، در این حالت برابر formula_59 می‌باشد. با مشتق گرفتن از از این انتگرال، تغییرات تقریباً برابر با formula_60 با خطای formula_61 خواهد بود. همین تحلیل تغییرات برای زمانی که به یال‌های داخل formula_35 نگاه کنیم صادق خواهد بود.
بنابراین، تغییرات در پتانسیل تقریباً برابر با formula_63 که مقداری منفی است، می‌باشد. این تناقض بوده و نتیجه می‌گیریم formula_58 کمینه نشده‌است. در نتیجه، کمینهٔ formula_58 باید یک تعادل نش باشد.
به دلیل وجود تعادل نش در بازی‌های ادغامی پیوسته، طبعاً موضوع بعدی تجزیه و تحلیل کیفیت این تعادل‌ها می‌باشد. میزان کیفیت تعادل‌ها را به صورت نسبت مجموع تأخیر در تعادل نش و حالت بهینه که به هزینهٔ هرج و مرج معروف است، استخراج می‌کنیم. در ابتدا، با یک شرط بر روی توابع تأخیر کار را آغاز می‌کنیم:
تعریف تأخیر formula_66ملایم است در صورتی که به ازای هر formula_67 داریم: formula_68
حال اگر تأخیر formula_69ملایم بود، formula_70یک تعادل نش می‌باشد و formula_71یک اختصاص بهینه منابع است و سپس داریم: formula_72. به عبارت دیگر، هزینهٔ هرج و مرج برابر با formula_73می‌باشد. برای اثبات این مطلب می‌توانید به این نوشته مراجعه کنید.
بازی پتانسیل