هزینه هرج‌ومرج

مفهوم هزینهٔ هرج‌ومرج (Price of Anarchy یا PoA)، از مباحث اقتصاد و نظریهٔ بازی است که در آن، میزان کاهش بازدهی سیستم به دلیل خودخواهی بازیکنان بررسی می‌شود. این مفهوم در سیستم‌های گوناگون با تعریف‌های متفاوتی از بازدهی کاربرد دارد. به عنوان مثال سیستم حمل‌ونقل شهری را، که بازدهی می‌تواند رسیدن در زمان کمتر تعریف شود، بررسی کنیم. در این سیستم، یک سری بازیکن می‌خواهند از یک مبدأ به یک مقصد بروند. دو حالت وجود دارد؛ حالت اول اینکه مدیریت مرکزی وجود داشته باشد و بازیکنان با توجه به فرمان مدیریت مرکزی جهت‌های حرکت خود را انتخاب کنند (فرض می‌شود بازیکن‌ها کاملاً به فرمان‌ها گوش می‌دهند) و حالت دوم اینکه مدیریت مرکزی وجود نداشته باشد و بازیکنان به‌صورت خودخواهانه تصمیم‌های خود را بگیرند، یعنی هر بازیکن تنها بازدهی خود را در نظر بگیرد. هزینهٔ هرج‌ومرج نمایشی برای اندازه‌گیری کاهش بازدهی سیستم در حالت دوم نسبت به حالت اول است.

سیستم‌هایی که در آن‌ها به بررسی هزینهٔ هرج‌ومرج پرداخته می‌شود معمولاً به صورت یک بازی مدل می‌شوند. در یک بازی، با توجه به اینکه هر بازیکن چه استراتژی‌ای را انتخاب می‌کند، هر بازیکن میزانی سود (یا ضرر) می‌کند. بازدهی در این مدل، تابعی از سود (یا ضرر) بازیکنان با توجه به استراتژی‌های انتخاب شده‌است. یعنی کارایی آن به صورت تابعی از نتیجهٔ برهم کنش رفتار عامل‌های مختلف آن مدل می‌شود. مثلاً تعریف کارایی در سیستم حمل‌ونقل برابر معکوس ازدحام، در شبکه برابر بیشترین تأخیر (Maximum Delay) و در بازارهای حراجی (Auction) برابر سود اجتماعی تعریف می‌شود.

برای مدل کردن رفتار خودخواهانهٔ بازیکنان، می‌توان از مفاهیم تعادل در بازی‌ها استفاده کرد که یکی از پرکاربردترین تعادل‌ها، تعادل نش است. حال با توجه به اینکه از کدام نوع تعادل نش استفاده شود، نوع‌های مختلف هزینهٔ هرج‌ومرج بدست می‌آید؛ مثلاً اگر از تعادل نش خالص استفاده شود، هزینهٔ هرج‌ومرج خالص بدست می‌آید یا اگر از تعادل نش ترکیبی استفاده شود، هزینهٔ هرج‌ومرج ترکیبی بدست می‌آید و یا برای بازی‌های با اطلاعات ناقص، هزینهٔ هرج‌ومرج بیز-نش بدست می‌آید.

تعریف قیمت هرج‌ومرج ابتدا توسط کوتسوپیاس (Koutsoupias) و پاپادیمیتریو (Papadimitriou) بیان شد، در حالی که اندازه‌گیری ناکارامدی تعادل نش از دیدگاه سود اجتماعی، ایده‌ای قدیمی تر است. مفهوم قیمت هرج‌ومرج به شکل امروزی خود، به گونهٔ معادل با ضریب تقریب (Approx-ratio) در بحث الگوریتم‌های تقریبی، یا به تعبیر دیگر به صورت معادل با نسبت رقابت (Competitive-ratio) در الگوریتم‌های آنلاین تعریف شده‌است.

تعریف ریاضی

هزینهٔ هرج‌ومرج را می‌خواهیم در بازی $G=(N,S,u)$ بررسی کنیم که $N$ مجموعهٔ بازیکنان است، $S=S_1\times S_2\times ...\times S_n$، در واقع $S$ مجموعهٔ استراتژی پروفایل‌ها است ($S_i$، مجموعهٔ استراتژی‌های بازیکن $i$ام است) و $u$ مجموعهٔ $u_i$ها است که هر $u_i$ یک تابع است که $u_i:S\to ℝ$ . در واقع $u_i$ تابعی است که سود نفر $i$ام را در هر استراتژی پروفایل بدست می‌آورد. تابع بازدهی را نیز، به صورت $Welf:S\to ℝ$ تعریف می‌کنیم، که برای هر استراتژی پروفایل، یک عدد به نشان میزان بازدهی ارائه می‌دهد. حال برای $Welf$، می‌توان تابع‌های بهینهٔ اجتماعی در بازی‌ها را در نظر گرفت، به عنوان مثال می‌توان $Welf(s)=\sum _{i\in N}{u}_i(s)$ (مجموع سود تمام بازیکنان در یک استراتژی پروفایل)، یا تابع $Welf(s)=\underset{i\in N}{\min }{u}_i(s)$ (کمترین مقدار سود بازیکنان در یک استراتژی پروفایل) و یا هر تابعی که مقدار مطلوبی را حداکثر می‌کند را در نظر گرفت. اگر در این مدل بازی، عددها به‌جای سود بازیکنان، هزینهٔ بازیکنان تعریف شده‌باشند، در این صورت به‌جای تابع $Welf$، تابع $Cost:S\to ℝ$ را تعریف می‌کنیم که هرچه مقدار کمتری داشته‌باشد، نشاندهندهٔ بازده بیشتری است.

اگر مجموعهٔ $Equil$ را مجموعه‌ای از استراتژی پروفایل‌هایی بگیریم که در آن‌ها تعادل داریم (در واقع $Equil\subseteq S$)، در این صورت هزینهٔ هرج‌ومرج ($PoA$) نسبت بازده در بهترین حالت از میان استراتژی پروفایل‌ها، به بدترین بازده در میان استراتژی‌های تعادل (یا همان بازده بدترین تعادل) است:

الگو:وسط‌چین $PoA=\frac{\underset{s\in S}{\max }Welf(s)}{\underset{s\in Equil}{\min }Welf(s)}$ الگو:پایان وسط‌چین

در صورتی که به‌جای تابع $Welf$، تابع $Cost$ داشته باشیم، در این صورت $PoA$ به صورت زیر تعریف می‌شود:

الگو:وسط‌چین $PoA=\frac{\underset{s\in Equil}{\max }Cost(s)}{\underset{s\in S}{\min }Cost(s)}$‍ الگو:پایان وسط‌چین

یکی دیگر از مفاهیم مرتبط با هزینهٔ هرج‌ومرج، هزینهٔ پایداری (Price of Stability یا $PoS$) است که تعریف آن نسبت بازده در بهترین حالت از میان استراتژی پروفایل‌ها، به بهترین بازده در میان استراتژی‌های تعادل (یا همان بازده بهترین تعادل) است:

الگو:وسط‌چین $PoS=\frac{\underset{s\in S}{\max }Welf(s)}{\underset{s\in Equil}{\max }Welf(s)}$ الگو:پایان وسط‌چین

مفهوم $PoS$ به این دلیل مهم است که بهترین تعادل نش به‌طور طبیعی مفهوم پایداری را در خود دارد و زمانی که بازی در بهترین تعادل نش از لحاظ بازده باشد، احتمال اینکه بازیکنی استراتژی خود را تغییر دهد کم است.

اگر به‌جای $Welf$، تابع $Cost$ تعریف شده باشد، $PoS$ به شکل زیر تعریف می‌شود: الگو:وسط‌چین

$PoS=\frac{\underset{s\in Equil}{\min }Cost(s)}{\underset{s\in S}{\min }Cost(s)}$ الگو:پایان وسط‌چین

با توجه به این تعریف‌ها، بدیهی است که $PoA\ge PoS\ge 1$ و تخمین زده‌می‌شود که از دست دادن بازده به دلیل محدودیت‌های نظریهٔ بازی، مقداری میان $PoS$ و $PoA$ است.

در زیر به بررسی $PoA$ و $PoS$ دریک مثال می‌پردازیم.

معمای زندانی

مثلاً بازی‌ای را در نظر بگیرید که جدول هزینه‌های آن به‌شکل زیر باشد:

	سکوت	اعتراف
سکوت	۱, ۱	۷, ۰
اعتراف	۰, ۷	۵, ۵

در این بازی، دو متهم همکار در یک جرم، زندانی شده‌اند و آن‌ها را به‌طور هم‌زمان و جدا از هم بازجویی می‌کنند. اگر هردو سکوت کنند و اعتراف نکنند، هر یک ۱ سال حبس می‌گیرند. اگر هر دو اعتراف کنند، هر یک ۵ سال حبس می‌گیرند و اگر یکی اعتراف کند و دیگری سکوت کند، متهمی که سکوت کرده ۱۰ سال حبس می‌گیرد و متهم دیگر آزاد می‌شود. این بازی به معمای زندانی معروف است. در این مثال تابع Cost را به شکل $Cost(s_1,s_2)=u_1(s_1,s_2)+u_2(s_1,s_2)$ تعریف می‌کنیم. حال تنها تعادل نش در این بازی، زمانی است که هر دو بازیکن، اعتراف کنند (زیرا اگر هر بازیکن استراتژی خود را عوض کند، سودی کمتر از حالت کنونی‌اش می‌گیرد). این درحالی است که $Cost$ زمانی که هر دو بازیکن همکاری کنند کمترین حالت است. پس:

اگر هردو بازیکن سکوت کنند: $Cos{t}_1=1+1=2$

اگر هردو بازیکن اعتراف کنند: $Cos{t}_2=5+5=10$

پس با توجه به این مقادیر، $PoA=\frac{Cos{t}_2}{Cos{t}_1}=\frac{10}{2}=5$ است و چون این بازی تنها یک تعادل نش دارد، پس $PoS$ نیز مقدارش برابر $PoA$ می‌شود.

شبکه‌های ترافیک خودخواهانه

شکلی از مفهوم هزینهٔ هرج‌ومرج در شبکه‌های ترافیک تعریف می‌شود که در تحلیل‌های شبکه‌ها از جمله شبکهٔ ترافیک حمل‌ونقل کاربرد زیادی دارد. مدل کردن این شبکه‌ها عموماً به شکل شبکه‌های چند جریانه (Multicommodity network) صورت می‌گیرد.

یک شبکهٔ چند جریانه با یک ۳ تای $(G=(V,E),S)$معرفی می‌شود. $G$ از گردایه‌ای از سفرها (Commodity) تشکیل شده‌است. هر سفر یک دوتایی $(t_i,s_i)$از رأس‌های گراف است، که $t_i$مبدا و $s_i$مقصد آن است. به ازای سفر $i$ام، $P_i$مجموعهٔ تمامی مسیرها در $G$است که با $t_i$شروع و با $s_i$بایان می‌یابند، و $P=\bigcup P_i$.

یک جریان (Flow) در شبکه، تشکیل شده از یک بردار $f$ با بعد $|P|$، به گونه‌ای که برای هر سفر مانند $(t_i,s_i)$و به ازای هر مسیر متناظر با این سفر مانند $p\in P_i$, $f_p$درایه‌ای از $f$را که متناظر با میزان جریان در مسیر $p$است نشان می‌دهد. از طرفی هر جریان $f$، میزانی از جریان را روی یال دلخواه $e$از $G$القا می‌کند که آن را با $f_e$نشان می‌دهیم. در این چارچوب، خواهیم داشت: $\sum f_p=\sum f_e$.

شبکه خودخواهانه

یک شبکهٔ خودخواهانه، یک ۳تایی $(G,r,c)$تلقی می‌شود که $G$، گراف در تناظر با شبکهٔ چند جریانهٔ $N$ است. اگر تعداد سفرهای متناظر با $N$ را $k$ بگیریم، آنگاه $r$ یک بردار با بعد $k$ است که درایهٔ $j$ام آن میزان ترافیک مورد نیاز برای سفر از راس $t_i$ به راس $s_i$ در شبکه است. بنابراین جریان $f$ را برای این شبکه مجاز گوییم، اگر به ازای تمام مسیرهای بین $t_i$ تا $s_i$، جمع جریانشان برابر با میزان مورد نیاز $r_i$ شود، یعنی: $\sum _{p\in P_i}{f}_p=r_i$ .

از طرفی، هر یال از $G$ دارای میزانی سربار است. مثلاً سربار می‌تواند میزان تأخیر عبور یک بستهٔ ترافیکی یا یک وسیلهٔ نقلیه از یال مورد نظر باشد. سربار یال $e$ را با $c_e$ نشان می‌دهیم که در تناظر با بردار $c$ است. برای این که قدرت مدل کردن ازدحام در شبکه را داشته باشیم، $c_e$ عموماً به صورت تابعی غیرنزولی از میزان جریان عبوری از یال مورد نظر تعریف می‌شود. برای مسیری از گراف که متناظر با یکی از سفرها باشد، یعنی برای $p\in P$، و نیز برای جریان $f$،$c_p(f)$ برابر میزان سربار در طول این مسیر، یعنی برابر $\sum _{e\in p}{c}_e(f_e)$ تعریف می‌شود.

