|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Кооперативная игра
Кооперативная игра — термин теории игр. Кооперативной называется игра, в которой группы игроков — коалиции — могут объединять свои усилия. Этим она отличается от игр, в которых коалиции неприемлемы и каждый обязан играть за себя. Теория игр занимается изучением конфликтов, то есть ситуаций, в которых группе людей необходимо выработать какое-либо решение, касающееся их всех. Некооперативная теория игр изучает то, как должны действовать игроки, чтобы прийти к тому или иному результату, кооперативная же теория игр изучает вопрос о том, какие исходы достижимы и условия достижения этих исходов. Математическое представление Согласно определению, кооперативной игрой называется пара (N,v), где N — это множество игроков, а v — это функция: 2N → R, из множества всех коалиций в множество вещественных чисел (так называемая характеристическая функция). Предполагается, что пустая коалиция зарабатывает ноль, то есть v(∅) = 0. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию. Подразумевается, что игроки примут решение о создании коалиции в зависимости от размеров выплат внутри коалиции. Свойства характеристической функции Монотонность — свойство, при котором у больших (в смысле включения) коалиций выплаты больше: если . Супераддитивность — свойство, при котором для любых двух непересекающихся коалиций A и B сумма их выгод по отдельности не больше их выгоды при объединении: Выпуклость — характеристическая функция является выпуклой: Примеры игр Простые игры — особый вид кооперативных игр, где все выплаты это 1 или 0, то есть коалиции либо «выигрывают», либо «проигрывают». Простая игра называется правильной, если: . Значение этого: коалиция выигрывает тогда и только тогда, когда дополняющая коалиция (оппозиция) проигрывает. Решение кооперативных игр В соответствии с определением кооперативной игры, множество игроков N в совокупности обладает некоторым количеством определенного блага, которое надлежит разделить между участниками. Принципы этого деления и называются решениями кооперативной игры. Решение может быть определено как для конкретной игры, так и для класса игр. Естественно, что наибольшей важностью обладают как раз те принципы, которые применимы в широком спектре случаев (то есть для обширного класса игр). Решение может быть как однозначным (в этом случае для каждой игры решением является единственное распределение выигрышей), так и многозначным (когда для каждой игры могут быть определены несколько распределений). Примерами однозначных решений служат N-ядро и вектор Шепли, примерами многозначных — C-ядро и K-ядро. C-ядро С-ядро — принцип оптимальности в теории кооперативных игр, представляющий собой множество эффективных распределений выигрыша, устойчивых к отклонениям любой коалиции игроков, то есть множество векторов , таких, что: и для любой коалиции выполнено: , где — характеристическая функция игры. Свойства Эквивалентным является определение С-ядра кооперативной игры в терминах блокирования распределений выигрыша коалициями. Говорят, что коалиция K блокирует распределение выигрыша x, если найдётся другое распределение выигрыша y, такое, что , и для любого участника выполнено . Тогда С-ядром кооперативной игры называется множество распределений выигрыша, которые не могут быть заблокированы ни одной коалицией.
Теорема. Кооперативная игра с супер модулярной характеристической функцией имеет непустое ядро. Необходимые и достаточные условия непустоты ядра были сформулированы О.Бондаревой и, позднее, Л.Шепли: Теорема. Ядро кооперативной игры непусто тогда и только тогда, когда она сбалансирована.
N-ядро N-ядро— решения кооперативных игр, основанные на минимизации степени неудовлетворённости выигрышем подмножеств участников игры (коалиций). Формальное определение Обозначим через 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-ядра за ограниченное число действий (полиномиально зависящее от количества игроков в игре) для отдельных классов игр. K-ядро K-ядро — принцип оптимальности в кооперативных играх, впервые введен в работе М. Дэвиса и М. Машлера (1965). Пусть задана кооперативная игра с характеристической функцией и — эффективный вектор выигрышей. Максимальный излишек игрока над игроком по отношению к определяется как . Максимальный излишек представляет собой наибольший выигрыш, который игрок может получить, войдя в какую-либо частичную коалицию без кооперации с игроком , в предположении, что остальные игроки в составе коалиции удовлетворены выигрышами, которые доставляет им распределение . Он представляет собой способ измерения сравнительной переговорной силы игроков. K-ядром кооперативной игры называется множество дележей , удовлетворяющих условиям: ; ; для всех пар игроков . Интуитивно, игрок имеет большую переговорную силу, чем игрок при дележе , если , но игрок защищен от угроз игрока , если , так как в этом случае он может получить выигрыш без кооперации. K-ядро содержит все дележи, при которых ни один игрок не имеет такой переговорной силы ни над каким другим игроком. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |