موضوع مقاله: بازی ازدحامی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بازی ازدحامی | مقدمه: بازی‌های ازدحامی دسته‌ای در نظریهٔ بازی‌ها هستند که در سال ۱۹۷۳ توسط رزنتال مطرح شدند. | ## بخش 1: بازی ازدحامی | رزنتال ثابت کرد که هر بازی ازدحامی یک بازی پتانسیل نیز می‌باشد و بعدها مندرر و شاپلی (۱۹۹۶) عکس آن را اثبات کردند: به ازای هر بازی پتانسیلی، یک بازی ازدحامی با تابع پتانسیل یکسان موجود است. مقدمه یک شبکهٔ ترافیکی را در نظر بگیرید که دو بازیکن از نقطهٔ O حرکت خود را آغاز می‌کنند و می‌خواهند به نقطهٔ T برسند. فرض کنید نقطهٔ O با مسیرهای ارتباطی A و B به نقطهٔ T متصل است، به صورتی که مسیر A کمی از مسیر B طول کمتری دارد (به عبارت دیگر مسیر A با احتمال بیشتری توسط هر بازیکن انتخاب می‌شود). اما هردو راه ارتباطی به سادگی شلوغ می‌شود؛ به این معنا که هر چه تعداد بازیکن بیشتری از یک مسیر عبور کنند تأخیر هر بازیکن بیشتر می‌شود. نتیجهٔ مطلوب در این بازی درصورتی کسب می‌شود که دو بازیکن همکاری کرده و از مسیرهای متفاوتی عبور کنند. تعریف بازی‌های ازدحامی گسسته دارای اجزای زیرند: یک مجموعه از عناصر ازدحام‌پذیر بازیکن یک مجموعه متناهی از استراتژی‌های برای هر بازیکن بدین صورت که هر استراتژی زیرمجموعه‌ای از می‌باشد. به‌ازای هر عنصر و یک بردار از استراتژی‌های ، باری که این عنصر متحمل می‌شود به صورت می‌باشد. به‌ازای هر عنصر ، یک تابع تأخیر به صورت به‌ازای استراتژی داده شده، بازیکن تأخیری معادل متحمل می‌شود. ماتریس زیر، هزینهٔ بازیکنان را به صورت تأخیری که بسته به انتخابشان متحمل می‌شوند، نشان می‌دهد. | ## بخش 2: بازی ازدحامی | این بدین دلیل است که هر تغییری توسط هر بازیکن باعث افزایش هزینهٔ او می‌شود (توجه کنید که اعداد جدول هزینه را نشان می‌دهند. در نتیجه بازیکنان مقادیر کوچکتر را ترجیح می‌دهند) وجود تعادل نش وجود تعادل نش را می‌توان با ساختن یک تابع پتانسیلی که به هر وضعیت خروجی یک مقدار نسبت می‌دهد اثبات کرد. علاوه بر این، ساختن این تابع نشان می‌دهد یافتن بهترین پاسخ به صورت تکرارشونده به تعادل نش منجر می‌شود. توجه کنید که این تابع همان رفاه اجتماعی نیست؛ بلکه بیشتر یک نوع انتگرال گسسته محسوب می‌شود. ویژگی اصلی تابع پتانسیلی این است که اگر یک بازیکن استراتژی خود را تفییر دهد، تغییر تأخیر او برابر با تغییر در تابع پتانسیل باشد.حالتی را در نظر بگیرید که بازیکن استراتژی خود را از به تغییر می‌دهد. عناصری که در هر دو استراتژی هستند بدون تغییر باقی می‌مانند و عناصری که این بازیکن آن‌ها را رها می‌کند (به عبارت دیگر ) تابع پتانسیل را به مقدار کاهش می‌دهند و همچنین عناصری که این بازیکن به آن‌ها می‌پیوندد (به عبارت دیگر ) تابع پتانسیلی را به اندازهٔ افزایش می‌دهند. بازی‌های ازدحامی پیوسته بازی‌های ازدحامی پیوسته حالت حدی این نوع بازی‌ها به‌طوری‌که هستند. درعوض به‌جای مشخص کردن بازیکن در حالت گسسته، نوع بازیکن داریم به صورتی که هر نوع بازیکن به که نشان‌دهندهٔ نرخ ترافیک برای آن نوع است، مرتبط است. هر نوع بازیکن یک استراتژی از مجموعه که مجزا در نظر گرفته می‌شوند،را انتخاب می‌کند. | ## بخش 3: بازی ازدحامی | همانند قبل، فرض کنید که یکنوا و مثبت می‌باشد اما فرض پیوسته بودن را هم به آن‌ها اضافه می‌کنیم. درنهایت، به بازیکنان از یک نوع اجازه می‌دهیم به‌طور نسبی بین مجموعهٔ استراتژی‌شان توزیع شوند. بدین صورت که به ازای استراتژی مقدار برابر با کسری از بازیکنان نوع که از استراتژی استفاده می‌کنند، می‌باشد. وجود تعادل در حالت پیوسته توجه کنید در این حالت استراتژی‌ها مجموعه استراتژی پروفایل‌های می‌باشند. برای یک مجموعه استراتژی با اندازهٔ ، مجموعهٔ تمام پروفایل‌های معتبر زیرمجموعهٔ فشرده‌ای از می‌باشد. همانند قبل، تابع پتانسیل را به صورت با جایگزینی انتگرال گسسته با نوع استاندارد آن، تعریف می‌کنیم. فرض کنید برخلاف این، یک مجموعه موجود است به صورتی که مقدار را کمینه می‌کند اما تعادل نش نیست. حال مقدار کوجک را از بازیکنانی که استراتژی را دارند، می‌گیریم و آن‌ها را به استراتژی تغییر می‌دهیم. کیفیت راه حل‌ها و هزینهٔ هرج و مرج به دلیل وجود تعادل نش در بازی‌های ادغامی پیوسته، طبعاً موضوع بعدی تجزیه و تحلیل کیفیت این تعادل‌ها می‌باشد. | ## جمع‌بندی | میزان کیفیت تعادل‌ها را به صورت نسبت مجموع تأخیر در تعادل نش و حالت بهینه که به هزینهٔ هرج و مرج معروف است، استخراج می‌کنیم.