هزینه هرج‌ومرج
پارادکس براوس

یک شبکهٔ خودخواهانه را در نظر بگیرید. به نظر می‌رسد که اضافه کردن یک یال بین دو راس، امکان جابه جایی ترافیک را در مسیرهای مختلف ارتقا دهد. به نحوی منطقی به نظر می‌رسد که با اضافه شدن این یال، سربار جابه جایی ترافیک در شبکه اگر کم نشود، زیاد هم نشود و بنابراین هزینهٔ هرج‌ومرج نیز زیاد نشود. اما این درست نیست. در حقیقت شبکه‌های بسیاری هستند که با اضافه کردن یال‌های به خصوصی در آن‌ها، نه تنها هزینهٔ هرج‌ومرج کاهش نمی‌یابد، بلکه افزایش پیدا می‌کند. این رخ داد به پارادوکس براوس (به انگلیسی: Braess' Paradox) معروف است.
مثلاً شکل مقابل، ۲ مسیر از  Start به  End نشان می‌دهد که زمان طی خیابان  Start تا  A و همچنین خیابان  B تا  End، برابر تعداد رانندگان تقسیم بر ۱۰۰ دقیقه است و زمان طی خیابان  A تا  End و همچنین خیابان  Start تا  B، مستقل از تعداد رانندگانی که این مسیر را انتخاب می‌کنند، برابر ۴۵ دقیقه است. فرض کنیم ۴۰۰۰ راننده می‌خواهند از  Start به  End بروند و در ابتدا، مسیری میان  A و  B وجود ندارد.
اگر یکی از مسیرهای  Start-A-End یا  Start-B-End کوتاه‌تر از مسیر دیگر باشد، به صورت خالص، همهٔ رانندگان مسیر کوتاه‌تر را انتخاب می‌کردند. اما در این مثال این دو مسیر هم‌اندازه و در نتیجه تعادل نش ترکیبی دارد. با فرض اینکه  A راننده از مسیر بالا می‌روند، زمانی که طول می‌کشد به مقصد برسند برابر  {\frac {A}{100}}+45 دقیقه است و با فرض اینکه  B راننده از مسیر پایین می‌روند، زمان رسیدن آن‌ها به مقصد نیز  45+{\frac {B}{100}} است. با توجه به اینکه ۴۰۰۰ راننده وجود دارد و  A+B=4000،  A=B=2000 باشد، یک تعادل برای این بازی است و زمان رسیدن تمام رانندگان، برابر  {\frac {2000}{100}}+45=65 دقیقه خواهد شد. اگر در این بازی،  Cost را مجموع زمانی که رانندگان در مسیر هستند در نظر بگیریم، می‌بینیم که  PoA برابر ۱ است، زیرا تعادل نش همان استراتژی پروفایلی است که در آن تابع هزینه کمترین مقدار می‌شود.
حال به هدف افزایش بازدهی، فرض کنیم خیابان  A-B را ایجاد کنیم که زمان طی آن برابر ۰ دقیقه باشد. در این صورت فرض کنیم در حالت تعادل قبلی که  A=B=2000 بود، راننده‌ای مسیر  Start-A-B-End را انتخاب کند. در این صورت زمان رسیدن او به مقصد برابر  {\frac {2000}{100}}+0+{\frac {2001}{100}}=40.01 دقیقه خواهد شد که نسبت به ۶۵ دقیقه، ۲۵ دقیقه بهتر است. پس با این وجود، به‌زودی تمام ۴۰۰۰ راننده این مسیر را انتخاب می‌کنند و هرچه رانندگان بیشتری این مسیر را انتخاب کنند، زمان بیشتری طول می‌کشد که به مقصد برسند. وقتی تعداد افرادی که از  Start-A-B-End می‌روند به ۲۵۰۰ برسد (۱۵۰۰ نفر هنوز در مسیر  Start-B-End باقی بمانند)، زمانی که طول می‌کشد هر یک از این ۲۵۰۰ نفر به مقصد برسند برابر  {\frac {2500}{100}}+0+{\frac {4000}{100}}=65 دقیقه خواهد بود که در تعادل ابتدایی نیز همین مقدار بود. اما برای ۱۵۰۰ نفر موجود در مسیر  Start-B-End، این زمان به  45+{\frac {4000}{100}}=85 دقیقه می‌رسد که ۲۰ دقیقه بیشتر از این زمان در تعادل اول است. پس به ناچار این ۱۵۰۰ راننده هم باید مسیر خود را به  Start-A-B-End عوض کنند که زودتر برسند. زمانی که تمام راننگان این مسیر را انتخاب کنند، زمان رسیدن هر راننده از  Start به  End برابر  {\frac {4000}{100}}+0+{\frac {4000}{100}}=80 دقیقه خواهد شد و در تعادل خواهد بود (زیرا اگر راننده‌ای مسیر خود را به  Start-B-End تغییر دهد، زمان رسیدنش به مقصد  45+{\frac {4000}{100}}=85 دقیقه خواهد شد که بدتر است، پس مسیر خود را عوض نمی‌کند). در این مثال دیدیم که با اضافه کردن یک خیابان، استراتژی پروفایل تعادل نش عوض شد اما بازدهی مثلاً در حالتی که هیچ راننده‌ای از خیابان  A-B عبور نکند و نصف-نصف از بالا و پایین عبور کنند بیشتر است. پس  PoA مقداری بزرگ‌تر از یک می‌گیرد. در نتیببجه در این مثال، اضافه کردن یک خیابان کوتاه به هدف کم کردن ترافیک و افزایش بازدهی، نتیجهٔ عکس می‌دهد.