Гедоникалық ойын - Hedonic game

Жылы кооператив ойын теориясы, а гедоникалық ойын^[1][2] (гедоникалық деп те аталады коалиция құру ойыны) - қалыптастыруды модельдейтін ойын коалициялар (топтар) ойыншылардың қай топқа жататындығына байланысты артықшылықтары болған кезде. Гедоникалық ойын шектеулі ойыншылар жиынтығын беру арқылы көрсетіледі, ал әр ойыншыға а артықшылық рейтингі ойыншы тиесілі барлық коалициялардың (ішкі жиындардың) үстінен. Гедоникалық ойынның нәтижесі а-дан тұрады бөлім ішіндегі ойыншылар бөлу коалициялар, яғни әр ойыншыға ерекше топ бөлінеді. Мұндай бөлімдер көбінесе коалициялық құрылымдар деп аталады.

Гедоникалық ойындар - бұл түрі ауыстырылмайтын утилиталар ойыны. Олардың айырықша ерекшелігі («гедоникалық аспект»)^[3]) - бұл ойыншылардың тек қамын ойлауы жеке басын куәландыратын олардың коалициясындағы ойыншылар туралы, бірақ қалған ойыншылардың қалай бөлінетіні туралы ойланбайды және олардың коалициядағы ойыншылардан басқа ешнәрсе туралы ойламайды. Осылайша, басқалардан айырмашылығы ынтымақтастық ойындары, коалиция өз мүшелері арасында пайданы қалай бөлуді таңдамайды және ол ойнау үшін белгілі бір әрекетті таңдамайды. Гедоникалық ойындардың кейбір белгілі кіші сыныптары сәйкес есептермен берілген, мысалы тұрақты неке, тұрақты бөлмеленушілер, және аурухана / тұрғындар мәселелер.

Гедоникалық ойындардың ойыншылары әдетте жеке мүдделер деп түсініледі, демек, гедоникалық ойындар коалициялық құрылымдардың тұрақтылығы тұрғысынан талданады, мұнда тұрақтылықтың бірнеше ұғымдары қолданылады, оның ішінде өзек және Нэш тұрақтылығы. Гедоникалық ойындар екі жерде де зерттеледі экономика, онда фокусты анықтауға бағытталған жеткілікті шарттар тұрақты нәтижелердің болуы үшін және көп агенттік жүйелер, онда назар гедоникалық ойындардың қысқаша көріністерін анықтауға бағытталған есептеу күрделілігі тұрақты нәтижелерді табу.^[2]

Анықтама

Ресми түрде, а гедоникалық ойын жұп ${ displaystyle (N, ( succcurlyeq _ {i}) _ {i in N})}$ ақырлы жиынтықтың ${ displaystyle N}$ ойыншылардың (немесе агенттердің), және әр ойыншы үшін ${ displaystyle i in}$ а толық және өтпелі артықшылықты қатынас ${ displaystyle succcurlyeq _ {i}}$ жиынтықтың үстінде ${ displaystyle {S subseteq N: i in S }}$ сол коалиция ${ displaystyle i}$ тиесілі. A одақ Бұл ішкі жиын ${ displaystyle S subseteq N}$ ойыншылар жиынтығы. Коалиция ${ displaystyle N}$ әдетте деп аталады үлкен коалиция.

A коалиция құрылымы ${ displaystyle pi}$ бөлімі болып табылады ${ displaystyle N}$. Осылайша, әр ойыншы ${ displaystyle i in}$ бірегей коалицияға жатады ${ displaystyle pi (i)}$ жылы ${ displaystyle pi}$.

Шешім туралы түсініктер

Ойындар теориясының басқа салалары сияқты, гедоникалық ойындардың нәтижелері шешім тұжырымдамалары арқылы бағаланады. Осы ұғымдардың көпшілігі ойын-теориялық тұрақтылық ұғымына сілтеме жасайды: егер субьективтік жағынан жақсы нәтижеге жету үшін бірде бір ойыншы (немесе, мүмкін, ойыншылар коалициясы) нәтижеден ауытқып кете алмаса, нәтиже тұрақты болады. Мұнда біз әдебиеттен бірнеше шешім тұжырымдамаларына анықтама береміз.^[1][2]

