هزینه پایداری
در نظریه بازی‌ها، هزینه پایداری (به انگلیسی: price of stability یا PoS) یک بازی به نسبت ""بهترین هزینه اجتماعی تعادل‌های نش بازی"" به ""هزینهٔ اجتماعی حالت بهینه اجتماعی"" گفته می‌شود. هدف از تعریف این نسبت پی بردن به این موضوع است که در یک بازی دخالت یک قدرت سوم برای خارج کردن رفتار بازیکنان از "خودخواه محض" بودن، به چه اندازه سودمند است. در کتاب دنیای جدید شجاع اثر آلدوس هاکسلی (Aldous Huxley) نیز اشاره‌ای به این مفهوم شده‌است. همچنین هنگامی که ما می‌خواهیم خوب و مؤثر بودن یک تعادل نش را در یک بازی خاص اندازه بگیریم، غالباً دربارهٔ هزینه آشوب (PoA) حرف می‌زنیم.
در یک بازی مفروض G با مجموعهٔ بازیکنان P و مجموعهٔ استراتژی‌های S، اگر {E:S^|P| -> {0,1 یک تابع تعادل بوده و f یک تابع هدف باشد که معمولاً سودمحور (به صورت جمع سودهای بازیکنان) یا بیشینه‌محور (به صورت بیشترین مقدار سود یک بازیکن) تعریف می‌شود، آنگاه اگر S1 تا Sn مجموعهٔ همهٔ استراتژی پروفایل‌های تعادل باشند، منظور از هزینهٔ پایداری نسبت ((f(S_i))/(f(S) است که در آن S_i تعادلی است که مقدار f را در میان سایر S_jها بیشینه می‌کند و S استراتژی پروفایلی است که مقدار f را بین همهٔ استراتژی پروفایل‌ها بیشینه می‌کند.
در کنار هزینهٔ پایداری، معیار دیگری نیز با عنوان هزینهٔ آشوب تعریف می‌شود که به معنی نسبت بدترین تعادل به حالت بهینهٔ تابع است.
به عبارتی هزینهٔ پایداری و هزینهٔ آشوب به همراه هم نشان می‌دهند اگر یک قدرت خارج از بازیکنان، آن‌ها را با قرار دادن سیاست‌هایی مجبور به انجام یکی دیگر از تعادلها کند، مقدار سود چقدر خواهد بود و اگر این کار را نکنند مقدار ضرر چقدر خواهد شد و در نهایت مشخص می‌شود که آیا این کار به صرفه هست یا نه. به‌طور خاص، هزینهٔ پایداری وقتی کاربردی است که بازیکنان برای دستیابی به یک حالت بهینه حاضر به همکاری هستند و مثالی خوب از هزینهٔ آشوب در اینترنت است که هر شرکت بدون در نظر گرفتن نفع جهانی در پی بیشینه کردن سود خود است.
همانگونه که گفته‌شد هزینه پایداری برابر است با "بیشترین مقدار هزینهٔ اجتماعی تعادل‌های نش بازی" تقسیم بر "هزینهٔ اجتماعی در حالت بهینهٔ اجتماعی".
برای مثال در بازی معمای زندانی‌های زیر، تنها یک تعادل نش وجود دارد که عبارت است از (عدم‌همکاری، عدم‌همکاری) بنابراین داریم: هزینه پایداری = هزینه بی‌نظمی = ۱/۲.
اما در مثال زیر که در واقع نسخه‌ای از بازی نبرد دو جنس است، دو تعادل وجود دارد: (A,A) و (R,R) با هزینهٔ اجتماعی ۳ و ۱۵. بنابراین در این بازی مقدار سود اجماعی حالت بهینهٔ اجتماعی ۱۵. بنابراین مقدار هزینه پایداری ۱ خواهد بود و هزینه بی‌نظمی ۱/۱۵.
هزینه پایداری نخستین بار توسط آ. شولتزان و م. موزز مورد مطالعه‌ای قرار گرفت که به مطالعات اِ. آنشلویچ مشهور است. آنها نشان دادند که همواره یک تعادل نش خالص در یک بازی وجود دارد و هزینه پایداری یک بازی حداکثر برابر n-اُمین عدد هارمونیک در یک گراف جهتدار است. برای یک گراف بدون جهت آنشلویچ و دیگران نشان دادند یک کران بالای ۴/۳ برای هزینه پایداری در یک گراف با یک منبع و با دو بازیکن وجود دارد. ژیان لی ثابت‌کرده‌است که برای یک گراف بدون‌جهت با یک مقصد مشخص که همهٔ بازیکنان باید به آن متصل شوند، هزینه پایداری این شبکهٔ بازی formula_1 است که n تعداد بازیکنان است. از طرفی دیگر هزینه بی‌نظمی نیز در این بازی حدود n است.
همچنین در تحقیقی دیگر که توسط آنشلویچ و جمعی دیگر از اعضای دپارتمان علوم کامپیوتر دانشگاه کرنل صورت پذیرفته‌است، نشان داده می‌شود که در یک طراحی شبکه‌ای با تخصیص هزینه عادلانه مقدار هزینه پایداری formula_2 می‌باشد.
میزان غیربهینگی تعادل‌ها در بازیها در حالت کلی قابل تخمین زدن نیست، این امر در بازی‌های ساده‌ای نظیر معمای زندانی‌ها هم قابل رویت است که تعادل در آن می‌تواند تا حد دلخواه غیر بهینه اجتماعی باشد. به همین منظور این فکر ایجاد شد تا به دنبال دسته‌هایی از بازیها بگردیم که در آنها تعادل بهینه به مقدار بهینه اجتماعی تا حد قابل قبولی نزدیک باشد. بازی‌های طراحی شبکه از این دسته اند.
مثال روبرو که با عنوان مثال پیگو (Pigou) به نام اقتصاددان پیگو در سال ۱۹۲۰ بیان شد، نشانگر یک مدل شبکه‌ای ساده است. در این مدل تعداد n بازیکن قصد رفتن از مبدأ s به مقصد t را دارند و برای این کار اگر مسیر بالایی را برگزینند یک واحد زمانی هزینه می‌کنند و اگر مسیر پایینی را برگزینند، به ازای هر واحد ترافیکی که از پایین می‌گذرد (که ممکن است نسبتی از کل جمعیت بازیکنان مثلاً ۰٫۱ آن باشد) یک واحد زمانی برای رسیدن به مقصد هزینه خواهند کرد. در این مثال اگر یک واحد ترافیک را کل افراد ایجاد کنند، حالت بهینهٔ اجتماعی زمانی اتفاق می‌افتد که نصف افراد از مسیر بالا و نصف دیگر از مسیر پایین عبور کنند و یک تعادل زمانی است که همهٔ افراد مسیر دوم را انتخاب کنند. در این مثال هم مقدار هزینهٔ آشوب و هم پایداری برابر با ۴/۳ خواهد بود. همچنین اگر شبکه به صورت گرافی جهت دار بزرگ شود اما همچنان تابع هزینهٔ هر مسیر به صورت ax+b باقی بماند، مقدار هزینه پایداری و آشوب حداکثر همین ۴/۳ خواهد بود.
این مثالی بسیار ساده از بازی‌های طراحی شبکه بود، در مثال‌های کلی‌تر به عنوان نمونه افراد این قابلیت را دارند که مبدأ و مقصدهای گوناگون داشته باشند. اما ویژگی‌ای ثابت در تمام چنین بازی‌هایی وجود دارد و آن این است که در تمام این بازی‌ها مقدار هزینهٔ آشوب با مقدار هزینهٔ پایداری یکسان است. این موضوع با استفاده از مفهوم تابع پتانسیل قابل اثبات است. مثال دیگری از چنین بازی‌هایی، بازی طراحی شبکهٔ شپلی (Shapley) است. در این بازی یک گراف جهتدار وجود دارد که هر یال e آن دارای هزینهٔ ثابت 𝑐𝑒 می‌باشد. n بازیکن هر یک دارای مقصد و مبدأ خاص خود است و هدفش رسیدن از مقصد به مبدأ می‌باشد. مجموعهٔ استراتژی‌های هر فرد همهٔ مسیرهایی می‌باشد که آن فرد می‌تواند با آنها به مقصد برسد. در نهایت هزینهٔ هر فرد به این صورت مشخص می‌شود که به ازای هر یالی از گراف که در مسیر طی شده توسط او وجود دارد، هزینهٔ آن یال بین تمام کسانی که در استراتژیشان از آن مسیر عبور می‌کنند، به صورت مساوی تقسیم می‌شود. حال می‌خواهیم در این بازی میزان بهینگی تعادل نش را بسنجیم. به این منظور حالت ساده شده‌ای از این بازی مانند زیر را در نظر می‌گیریم. در اینجا n بازیکن با مبدأ و مقصد یکسان s و t داریم و n و 1+e به ترتیب میزان هزینهٔ هریک از مسیرها هستند که در آن: e> 0. در این بازی حالتی که همهٔ افراد مسیر پایینی را انتخاب کنند، یک تعادل و حالتی که همگی مسیر بالایی را انتخاب کنند هم یک تعادل است و حالت بهینهٔ اجتماعی در حالت اول اتفاق می‌افتد. پس در اینجا میزان هزینهٔ پایداری برابر ۱ و میزان هزینهی آشوب برابر n است. البته در همهٔ بازی‌های شیپلی مقدار هزینهٔ پایداری برابر ۱ باقی نمی‌ماند.
طراحی شبکه‌ای بازی‌ها بسیار برای "هزینه پایداری" مفید است. در این بازی‌ها، هزینه "بی‌نظمی" می‌تواند بدتر از "هزینه پایداری" باشد.
بازی زیر را در نظر بگیرید.
هزینه بی‌نظمی می‌تواند formula_16 باشد. طراحی شبکه‌ای بازی شیپلی را که در بالا گفته شد، در نظر بگیرید: دو تعادل متفاوت در این بازی وجود دارد؛ اگر همه یال formula_17 به اشتراک بگذارند، هزینهٔ اجتماعی برابر formula_17 خواهد بود. این تعادل در واقع یک هزینهٔ اجتماعی بهینه است. دقت کنید این که همه یال formula_19 را به اشتراک بگذارند، نیز، یک تعادل نش است و تغییر به یال دیگر، هزینهٔ فرد موردنظر را افزایش می‌دهد.
در اینجا یک بازی آسیب‌شناختی با محتوای مشابه برای هزینه پایداری داریم. در نظر بگیرید formula_19 بازیکن، هر کدام از formula_3 شروع می‌کنند و سعی در متصل شدن به formula_22 دارند. هزینه یال برچسب‌گذاری‌نشده صفر در نظر گرفته می‌شود.
استراتژی بهینهٔ اجتماعی برای هر کس این است که یال formula_23 را به اشتراک بگذارد تا هزینهٔ اجتماعی formula_24 به دست آید. هرچند، تنها یک تعادل نش برای این بازی وجود دارد. باید توجه شود که در حالت بهینهٔ اجتماعی، هر بازیکن هزینهٔ formula_25 می‌پردازد و بازیکن ۱ می‌تواند هزینه‌اش را با تغییر مسیر به یال formula_26 کاهش‌دهد. وقتی این اتفاق بیفتد، بازیکن ۲ نیز تمایل دارد یال formula_27 تغییر مسیر دهد و این روند به این شکل ادامه پیدا خواهد کرد. نهایتاً بازیکنان به تعادل نش برای یال خودشان خواهند رسید. این تخصیص هزینهٔ اجتماعی formula_28 خواهد داشت که formula_29، formula_29اُمین عدد هارمونیک خواهد بود؛ که برابر است با: formula_31. بناباین با این که کران نخواهد داشت، هزینه پایداری در این بازی به‌طور نمایی بهتر از هزینه بی‌نظمی است.
باید دقت شود که بازی‌های طراحی شبکه‌ای، بازی‌های تراکمی هستند. در نتیجه آنها یک تابع پتانسیل دارند: formula_32
قضیه. [قضیه ۱۹٫۱۳ از مرجع ۱] فرض کنید ثابت‌های formula_33 و formula_34ای برای هر استراتژی formula_35 وجود دارد و formula_36. در این صورت هزینه پایداری کوچک‌تر از formula_37 خواهد بود.
"اثبات." مقدار کمینهٔ formula_38 ِ formula_39 یک تعادل نش است؛ بنابراین: formula_40.
حال چون هزینهٔ اجتماعی مجموع هزینه‌های یال‌هاست، در نتیجه: formula_41.
ما معمولاً formula_42 در نظر می‌گیریم و محاسبات بالا formula_43 به‌دست می‌دهد؛ پس ما توانستیم قضیه را ثابت کنیم.