N-kerne

N-kerne , præ-N-kerne ( nucleolus , prenucleolus ) - løsninger til samarbejdsspil baseret på at minimere graden af ​​utilfredshed med gevinsterne fra delmængder af spildeltagere (koalitioner).

Formel definition

Angiv med e(x) for hver tilladt fordeling af gevinster x i samarbejdsspillet (N,v) kurtosis -vektoren for alle koalitioner, med elementer sorteret i stigende rækkefølge.

Overvej et sæt udbetalingsfordelinger A. N-kernen i et samarbejdsspil med hensyn til mængden A er punktet x svarende til minimum af den leksikografiske ordensrelation på sættet af alle mulige vektorer e(x) for x tilhørende til EN.

I det tilfælde, hvor sættet A falder sammen med sættet af alle tilladte udbetalingsfordelinger, kaldes den tilsvarende N-kerne spillets præ-N-kerne (N,v). Hvis A falder sammen med sættet af imputationer , kaldes den tilsvarende N-kerne for spillets N-kerne (N,v).

Intuitivt repræsenterer N-kernen payoff-fordelingen, hvor graden af ​​utilfredshed hos de mest utilfredse koalitioner, målt på deres kurtosis, vil være den mindste.

Oprindelse

N-kernen blev først introduceret af Schmeidler i 1969. Schmeidler betragtede præcis N-kernen (det vil sige det leksikografiske minimum på sættet af divisioner , og ikke alle distributioner af udbetalinger). Efterfølgende blev præ-N-kernen mere almindelig, på grund af det store antal interessante egenskaber, men da udtrykket "N-kerne" allerede var taget, blev det kendt som "præ-N-kernen".

Schmeidler beviste eksistensen og unikheden af ​​N-kernen, viste også, at den ligger i K-kernen og konstant afhænger af værdierne af spillets karakteristiske funktion v.

Yderligere egenskaber

Karakterisering gennem balance

I 1971 beviste Kohlberg en elegant karakterisering af præ-N-kernen i form af afbalancerede sæt koalitioner .

Hans teorem siger, at en given udbetalingsfordeling er en N-kerne, hvis og kun hvis det for et hvilket som helst reelt tal er sandt, at sættet af koalitioner med kurtosis ikke længere er et afbalanceret sæt.

Forholdet til andre løsninger

1. Præ-N-kernen er altid indeholdt i K-kernen. Det er normalt sådan, at K-kernen viser sig at være ikke-tom for ethvert spil.

2. Hvis C-kernen ikke er tom, er præ-N-kernen indeholdt i C-kernen.

Andre egenskaber

Præ-N-kernen har egenskaberne anonymitet , kovarians , opfylder booby-aksiomet og er en konsistent løsning i Davies-Mashler- forstand .

Beregningsmæssig kompleksitet

Præ-N-kernen adskiller sig fra andre kendte løsninger i den ikke-konstruktive karakter af dens definition. At finde N-kernen ved hjælp af dens definition er meget besværligt, selv for spil med et lille antal spillere (da vi taler om at finde det leksikografiske minimum på et sæt vektorer i et rum med dimension , hvor n er lig med antallet af spillere i spillet).

På grund af dette er problemer relateret til at finde præ-N-kernen i et begrænset antal handlinger (polynomielt afhængig af antallet af spillere i spillet) for visse klasser af spil blevet udbredt i de senere år.

Se også