• Коалициялық құрылым ${ displaystyle pi}$ егер коалиция болмаса, өзекте болады (немесе тұрақты) ${ displaystyle S}$ оның мүшелері бәрін қалайды ${ displaystyle S}$ дейін ${ displaystyle pi}$. Ресми түрде бос емес коалиция ${ displaystyle S}$ айтылады блок ${ displaystyle pi}$ егер ${ displaystyle S succ _ {i} pi (i)}$ барлығына ${ displaystyle i in S}$. Содан кейін ${ displaystyle pi}$ егер блоктаушы коалициялар болмаса, өзекте болады.
• Коалициялық құрылым ${ displaystyle pi}$ егер әлсіз блоктайтын коалиция болмаса, қатаң ядрода болады (немесе қатаң түрде тұрақты) ${ displaystyle S}$ мұнда барлық мүшелер әлсіз көреді ${ displaystyle S}$ дейін ${ displaystyle pi}$ және кейбір мүшелер қатаң түрде қалайды ${ displaystyle S}$ дейін ${ displaystyle pi}$. Басқа сөздермен айтқанда, ${ displaystyle pi}$ егер қатаң ядрода болса ${ displaystyle not бар: S subseteq N: ( forall i in N: S succeq pi) land ( бар i N: S succ pi)}$.
• Коалициялық құрылым ${ displaystyle pi}$ Егер бірде-бір ойыншы коалицияны өзгерткісі келмесе, ол тұрақты болып табылады ${ displaystyle pi}$. Ресми түрде, ${ displaystyle pi}$ жоқ болса, Nash тұрақты болып табылады ${ displaystyle i in}$ осындай ${ displaystyle S cup {i } succ _ {i} pi (i)}$ кейбіреулер үшін ${ displaystyle S in pi cup { emptyset }}$. Назар аударыңыз, Nash-тұрақтылыққа сәйкес, топ мүшелері болса да ойыншының ауытқуына жол беріледі ${ displaystyle S}$ қосылады ${ displaystyle i}$ ауытқудан нашарлайды.
• Коалициялық құрылым ${ displaystyle pi}$ егер бірде-бір ойыншы басқа коалицияға қосылғысы келмесе, жеке-дара тұрақты болады, оның мүшелері барлығы ойыншыны қуана қарсы алады. Ресми түрде, ${ displaystyle pi}$ жоқ болса, жеке-жеке тұрақты болады ${ displaystyle i in}$ осындай ${ displaystyle S cup {i } succ _ {i} pi (i)}$ кейбіреулер үшін ${ displaystyle S in pi cup { emptyset }}$ қайда ${ displaystyle S cup {i } succeq _ {j} S}$ барлығына ${ displaystyle j in S}$.
• Коалициялық құрылым ${ displaystyle pi}$ егер коалицияға кіруге рұқсат беретін және оған ие болғысы келетін коалицияға кіргісі келетін ойыншы болмаса, шарт бойынша жеке-жеке тұрақты болады. Басқа сөздермен айтқанда, ${ displaystyle pi}$ егер шарт бойынша жеке-дара тұрақты болса ${ displaystyle not бар i N: ( forall j in pi (i): pi (i) setminus {i } succeq _ {j} pi (i)) ~ ~ land ~ ( C in pi бар: (C succ _ {i} pi (i)) ~ land ~ ( for all j in C: C cup {i } succeq _ {j } C))}$.

Сондай-ақ анықтауға болады Паретоның оңтайлылығы коалициялық құрылым.^[4] Артықшылық қатынастар ұсынылған жағдайда утилита функциялары Сонымен қатар, әлеуметтік әл-ауқатты барынша арттыратын коалициялық құрылымдарды қарастыруға болады.

Мысалдар

Келесі үш ойыншы ойыны аталды «қалаусыз қонақ".^[1]

