FA
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

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

From Wikipedia, the free encyclopedia

هزینه هرج‌ومرج
تعریف ریاضیمعمای زندانیشبکه‌های ترافیک خودخواهانه [3]شبکه خودخواهانهتعادل واردراپبازی‌های پتانسیلیهزینهٔ هرج‌ومرج در شبکه‌های خودخواهانهکران پیگو[6]پارادکس براوسنمونه‌هایی از پارادوکس براوسروش‌های مهار هزینهٔ هرج‌ومرج [11]منابع

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

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

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

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

هزینهٔ هرج‌ومرج را می‌خواهیم در بازی G = ( N , S , u ) {\displaystyle G=(N,S,u)} {\displaystyle G=(N,S,u)} بررسی کنیم که N {\displaystyle N} {\displaystyle N} مجموعهٔ بازیکنان است، S = S 1 × S 2 × . . . × S n {\displaystyle S=S_{1}\times S_{2}\times ...\times S_{n}} {\displaystyle S=S_{1}\times S_{2}\times ...\times S_{n}}، در واقع S {\displaystyle S} {\displaystyle S} مجموعهٔ استراتژی پروفایل‌ها است ( S i {\displaystyle S_{i}} {\displaystyle S_{i}}، مجموعهٔ استراتژی‌های بازیکن i {\displaystyle i} {\displaystyle i}ام است) و u {\displaystyle u} {\displaystyle u} مجموعهٔ u i {\displaystyle u_{i}} {\displaystyle u_{i}}ها است که هر u i {\displaystyle u_{i}} {\displaystyle u_{i}} یک تابع است که u i : S → R {\displaystyle u_{i}:S\rightarrow \mathbb {R} } {\displaystyle u_{i}:S\rightarrow \mathbb {R} } . در واقع u i {\displaystyle u_{i}} {\displaystyle u_{i}} تابعی است که سود نفر i {\displaystyle i} {\displaystyle i}ام را در هر استراتژی پروفایل بدست می‌آورد. تابع بازدهی را نیز، به صورت W e l f : S → R {\displaystyle Welf:S\rightarrow \mathbb {R} } {\displaystyle Welf:S\rightarrow \mathbb {R} } تعریف می‌کنیم، که برای هر استراتژی پروفایل، یک عدد به نشان میزان بازدهی ارائه می‌دهد. حال برای W e l f {\displaystyle Welf} {\displaystyle Welf}، می‌توان تابع‌های بهینهٔ اجتماعی در بازی‌ها را در نظر گرفت، به عنوان مثال می‌توان W e l f ( s ) = ∑ i ∈ N u i ( s ) {\displaystyle Welf(s)=\sum _{i\in N}u_{i}(s)} {\displaystyle Welf(s)=\sum _{i\in N}u_{i}(s)} (مجموع سود تمام بازیکنان در یک استراتژی پروفایل)، یا تابع W e l f ( s ) = min i ∈ N u i ( s ) {\displaystyle Welf(s)=\min _{i\in N}u_{i}(s)} {\displaystyle Welf(s)=\min _{i\in N}u_{i}(s)} (کمترین مقدار سود بازیکنان در یک استراتژی پروفایل) و یا هر تابعی که مقدار مطلوبی را حداکثر می‌کند را در نظر گرفت. اگر در این مدل بازی، عددها به‌جای سود بازیکنان، هزینهٔ بازیکنان تعریف شده‌باشند، در این صورت به‌جای تابع W e l f {\displaystyle Welf} {\displaystyle Welf}، تابع C o s t : S → R {\displaystyle Cost:S\rightarrow \mathbb {R} } {\displaystyle Cost:S\rightarrow \mathbb {R} } را تعریف می‌کنیم که هرچه مقدار کمتری داشته‌باشد، نشاندهندهٔ بازده بیشتری است.

اگر مجموعهٔ E q u i l {\displaystyle Equil} {\displaystyle Equil} را مجموعه‌ای از استراتژی پروفایل‌هایی بگیریم که در آن‌ها تعادل داریم (در واقع E q u i l ⊆ S {\displaystyle Equil\subseteq S} {\displaystyle Equil\subseteq S})، در این صورت هزینهٔ هرج‌ومرج ( P o A {\displaystyle PoA} {\displaystyle PoA}) نسبت بازده در بهترین حالت از میان استراتژی پروفایل‌ها، به بدترین بازده در میان استراتژی‌های تعادل (یا همان بازده بدترین تعادل) است:

P o A = max s ∈ S W e l f ( s ) min s ∈ E q u i l W e l f ( s ) {\displaystyle PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}} {\displaystyle PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}}

در صورتی که به‌جای تابع W e l f {\displaystyle Welf} {\displaystyle Welf}، تابع C o s t {\displaystyle Cost} {\displaystyle Cost} داشته باشیم، در این صورت P o A {\displaystyle PoA} {\displaystyle PoA} به صورت زیر تعریف می‌شود:

P o A = max s ∈ E q u i l C o s t ( s ) min s ∈ S C o s t ( s ) {\displaystyle PoA={\frac {\max _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}} {\displaystyle PoA={\frac {\max _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}}‍

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

P o S = max s ∈ S W e l f ( s ) max s ∈ E q u i l W e l f ( s ) {\displaystyle PoS={\frac {\max _{s\in S}Welf(s)}{\max _{s\in Equil}Welf(s)}}} {\displaystyle PoS={\frac {\max _{s\in S}Welf(s)}{\max _{s\in Equil}Welf(s)}}}

مفهوم P o S {\displaystyle PoS} {\displaystyle PoS} به این دلیل مهم است که بهترین تعادل نش به‌طور طبیعی مفهوم پایداری را در خود دارد و زمانی که بازی در بهترین تعادل نش از لحاظ بازده باشد، احتمال اینکه بازیکنی استراتژی خود را تغییر دهد کم است.[2]

اگر به‌جای W e l f {\displaystyle Welf} {\displaystyle Welf}، تابع C o s t {\displaystyle Cost} {\displaystyle Cost} تعریف شده باشد، P o S {\displaystyle PoS} {\displaystyle PoS} به شکل زیر تعریف می‌شود:

P o S = min s ∈ E q u i l C o s t ( s ) min s ∈ S C o s t ( s ) {\displaystyle PoS={\frac {\min _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}} {\displaystyle PoS={\frac {\min _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}}

با توجه به این تعریف‌ها، بدیهی است که P o A ≥ P o S ≥ 1 {\displaystyle PoA\geq PoS\geq 1} {\displaystyle PoA\geq PoS\geq 1} و تخمین زده‌می‌شود که از دست دادن بازده به دلیل محدودیت‌های نظریهٔ بازی، مقداری میان P o S {\displaystyle PoS} {\displaystyle PoS} و P o A {\displaystyle PoA} {\displaystyle PoA} است.

در زیر به بررسی P o A {\displaystyle PoA} {\displaystyle PoA} و P o S {\displaystyle PoS} {\displaystyle PoS} دریک مثال می‌پردازیم.

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

اطلاعات بیشتر سکوت, اعتراف ...
سکوت اعتراف
سکوت ۱, ۱ ۷, ۰
اعتراف ۰, ۷ ۵, ۵
بستن

در این بازی، دو متهم همکار در یک جرم، زندانی شده‌اند و آن‌ها را به‌طور هم‌زمان و جدا از هم بازجویی می‌کنند. اگر هردو سکوت کنند و اعتراف نکنند، هر یک ۱ سال حبس می‌گیرند. اگر هر دو اعتراف کنند، هر یک ۵ سال حبس می‌گیرند و اگر یکی اعتراف کند و دیگری سکوت کند، متهمی که سکوت کرده ۱۰ سال حبس می‌گیرد و متهم دیگر آزاد می‌شود. این بازی به معمای زندانی معروف است. در این مثال تابع Cost را به شکل C o s t ( s 1 , s 2 ) = u 1 ( s 1 , s 2 ) + u 2 ( s 1 , s 2 ) {\displaystyle Cost(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2})} {\displaystyle Cost(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2})} تعریف می‌کنیم. حال تنها تعادل نش در این بازی، زمانی است که هر دو بازیکن، اعتراف کنند (زیرا اگر هر بازیکن استراتژی خود را عوض کند، سودی کمتر از حالت کنونی‌اش می‌گیرد). این درحالی است که C o s t {\displaystyle Cost} {\displaystyle Cost} زمانی که هر دو بازیکن همکاری کنند کمترین حالت است. پس:

اگر هردو بازیکن سکوت کنند: C o s t 1 = 1 + 1 = 2 {\displaystyle Cost_{1}=1+1=2} {\displaystyle Cost_{1}=1+1=2}

اگر هردو بازیکن اعتراف کنند: C o s t 2 = 5 + 5 = 10 {\displaystyle Cost_{2}=5+5=10} {\displaystyle Cost_{2}=5+5=10}

پس با توجه به این مقادیر، P o A = C o s t 2 C o s t 1 = 10 2 = 5 {\displaystyle PoA={\frac {Cost_{2}}{Cost_{1}}}={\frac {10}{2}}=5} {\displaystyle PoA={\frac {Cost_{2}}{Cost_{1}}}={\frac {10}{2}}=5} است و چون این بازی تنها یک تعادل نش دارد، پس P o S {\displaystyle PoS} {\displaystyle PoS} نیز مقدارش برابر P o A {\displaystyle PoA} {\displaystyle PoA} می‌شود.

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

یک شبکهٔ چند جریانه با یک ۳ تای ( G = ( V , E ) , S ) {\displaystyle (G=(V,E),S)} {\displaystyle (G=(V,E),S)}معرفی می‌شود. G {\displaystyle G} {\displaystyle G} از گردایه‌ای از سفرها (Commodity) تشکیل شده‌است. هر سفر یک دوتایی ( t i , s i ) {\displaystyle (t_{i},s_{i})} {\displaystyle (t_{i},s_{i})}از رأس‌های گراف است، که t i {\displaystyle t_{i}} {\displaystyle t_{i}}مبدا و s i {\displaystyle s_{i}} {\displaystyle s_{i}}مقصد آن است. به ازای سفر i {\displaystyle i} {\displaystyle i}ام، P i {\displaystyle P_{i}} {\displaystyle P_{i}}مجموعهٔ تمامی مسیرها در G {\displaystyle G} {\displaystyle G}است که با t i {\displaystyle t_{i}} {\displaystyle t_{i}}شروع و با s i {\displaystyle s_{i}} {\displaystyle s_{i}}بایان می‌یابند، و P = ⋃ P i {\displaystyle P=\bigcup P_{i}} {\displaystyle P=\bigcup P_{i}}.

یک جریان (Flow) در شبکه، تشکیل شده از یک بردار f {\displaystyle f} {\displaystyle f} با بعد | P | {\displaystyle |P|} {\displaystyle |P|}، به گونه‌ای که برای هر سفر مانند ( t i , s i ) {\displaystyle (t_{i},s_{i})} {\displaystyle (t_{i},s_{i})}و به ازای هر مسیر متناظر با این سفر مانند p ∈ P i {\displaystyle p\in P_{i}} {\displaystyle p\in P_{i}}, f p {\displaystyle f_{p}} {\displaystyle f_{p}}درایه‌ای از f {\displaystyle f} {\displaystyle f}را که متناظر با میزان جریان در مسیر p {\displaystyle p} {\displaystyle p}است نشان می‌دهد. از طرفی هر جریان f {\displaystyle f} {\displaystyle f}، میزانی از جریان را روی یال دلخواه e {\displaystyle e} {\displaystyle e}از G {\displaystyle G} {\displaystyle G}القا می‌کند که آن را با f e {\displaystyle f_{e}} {\displaystyle f_{e}}نشان می‌دهیم. در این چارچوب، خواهیم داشت: ∑ f p = ∑ f e {\displaystyle \sum f_{p}=\sum f_{e}} {\displaystyle \sum f_{p}=\sum f_{e}}.

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

یک شبکهٔ خودخواهانه، یک ۳تایی ( G , r , c ) {\displaystyle (G,r,c)} {\displaystyle (G,r,c)}تلقی می‌شود که G {\displaystyle G} {\displaystyle G}، گراف در تناظر با شبکهٔ چند جریانهٔ N {\displaystyle N} {\displaystyle N} است. اگر تعداد سفرهای متناظر با N {\displaystyle N} {\displaystyle N} را k {\displaystyle k} {\displaystyle k} بگیریم، آنگاه r {\displaystyle r} {\displaystyle r} یک بردار با بعد k {\displaystyle k} {\displaystyle k} است که درایهٔ j {\displaystyle j} {\displaystyle j}ام آن میزان ترافیک مورد نیاز برای سفر از راس t i {\displaystyle t_{i}} {\displaystyle t_{i}} به راس s i {\displaystyle s_{i}} {\displaystyle s_{i}} در شبکه است. بنابراین جریان f {\displaystyle f} {\displaystyle f} را برای این شبکه مجاز گوییم، اگر به ازای تمام مسیرهای بین t i {\displaystyle t_{i}} {\displaystyle t_{i}} تا s i {\displaystyle s_{i}} {\displaystyle s_{i}}، جمع جریانشان برابر با میزان مورد نیاز r i {\displaystyle r_{i}} {\displaystyle r_{i}} شود، یعنی: ∑ p ∈ P i f p = r i {\displaystyle \sum _{p\in P_{i}}f_{p}=r_{i}} {\displaystyle \sum _{p\in P_{i}}f_{p}=r_{i}} .

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

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

شکل معادلی از تعادل نش در مدل کردن شبکه‌های ترافیکی به صورت بازی، توسط جان گلن واردراپ (John Glen Wardrop) تعریف شده‌است، که به تعادل واردراپ (به انگلیسی: Wardrop Equilibrium[4]) شهرت یافته‌است. مشابه با مفهوم کلیدی در تعریف تعادل نش، موسوم به اینکه بازیکنی انگیزه تخطی نداشته‌باشد، جریانی در شبکهٔ خودخواهانهٔ ( G , r , c ) {\displaystyle (G,r,c)} {\displaystyle (G,r,c)} تعادل واردراپ است، اگر به ازای هر 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} {\displaystyle 1\leq i\leq k}، و به ازای هر دو مسیر p , p ~ ∈ P i {\displaystyle p,{\tilde {p}}\in P_{i}} {\displaystyle p,{\tilde {p}}\in P_{i}}، به گونه‌ای که f p > 0 {\displaystyle f_{p}>0} {\displaystyle f_{p}>0}، داشته باشیم c p f ≤ c p ~ f {\displaystyle c_{p}f\leq c_{\tilde {p}}f} {\displaystyle c_{p}f\leq c_{\tilde {p}}f}. بنابراین، تمامی مسیرهایی از t i {\displaystyle t_{i}} {\displaystyle t_{i}} به s i {\displaystyle s_{i}} {\displaystyle s_{i}} که جریان مثبت دارند، همگی الزاماً هزینه (سربار) یکسان دارند.

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

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

. c e ( f e ) = c e ( f e ~ ) {\displaystyle c_{e}(f_{e})=c_{e}({\tilde {f_{e}}})} {\displaystyle c_{e}(f_{e})=c_{e}({\tilde {f_{e}}})}

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

راه حل اثبات این حقیقت از ایده‌ای بسیار کلیدی در حل مسایل جستجو در ریاضیات استفاده می‌کند، که به ایدهٔ وریشنال‌ (Variational) معروف است، به این صورت عمل می‌کند که برای بررسی وجود و یافتن جواب ایده‌آل یک مساله در فضای جستجو، تابعی به اعضای آن فضا نسبت می‌دهد، به گونه‌ای که جواب ایده‌آل میزان تابع را کمینه (یا بیشنیه) کند. به این ترتیب، تحلیل جواب ایده‌آل به یک مسالهٔ بهینه‌سازی تقلیل پیدا می‌کند. استفاده از این ایده در نظریهٔ بازی، منجر به تعریف مفهوم مهمی تحت عنوان بازی‌های پتانسیلی شده‌است. در این قشر از بازی‌ها، خروجی‌ها به گونه‌ای تعریف شده‌است که می‌توان تابع پتانسیل ϕ {\displaystyle \phi } {\displaystyle \phi } را تعریف کرد، به‌گونه‌ای که مقدار کمینهٔ آن در تعادل نش اتفاق بیفتد. در راه حلی که بکمن، مک گور و وینستن ارائه دادند، تابع پتاسیل به‌صورت مقابل تعریف شد: ϕ ( f ) = ∑ e ∈ E ∫ 0 f e c e ( x ) d x {\displaystyle \phi (f)=\sum _{e\in E}\int _{0}^{f_{e}}c_{e}(x)dx} {\displaystyle \phi (f)=\sum _{e\in E}\int _{0}^{f_{e}}c_{e}(x)dx}.

نکته‌ای که منجر به مناسب بودن تابع معرفی‌شده، به عنوان یک تابع پتانسیل می‌گردد، این حقیقت است که اگر f {\displaystyle f} {\displaystyle f} یک تعادل واردراپ و f ∗ {\displaystyle f^{*}} {\displaystyle f^{*}} یک جریان دلخواه در شبکه باشد، رابطهٔ مقابل را داریم: ∑ p ∈ P c p ( f ) f p ≤ ∑ p ∈ P c p ( f ) f p ∗ {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}\leq \sum _{p\in P}c_{p}(f)f_{p}^{*}} {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}\leq \sum _{p\in P}c_{p}(f)f_{p}^{*}} ، که طبق c p f ≤ c p ~ f {\displaystyle c_{p}f\leq c_{\tilde {p}}f} {\displaystyle c_{p}f\leq c_{\tilde {p}}f} به راحتی نتیجه می‌شود. اما با در نظر گرفتن یک دوگانه شماری ساده، روابط زیر را خواهیم داشت:

. ∑ p ∈ P c p ( f ) f p = ∑ e ∈ E c e ( f e ) f e {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}=\sum _{e\in E}c_{e}(f_{e})f_{e}} {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}=\sum _{e\in E}c_{e}(f_{e})f_{e}}، ∑ p ∈ P c p ( f ) f p ∗ = ∑ e ∈ E c e ( f e ) f e ∗ {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}^{*}=\sum _{e\in E}c_{e}(f_{e})f_{e}^{*}} {\displaystyle \sum _{p\in P}c_{p}(f)f_{p}^{*}=\sum _{e\in E}c_{e}(f_{e})f_{e}^{*}}

بنابراین نامساوی ∑ e ∈ E c e ( f e ) f e ≤ ∑ e ∈ E c e ( f e ) f e ∗ {\displaystyle \sum _{e\in E}c_{e}(f_{e})f_{e}\leq \sum _{e\in E}c_{e}(f_{e})f_{e}^{*}} {\displaystyle \sum _{e\in E}c_{e}(f_{e})f_{e}\leq \sum _{e\in E}c_{e}(f_{e})f_{e}^{*}}را داریم. در ادامه، طبق خاصیت انتگرال، به راحتی خواهیم داشت: ϕ ( f ) ≤ ϕ ( f ∗ ) {\displaystyle \phi (f)\leq \phi (f^{*})} {\displaystyle \phi (f)\leq \phi (f^{*})}. بنابراین همان‌گونه که انتظار داشتیم، تابع پتانسیل معرفی شده مقدار کمینه خود را در تعادل واردراپ اتخاذ می‌کند. اما دقت کنید که فضای همهٔ جریان‌ها یک مجموعه فشرده (Compact) است و می‌دانیم طبق قضیه مقدار بحرانی، طبق پیوستگی، ϕ {\displaystyle \phi } {\displaystyle \phi } حتماً میزان کمینهٔ خود را روی همهٔ جریان‌ها اتخاذ می‌کند، که مستقیماً وجود حداقل یک تعادل واردراپ را نتیجه می‌دهد.

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

c e ( f e ) = c e ( f e ~ ) {\displaystyle c_{e}(f_{e})=c_{e}({\tilde {f_{e}}})} {\displaystyle c_{e}(f_{e})=c_{e}({\tilde {f_{e}}})}[5]].

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

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

. C ( f ) = ∑ p ∈ P c p ( f ) f p = ∑ e ∈ E c e ( f e ) f e {\displaystyle C(f)=\sum _{p\in P}c_{p}(f)f_{p}=\sum _{e\in E}c_{e}(f_{e})f_{e}} {\displaystyle C(f)=\sum _{p\in P}c_{p}(f)f_{p}=\sum _{e\in E}c_{e}(f_{e})f_{e}}

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

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

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

کران پیگو[6]

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

. α ( ζ ) = s u p c ∈ ζ s u p x , r ≥ 0 r . c ( r ) x . c ( x ) + ( r − x ) c ( r ) {\displaystyle \alpha (\zeta )=sup_{c\in \zeta }sup_{x,r\geq 0}{\frac {r.c(r)}{x.c(x)+(r-x)c(r)}}} {\displaystyle \alpha (\zeta )=sup_{c\in \zeta }sup_{x,r\geq 0}{\frac {r.c(r)}{x.c(x)+(r-x)c(r)}}}

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

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