تعادل واردراپ

شکل معادلی از تعادل نش در مدل کردن شبکه‌های ترافیکی به صورت بازی، توسط جان گلن واردراپ (John Glen Wardrop) تعریف شده‌است، که به تعادل واردراپ (به انگلیسی: Wardrop Equilibrium) شهرت یافته‌است. مشابه با مفهوم کلیدی در تعریف تعادل نش، موسوم به اینکه بازیکنی انگیزه تخطی نداشته‌باشد، جریانی در شبکهٔ خودخواهانهٔ $(G,r,c)$ تعادل واردراپ است، اگر به ازای هر $1\le i\le k$، و به ازای هر دو مسیر $p,\tilde{p}\in P_i$، به گونه‌ای که $f_p>0$، داشته باشیم $c_{p}f\le c_{\tilde{p}}f$. بنابراین، تمامی مسیرهایی از $t_i$ به $s_i$ که جریان مثبت دارند، همگی الزاماً هزینه (سربار) یکسان دارند.

همان‌گونه که بیان شد، تعادل واردراپ، صورت‌بندی دیگری از مفهوم تعادل نش است، به همین دلیل به آن اصطلاح جریان نش (Nash flows) نیز اختصاص داده شده‌است. هری (Haurie) و مارکوت (Marcotte) صورت‌بندی دقیقی از تناظر دو مفهوم تعادل واردراپ و تعادل نش برای بازی‌های متناهی و فرم نرمال ارائه کردند.

شاید بتوان گفت پایه‌ای‌ترین قضیه در این باب، قضیه وجود تعادل واردراپ در شبکهٔ خودخواهانه دلخواه است. بکمن، مک گور و وینستن صورت‌بندی مناسبی از این قضیه ارائه کردند، به این صورت که اولاً به ازای هر شبکه خودخواهانهٔ دلخواه $(G,r,c)$، حداقل یک تعادل واردراپ داریم، ثانیاً اگر $f,\tilde{f}$ دو تعادل واردراپ باشند، آنگاه به ازای هر یال دلخواه $e$خواهیم داشت: الگو:وسط‌چین.$c_e(f_e)=c_e(\widetilde{f_e})$الگو:پایان وسط‌چین

بازی‌های پتانسیلی

راه حل اثبات این حقیقت از ایده‌ای بسیار کلیدی در حل مسایل جستجو در ریاضیات استفاده می‌کند، که به ایدهٔ وریشنال‌ (Variational) معروف است، به این صورت عمل می‌کند که برای بررسی وجود و یافتن جواب ایده‌آل یک مساله در فضای جستجو، تابعی به اعضای آن فضا نسبت می‌دهد، به گونه‌ای که جواب ایده‌آل میزان تابع را کمینه (یا بیشنیه) کند. به این ترتیب، تحلیل جواب ایده‌آل به یک مسالهٔ بهینه‌سازی تقلیل پیدا می‌کند. استفاده از این ایده در نظریهٔ بازی، منجر به تعریف مفهوم مهمی تحت عنوان بازی‌های پتانسیلی شده‌است. در این قشر از بازی‌ها، خروجی‌ها به گونه‌ای تعریف شده‌است که می‌توان تابع پتانسیل $\varphi$ را تعریف کرد، به‌گونه‌ای که مقدار کمینهٔ آن در تعادل نش اتفاق بیفتد. در راه حلی که بکمن، مک گور و وینستن ارائه دادند، تابع پتاسیل به‌صورت مقابل تعریف شد: $\varphi (f)=\sum _{e\in E}\underset{0}{\overset{f_e}{\int }}{c}_e(x)dx$.

نکته‌ای که منجر به مناسب بودن تابع معرفی‌شده، به عنوان یک تابع پتانسیل می‌گردد، این حقیقت است که اگر $f$ یک تعادل واردراپ و $f^{*}$ یک جریان دلخواه در شبکه باشد، رابطهٔ مقابل را داریم: $\sum _{p\in P}{c}_p(f)f_p\le \sum _{p\in P}{c}_p(f)f_p^{*}$ ، که طبق $c_{p}f\le c_{\tilde{p}}f$ به راحتی نتیجه می‌شود. اما با در نظر گرفتن یک دوگانه شماری ساده، روابط زیر را خواهیم داشت:

الگو:وسط‌چین

.$\sum _{p\in P}{c}_p(f)f_p=\sum _{e\in E}{c}_e(f_e)f_e$، $\sum _{p\in P}{c}_p(f)f_p^{*}=\sum _{e\in E}{c}_e(f_e)f_e^{*}$ الگو:پایان وسط‌چین

بنابراین نامساوی $\sum _{e\in E}{c}_e(f_e)f_e\le \sum _{e\in E}{c}_e(f_e)f_e^{*}$را داریم. در ادامه، طبق خاصیت انتگرال، به راحتی خواهیم داشت: $\varphi (f)\le \varphi (f^{*})$. بنابراین همان‌گونه که انتظار داشتیم، تابع پتانسیل معرفی شده مقدار کمینه خود را در تعادل واردراپ اتخاذ می‌کند. اما دقت کنید که فضای همهٔ جریان‌ها یک مجموعه فشرده (Compact) است و می‌دانیم طبق قضیه مقدار بحرانی، طبق پیوستگی، $\varphi$ حتماً میزان کمینهٔ خود را روی همهٔ جریان‌ها اتخاذ می‌کند، که مستقیماً وجود حداقل یک تعادل واردراپ را نتیجه می‌دهد.

بکمن، مک گور و وینستن علاوه بر اثبات وجود تعادل واردراپ، در مقالهٔ خود نشان دادند که اگر $f,\tilde{f}$دو تعادل واردراپ باشند، آن‌گاه به ازای هر یال دلخواه $e$خواهیم داشت:

$c_e(f_e)=c_e(\widetilde{f_e})$].

هزینهٔ هرج‌ومرج در شبکه‌های خودخواهانه

برای جریان $f$، هزینهٔ اجتماعی $C(f)$ به‌طور طبیعی به صورت زیر تعریف می‌شود:

الگو:وسط‌چین .$C(f)=\sum _{p\in P}{c}_p(f)f_p=\sum _{e\in E}{c}_e(f_e)f_e$ الگو:پایان وسط‌چین

تابع $C(f)$، پیوسته از دامنه‌ای فشرده است. پس طبق قضیه مقدار بحرانی مقدار مینیمم خود را اتخاذ خواهد کرد. فرض کنید که این مینیمم در جریان $f^{*}$اتخاذ گردد. $f$را نیز تعادل واردراپ بگیرید. توجه کنید که می‌دانستیم برای تمامی تعادل‌های واردراپ، میزان $C(f)$ یکسان خواهد بود.

هزینهٔ هرج‌ومرج $\rho (G,r,c)$ در این شبکه به صورت مقابل تعریف می‌شود: $\rho (G,r,c)=\frac{C(f)}{C(f^{*})}$. همچنین اگر $\mathrm{I}$ گردایه‌ای از شبکه‌های خودخواهانه باشد، به طریق مشابه هزینهٔ هرج‌ومرج $\rho (\mathrm{I})$به صورت بیشینهٔ هزینهٔ هرج‌ومرج بین اعضای $\mathrm{I}$تعریف می‌شود: $\rho (\mathrm{I})=su{p}_{(G,r,c)\in \mathrm{I}}\rho (G,r,c)$.

یکی از اساسی‌ترین هدف‌ها که تیوریسین‌های نظریهٔ بازی در مقولهٔ شبکه‌های خودخواهانه دنبال می‌کنند، دادن کران‌هایی تئوری برای هزینهٔ هرج‌ومرج، برحسب خانواده‌های متفاوت از توابع سربار روی یال‌ها است. به‌طور کلی، عامل‌ها در شبکه‌های خودخواهانه مسیری را انتخاب می‌کنند که به‌طور خودخواهانه سربار سفرشان را کمینه کند، که در نتیجهٔ آن رفتار جمعیتی آن‌ها در نقطهٔ تعادل واردراپ رخ می‌دهد. نکته اینجاست که تعادل واردراپ در جریانی رخ می‌داد که تابع پتانسیل را کمینه کند، در حالیکه دلخواه مدیر شبکه این است که سود اجتماعی بیشینه شود، یا به عبارتی دیگر هزینهٔ اجتماعی ($C(f)$) کمینه شود، که فاصلهٔ آن‌ها همان هزینهٔ هرج‌ومرج است. بنابراین که هر قدر که تابع پتانسیل شبکه $\varphi$ به تابع هزینهٔ اجتماعی $C$ به اصطلاح "شبیه‌تر" باشد، احتمالاً هزینهٔ هرج‌ومرج کمتری خواهیم داشت. در ادامه تلاش‌هایی را، که برای دادن کران‌های اطمینان در مورد هزینهٔ هرج‌ومرج در این گونه شبکه‌ها شده‌است، بررسی می‌کنیم.