$${ displaystyle { begin {aligned} & {1,2 } succ _ {1} {1 } succ _ {1} {1,2,3 } succ _ {1} {1,3 }, & {1,2 } succ _ {2} {2 } succ _ {2} {1,2,3 } succ _ {2} {2,3 }, & {1,2,3 } succ _ {3} {2,3 } succ _ {3} {1,3 } succ _ {3 } {3 }. Соңы {тураланған}}}$$

${ displaystyle 1}$

${ displaystyle 2}$

${ displaystyle 3}$

Бөлімді қарастырайық ${ displaystyle pi = { {1,2 }, {3 } }}$. Мұнда назар аударыңыз ${ displaystyle pi}$, 3 ойыншы коалицияға кіруді жөн көреді ${ displaystyle {1,2 }}$, өйткені ${ displaystyle {1,2,3 } succ _ {3} {3 }}$, демек ${ displaystyle pi}$ Nash тұрақты емес. Алайда, егер ойыншы болса ${ displaystyle 3}$ қосылу керек еді ${ displaystyle {1,2 }}$, ойыншы ${ displaystyle 1}$ (және сонымен қатар ойыншы ${ displaystyle 2}$) осы ауытқу салдарынан нашарлауы мүмкін, сондықтан ойыншы ${ displaystyle 3}$ауытқу жеке тұрақтылыққа қайшы келмейді. Шынында да, мұны тексеруге болады ${ displaystyle pi}$ жеке-жеке тұрақты. Сондай-ақ, топтың жоқтығын байқауға болады ${ displaystyle S subseteq N}$ ойыншылардың әрқайсысының мүшелері ${ displaystyle S}$ қалайды ${ displaystyle S}$ олардың коалициясына ${ displaystyle pi}$ сондықтан бөлім де өзек болады.

Үш ойыншының тағы бір мысалы «екеуі - компания, үшеуі - тобыр".^[1]

$${ displaystyle { begin {aligned} & {1,2 } succ _ {1} {1,3 } succ _ {1} {1,2,3 } succ _ {1 } {1 }, & {2,3 } succ _ {2} {2,1 } succ _ {2} {1,2,3 } succ _ {2 } {2 }, & {3,1 } succ _ {3} {3,2 } succ _ {3} {1,2,3 } succ _ {3 } {3 }. Соңы {тураланған}}}$$

${ displaystyle { {1 }, {2 }, {3 } }}$

${ displaystyle {1,2,3 }}$

${ displaystyle { {1,2,3 } }}$

${ displaystyle {1,2 }}$

Қысқаша ұсыныстар және шектеулі артықшылықтар

Гедоникалық ойындағы артықшылық қатынастар бәрінің жиынтығына қарағанда анықталғандықтан ${ displaystyle 2 ^ {| N | -1}}$ ойыншының жиынтығы, гедоникалық ойынды сақтау экспоненциалды кеңістікті алады. Бұл гедоникалық ойындардың әр түрлі көріністерін шабыттандырды, олар қысқаша, олар (көбінесе) қажет етеді көпмүшелік ғарыш.

