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-ядром тогда и только тогда, когда для любого вещественного числа
верно, что набор коалиций с эксцессом больше является сбалансированным набором.Связь с другими решениями[]
1. Пред-N-ядро всегда содержится в K-ядре. Обычно именно так показывают непустоту K-ядра для любой игры.
2. Если C-ядро непусто, то пред-N-ядро содержится в С-ядре.
Другие свойства[]
Пред-N-ядро обладает свойствами анонимности, ковариантности, удовлетворяет аксиоме болвана и является согласованным решением в смысле Девиса-Машлера.
Вычислительная сложность[]
Пред-N-ядро отличается от других известных решений неконструктивностью своего определения. Нахождение N-ядра с помощью его определения является весьма трудоемким даже для игр с небольшим числом игроков (так как речь идет о поиске лексикографического минимума на множестве векторов в пространстве размерности
, где n равно количеству игроков в игре).Из-за этого большое распространение в последние годы получили задачи, связанные с нахождением пред-N-ядра за ограниченное число действий (полиномиально зависящее от количества игроков в игре) для отдельных классов игр.
См. также[]
Формула | Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
Теория игр |
|
---|---|
Определения |
Кооперативная игра · Антагонистическая игра · Стохастическая игра · Дифференциальные игры · Игрок · Стратегия ·Доминирование стратегий |
Принципы оптимальности |
Эффективность по Парето · Равновесие в доминирующих стратегиях · Решение по доминированию · Равновесие дрожащей руки · Равновесие, совершенное по под-играм · Собственное равновесие · Сильное равновесие · Эпсилон-равновесие · Коррелированное равновесие · Секвенциальное равновесие · Доминирование по риску ·Эволюционно стабильная стратегия |
Примеры игр |
Трагедия общин · Модель Бертрана · Модель Курно ·Модель Штакельберга |