α ( ζ ) = [ 1 − p . ( p + 1 ) − p + 1 p ] − 1 {\displaystyle \alpha (\zeta )=[1-p.(p+1)^{-{\frac {p+1}{p}}}]^{-1}} {\displaystyle \alpha (\zeta )=[1-p.(p+1)^{-{\frac {p+1}{p}}}]^{-1}} [8].

برای اثبات درستی کران پیگو، فرض کنید c ∈ ζ {\displaystyle c\in \zeta } {\displaystyle c\in \zeta } یک تابع هزینه باشد. طبق تعریف ضریب پیگو، برای هر x , r > 0 {\displaystyle x,r>0} {\displaystyle x,r>0} خواهیم داشت:

. x . c ( x ) ≥ r . c ( x ) α ( ζ ) + ( x − r ) c ( r ) {\displaystyle x.c(x)\geq {\frac {r.c(x)}{\alpha (\zeta )}}+(x-r)c(r)} {\displaystyle x.c(x)\geq {\frac {r.c(x)}{\alpha (\zeta )}}+(x-r)c(r)}

اگر قرار دهید x = f ∗ , r = f e {\displaystyle x=f^{*},r=f_{e}} {\displaystyle x=f^{*},r=f_{e}} خواهیم داشت:

C ( f ∗ ) = ∑ e ∈ E c e ( f ∗ ) f ∗ ≥ 1 α ( ζ ) ∑ e ∈ E c e ( f e ) f e + ∑ e ∈ E ( f e ∗ − f e ) c e ( f e ) ≥ C ( f ) α ( ζ ) {\displaystyle C(f^{*})=\sum _{e\in E}c_{e}(f^{*})f^{*}\geq {\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})\geq {\frac {C(f)}{\alpha (\zeta )}}} {\displaystyle C(f^{*})=\sum _{e\in E}c_{e}(f^{*})f^{*}\geq {\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})\geq {\frac {C(f)}{\alpha (\zeta )}}}

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