کران پیگو

معمولاً برای تابع سربار یال‌ها، یک خانواده پارامتری $\zeta$ در نظر می‌گیرند، که توابع سربار یال‌ها از آن انتخاب می‌شوند، سپس برای این خانواده پارامتری خاص، کران هزینهٔ هرج‌ومرج معرفی می‌کنند. کران پیگو برای خانواده $\zeta$ به صورت زیر تعریف می‌شود:

الگو:وسط‌چین .$\alpha (\zeta )=su{p}_{c\in \zeta }su{p}_{x,r\ge 0}\frac{r.c(r)}{x.c(x)+(r-x)c(r)}$ الگو:پایان وسط‌چین

با اینکه ممکن است عبارت کران پیگو سخت به نظر برسد، اما این در حالی است که برای خانواده‌های خاص از توابع سربار، پیگو باند مقدار قابل محاسبه‌ای خواهد داشت. مثلاً اگر $\zeta$ خانواده توابع خطی با ضرایب نامنفی باشد، خواهیم داشت: $\alpha (\zeta )=\frac{4}{3}$. این کران حتی زمانی که $\zeta$ خانواده توابع مقعر باشد هم برقرار است.

همچنین اگر $\zeta$ خانوادهٔ چند جمله‌ای‌های با ضرایب نامنفی و درجه حداکثر p باشد، آن‌گاه:

$\alpha (\zeta )=[1-p.(p+1{)}^{-\frac{p+1}{p}}{]}^{-1}$ .

برای اثبات درستی کران پیگو، فرض کنید $c\in \zeta$ یک تابع هزینه باشد. طبق تعریف ضریب پیگو، برای هر $x,r>0$ خواهیم داشت: الگو:وسط‌چین.$x.c(x)\ge \frac{r.c(x)}{\alpha (\zeta )}+(x-r)c(r)$الگو:پایان وسط‌چین اگر قرار دهید $x=f^{*},r=f_e$ خواهیم داشت: الگو:وسط‌چین $C(f^{*})=\sum _{e\in E}{c}_e(f^{*})f^{*}\ge \frac{1}{\alpha (\zeta )}\sum _{e\in E}{c}_e(f_e)f_e+\sum _{e\in E}(f_e^{*}-f_e)c_e(f_e)\ge \frac{C(f)}{\alpha (\zeta )}$الگو:پایان وسط‌چین

که نامساوی آخر در بخش بازی‌های پتانسیلی ثابت شد. بنابراین: $C(f)\le C(f^{*})\alpha (\zeta )$. یعنی هزینهٔ اجتماعی تعادل واردراپ، حداکثر به اندازهٔ ضریب پیگو نسبت به هزینهٔ اجتماعی بهینه، افزایش پیدا کرده‌است: $\rho (G,r,c)\le \alpha (\zeta )$.

پارادکس براوس

