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