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

مفهوم هزینهٔ هرج ومرج ( Price of Anarchy یا PoA[ ۱] ) ، از مباحث اقتصاد و نظریهٔ بازی است که در آن، میزان کاهش بازدهی سیستم به دلیل خودخواهی بازیکنان بررسی می شود. این مفهوم در سیستم های گوناگون با تعریف های متفاوتی از بازدهی کاربرد دارد. به عنوان مثال سیستم حمل ونقل شهری را، که بازدهی می تواند رسیدن در زمان کمتر تعریف شود، بررسی کنیم. در این سیستم، یک سری بازیکن می خواهند از یک مبدأ به یک مقصد بروند. دو حالت وجود دارد؛ حالت اول اینکه مدیریت مرکزی وجود داشته باشد و بازیکنان با توجه به فرمان مدیریت مرکزی جهت های حرکت خود را انتخاب کنند ( فرض می شود بازیکن ها کاملاً به فرمان ها گوش می دهند ) و حالت دوم اینکه مدیریت مرکزی وجود نداشته باشد و بازیکنان به صورت خودخواهانه تصمیم های خود را بگیرند، یعنی هر بازیکن تنها بازدهی خود را در نظر بگیرد. هزینهٔ هرج ومرج نمایشی برای اندازه گیری کاهش بازدهی سیستم در حالت دوم نسبت به حالت اول است.
سیستم هایی که در آن ها به بررسی هزینهٔ هرج ومرج پرداخته می شود معمولاً به صورت یک بازی مدل می شوند. در یک بازی، با توجه به اینکه هر بازیکن چه استراتژی ای را انتخاب می کند، هر بازیکن میزانی سود ( یا ضرر ) می کند. بازدهی در این مدل، تابعی از سود ( یا ضرر ) بازیکنان با توجه به استراتژی های انتخاب شده است. یعنی کارایی آن به صورت تابعی از نتیجهٔ برهم کنش رفتار عامل های مختلف آن مدل می شود. مثلاً تعریف کارایی در سیستم حمل ونقل برابر معکوس ازدحام، در شبکه برابر بیشترین تأخیر ( Maximum Delay ) و در بازارهای حراجی ( Auction ) برابر سود اجتماعی تعریف می شود.
برای مدل کردن رفتار خودخواهانهٔ بازیکنان، می توان از مفاهیم تعادل در بازی ها استفاده کرد که یکی از پرکاربردترین تعادل ها، تعادل نش است. حال با توجه به اینکه از کدام نوع تعادل نش استفاده شود، نوع های مختلف هزینهٔ هرج ومرج بدست می آید؛ مثلاً اگر از تعادل نش خالص استفاده شود، هزینهٔ هرج ومرج خالص بدست می آید یا اگر از تعادل نش ترکیبی استفاده شود، هزینهٔ هرج ومرج ترکیبی بدست می آید و یا برای بازی های با اطلاعات ناقص، هزینهٔ هرج ومرج بیز - نش بدست می آید.
تعریف قیمت هرج ومرج ابتدا توسط کوتسوپیاس ( Koutsoupias ) و پاپادیمیتریو ( Papadimitriou ) بیان شد، در حالی که اندازه گیری ناکارامدی تعادل نش از دیدگاه سود اجتماعی، ایده ای قدیمی تر است. مفهوم قیمت هرج ومرج به شکل امروزی خود، به گونهٔ معادل با ضریب تقریب ( Approx - ratio ) در بحث الگوریتم های تقریبی، یا به تعبیر دیگر به صورت معادل با نسبت رقابت ( Competitive - ratio ) در الگوریتم های آنلاین تعریف شده است.