N-ydin

N-ydin , pre-N-ydin ( nucleolus , prenucleolus ) - ratkaisut yhteistyöpeleihin , jotka perustuvat pelin osallistujien (koalitioiden) osajoukkojen voittojen tyytymättömyyden minimoimiseen.

Muodollinen määritelmä

Merkitse e(x) jokaiselle voittojakauman x hyväksytylle jakaumille yhteistyöpelissä (N,v) kaikkien koalitioiden kurtosis -vektoria , jossa elementit on lajiteltu nousevaan järjestykseen.

Tarkastellaan joukkoa voittojakaumia A. Yhteistyöpelin N-ydin suhteessa joukkoon A on piste x, joka vastaa leksikografisen järjestysrelaation minimiä kaikkien mahdollisten vektorien e(x) joukossa x:lle A.

Siinä tapauksessa, että joukko A osuu yhteen kaikkien sallittujen voittojakaumien joukon kanssa, vastaavaa N-ydintä kutsutaan pelin pre-N-ytimeksi (N,v). Jos A osuu yhteen imputaatioiden joukon kanssa , niin vastaavaa N-ydintä kutsutaan pelin N-ytimeksi (N,v).

Intuitiivisesti N-ydin edustaa voittojakaumaa, jossa tyytymättömimpien koalitioiden tyytymättömyyden aste niiden kurtoosilla mitattuna on pienin.

Origins

N-ytimen esitteli ensimmäisen kerran Schmeidler vuonna 1969. Schmeidler tarkasteli täsmälleen N-ydintä (eli jakojoukon leksikografista minimiä , eikä kaikkia voittojakaumia). Myöhemmin pre-N-ydin yleistyi, johtuen suuresta määrästä mielenkiintoisia ominaisuuksia, mutta koska termi "N-ydin" oli jo käytössä, se tuli tunnetuksi "pre-N-ytimenä".

Schmeidler osoitti N-ytimen olemassaolon ja ainutlaatuisuuden, osoitti myös, että se on K-ytimessä ja riippuu jatkuvasti pelin ominaisfunktion arvoista v.

Muita ominaisuuksia

Karakterisointi saldon kautta

Vuonna 1971 Kohlberg osoitti tyylikkään esi-N-ytimen luonnehdinnan tasapainoisten koalitioiden joukoissa .

Hänen lauseensa sanoo, että tietty voittojakauma on N-ydin, jos ja vain jos millä tahansa reaaliluvulla on totta, että koalitioiden joukko kurtoosilla ei ole enää tasapainoinen joukko.

Suhde muihin ratkaisuihin

1. Pre-N-ydin sisältyy aina K-ytimeen. Näin K-ydin ei yleensä näytetä olevan tyhjä missään pelissä.

2. Jos C-ydin ei ole tyhjä, niin N-ydintä edeltävä ydin sisältyy C-ytimeen.

Muut ominaisuudet

Pre-N-ytimellä on anonymiteetin , kovarianssin ominaisuudet , se täyttää booby-aksiooman ja on johdonmukainen ratkaisu Davies-Mashlerin mielessä .

Laskennallinen monimutkaisuus

Pre-N-ydin eroaa muista tunnetuista ratkaisuista määritelmänsä ei-rakentavassa luonteessa. N-ytimen löytäminen sen määritelmän mukaan on erittäin työlästä jopa pienillä pelaajilla (koska puhumme leksikografisen minimin löytämisestä vektorijoukosta ulottuvuusavaruudessa , jossa n on yhtä kuin pelaajien lukumäärä pelissä).

Tästä johtuen ongelmat, jotka liittyvät pre-N-ytimen löytämiseen rajoitetussa määrässä toimintoja (riippuen polynomiaalisesti pelaajien lukumäärästä pelissä) tietyissä peliluokissa, ovat yleistyneet viime vuosina.

Katso myös