Hedoniskt spel

I kooperativ spelteori är ett hedoniskt spel (även känt som ett hedoniskt koalitionsbildande spel ) ett spel som modellerar bildandet av koalitioner (grupper) av spelare när spelare har preferenser över vilken grupp de tillhör. Ett hedoniskt spel specificeras genom att ge en ändlig uppsättning spelare, och, för varje spelare, en preferensrankning över alla koalitioner (underuppsättningar) av spelare som spelaren tillhör. Resultatet av ett hedoniskt spel består av en uppdelning av spelarna i osammanhängande koalitioner, det vill säga varje spelare tilldelas en unik grupp. Sådana partitioner kallas ofta koalitionsstrukturer.

Hedoniska spel är en typ av icke-överlåtbara bruksspel. Deras utmärkande särdrag (den "hedoniska aspekten") är att spelarna bara bryr sig om identiteten på spelarna i deras koalition, men bryr sig inte om hur de återstående spelarna är uppdelade och bryr sig inte om något annat än vilka spelare som finns i deras koalition. Således, till skillnad från andra kooperativa spel , väljer en koalition inte hur den ska fördela vinsten mellan sina medlemmar, och den väljer inte en viss åtgärd att spela. Vissa välkända underklasser av hedoniska spel ges av matchningsproblem, såsom det stabila äktenskapet , stabila rumskamrater och problem med sjukhuset/invånarna .

Spelarna i hedoniska spel anses vanligtvis vara egenintresserade, och därför analyseras hedoniska spel vanligtvis i termer av stabiliteten hos koalitionsstrukturer, där flera begrepp om stabilitet används, inklusive kärnan och Nash - stabilitet . Hedoniska spel studeras både inom ekonomi , där fokus ligger på att identifiera tillräckliga förutsättningar för existensen av stabila utfall, och i multi-agent system , där fokus ligger på att identifiera kortfattade representationer av hedoniska spel och på beräkningskomplexiteten för att hitta stabila utfall. .

Definition

Formellt är ett hedoniskt spel ett par $(N,(\succcurlyeq _{i})_{i\in N})$ av en finit mängd $N$ spelare (eller agenter), och för varje spelare $i\in N$ en fullständig och transitiv preferensrelation $\succcurlyeq _{i}$ över mängden $\{S\subseteq N:i\in S\}$ av koalitioner som spelare $i$ tillhör. En koalition är en delmängd $S\subseteq N$ av uppsättningen spelare. Koalitionen $N$ kallas vanligtvis den stora koalitionen .

En koalitionsstruktur $\pi$ är en partition av $N$ . Således tillhör varje spelare ${\displaystyle i\in N} en unik koalition$$\pi (i)$ i $\pi$ .

Lösningskoncept

Liksom inom andra områden av spelteorin utvärderas resultaten av hedoniska spel med hjälp av lösningskoncept. Många av dessa begrepp hänvisar till en föreställning om spelteoretisk stabilitet: ett resultat är stabilt om ingen spelare (eller möjligen ingen koalition av spelare) kan avvika från resultatet för att nå ett subjektivt bättre resultat. Här ger vi definitioner av flera lösningsbegrepp från litteraturen.

• En koalitionsstruktur $\pi$ finns i kärnan (eller är core-stabil) om det inte finns någon koalition $S$ vars medlemmar alla föredrar $S$ framför $\pi$ . Formellt sägs en icke-tom koalition $S$ blockera $\pi$ om $S\succ _{i}\pi (i)$ för alla $i\in S$ . Då $\pi$ i kärnan om det inte finns några blockerande koalitioner.
• En koalitionsstruktur $\pi$ är i den strikta kärnan (eller är strikt kärnstabil) om det inte finns någon svagt blockerande koalition $S$ där alla medlemmar svagt föredrar $S$ framför ${\ displaystyle \pi }$ och vissa medlemmar föredrar strikt $S$ framför $\pi$ . Med andra ord, $\pi$ finns i den strikta kärnan om $\not \not \ existerar :S\subseteq N:(\forall i\in N:S\succeq \pi )\land (\exists i\in N:S\succ \pi )$ .
• En koalitionsstruktur $\pi$ är Nash-stabil om ingen spelare vill byta koalition inom $\pi$ . Formellt $\pi$ Nash-stabil om det inte finns någon $i\in N$ så att $S\cup \{i \}\succ _{i}\pi (i)$ för vissa $S\in \pi \cup \{\emptyset \}$ . Lägg märke till att, enligt Nash-stabilitet, är en avvikelse av en spelare tillåten även om medlemmar i gruppen $S$ som är förenade med $i$ blir sämre av avvikelsen.
• En koalitionsstruktur $\pi$ är individuellt stabil om ingen spelare vill gå med i en annan koalition vars medlemmar alla välkomnar spelaren. Formellt $\pi$ individuellt stabil om det inte finns någon $i\in N$ så att $S\cup \{i\ }\succ _{i}\pi (i)$ för vissa $S\in \pi \cup \{\emptyset \}$ där ${\ displaystyle S\cup \{i\}\succeq _{j}S}$ för alla $j\in S$ .
• En koalitionsstruktur $\pi$ är kontraktuellt individuellt stabil om det inte finns någon spelare som tillhör en koalition som är villig att låta honom lämna och som vill gå med i en koalition som är villig att ha honom. Med andra ord, $\pi$ är kontraktuellt individuellt stabil om $\not \exists i\in N:(\forall j\in \pi (i):\pi (i)\setminus \{i\}\succeq _{j}\pi (i))~\land ~(\exists C\in \pi :(C\cup \{i \}\succ _{i}\pi (i))~\land ~(\forall j\in C:C\cup \{i\}\succeq _{j}C))$ .

Man kan också definiera Pareto-optimalitet för en koalitionsstruktur. I det fall att preferensrelationerna representeras av nyttofunktioner kan man också överväga koalitionsstrukturer som maximerar social välfärd.

Exempel

Följande spel för tre spelare har fått namnet " en oönskad gäst ".

$${\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\}.\end{aligned}}$$

Från dessa inställningar kan vi se att $1$ och $2$ gillar varandra, men ogillar närvaron av spelare $3$ .

Betrakta partitionen $\pi =\{\{1,2\},\{3\}\}$ . Lägg märke till att i $\pi$ skulle spelare 3 föredra att gå med i koalitionen $\{1,2\}$ , eftersom ${ \displaystyle \{1,2,3\}\succ _{3}\{3\}} ,$ och därför är $\pi$ inte Nash-stabil. Men om spelare $3$ skulle gå med i $\{1,2\}$ , skulle spelare $1$ (och även spelare ${\displaystyle 2})$ vara förvärras av denna avvikelse, så spelare $3$ s avvikelse motsäger inte individuell stabilitet. Man kan faktiskt kontrollera att $\pi$ är individuellt stabil. Vi kan också se att det inte finns någon grupp $S\subseteq N$ av spelare så att varje medlem av $S$ föredrar $S$ framför sin koalition i $\pi$ och så är partitionen också i kärnan.

Ett annat exempel för tre spelare är känt som " två är ett företag, tre är en publik" .

$${\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\}.\end{aligned}}$$

I det här spelet är ingen partition kärnstabil: Partitionen $\{\{1\},\{2\},\{3\}\}$ (där alla är ensamma) blockeras av $\{1,2,3\}$ ; partitionen $\{\{1,2,3\}\}$ (där alla är tillsammans) blockeras av $\{1,2 \}$ ; och partitioner som består av ett par och en singel är blockerade av ett annat par, eftersom inställningarna innehåller en cykel.

Kortfattade representationer och begränsade preferenser

Eftersom preferensrelationerna i ett hedoniskt spel definieras över samlingen av alla $2^{|N|-1}$ delmängder av spelaruppsättningen, att lagra ett hedoniskt spel tar exponentiellt utrymme. Detta har inspirerat olika representationer av hedoniska spel som är koncisa, i den meningen att de (ofta) bara kräver polynomutrymme .

• Individuellt rationella koalitionslistor $S\succcurlyeq _{i }\{i\}$ ett hedoniskt spel genom att explicit lista preferensrankningarna för alla agenter, men bara lista individuella rationella koalitioner, det vill säga koalitioner $S$ med . För många lösningskoncept är det irrelevant hur exakt spelaren rankar oacceptabla koalitioner, eftersom ingen stabil koalitionsstruktur kan innehålla en koalition som inte är individuellt rationell för en av spelarna. Observera att om det bara finns polynomiellt många individuellt rationella koalitioner, så tar denna representation bara polynomutrymme.
• Hedoniska koalitionsnät representerar hedoniska spel genom viktade booleska formler . Som ett exempel betyder den viktade formeln $j\land \lnot k\mapsto _{i}5$ att spelare $i$ får 5 nyttopoäng i koalitioner som inkluderar ${ \displaystyle j}$ men inkluderar inte $k$ . Denna representationsformalism är universellt uttrycksfull och ofta koncis (även om det av nödvändighet finns några hedoniska spel vars hedoniska koalitionsnätrepresentation kräver exponentiellt utrymme).
• Additivt separerbara hedoniska spel är baserade på att varje spelare tilldelar numeriska värden till de andra spelarna; en koalition är lika bra för en spelare som summan av spelarnas värden. Formellt är additivt separerbara hedoniska spel de för vilka det finns värderingar $v_{i}(j)\in \mathbb {R}$ för varje $i, j\in N$ så att för alla spelare $i$ och alla koalitioner $S,T\ni i$ , vi har $S\succcurlyeq _{i }T$ om och endast om $\textstyle \sum _{j\in S}v_{i}(j)\geq \ textstil \sum _{j\in T}v_{i}(j)$ . En liknande definition, med hjälp av genomsnittet snarare än summan av värden, leder till klassen av fraktionerade hedoniska spel.
• I anonyma hedoniska spel bryr sig spelarna bara om storleken på sin koalition, och agenter är likgiltiga mellan två koalitioner med samma kardinalitet: if $|S|=|T|$ sedan $S\sim _{i}T$ . Dessa spel är anonyma i den meningen att individernas identiteter inte påverkar preferensrankningen.
• I booleska hedoniska spel har varje spelare en boolesk formel vars variabler är de andra spelarna. Varje spelare föredrar koalitioner som uppfyller dess formel framför koalitioner som inte gör det, men är annars likgiltiga.
• I hedoniska spel med preferenser beroende på den sämsta spelaren (eller W-preferenser ) har spelare en preferensrankning framför spelare och utökar denna rankning till koalitioner genom att utvärdera en koalition enligt den (subjektivt) sämsta spelaren i den. Flera liknande begrepp (som B-preferenser ) har definierats.

Existensgarantier

Denna digraf beskriver ett additivt separerbart hedoniskt spel vars kärna är tom. Den har fem spelare (visas som inringade hörn). Alla två spelare som inte är sammankopplade med en båge har en värdering -1000 för varandra.

Inte alla hedoniska spel tillåter en koalitionsstruktur som är stabil. Till exempel kan vi betrakta stalkerspelet , som består av bara två spelare $N=\{1,2\}$ med $\{1\}\succ _{1}\{1,2\}$ och $\{1,2\}\succ _{2}\{2\ }$ . Här kallar vi spelare 2 för stalkern . Observera att ingen koalitionsstruktur för detta spel är Nash-stabil: i koalitionsstrukturen $\pi _{1}=\{\{1\},\{2 \}\}$ , där båda spelarna är ensamma, avviker stalker 2 och går med 1; i koalitionsstrukturen ${\displaystyle \pi _{2}=\{\{1,2\}\}} ,$ där spelarna är tillsammans, avviker spelare 1 in i den tomma koalitionen för att inte vara tillsammans med stalkern. Det finns ett välkänt exempel på stabila rumskamrater med 4 spelare som har tom kärna, och det finns också ett additivt separerbart hedoniskt spel med 5 spelare som har tom kärna och inga individuellt stabila koalitionsstrukturer.

För symmetriska additivt separerbara hedoniska spel (de som uppfyller $v_{i}(j)=v_{j}(i)$ för alla $i,j\in N$ ), finns det alltid en Nash-stabil koalitionsstruktur med ett potentiellt funktionsargument . I synnerhet koalitionsstrukturer som maximerar social välfärd är Nash-stabila. Ett liknande argument visar att en Nash-stabil koalitionsstruktur alltid existerar i den mer allmänna klassen av subset-neutrala hedoniska spel . Det finns dock exempel på symmetriska additivt separerbara hedoniska spel som har tom kärna.

Flera villkor har identifierats som garanterar existensen av en kärnkoalitionsstruktur. Detta är särskilt fallet för hedoniska spel med den gemensamma rankningsegenskapen, med den översta koalitionsegenskapen, med topp- eller bottenrespons, med fallande separerbara preferenser och med dikotoma preferenser . Dessutom har gemensam rankningsegendom visat sig garantera existensen av en koalitionsstruktur som är kärnstabil, individuellt stabil och Pareto-optimal på samma gång.

Beräkningskomplexitet

När man överväger hedoniska spel är området algoritmisk spelteori vanligtvis intresserad av komplexiteten i problemet med att hitta en koalitionsstruktur som uppfyller ett visst lösningskoncept när det ges ett hedoniskt spel som input (i någon kortfattad representation). Eftersom det vanligtvis inte är garanterat att ett givet hedoniskt spel medger ett stabilt resultat, kan sådana problem ofta formuleras som ett beslutsproblem som frågar om ett givet hedoniskt spel medger något stabilt resultat. I många fall visar sig detta problem vara beräkningsmässigt svårlöst. Ett undantag är hedoniska spel med gemensam rankningsegenskap där en kärnkoalitionsstruktur alltid existerar, och den kan hittas i polynomtid. Det är dock fortfarande NP-svårt att hitta ett Pareto-optimalt eller socialt optimalt resultat.

I synnerhet för hedoniska spel som ges av individuellt rationella koalitionslistor, är det NP-komplett att bestämma om spelet tillåter ett core-stable, ett Nash-stable eller ett individuellt stabilt resultat. Detsamma gäller för anonyma spel. För additivt separerbara hedoniska spel är det NP-komplett att bestämma existensen av ett Nash-stabilt eller ett individuellt stabilt resultat och komplett för den andra nivån i polynomhierarkin för att avgöra om det finns ett kärnstabilt resultat , även för symmetrisk additiv preferenser. Dessa hårdhetsresultat sträcker sig till spel som ges av hedoniska koalitionsnät. Medan Nash- och individuellt stabila utfall garanteras existerar för symmetriska additivt separerbara hedoniska spel, kan det fortfarande vara svårt att hitta ett om värderingarna $v_{i}(j)$ ges i binärt; problemet är PLS-komplett . För det stabila äktenskapsproblemet kan ett kärnstabilt resultat hittas i polynomtid med användning av algoritmen för uppskjuten acceptans ; för problemet med stabila rumskamrater kan förekomsten av ett kärnstabilt utfall avgöras i polynomtid om preferenser är strikta, men problemet är NP-komplett om preferensbindningar är tillåtna. Hedoniska spel med preferenser baserade på den sämsta spelaren beter sig väldigt likt problem med stabila rumskamrater med avseende på kärnan, men det finns hårdhetsresultat för andra lösningskoncept. Många av de föregående hårdhetsresultaten kan förklaras genom metateorem om att utöka preferenser över enstaka spelare till koalitioner.

Ansökningar

Robotik

För ett robotsystem som består av flera autonoma intelligenta robotar (t.ex. svärmrobotik ) är en av deras beslutsfattande frågor hur man skapar ett robotteam för var och en av givna uppgifter som kräver samarbete mellan robotarna. Ett sådant problem kan kallas multi-robot uppgift tilldelning eller multi-robot koalition formation problem . Detta problem kan modelleras som ett hedoniskt spel, och preferenser i spelet kan återspegla deras individuella fördelar (t.ex. möjlig batteriförbrukning för att slutföra en uppgift) och/eller sociala förmåner (t.ex. komplementaritet av andra robotars kapacitet, trångt för delad resurs).

Några av de speciella problemen i sådan robotapplikation av hedoniska spel i förhållande till andra applikationer inkluderar kommunikationsnätverkstopologin för robotar (t.ex. är nätverket troligen delvis anslutet nätverk ) och behovet av en decentraliserad algoritm som hittar en Nash-stabil partition (eftersom multirobotsystemet är ett decentraliserat system ).

Denna figur visar hur var och en av 320 robotar fattar ett beslut i termer av vilken uppgift den har att arbeta med vem, genom att använda den decentraliserade algoritmen i. Här representerar varje cirkel varje robot, och linjerna mellan dem representerar robotarnas kommunikationsnätverk . Varje ruta och dess storlek anger var och en av de givna uppgifterna och dess uppgiftsbehov. Slutresultatet är en Nash-stabil partition, där robotarna bildar uppgiftsspecifika koalitioner.

Genom att använda anonyma hedoniska spel under SPAO(Single-Peaked-At-One) -preferensen kommer en Nash-stabil partition av decentraliserade robotar, där varje koalition är dedikerad till varje uppgift, garanterat att finnas inom ${ \displaystyle O(n_{a}^{2}d_{G})}$ av iterationer, där $n_{a}$ är numret på robotarna och $d_{G}$ är deras kommunikationsnätverksdiameter . Här är innebörden av SPAO robotars sociala hämning (dvs. motvilja mot att vara tillsammans), som normalt uppstår när deras samarbete är subadditivt .