یک شبکهٔ خودخواهانه را در نظر بگیرید. به نظر می‌رسد که اضافه کردن یک یال بین دو راس، امکان جابه جایی ترافیک را در مسیرهای مختلف ارتقا دهد. به نحوی منطقی به نظر می‌رسد که با اضافه شدن این یال، سربار جابه جایی ترافیک در شبکه اگر کم نشود، زیاد هم نشود و بنابراین هزینهٔ هرج‌ومرج نیز زیاد نشود. اما این درست نیست. در حقیقت شبکه‌های بسیاری هستند که با اضافه کردن یال‌های به خصوصی در آن‌ها، نه تنها هزینهٔ هرج‌ومرج کاهش نمی‌یابد، بلکه افزایش پیدا می‌کند. این رخ داد به پارادوکس براوس (به انگلیسی: 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$ مقداری بزرگ‌تر از یک می‌گیرد. در نتیببجه در این مثال، اضافه کردن یک خیابان کوتاه به هدف کم کردن ترافیک و افزایش بازدهی، نتیجهٔ عکس می‌دهد.

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

مثال‌هایی از این پارادوکس براوس در شهرهای مختلف دیده‌شده‌است. مثلاً در شهر سئول در کرهٔ جنوبی، با برداشتن یکی از اتوبان‌ها به عنوان بخشی از پروژهٔ بهبودسازی چئونگ چئون، ترافیک در سراسر شهر روان‌تر و بهتر شد. مثال دیگر شهر اشتوگارت واقع در کشور آلمان است که بعد از سرمایه‌گذاری در شبکهٔ راهی شهر در سال ۱۹۶۹، ترافیک بهبود نیافت؛ اما با بسته شدن بعضی خیابان‌های تازه ساخته‌شده، ترافیک بهبود یافت.

حتی این پارادوکس در استراتژی تیم‌های ورزشی دیده می‌شود. مثلاً در بسکتبال، تیم را می‌توان به عنوان یک شبکهٔ راه برای انداختن توپ در سبد دید که هر استراتژی استفاده شده در تیم، یک بازده متناظر خود دارد. همچنین در این مدل بهترین بازیکن به‌عنوان راه میانبر است که به دلیل استفادهٔ بیش از اندازه از او، باعث کاهش بازدهی تیم می‌شود. راه پیشنهاد شده برای حداکثر بازدهی می‌تواند این باشد که بهترین بازیکن نیز حدوداً اندازهٔ بازیکنان دیگر توپ را شوت کند.

روش‌های مهار هزینهٔ هرج‌ومرج

مثال‌های ساده‌ای وجود دارد که در آن‌ها هزینهٔ هرج‌ومرج می‌تواند به شدت زیاد شود. به‌طور کلی پارادوکس براوس به خصوص در شبکه‌های بزرگ می‌تواند خطرناک شود ، و هزینهٔ هرج‌ومرج را به شدت افزایش دهد. بنابراین از دید فنی نمی‌توان برای شبکهٔ دلخواه، کران بالای کلی‌ای در مورد هزینهٔ هرج‌ومرج آن داد. در واقع مثال‌های نقض نسبتاً ساده‌ای در شبکه‌های خودخواهانه با یک سفر می‌توان ساخت، که در آن‌ها هزینهٔ هرج‌ومرج به بی‌نهایت میل کند. راه حل کلی‌ای که برای کران‌دار کردن هزینهٔ هرج‌ومرج وجود دارد، اضافه کردن محدودیت‌های جدید به مساله است. این محدودیت‌ها می‌تواند در دو بعد الگوریتمی، و یا محدود کردن توابع سربار یال‌ها به خانواده‌های مشخص صورت پذیرد. برای نمونه می‌توان شبکه را به گونه‌ای دست کاری کرد، یعنی برخی از یال‌ها را حذف و در صورت امکان، برخی از یال‌ها را اضافه کنیم، به گونه‌ای که هزینهٔ هرج‌ومرج کاهش پیدا کند. امروزه، این راه حل به‌طور ویژه در مورد مدیریت ترافیک شهری مورد استفاده است.

راه حل دیگری که برای کنترل هزینهٔ هرج‌ومرج استفاده می‌شود، این است که بخشی از ترافیک به صورت مرکزی مدیریت شود، سپس عامل‌های خودخواه متعاقباً نسبت به ازدحام موجود در شبکه، مسیر خودخواهانهٔ خود را انتخاب کنند. کاراکوستاس (Karakostas) نشان داد که پیش گرفتن چنین استراتژی‌هایی می‌تواند به طرز چشم‌گیری ضریب هرج‌ومرج را در شبکه کاهش دهد.

قیمت‌گذاری روی یال‌ها، استراتژی دیگری است که در این باب می‌تواند پیش گرفته شود، به نحوی که هزینهٔ یک مسیر، برای هر یک از عوامل تغییر کند، و در نتیجهٔ آن، برخی از آن‌ها مسیر خود را تغییر دهند. اگر قیمت‌گذاری هوشمندانه باشد، این تغییر مسیرها می‌تواند و جهت سود اجتماعی ایجاد شود، که در نتیجهٔ آن هزینهٔ هرج‌ومرج کاهش یابد.

ریچارد کول (Richard Cole)، یوگنی دودیس (Yevgeniy Dodis) و تیم رافگاردن (Tim Roughgarden) در مقاله‌ای کارا بودن روش قیمت‌گذاری را در این راستا نشان دادند.