• Жеке ұтымды коалициялық тізімдер^[5] барлық агенттердің артықшылық рейтингтерін нақты тізімдеу арқылы гедоникалық ойынды білдіреді, бірақ тек жеке рационалды коалицияларды, яғни коалицияларды тізімдеу ${ displaystyle S}$ бірге ${ displaystyle S succcurlyeq _ {i} {i }}$. Көптеген шешімдер тұжырымдамалары үшін ойыншының қабылданбайтын коалицияларды қаншалықты дәл дәрежеде қоюы маңызды емес, өйткені ешқандай тұрақты коалиция құрамы ойыншылардың біреуі үшін жеке ұтымды емес коалицияны қамти алмайды. Егер жеке рационалды коалициялар тек көпмүшелік көп болса, онда бұл ұсыну тек көпмүшелік кеңістікті алады.
• Гедоникалық коалиция торлары^[6] салмақтылық арқылы гедоникалық ойындарды ұсынады Буль формулалары. Мысал ретінде өлшенген формула келтірілген ${ displaystyle j land lnot k mapsto _ {i} 5}$ сол ойыншыны білдіреді ${ displaystyle i}$ құрамына кіретін коалицияларда 5 пайдалы пункт алады ${ displaystyle j}$ бірақ кірмейді ${ displaystyle k}$. Бұл бейнелеу формализмі әмбебап мәнерлі және көбіне қысқа болып келеді^[6] (дегенмен, қажеттілік бойынша, гедоникалық коалицияның таза көрінісі экспоненциалды кеңістікті қажет ететін кейбір гедоникалық ойындар бар).
• Қосымша бөлінетін гедоникалық ойындар^[1] басқа ойыншыларға сандық мәндерді тағайындаған әр ойыншыға негізделген; коалиция ойыншылар үшін құндылықтардың қосындысы сияқты жақсы. Формальды түрде аддитивті түрде бөлінетін гедоникалық ойындар - бұл бағалау бар ойындар ${ displaystyle v_ {i} (j) in mathbb {R}}$ әрқайсысы үшін ${ displaystyle i, j in}$ барлық ойыншыларға арналған ${ displaystyle i}$ және барлық коалициялар ${ displaystyle S, T ni i}$, Бізде бар ${ displaystyle S succcurlyeq _ {i} T}$ егер және егер болса ${ displaystyle textstyle sum _ {j in S} v_ {i} (j) geq textstyle sum _ {j in T} v_ {i} (j)}$. Ұқсас анықтама, мәндердің қосындысынан гөрі орташа мәнін қолдана отырып, классына әкеледі бөлшек гедоникалық ойындар.^[7]
• Жылы анонимді гедоникалық ойындар,^[8] ойыншылар тек туралы ойлайды өлшемі олардың коалициясы, және агенттері бірдей коалицияға немқұрайлы қарамайды: егер ${ displaystyle | S | = | T |}$ содан кейін ${ displaystyle S sim _ {i} T}$. Бұл ойындар жеке тұлғаның жеке басының артықшылық рейтингіне әсер етпейтіндігіне байланысты жасырын болып табылады.
• Жылы Бульдік гедоникалық ойындар,^[9] әр ойыншының логикалық формуласы бар, оның айнымалылары басқа ойыншылар болып табылады. Әр ойыншы өз формуласын қанағаттандыратын коалицияға сәйкес келмейтін коалициялардан гөрі бей-жай қарайды.
• Гедоникалық ойындарда ең нашар ойыншыға байланысты артықшылықтары бар (немесе W-теңшелімдері^[10]), ойыншылардың артықшылықты рейтингі бар ойыншыларжәне коалицияны ондағы (субъективті) ең нашар ойыншыға қарай бағалау арқылы коалицияға дейін осы рейтингті кеңейту. Бірнеше ұқсас тұжырымдамалар (мысалы B-артықшылықтар) анықталды.^[11][12][13]

Болу кепілдігі

Бұл диграф өзегі бос аддитивті бөлінетін гедоникалық ойын сипаттайды. Онда бес ойыншы бар (шеңбер түрінде көрсетілген). Доғамен байланыспаған кез-келген екі ойыншының бір-бірінің бағасы -1000 болады.

Әрбір гедоникалық ойын тұрақты коалиция құрылымын қабылдамайды. Мысалы, біз сталкер ойынытек екі ойыншыдан тұрады ${ displaystyle N = {1,2 }}$ бірге ${ displaystyle {1 } succ _ {1} {1,2 }}$ және ${ displaystyle {1,2 } succ _ {2} {2 }}$. Мұнда біз 2 ойыншыны Сталкер. Назар аударыңыз, бұл ойынға арналған коалиция құрылымы тұрақты емес: коалициялық құрылымда ${ displaystyle pi _ {1} = { {1 }, {2 } }}$, екі ойыншы жалғыз болған жерде, сталкер 2 ауытқып, 1-ге қосылады; коалиция құрылымында ${ displaystyle pi _ {2} = { {1,2 } }}$, онда ойыншылар бірге болған кезде, 1 ойыншы сталкермен бірге болмас үшін бос коалицияға ауысады. Белгілі данасы бар тұрақты бөлмеленушілер бос ядросы бар 4 ойыншыға қатысты мәселе,^[14] сонымен қатар құрамында 5 тұрақты ойыншы бар, құрамында бос ядросы бар және жеке-дара коалициялық құрылымдары жоқ, аддитивті түрде бөлінетін гедоникалық ойын бар.^[15]

