Показать меню

N-ядро

18.12.2020
13

N-ядро, пред-N-ядро (nucleolus, prenucleolus) — решения кооперативных игр, основанные на минимизации степени неудовлетворённости выигрышем подмножеств участников игры (коалиций).

Формальное определение

Обозначим через e(x) для каждого допустимого распределения выигрышей x в кооперативной игре (N,v) вектор эксцессов всех коалиций, с элементами, упорядоченными по возрастанию.

Рассмотрим некоторое множество распределений выигрышей A. N-ядром кооперативной игры относительно множества A называется точка x, соответствующая минимуму отношения лексикографического порядка на множестве всевозможных векторов e(x) для x принадлежащих A.

В случае когда множество A совпадает с множеством всех допустимых распределений выигрышей, соответствующее N-ядро называется пред-N-ядром игры (N,v). Если же A совпадает с множеством дележей, то соответствующее N-ядро называется N-ядром игры (N,v).

Интуитивно N-ядро представляет распределение выигрыша, на котором степень неудовлетворённости самых неудовлетворённых коалиций, измеряемая величиной их эксцесса, будет наименьшей.

История возникновения

Впервые N-ядро было введено Шмайдлером (Schmeidler) в 1969 году. Шмайдлер рассматривал именно N-ядро (то есть лексикографический минимум на множестве дележей, а не всех распределений выигрышей). Впоследствии большее распространение получило пред-N-ядро, ввиду большого количества интересных свойств, однако, так как термин «N-ядро» уже был занят, оно стало называться «пред-N-ядром».

Шмайдлер доказал существование и единственность N-ядра, также показал, что оно лежит в K-ядре и непрерывно зависит от значений характеристической функции игры v.

Дальнейшие свойства

Характеризация посредством сбалансированности

В 1971 году Колберг доказал элегантную характеризацию пред-N-ядра в терминах сбалансированных наборов коалиций.

Его теорема гласит, что данное распределение выигрышей является N-ядром тогда и только тогда, когда для любого вещественного числа α {displaystyle alpha } верно, что набор коалиций с эксцессом больше α {displaystyle alpha } является сбалансированным набором.

Связь с другими решениями

1. Пред-N-ядро всегда содержится в K-ядре. Обычно именно так показывают непустоту K-ядра для любой игры.

2. Если C-ядро непусто, то пред-N-ядро содержится в С-ядре.

Другие свойства

Пред-N-ядро обладает свойствами анонимности, ковариантности, удовлетворяет аксиоме болвана и является согласованным решением в смысле Девиса-Машлера.

Вычислительная сложность

Пред-N-ядро отличается от других известных решений неконструктивностью своего определения. Нахождение N-ядра с помощью его определения является весьма трудоемким даже для игр с небольшим числом игроков (так как речь идет о поиске лексикографического минимума на множестве векторов в пространстве размерности 2 n {displaystyle 2^{n}} , где n равно количеству игроков в игре).

Из-за этого большое распространение в последние годы получили задачи, связанные с нахождением пред-N-ядра за ограниченное число действий (полиномиально зависящее от количества игроков в игре) для отдельных классов игр.

Еще по этой теме:
Coda (файловая система)
08:50, 18 декабрь
Coda (файловая система)
Coda — Распределённая (сетевая) файловая система (ФС), разработанная как исследовательский проект в университете Карнеги — Меллона в 1987 году под руководством Махадева Сатьянарайанана (англ. Mahadev
NGC 985
05:47, 15 декабрь
NGC 985
NGC 985 (другие обозначения — MCG −2-7-35, MK 1048, VV 285, KUG 0232-090, IRAS02321-0900, PGC 9817) — галактика в созвездии Кит. Этот объект входит в число перечисленных в оригинальной редакции
Шрапнель, Генри
01:58, 15 декабрь
Шрапнель, Генри
Генри Шрапнель (англ. Henry Shrapnel — Генри Шрэпнел) (3 июня 1761, Брадфорд-он-Эйвон — 13 марта 1842, Саутгемптон) — офицер Британской армии, предложивший конструкцию артиллерийского снаряда для
Класс PH
08:42, 11 декабрь
Класс PH
Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: PH =
Носитель (кооперативная игра)
03:46, 05 декабрь
Носитель (кооперативная игра)
Носитель — подмножество множества игроков в кооперативной игре, которые вносят ненулевой вклад в некоторую коалицию. Формально носитель кооперативной игры определяется как: S
Теорема Бондаревой — Шепли
20:24, 03 декабрь
Теорема Бондаревой — Шепли
В теории игр теорема Бондаревой — Шепли описывает необходимые и достаточные условия для непустоты ядра в кооперативной игре. В частности, ядро игры непусто тогда и только тогда, когда игра
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent