N-jádro

N-core , pre-N-core ( nucleolus , prenucleolus ) - řešení pro kooperativní hry založené na minimalizaci míry nespokojenosti s výhrami podskupin účastníků hry (koalice).

Formální definice

Označte e(x) pro každé přípustné rozdělení výplat x v kooperativní hře (N,v) vektor špičatosti všech koalic, s prvky seřazenými vzestupně.

Uvažujme množinu výplatních rozdělení A. N-jádro kooperativní hry vzhledem k množině A je bod x odpovídající minimu relace lexikografického řádu na množině všech možných vektorů e(x) pro x patřících do A.

V případě, že se množina A shoduje s množinou všech přípustných rozdělení výplat, odpovídající N-jádro se nazývá pre-N-jádro hry (N,v). Pokud se A shoduje se sadou imputací , pak se odpovídající N-jádro nazývá N-jádro hry (N,v).

Intuitivně N-kernel představuje distribuci výplaty, kde míra nespokojenosti nejvíce nespokojených koalic, měřená jejich špičatostí, bude nejmenší.

Origins

N-kernel poprvé představil Schmeidler v roce 1969. Schmeidler uvažoval přesně o N-kernelu (to je lexikografické minimum na množině dělení , a ne všechna rozdělení výplat). Následně se pre-N-kernel stal běžnějším, vzhledem k velkému množství zajímavých vlastností, nicméně protože termín "N-kernel" již byl převzat, stal se známým jako "pre-N-kernel".

Schmeidler prokázal existenci a jedinečnost N-kernelu, také ukázal, že leží v K-kernelu a nepřetržitě závisí na hodnotách charakteristické funkce hry v.

Další vlastnosti

Charakterizace prostřednictvím rovnováhy

V roce 1971 Kohlberg prokázal elegantní charakterizaci pre-N-kernelu ve smyslu vyvážených sad koalic .

Jeho teorém říká, že dané rozdělení výplaty je N-kernel tehdy a jen tehdy, když pro jakékoli reálné číslo platí, že množina koalic se špičatostí již není vyváženou množinou.

Vztah k jiným řešením

1. Pre-N-kernel je vždy obsažen v K-kernelu. Takto se obvykle ukazuje, že K-core není pro žádnou hru prázdné.

2. Pokud není C-kernel prázdné, pak je pre-N-kernel obsaženo v C-kernelu.

Další vlastnosti

Pre-N-kernel má vlastnosti anonymity , kovariance , splňuje axiom axiomu a je konzistentním řešením ve smyslu Davies- Mashler .

Výpočetní složitost

Pre-N-kernel se liší od jiných známých řešení v nekonstruktivní povaze své definice. Hledání N-jádra pomocí jeho definice je velmi pracné i pro hry s malým počtem hráčů (protože mluvíme o hledání lexikografického minima na množině vektorů v prostoru dimenze , kde n je rovno počtu hráčů ve hře).

Z tohoto důvodu se v posledních letech rozšířily problémy související s nalezením pre-N-kernelu v omezeném počtu akcí (polynomiálně závislých na počtu hráčů ve hře) pro určité třídy her.

Viz také