Үшін симметриялы аддитивті түрде бөлінетін гедоникалық ойындар (қанағаттандыратын ойындар) ${ displaystyle v_ {i} (j) = v_ {j} (i)}$ барлығына ${ displaystyle i, j in}$), әрдайым а бар Nash тұрақты коалиция құрылымы бар потенциалды функция аргументі. Атап айтқанда, әлеуметтік әл-ауқатты барынша арттыратын коалициялық құрылымдар тұрақты болып табылады.^[1] Осыған ұқсас аргумент Nash тұрақты коалиция құрылымының әрқашан жалпы сыныпта өмір сүретіндігін көрсетеді жиынтық бейтарап гедоникалық ойындар.^[16] Алайда, бос өзегі бар симметриялық аддитивті бөлінетін гедоникалық ойындардың мысалдары бар.^[8]

Негізгі коалиция құрылымының болуына кепілдік беретін бірнеше шарттар анықталды. Бұл, атап айтқанда, жалпы рейтингтік қасиеті бар гедоникалық ойындарға қатысты,^[17][18] жоғарғы коалиция меншігімен,^[8] жоғары немесе төменгі жауаптылықпен,^[19] бөлінетін артықшылықтардың төмендеуімен,^[20][21] және бірге дихотомиялық артықшылықтар.^[9] Сонымен қатар, жалпыға ортақ рейтинг қасиеті коалициялық құрылымның болуына кепілдік береді, ол негізгі тұрақты, жеке-дара тұрақты және бір уақытта Парето оңтайлы болып табылады.^[22]

Есептеудің күрделілігі

Гедоникалық ойындарды қарастыру кезінде алгоритмдік ойындар теориясы әдетте белгілі бір шешім тұжырымдамасын қанағаттандыратын коалициялық құрылымды іздеу проблемасының күрделілігіне гедоникалық ойын берілген кезде ұсынылады (кейбір қысқаша ұсынуда).^[2] Әдетте, берілген гедоникалық ойынның тұрақты нәтиже беретіндігіне кепілдік берілмегендіктен, мұндай проблемаларды көбінесе « шешім мәселесі берілген гедоникалық ойынның қабылданатындығын сұрайды кез келген тұрақты нәтиже. Көптеген жағдайларда бұл проблема есептеумен шешілмейтін болып шығады.^[18][23] Ерекшелік - бұл негізгі коалиция құрылымы әрқашан болатын жалпы рейтингтік қасиеті бар гедоникалық ойындар және оны полиномдық уақытта табуға болады.^[17] Алайда, Pareto-ны оңтайлы немесе әлеуметтік тұрғыдан оңтайлы нәтиже табу әлі де қиын.^[22]

