- •Теория игр
- •. Содержание
- •История исследований по теории игр
- •Представление игр
- •Экстенсивная форма
- •Нормальная форма
- •Характеристическая функция в игре
- •Применение теории игр
- •Описание и моделирование
- •Нормативный анализ (выявление наилучшего поведения)
- •Типы игр Кооперативные и некооперативные
- •Симметричные и несимметричные
- •С нулевой суммой и с ненулевой суммой
- •Параллельные и последовательные
- •С полной или неполной информацией
- •Игры с бесконечным числом шагов
- •Дискретные и непрерывные игры
- •Метаигры
- •Стохастическая игра
- •История исследований стохастических игр
- •Применение стохастических игр
- •Некооперативная игра
- •Некооперативная игра в нормальной форме
- •Некооперативная игра в развернутой форме
- •Принципы оптимальности Эффективность по Парето
- •Равновесие Нэша: формальное определение
- •Равновесии дрожащей руки: формальное определение
- •Собственное равновесие
- •Определение
- •Сильное равновесие
- •Равновесие в доминирующих стратегиях
- •Равновесие, совершенное по под-играм
- •Кооперативная игра
- •Математическое представление кооперативной игры
- •Свойства характеристической функции
- •Примеры кооперативных игр
- •Решение кооперативных игр
- •Свойства
- •Формальное определение
- •История возникновения
- •Дальнейшие свойства
- •Вектор Шепли
- •Формальное определение
- •Аксиоматика вектора Шепли
- •Литература
- •Антагонистическая игра
- •Дифференциальные игры
- •Сетевые игры
- •Кооперативные стохастические игры
- •Марковский процесс принятия решений
- •Определение
- •Классическая дилемма заключённого
- •Обобщённая форма
- •Примеры из реальной жизни
- •Повторяющаяся дилемма заключённого
- •Психология обучения и теория игр
- •Восточная философия
- •Генетика
- •Игрок в теории игр
- •Типы стратегий
- •Терминология
- •Формальные определения
- •Доминирование и равновесие Нэша
- •Последовательное исключение доминируемых стратегий
- •Литература
Равновесие, совершенное по под-играм
Равновесие, совершенное по подиграм— принцип оптимальности втеории игр, представляющий адаптациюравновесия Нэшадля игр в развернутой форме.
Набор стратегий игроков называется равновесием, совершенным по подиграм, если его сужение на любую подигруданной игры есть равновесие Нэша в ней. Интуитивно это означает, что действия сторон в некоторой игре будут одинаковы, независимо от того, разыгрывается ли она отдельно или является частью более общей надыгры.
Равновесие, совершенное по подиграм, позволяет отсеять равновесия Нэша, основанные на недостоверных угрозахигроков.
Общим методом определения совершенных по под-играм равновесий является обратная индукция, при которой оптимизация ходов игроков начинается с конца игры. Данный метод не работает, если в игре отсутствуют под-игры, а также для повторяющихся игр с бесконечным горизонтом.
Кооперативная игра
Кооперативной называется игра, в которой группы игроков — коалиции — могут объединять свои усилия. Этим она отличается от игр, в которых коалиции неприемлемы и каждый обязан играть за себя. Примером такой игры может являться карточная игра в дурака«двое на двое» или «трое на трое», либо разыгрывание «втёмную» виста впреферансе.
Развлекательные игры редко являются кооперативными, из-за отсутствия механизмов, которые могли бы навязывать координацию действий между членами коалиции. Однако такие механизмы нередки в повседневной жизни.
Теория игр занимается изучением конфликтов, то есть ситуаций, в которых группе людей необходимо выработать какое-либо решение, касающееся их всех. Некооперативная теория игр изучает то, как должны действовать игроки, чтобы прийти к тому или иному результату, кооперативная же теория игр изучает вопрос о том, какие исходы достижимы и условия достижения этих исходов.
Математическое представление кооперативной игры
Согласно определению, кооперативной игрой называется пара (N,v), где N — это множество игроков, а v — это функция: 2N→R, из множества всех коалиций в множество вещественных чисел (так называемая характеристическая функция). Предполагается, что пустая коалиция зарабатывает ноль, то есть v(∅) = 0. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию. Подразумевается, что игроки примут решение о создании коалиции в зависимости от размеров выплат внутри коалиции.
Свойства характеристической функции
Монотонность— свойство, при котором у больших (в смысле включения) коалиций выплаты больше: если.
Супераддитивность— свойство, при котором для любых двух непересекающихся коалиций A и B сумма их выгод по отдельности не больше их выгоды при объединении:
Выпуклость— характеристическая функция является выпуклой:
Примеры кооперативных игр
Простые игры— особый вид кооперативных игр, где все выплаты это 1 или 0, то есть коалиции либо «выигрывают», либо «проигрывают». Простая игра называется правильной, если:
.
Значение этого: коалиция выигрывает тогда и только тогда, когда дополняющая коалиция (оппозиция) проигрывает.
Решение кооперативных игр
В соответствии с определением кооперативной игры, множество игроков N в совокупности обладает некоторым количеством определенного блага, которое надлежит разделить между участниками. Принципы этого деления и называются решениями кооперативной игры.
Решение может быть определено как для конкретной игры, так и для класса игр. Естественно, что наибольшей важностью обладают как раз те принципы, которые применимы в широком спектре случаев (то есть для обширного класса игр).
Решение может быть как однозначным (в этом случае для каждой игры решением является единственное распределение выигрышей), так и многозначным (когда для каждой игры могут быть определены несколько распределений). Примерами однозначных решений служат N-ядроивектор Шепли, примерами многозначных —C-ядроиK-ядро.
C-ядро
С-ядро(произноситсяцэ-ядро) — принцип оптимальности в теориикооперативных игр, представляющий собой множество эффективных распределений выигрыша, устойчивых к отклонениям любой коалиции игроков, то есть множество векторов, таких, что:
и для любой коалиции выполнено:
,
где — характеристическая функция игры.