موضوع مقاله: هزینه هرج‌ومرج | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # هزینه هرج‌ومرج | مقدمه: به عنوان مثال سیستم حمل‌ونقل شهری را، که بازدهی می‌تواند رسیدن در زمان کمتر تعریف شود، بررسی کنیم. | ## بخش 1: هزینه هرج‌ومرج | دو حالت وجود دارد؛ حالت اول اینکه مدیریت مرکزی وجود داشته باشد و بازیکنان با توجه به فرمان مدیریت مرکزی جهت‌های حرکت خود را انتخاب کنند (فرض می‌شود بازیکن‌ها کاملاً به فرمان‌ها گوش می‌دهند) و حالت دوم اینکه مدیریت مرکزی وجود نداشته باشد و بازیکنان به‌صورت خودخواهانه تصمیم‌های خود را بگیرند، یعنی هر بازیکن تنها بازدهی خود را در نظر بگیرد. هزینهٔ هرج‌ومرج نمایشی برای اندازه‌گیری کاهش بازدهی سیستم در حالت دوم نسبت به حالت اول است. سیستم‌هایی که در آن‌ها به بررسی هزینهٔ هرج‌ومرج پرداخته می‌شود معمولاً به صورت یک بازی مدل می‌شوند. در یک بازی، با توجه به اینکه هر بازیکن چه استراتژی‌ای را انتخاب می‌کند، هر بازیکن میزانی سود (یا ضرر) می‌کند. بازدهی در این مدل، تابعی از سود (یا ضرر) بازیکنان با توجه به استراتژی‌های انتخاب شده‌است. یعنی کارایی آن به صورت تابعی از نتیجهٔ برهم کنش رفتار عامل‌های مختلف آن مدل می‌شود. برای مدل کردن رفتار خودخواهانهٔ بازیکنان، می‌توان از مفاهیم تعادل در بازی‌ها استفاده کرد که یکی از پرکاربردترین تعادل‌ها، تعادل نش است. حال با توجه به اینکه از کدام نوع تعادل نش استفاده شود، نوع‌های مختلف هزینهٔ هرج‌ومرج بدست می‌آید؛ مثلاً اگر از تعادل نش خالص استفاده شود، هزینهٔ هرج‌ومرج خالص بدست می‌آید یا اگر از تعادل نش ترکیبی استفاده شود، هزینهٔ هرج‌ومرج ترکیبی بدست می‌آید و یا برای بازی‌های با اطلاعات ناقص، هزینهٔ هرج‌ومرج بیز-نش بدست می‌آید. تعریف ریاضی هزینهٔ هرج‌ومرج را می‌خواهیم در بازی بررسی کنیم که مجموعهٔ بازیکنان است، ، در واقع مجموعهٔ استراتژی پروفایل‌ها است (، مجموعهٔ استراتژی‌های بازیکن ام است) و مجموعهٔ ها است که هر یک تابع است که . تابع بازدهی را نیز، به صورت تعریف می‌کنیم، که برای هر استراتژی پروفایل، یک عدد به نشان میزان بازدهی ارائه می‌دهد. حال برای ، می‌توان تابع‌های بهینهٔ اجتماعی در بازی‌ها را در نظر گرفت، به عنوان مثال می‌توان (مجموع سود تمام بازیکنان در یک استراتژی پروفایل)، یا تابع (کمترین مقدار سود بازیکنان در یک استراتژی پروفایل) و یا هر تابعی که مقدار مطلوبی را حداکثر می‌کند را در نظر گرفت. اگر در این مدل بازی، عددها به‌جای سود بازیکنان، هزینهٔ بازیکنان تعریف شده‌باشند، در این صورت به‌جای تابع ، تابع را تعریف می‌کنیم که هرچه مقدار کمتری داشته‌باشد، نشاندهندهٔ بازده بیشتری است. معمای زندانی مثلاً بازی‌ای را در نظر بگیرید که جدول هزینه‌های آن به‌شکل زیر باشد: سکوتاعترافسکوت۱, ۱۷, ۰اعتراف۰, ۷۵, ۵ در این بازی، دو متهم همکار در یک جرم، زندانی شده‌اند و آن‌ها را به‌طور هم‌زمان و جدا از هم بازجویی می‌کنند. اگر هر دو اعتراف کنند، هر یک ۵ سال حبس می‌گیرند و اگر یکی اعتراف کند و دیگری سکوت کند، متهمی که سکوت کرده ۱۰ سال حبس می‌گیرد و متهم دیگر آزاد می‌شود. حال تنها تعادل نش در این بازی، زمانی است که هر دو بازیکن، اعتراف کنند (زیرا اگر هر بازیکن استراتژی خود را عوض کند، سودی کمتر از حالت کنونی‌اش می‌گیرد). پس: اگر هردو بازیکن سکوت کنند: اگر هردو بازیکن اعتراف کنند: پس با توجه به این مقادیر، است و چون این بازی تنها یک تعادل نش دارد، پس نیز مقدارش برابر می‌شود. شبکه‌های ترافیک خودخواهانه شکلی از مفهوم هزینهٔ هرج‌ومرج در شبکه‌های ترافیک تعریف می‌شود که در تحلیل‌های شبکه‌ها از جمله شبکهٔ ترافیک حمل‌ونقل کاربرد زیادی دارد. یک جریان (Flow) در شبکه، تشکیل شده از یک بردار با بعد ، به گونه‌ای که برای هر سفر مانند و به ازای هر مسیر متناظر با این سفر مانند , درایه‌ای از را که متناظر با میزان جریان در مسیر است نشان می‌دهد. از طرفی هر جریان ، میزانی از جریان را روی یال دلخواه از القا می‌کند که آن را با نشان می‌دهیم. شبکه خودخواهانه یک شبکهٔ خودخواهانه، یک ۳تایی تلقی می‌شود که ، گراف در تناظر با شبکهٔ چند جریانهٔ است. اگر تعداد سفرهای متناظر با را بگیریم، آنگاه یک بردار با بعد است که درایهٔ ام آن میزان ترافیک مورد نیاز برای سفر از راس به راس در شبکه است. بنابراین جریان را برای این شبکه مجاز گوییم، اگر به ازای تمام مسیرهای بین تا ، جمع جریانشان برابر با میزان مورد نیاز شود، یعنی: . مثلاً سربار می‌تواند میزان تأخیر عبور یک بستهٔ ترافیکی یا یک وسیلهٔ نقلیه از یال مورد نظر باشد. برای این که قدرت مدل کردن ازدحام در شبکه را داشته باشیم، عموماً به صورت تابعی غیرنزولی از میزان جریان عبوری از یال مورد نظر تعریف می‌شود. برای مسیری از گراف که متناظر با یکی از سفرها باشد، یعنی برای ، و نیز برای جریان ، برابر میزان سربار در طول این مسیر، یعنی برابر تعریف می‌شود. مشابه با مفهوم کلیدی در تعریف تعادل نش، موسوم به اینکه بازیکنی انگیزه تخطی نداشته‌باشد، جریانی در شبکهٔ خودخواهانهٔ تعادل واردراپ است، اگر به ازای هر ، و به ازای هر دو مسیر ، به گونه‌ای که ، داشته باشیم . | ## بخش 2: هزینه هرج‌ومرج | بنابراین، تمامی مسیرهایی از به که جریان مثبت دارند، همگی الزاماً هزینه (سربار) یکسان دارند. همان‌گونه که بیان شد، تعادل واردراپ، صورت‌بندی دیگری از مفهوم تعادل نش است، به همین دلیل به آن اصطلاح جریان نش (Nash flows) نیز اختصاص داده شده‌است. شاید بتوان گفت پایه‌ای‌ترین قضیه در این باب، قضیه وجود تعادل واردراپ در شبکهٔ خودخواهانه دلخواه است. بکمن، مک گور و وینستن صورت‌بندی مناسبی از این قضیه ارائه کردند، به این صورت که اولاً به ازای هر شبکه خودخواهانهٔ دلخواه ، حداقل یک تعادل واردراپ داریم، ثانیاً اگر دو تعادل واردراپ باشند، آنگاه به ازای هر یال دلخواه خواهیم داشت: . بازی‌های پتانسیلی راه حل اثبات این حقیقت از ایده‌ای بسیار کلیدی در حل مسایل جستجو در ریاضیات استفاده می‌کند، که به ایدهٔ وریشنال‌ (Variational) معروف است، به این صورت عمل می‌کند که برای بررسی وجود و یافتن جواب ایده‌آل یک مساله در فضای جستجو، تابعی به اعضای آن فضا نسبت می‌دهد، به گونه‌ای که جواب ایده‌آل میزان تابع را کمینه (یا بیشنیه) کند. استفاده از این ایده در نظریهٔ بازی، منجر به تعریف مفهوم مهمی تحت عنوان بازی‌های پتانسیلی شده‌است. در این قشر از بازی‌ها، خروجی‌ها به گونه‌ای تعریف شده‌است که می‌توان تابع پتانسیل را تعریف کرد، به‌گونه‌ای که مقدار کمینهٔ آن در تعادل نش اتفاق بیفتد. در راه حلی که بکمن، مک گور و وینستن ارائه دادند، تابع پتاسیل به‌صورت مقابل تعریف شد: . نکته‌ای که منجر به مناسب بودن تابع معرفی‌شده، به عنوان یک تابع پتانسیل می‌گردد، این حقیقت است که اگر یک تعادل واردراپ و یک جریان دلخواه در شبکه باشد، رابطهٔ مقابل را داریم: ، که طبق به راحتی نتیجه می‌شود. اما با در نظر گرفتن یک دوگانه شماری ساده، روابط زیر را خواهیم داشت: .، بنابراین نامساوی را داریم. بنابراین همان‌گونه که انتظار داشتیم، تابع پتانسیل معرفی شده مقدار کمینه خود را در تعادل واردراپ اتخاذ می‌کند. اما دقت کنید که فضای همهٔ جریان‌ها یک مجموعه فشرده (Compact) است و می‌دانیم طبق قضیه مقدار بحرانی، طبق پیوستگی، حتماً میزان کمینهٔ خود را روی همهٔ جریان‌ها اتخاذ می‌کند، که مستقیماً وجود حداقل یک تعادل واردراپ را نتیجه می‌دهد. هزینهٔ هرج‌ومرج در شبکه‌های خودخواهانه برای جریان ، هزینهٔ اجتماعی به‌طور طبیعی به صورت زیر تعریف می‌شود: . همچنین اگر گردایه‌ای از شبکه‌های خودخواهانه باشد، به طریق مشابه هزینهٔ هرج‌ومرج به صورت بیشینهٔ هزینهٔ هرج‌ومرج بین اعضای تعریف می‌شود: . یکی از اساسی‌ترین هدف‌ها که تیوریسین‌های نظریهٔ بازی در مقولهٔ شبکه‌های خودخواهانه دنبال می‌کنند، دادن کران‌هایی تئوری برای هزینهٔ هرج‌ومرج، برحسب خانواده‌های متفاوت از توابع سربار روی یال‌ها است. به‌طور کلی، عامل‌ها در شبکه‌های خودخواهانه مسیری را انتخاب می‌کنند که به‌طور خودخواهانه سربار سفرشان را کمینه کند، که در نتیجهٔ آن رفتار جمعیتی آن‌ها در نقطهٔ تعادل واردراپ رخ می‌دهد. نکته اینجاست که تعادل واردراپ در جریانی رخ می‌داد که تابع پتانسیل را کمینه کند، در حالیکه دلخواه مدیر شبکه این است که سود اجتماعی بیشینه شود، یا به عبارتی دیگر هزینهٔ اجتماعی کمینه شود، که فاصلهٔ آن‌ها همان هزینهٔ هرج‌ومرج است. بنابراین که هر قدر که تابع پتانسیل شبکه به تابع هزینهٔ اجتماعی به اصطلاح "شبیه‌تر" باشد، احتمالاً هزینهٔ هرج‌ومرج کمتری خواهیم داشت. در ادامه تلاش‌هایی را، که برای دادن کران‌های اطمینان در مورد هزینهٔ هرج‌ومرج در این گونه شبکه‌ها شده‌است، بررسی می‌کنیم. کران پیگو معمولاً برای تابع سربار یال‌ها، یک خانواده پارامتری در نظر می‌گیرند، که توابع سربار یال‌ها از آن انتخاب می‌شوند، سپس برای این خانواده پارامتری خاص، کران هزینهٔ هرج‌ومرج معرفی می‌کنند. با اینکه ممکن است عبارت کران پیگو سخت به نظر برسد، اما این در حالی است که برای خانواده‌های خاص از توابع سربار، پیگو باند مقدار قابل محاسبه‌ای خواهد داشت. همچنین اگر خانوادهٔ چند جمله‌ای‌های با ضرایب نامنفی و درجه حداکثر p باشد، آن‌گاه: . یعنی هزینهٔ اجتماعی تعادل واردراپ، حداکثر به اندازهٔ ضریب پیگو نسبت به هزینهٔ اجتماعی بهینه، افزایش پیدا کرده‌است: . به نظر می‌رسد که اضافه کردن یک یال بین دو راس، امکان جابه جایی ترافیک را در مسیرهای مختلف ارتقا دهد. به نحوی منطقی به نظر می‌رسد که با اضافه شدن این یال، سربار جابه جایی ترافیک در شبکه اگر کم نشود، زیاد هم نشود و بنابراین هزینهٔ هرج‌ومرج نیز زیاد نشود. در حقیقت شبکه‌های بسیاری هستند که با اضافه کردن یال‌های به خصوصی در آن‌ها، نه تنها هزینهٔ هرج‌ومرج کاهش نمی‌یابد، بلکه افزایش پیدا می‌کند. | ## بخش 3: هزینه هرج‌ومرج | چپ|500x500پیکسل مثلاً شکل مقابل، ۲ مسیر از به نشان می‌دهد که زمان طی خیابان تا و همچنین خیابان تا ، برابر تعداد رانندگان تقسیم بر ۱۰۰ دقیقه است و زمان طی خیابان تا و همچنین خیابان تا ، مستقل از تعداد رانندگانی که این مسیر را انتخاب می‌کنند، برابر ۴۵ دقیقه است. اگر یکی از مسیرهای یا کوتاه‌تر از مسیر دیگر باشد، به صورت خالص، همهٔ رانندگان مسیر کوتاه‌تر را انتخاب می‌کردند. با فرض اینکه راننده از مسیر بالا می‌روند، زمانی که طول می‌کشد به مقصد برسند برابر دقیقه است و با فرض اینکه راننده از مسیر پایین می‌روند، زمان رسیدن آن‌ها به مقصد نیز است. با توجه به اینکه ۴۰۰۰ راننده وجود دارد و ، باشد، یک تعادل برای این بازی است و زمان رسیدن تمام رانندگان، برابر دقیقه خواهد شد. اگر در این بازی، را مجموع زمانی که رانندگان در مسیر هستند در نظر بگیریم، می‌بینیم که برابر ۱ است، زیرا تعادل نش همان استراتژی پروفایلی است که در آن تابع هزینه کمترین مقدار می‌شود. حال به هدف افزایش بازدهی، فرض کنیم خیابان را ایجاد کنیم که زمان طی آن برابر ۰ دقیقه باشد. در این صورت زمان رسیدن او به مقصد برابر دقیقه خواهد شد که نسبت به ۶۵ دقیقه، ۲۵ دقیقه بهتر است. پس با این وجود، به‌زودی تمام ۴۰۰۰ راننده این مسیر را انتخاب می‌کنند و هرچه رانندگان بیشتری این مسیر را انتخاب کنند، زمان بیشتری طول می‌کشد که به مقصد برسند. وقتی تعداد افرادی که از می‌روند به ۲۵۰۰ برسد (۱۵۰۰ نفر هنوز در مسیر باقی بمانند)، زمانی که طول می‌کشد هر یک از این ۲۵۰۰ نفر به مقصد برسند برابر دقیقه خواهد بود که در تعادل ابتدایی نیز همین مقدار بود. اما برای ۱۵۰۰ نفر موجود در مسیر ، این زمان به دقیقه می‌رسد که ۲۰ دقیقه بیشتر از این زمان در تعادل اول است. زمانی که تمام راننگان این مسیر را انتخاب کنند، زمان رسیدن هر راننده از به برابر دقیقه خواهد شد و در تعادل خواهد بود (زیرا اگر راننده‌ای مسیر خود را به تغییر دهد، زمان رسیدنش به مقصد دقیقه خواهد شد که بدتر است، پس مسیر خود را عوض نمی‌کند). در این مثال دیدیم که با اضافه کردن یک خیابان، استراتژی پروفایل تعادل نش عوض شد اما بازدهی مثلاً در حالتی که هیچ راننده‌ای از خیابان عبور نکند و نصف-نصف از بالا و پایین عبور کنند بیشتر است. در نتیببجه در این مثال، اضافه کردن یک خیابان کوتاه به هدف کم کردن ترافیک و افزایش بازدهی، نتیجهٔ عکس می‌دهد. نمونه‌هایی از پارادوکس براوس مثال‌هایی از این پارادوکس براوس در شهرهای مختلف دیده‌شده‌است. مثلاً در شهر سئول در کرهٔ جنوبی، با برداشتن یکی از اتوبان‌ها به عنوان بخشی از پروژهٔ بهبودسازی چئونگ چئون، ترافیک در سراسر شهر روان‌تر و بهتر شد. مثال دیگر شهر اشتوگارت واقع در کشور آلمان است که بعد از سرمایه‌گذاری در شبکهٔ راهی شهر در سال ۱۹۶۹، ترافیک بهبود نیافت؛ اما با بسته شدن بعضی خیابان‌های تازه ساخته‌شده، ترافیک بهبود یافت. مثلاً در بسکتبال، تیم را می‌توان به عنوان یک شبکهٔ راه برای انداختن توپ در سبد دید که هر استراتژی استفاده شده در تیم، یک بازده متناظر خود دارد. همچنین در این مدل بهترین بازیکن به‌عنوان راه میانبر است که به دلیل استفادهٔ بیش از اندازه از او، باعث کاهش بازدهی تیم می‌شود. به‌طور کلی پارادوکس براوس به خصوص در شبکه‌های بزرگ می‌تواند خطرناک شود ، و هزینهٔ هرج‌ومرج را به شدت افزایش دهد. بنابراین از دید فنی نمی‌توان برای شبکهٔ دلخواه، کران بالای کلی‌ای در مورد هزینهٔ هرج‌ومرج آن داد. در واقع مثال‌های نقض نسبتاً ساده‌ای در شبکه‌های خودخواهانه با یک سفر می‌توان ساخت، که در آن‌ها هزینهٔ هرج‌ومرج به بی‌نهایت میل کند. راه حل کلی‌ای که برای کران‌دار کردن هزینهٔ هرج‌ومرج وجود دارد، اضافه کردن محدودیت‌های جدید به مساله است. این محدودیت‌ها می‌تواند در دو بعد الگوریتمی، و یا محدود کردن توابع سربار یال‌ها به خانواده‌های مشخص صورت پذیرد. برای نمونه می‌توان شبکه را به گونه‌ای دست کاری کرد، یعنی برخی از یال‌ها را حذف و در صورت امکان، برخی از یال‌ها را اضافه کنیم، به گونه‌ای که هزینهٔ هرج‌ومرج کاهش پیدا کند. راه حل دیگری که برای کنترل هزینهٔ هرج‌ومرج استفاده می‌شود، این است که بخشی از ترافیک به صورت مرکزی مدیریت شود، سپس عامل‌های خودخواه متعاقباً نسبت به ازدحام موجود در شبکه، مسیر خودخواهانهٔ خود را انتخاب کنند. قیمت‌گذاری روی یال‌ها، استراتژی دیگری است که در این باب می‌تواند پیش گرفته شود، به نحوی که هزینهٔ یک مسیر، برای هر یک از عوامل تغییر کند، و در نتیجهٔ آن، برخی از آن‌ها مسیر خود را تغییر دهند. | ## جمع‌بندی | اگر قیمت‌گذاری هوشمندانه باشد، این تغییر مسیرها می‌تواند و جهت سود اجتماعی ایجاد شود، که در نتیجهٔ آن هزینهٔ هرج‌ومرج کاهش یابد.