Атап айтқанда, жекелеген рационалды коалициялық тізімдермен берілген гедоникалық ойындар үшін ойынның негізгі-тұрақтылықты, Nash-тұрақты немесе жеке-жеке тұрақты нәтижені мойындайтындығын NP аяқтайды.^[5] Анонимді ойындарға да қатысты.^[5] Қосымша бөлінетін гедоникалық ойындар үшін Nash-тұрақты немесе жеке-жеке тұрақты нәтиженің бар-жоқтығын анықтау NP аяқталды^[15] және деңгейдің екінші деңгейіне аяқтаңыз көпмүшелік иерархия негізгі тұрақты нәтиже бар-жоғын шешу,^[24] симметриялы аддитивті артықшылықтар үшін де.^[25] Бұл қаттылық нәтижелері гедоникалық коалиция торлары берген ойындарға таралады. Nash- және жеке-дара тұрақты нәтижелер үшін кепілдік бар симметриялы аддитивті түрде бөлінетін гедоникалық ойындар, егер бағалау болса, оны табу қиынға соғуы мүмкін ${ displaystyle v_ {i} (j)}$ екілік түрінде беріледі; мәселе мынада PLS аяқталды.^[26] Тұрақты неке мәселесі үшін полиномдық уақыт ішінде негізгі тұрақты нәтижені табуға болады кейінге қалдырылған қабылдау алгоритмі; тұрақты бөлмеленушілер проблемасы үшін, егер тұрақтылық қатаң болса, полиномдық уақытта негізгі тұрақты нәтиженің болуын шешуге болады,^[27] бірақ артықшылықты байланыстарға рұқсат етілсе, проблема NP-де аяқталады.^[28] Нашар ойыншыға негізделген артықшылықтары бар гедоникалық ойындар негізгі бөлмеге қатысты тұрақты бөлмеленушілердің проблемаларына ұқсас,^[10] бірақ шешімнің басқа тұжырымдамалары үшін қаттылық нәтижелері бар.^[13] Алдыңғы қаттылықтың көптеген нәтижелерін коалицияға жалғыз ойыншыдан артықшылық беру туралы мета-теоремалар арқылы түсіндіруге болады.^[23]

Қолданбалар

Робототехника

Бірнеше автономды интеллектуалды роботтардан тұратын робот жүйесі үшін (мысалы, робототехника ), шешім қабылдау мәселелерінің бірі - роботтардың бірлесіп жұмыс істеуін қажет ететін тапсырмалардың әрқайсысы үшін робот командасын құру. Мұндай проблеманы атауға болады мульти-роботтарды бөлу немесе көп роботты коалиция құру проблемасы. Бұл мәселені гедоникалық ойын ретінде модельдеуге болады, және артықшылықтар Ойындағы роботтардың жекелеген артықшылықтары (мысалы, тапсырманы орындау үшін батареяны тұтынуы мүмкін) және / немесе әлеуметтік жағымды жақтары (мысалы, басқа роботтардың мүмкіндіктерінің толықтырылуы, ортақ ресурстарға деген тығыздығы) көрсетілуі мүмкін.

Гедоникалық ойындардың басқа қосымшаларға қатысты мұндай робототехниканы қолданудағы кейбір ерекше мазасыздықтары роботтардың байланыс желісінің топологиясын қамтиды (мысалы, желі, мүмкін ішінара қосылған желі ) және Nash тұрақты бөлімін табатын орталықтандырылмаған алгоритмнің қажеттілігі (өйткені көп роботты жүйе орталықтандырылмаған жүйе ).

Бұл суретте орталықтандырылмаған алгоритмді қолдану арқылы 320 роботтың әрқайсысы кіммен жұмыс жасауы керек екендігі туралы шешім қабылдауы көрсетілген.^[29] Мұнда әр шеңбер әр роботты, ал олардың арасындағы сызықтар роботтардың байланыс желісін бейнелейді. Әрбір квадрат пен оның өлшемі сәйкесінше берілген тапсырмалардың әрқайсысын және оның тапсырма сұранысын көрсетеді. Соңғы нәтиже - роботтар арнайы коалиция құратын Nash тұрақты бөлімі.

Астында анонимді гедоникалық ойындарды пайдалану SPAO (бір шыңды-бір) әр коалиция әр тапсырмаға арналған орталықтандырылмаған роботтардың Nash тұрақты бөлігін табуға кепілдік беріледі. ${ displaystyle O (n_ {a} ^ {2} d_ {G})}$ қайталану,^[29] қайда ${ displaystyle n_ {a}}$ бұл роботтардың саны және ${ displaystyle d_ {G}}$ олардың байланыс желісі болып табылады диаметрі. Мұнда SPAO-ның мәні роботтар болып табылады әлеуметтік тежеу (яғни, бірге болуға құлықсыздық), бұл әдетте олардың ынтымақтастығы болған кезде пайда болады қосалқы.

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