N-kärna

N-core , pre-N-core ( nucleolus , prenucleolus ) - lösningar för kooperativa spel baserade på att minimera graden av missnöje med vinsterna för delmängder av speldeltagare (koalitioner).

Formell definition

Beteckna med e(x) för varje tillåten fördelning av vinster x i samarbetsspelet (N,v) kurtosisvektorn för alla koalitioner, med element sorterade i stigande ordning.

Betrakta en uppsättning utdelningsfördelningar A. N-kärnan i ett kooperativt spel med avseende på mängden A är punkten x som motsvarar minimum av den lexikografiska ordningsrelationen på mängden av alla möjliga vektorer e(x) för x tillhörande A.

I fallet när mängden A sammanfaller med mängden av alla tillåtna utdelningsfördelningar, kallas motsvarande N-kärna spelets pre-N-kärna (N,v). Om A sammanfaller med uppsättningen imputationer kallas motsvarande N-kärna för spelets N-kärna (N,v).

Intuitivt representerar N-kärnan utdelningsfördelningen där graden av missnöje hos de mest missnöjda koalitionerna, mätt med deras kurtosis, kommer att vara den minsta.

Origins

N-kärnan introducerades först av Schmeidler 1969. Schmeidler ansåg exakt N-kärnan (det vill säga det lexikografiska minimumet på uppsättningen av divisioner , och inte alla fördelningar av utdelningar). Därefter blev pre-N-kärnan vanligare, på grund av det stora antalet intressanta egenskaper, men eftersom termen "N-kärna" redan togs, blev den känd som "pre-N-kärnan".

Schmeidler bevisade existensen och unikheten hos N-kärnan, visade också att den ligger i K-kärnan och ständigt beror på värdena för spelets karakteristiska funktion v.

Ytterligare egenskaper

Karakterisering genom balans

1971 visade Kohlberg en elegant karaktärisering av pre-N-kärnan i form av balanserade uppsättningar av koalitioner .

Hans teorem säger att en given utdelningsfördelning är en N-kärna om och bara om, för något reellt tal , det är sant att uppsättningen av koalitioner med kurtosis inte längre är en balanserad uppsättning.

Samband med andra lösningar

1. Pre-N-kärnan finns alltid i K-kärnan. Detta är vanligtvis hur K-kärnan visas vara icke-tom för något spel.

2. Om C-kärnan inte är tom, så finns pre-N-kärnan i C-kärnan.

Andra egenskaper

Pre-N-kärnan har egenskaperna anonymitet , kovarians , uppfyller booby-axiomet och är en konsekvent lösning i Davies-Mashlers mening .

Beräkningskomplexitet

Pre-N-kärnan skiljer sig från andra kända lösningar i den icke-konstruktiva karaktären av dess definition. Att hitta N-kärnan med hjälp av dess definition är mycket mödosamt även för spel med ett litet antal spelare (eftersom vi talar om att hitta det lexikografiska minimumet på en uppsättning vektorer i ett dimensionsutrymme , där n är lika med antalet spelare i spelet).

På grund av detta har problem relaterade till att hitta pre-N-kärnan i ett begränsat antal åtgärder (polynomiellt beroende på antalet spelare i spelet) för vissa klasser av spel blivit utbredda de senaste åren.

Se även