یک شبکهٔ خودخواهانه را در نظر بگیرید. به نظر می‌رسد که اضافه کردن یک یال بین دو راس، امکان جابه جایی ترافیک را در مسیرهای مختلف ارتقا دهد. به نحوی منطقی به نظر می‌رسد که با اضافه شدن این یال، سربار جابه جایی ترافیک در شبکه اگر کم نشود، زیاد هم نشود و بنابراین هزینهٔ هرج‌ومرج نیز زیاد نشود. اما این درست نیست. در حقیقت شبکه‌های بسیاری هستند که با اضافه کردن یال‌های به خصوصی در آن‌ها، نه تنها هزینهٔ هرج‌ومرج کاهش نمی‌یابد، بلکه افزایش پیدا می‌کند. این رخ داد به پارادوکس براوس (به انگلیسی: Braess' Paradox) معروف است.

Thumb

مثلاً شکل مقابل، ۲ مسیر از S t a r t {\displaystyle Start} {\displaystyle Start} به E n d {\displaystyle End} {\displaystyle End} نشان می‌دهد که زمان طی خیابان S t a r t {\displaystyle Start} {\displaystyle Start} تا A {\displaystyle A} {\displaystyle A} و همچنین خیابان B {\displaystyle B} {\displaystyle B} تا E n d {\displaystyle End} {\displaystyle End}، برابر تعداد رانندگان تقسیم بر ۱۰۰ دقیقه است و زمان طی خیابان A {\displaystyle A} {\displaystyle A} تا E n d {\displaystyle End} {\displaystyle End} و همچنین خیابان S t a r t {\displaystyle Start} {\displaystyle Start} تا B {\displaystyle B} {\displaystyle B}، مستقل از تعداد رانندگانی که این مسیر را انتخاب می‌کنند، برابر ۴۵ دقیقه است. فرض کنیم ۴۰۰۰ راننده می‌خواهند از S t a r t {\displaystyle Start} {\displaystyle Start} به E n d {\displaystyle End} {\displaystyle End} بروند و در ابتدا، مسیری میان A {\displaystyle A} {\displaystyle A} و B {\displaystyle B} {\displaystyle B} وجود ندارد.

اگر یکی از مسیرهای S t a r t − A − E n d {\displaystyle Start-A-End} {\displaystyle Start-A-End} یا S t a r t − B − E n d {\displaystyle Start-B-End} {\displaystyle Start-B-End} کوتاه‌تر از مسیر دیگر باشد، به صورت خالص، همهٔ رانندگان مسیر کوتاه‌تر را انتخاب می‌کردند. اما در این مثال این دو مسیر هم‌اندازه و در نتیجه تعادل نش ترکیبی دارد. با فرض اینکه A {\displaystyle A} {\displaystyle A} راننده از مسیر بالا می‌روند، زمانی که طول می‌کشد به مقصد برسند برابر A 100 + 45 {\displaystyle {\frac {A}{100}}+45} {\displaystyle {\frac {A}{100}}+45} دقیقه است و با فرض اینکه B {\displaystyle B} {\displaystyle B} راننده از مسیر پایین می‌روند، زمان رسیدن آن‌ها به مقصد نیز 45 + B 100 {\displaystyle 45+{\frac {B}{100}}} {\displaystyle 45+{\frac {B}{100}}} است. با توجه به اینکه ۴۰۰۰ راننده وجود دارد و A + B = 4000 {\displaystyle A+B=4000} {\displaystyle A+B=4000}، A = B = 2000 {\displaystyle A=B=2000} {\displaystyle A=B=2000} باشد، یک تعادل برای این بازی است و زمان رسیدن تمام رانندگان، برابر 2000 100 + 45 = 65 {\displaystyle {\frac {2000}{100}}+45=65} {\displaystyle {\frac {2000}{100}}+45=65} دقیقه خواهد شد. اگر در این بازی، C o s t {\displaystyle Cost} {\displaystyle Cost} را مجموع زمانی که رانندگان در مسیر هستند در نظر بگیریم، می‌بینیم که P o A {\displaystyle PoA} {\displaystyle PoA} برابر ۱ است، زیرا تعادل نش همان استراتژی پروفایلی است که در آن تابع هزینه کمترین مقدار می‌شود.

حال به هدف افزایش بازدهی، فرض کنیم خیابان A − B {\displaystyle A-B} {\displaystyle A-B} را ایجاد کنیم که زمان طی آن برابر ۰ دقیقه باشد. در این صورت فرض کنیم در حالت تعادل قبلی که A = B = 2000 {\displaystyle A=B=2000} {\displaystyle A=B=2000} بود، راننده‌ای مسیر S t a r t − A − B − E n d {\displaystyle Start-A-B-End} {\displaystyle Start-A-B-End} را انتخاب کند. در این صورت زمان رسیدن او به مقصد برابر 2000 100 + 0 + 2001 100 = 40.01 {\displaystyle {\frac {2000}{100}}+0+{\frac {2001}{100}}=40.01} {\displaystyle {\frac {2000}{100}}+0+{\frac {2001}{100}}=40.01} دقیقه خواهد شد که نسبت به ۶۵ دقیقه، ۲۵ دقیقه بهتر است. پس با این وجود، به‌زودی تمام ۴۰۰۰ راننده این مسیر را انتخاب می‌کنند و هرچه رانندگان بیشتری این مسیر را انتخاب کنند، زمان بیشتری طول می‌کشد که به مقصد برسند. وقتی تعداد افرادی که از S t a r t − A − B − E n d {\displaystyle Start-A-B-End} {\displaystyle Start-A-B-End} می‌روند به ۲۵۰۰ برسد (۱۵۰۰ نفر هنوز در مسیر S t a r t − B − E n d {\displaystyle Start-B-End} {\displaystyle Start-B-End} باقی بمانند)، زمانی که طول می‌کشد هر یک از این ۲۵۰۰ نفر به مقصد برسند برابر 2500 100 + 0 + 4000 100 = 65 {\displaystyle {\frac {2500}{100}}+0+{\frac {4000}{100}}=65} {\displaystyle {\frac {2500}{100}}+0+{\frac {4000}{100}}=65} دقیقه خواهد بود که در تعادل ابتدایی نیز همین مقدار بود. اما برای ۱۵۰۰ نفر موجود در مسیر S t a r t − B − E n d {\displaystyle Start-B-End} {\displaystyle Start-B-End}، این زمان به 45 + 4000 100 = 85 {\displaystyle 45+{\frac {4000}{100}}=85} {\displaystyle 45+{\frac {4000}{100}}=85} دقیقه می‌رسد که ۲۰ دقیقه بیشتر از این زمان در تعادل اول است. پس به ناچار این ۱۵۰۰ راننده هم باید مسیر خود را به S t a r t − A − B − E n d {\displaystyle Start-A-B-End} {\displaystyle Start-A-B-End} عوض کنند که زودتر برسند. زمانی که تمام راننگان این مسیر را انتخاب کنند، زمان رسیدن هر راننده از S t a r t {\displaystyle Start} {\displaystyle Start} به E n d {\displaystyle End} {\displaystyle End} برابر 4000 100 + 0 + 4000 100 = 80 {\displaystyle {\frac {4000}{100}}+0+{\frac {4000}{100}}=80} {\displaystyle {\frac {4000}{100}}+0+{\frac {4000}{100}}=80} دقیقه خواهد شد و در تعادل خواهد بود (زیرا اگر راننده‌ای مسیر خود را به S t a r t − B − E n d {\displaystyle Start-B-End} {\displaystyle Start-B-End} تغییر دهد، زمان رسیدنش به مقصد 45 + 4000 100 = 85 {\displaystyle 45+{\frac {4000}{100}}=85} {\displaystyle 45+{\frac {4000}{100}}=85} دقیقه خواهد شد که بدتر است، پس مسیر خود را عوض نمی‌کند). در این مثال دیدیم که با اضافه کردن یک خیابان، استراتژی پروفایل تعادل نش عوض شد اما بازدهی مثلاً در حالتی که هیچ راننده‌ای از خیابان A − B {\displaystyle A-B} {\displaystyle A-B} عبور نکند و نصف-نصف از بالا و پایین عبور کنند بیشتر است. پس P o A {\displaystyle PoA} {\displaystyle PoA} مقداری بزرگ‌تر از یک می‌گیرد. در نتیببجه در این مثال، اضافه کردن یک خیابان کوتاه به هدف کم کردن ترافیک و افزایش بازدهی، نتیجهٔ عکس می‌دهد.

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

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

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

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

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

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

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

  1. [1]
    Koutsoupias, Elias; Papadimitriou, Christos (May 2009). ""Worst-case Equilibria". Computer Science Review. 3 (2): 65–69. Archived from the original on 13 March 2016. Retrieved 26 January 2018.
  2. [2]
    The Price of Stability for Network Design withFair Cost Allocation, Elliot Anshelevich
  3. [3]
    «Stanford Theory group survey on Price of Anarchy» (PDF).
  4. [4]
    «Wardrop Equilibrium» (PDF).
  5. [5]
    Studies in the Economics of Transportation بایگانی‌شده در ۱۸ دسامبر ۲۰۱۵ توسط Wayback Machine.
  6. [6]
    «Pigou effect».
  7. [7]
    «Selfish routing in capacitated networks».
  8. [8]
    «The price of anarchy is independent of the network topology» (PDF).
  9. [9]
    Knödel, W. (31 January 1969). Graphentheoretische Methoden Und Ihre Anwendungen. Springer-Verlag. pp. 57–59. ISBN 978-3-540-04668-4.
  10. [10]
    The price of Anarchy in Basketball, Brian Skinner
  11. [11]
    «Lecture on bounding the Price of Anarchy» (PDF).
  12. [12]
    «Selfish Routing and The Price of Anarchy».
  13. [13]
    Gourge Karakostas, Stavros G. Kolliopoulos. «Stackelburg strategies for selfish routing in general multicommodity networks».
  14. [14]
    Richard Cole, Yevgeny Dodis, Tim Roghgarden. «Pricing Networks with Selfish Routing» (PDF).نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)
Edit in WikipediaRevision historyRead in Wikipedia

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox

تعریف ریاضی

معمای زندانی

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

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

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

منابع