Тұрақтылық бағасы - Price of stability - Wikipedia

Жылы ойын теориясы, тұрақтылық бағасы (PoS) ойын дегеніміз - бұл тепе-теңдіктің бірінің функционалды мәні мен оңтайлы нәтиженің арақатынасы. PoS ойыншыларға әсер етуі мүмкін объективті авторитеті бар ойындарға қатысты, мүмкін олардың ойынға жақындауына көмектеседі. Нэш тепе-теңдігі. Нэш тепе-теңдігі белгілі бір ойында қаншалықты тиімді екенін өлшегенде біз көбінесе туралы айтамыз анархияның бағасы (PoA).

Мысалдар

PoS білдірудің тағы бір тәсілі:

Келесіде тұтқынның дилеммасы ойын, өйткені бірыңғай тепе-теңдік бар (B, R) бізде PoS = PoA = 1/2.

Тұтқынның дилеммасы
СолДұрыс
Жоғары(2,2)(0,3)
Төменде(3,0)(1,1)

Жыныс ойынының нұсқасы болып табылатын осы мысалда, тепе-теңдік нүктелері (T, L) және (B, R) сәйкесінше 3 және 15 мәндері бар. Оңтайлы мәні 15. Сонымен, PoS = 1, ал PoA = 1/5.

СолДұрыс
Жоғары(2,1)(0,0)
Төменде(0,0)(5,10)

Тарих және маңызды кезеңдер

Тұрақтылық бағасын алғаш А.Шульцан мен Н.Муза зерттеген және Э.Аншелевичтің зерттеулерінде осылай аталған. Олар таза стратегия екенін көрсетті Нэш тепе-теңдігі әрқашан бар және бұл ойынның тұрақтылығы ең көп дегенде n-ші болып табылады гармоникалық сан бағытталған графиктерде. Аншелевич және басқалар бағытталмаған графиктер үшін бір көзге және екі ойыншыға арналған тұрақтылықтың бағасын 4/3-ке қатаң түрде ұсынды. Цзян Ли барлық ойыншылар Shapely желісін жобалау ойынының тұрақтылығының бағасын байланыстыруы керек белгілі бағыттағы бағдарсыз графиктер үшін екенін дәлелдеді қайда ойыншылардың саны. Екінші жағынан, анархияның бағасы туралы осы ойында.

Желілік дизайн ойындары

Орнату

Желілік дизайн ойындары тұрақтылықтың бағасына деген табиғи мотивацияға ие, бұл ойындарда анархия бағасы тұрақтылық бағасынан әлдеқайда нашар болуы мүмкін.

Келесі ойынды қарастырайық.

  • ойыншылар;
  • Әр ойыншы байланыстыруға бағытталған дейін бағытталған графикте ;
  • Стратегиялар ойыншы үшін барлық жолдар бар дейін жылы ;
  • Әр шетінің өзіндік құны бар ;
  • 'Әділ құнын бөлу': қашан ойыншылар шетін таңдайды , баға олардың арасында тең бөлінеді;
  • Ойыншының құны
  • Әлеуметтік шығын - ойыншы шығындарының сомасы: .
Желілік дизайн ойыны Анархияның бағасы

Анархияның бағасы

Анархияның бағасы болуы мүмкін . Келесі желілік дизайн ойынын қарастырайық.

Тұрақтылық ойынының патологиялық бағасы

Бұл ойындағы екі түрлі тепе-теңдікті қарастырайық. Егер барлығы бөлісетін болса әлеуметтік шығындар . Бұл тепе-теңдік шынымен де оңтайлы. Дегенмен, бәрімен бөлісетінін ескеріңіз жиегі - бұл Nash тепе-теңдігі. Әр агенттің өзіндік құны бар тепе-теңдікте және басқа шетке ауыстыру оның құнын арттырады .

Тұрақтылық бағасының төмендеуі

Мұнда тұрақтылықтың бағасы үшін сол рухтағы патологиялық ойын бар әрқайсысы шыққан ойыншылар және қосылуға тырысу . Белгіленбеген шеттердің құны 0-ге тең алынады.

Оңтайлы стратегия - бұл бәрімен бөлісу жиынтық әлеуметтік шығындар . Алайда, бұл ойынға арналған ерекше Nash бар, ескере отырып, оңтайлы болған кезде әр ойыншы төлейді , және 1 ойыншы өзінің құнын төменге ауысу арқылы төмендетуі мүмкін шеті. Бұл орын алғаннан кейін, ойыншыға ауысу 2 ойыншының мүддесіне сәйкес келеді жиегі және т.б. Сайып келгенде, агенттер өздерінің шегіне төлеу үшін Нэш тепе-теңдігіне жетеді. Бұл бөлудің әлеуметтік мәні бар , қайда болып табылады мың гармоникалық сан, қайсысы . Бұл шектеусіз болса да, тұрақтылық бағасы бұл ойындағы анархия бағасынан гөрі жақсы.

Тұрақтылық бағасына байланысты

Желілік дизайн ойындары дизайн бойынша көп жиналатын ойындар екенін ескеріңіз, сондықтан олар әлеуетті функцияны мойындайды .

Теорема. [1 сілтемедегі 19.13 теорема] тұрақтылар бар делік және әрбір стратегия үшін ,

Сонда тұрақтылықтың бағасы төмен болады

Дәлел. Әлемдік минимум туралы бұл теңгерімсіздік, сондықтан

Енді есіңізде болсын, әлеуметтік шығындар шеттер бойынша шығындар сомасы ретінде анықталды, сондықтан

Бізде маңызды емес және жоғарыдағы есептеу береді , сондықтан біз тұрақтылық бағасының жоғарғы шекарасы туралы теореманы айтуға болады.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Эва (2007). Алгоритмдік ойындар теориясы (PDF). Кембридж, Ұлыбритания: Кембридж университетінің баспасы. ISBN  0-521-87282-0.
  2. Л.Агуссурья және Х.К.Лау. Өзімшіл жоспарлау ойындарындағы тұрақтылық бағасы. Веб-интеллект және агент жүйелері: Халықаралық журнал, 9: 4, 2009 ж.
  3. Цзян Ли. Ан бағытталмаған Shapely желісін жобалау ойындары үшін тұрақтылық бағасының жоғарғы шегі. Ақпаратты өңдеу хаттары 109 (15), 876-878, 2009 ж.