Некооперативная игра

Некооперативная игра — термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.

Некооперативная игра в нормальной форме

Некооперативной игрой в нормальной форме называется тройка $\Gamma = <I,\ S_i,\ H_i>$, где $\ I$ - множество участников игры (сторон, игроков); $\ S_i$ - множество стратегий участника $\ i \in \ I$; $\ H_i$ - функция выигрыша участника $\ i$, определенная на множестве ситуаций $\ S = \prod_{i \in I} S_i$ и отображающая его во множество действительных чисел.

Некооперативная игра в нормальной форме предполагает следующий порядок разыгрывания.

1. Игроки одновременно и независимо друг от друга выбирают из множеств $\ S_i$ свои стратегии. Вектор стратегий $\ s=(s_1, s_2, ..., s_n)$ всех игроков представляет собой ситуацию в игре.

2. Каждый игрок получает выигрыш, определяемый значением функции $\ H_i(s)$, на этом взаимодействие между ними прекращается.

Нормальная форма игры описывает статическое взаимодействие игроков, не предусматривая возможности последовательных ходов, накопления информации о действиях соперника и повторяющегося взаимодействия. Для моделирования этих аспектов используется развернутая форма игры.

Некооперативная игра в развернутой форме

Некооперативная игра в развернутой форме с множеством игроков $\ I$ представляется с использованием ориентированного дерева (дерева игры) следующим образом.

Вершины дерева представляют собой состояния (позиции), в которых может оказываться игра, ребра - ходы, которые могут использовать игроки. Предполагается, что в каждой позиции может совершать ход не более одного игрока. Выделяется три вида позиций в игре:

• начальная, представляемая корнем дерева (вершиной, не имеющей входящих ребер);
• промежуточные, имеющие входящие и выходящие ребра;
• терминальные, имеющие только входящие ребра.

Начальная и промежуточные позиции образуют множество нетерминальных позиций.

Для каждой вершины дерева $\ v$, соответствующей нетерминальной позиции, определен игрок $\ i$, совершающий в ней ход и множество ходов этого игрока $\ S_v$. Каждому ходу $\ s \in \ S_v$ соответствует ребро, выходящее из вершины $\ v$.

Для учета несовершенства информации, имеющейся у игроков, нетерминальные вершины могут объединяться в информационные множества.

Для каждой вершины $\ v$, соответствующей терминальной позиции, определены функции выигрыша всех игроков $\ H_i(v)$.

Игра предполагает следующий порядок разыгрывания:

1. Игра начинается из начальной позиции.

2. В любой нетерминальной позиции $\ v$ игрок, имеющий в ней право хода, выбирает ход $\ s \in \ S_v$, в результате чего игра попадает в следующую позицию, в которую входит ребро, соответствующее ходу $\ s$. Если эта позиция является нетерминальной, то повторяется п. 2.

3. Если игра попадает в терминальную позицию $\ v$, то все игроки получают выигрыши $\ H_i(v)$, и игра завершается.

Принципы оптимальности

Основным принципом оптимальности стратегий для некооперативных игр в нормальной форме является равновесие Нэша, основанное на невозможности отклонений участников от выбранных стратегий. К настоящему времени разработано семейство принципов, основанных на равновесии Нэша, и называемых очищениями равновесия Нэша (Nash equilibrium refinements), наиболее часто используемыми среди которых являются:

• равновесие дрожащей руки;
• собственное равновесие;
• сильное равновесие.

Менее универсальными, используемыми в отдельных классах некооперативных игр, являются следующие принципы:

• ε-равновесие;
• равновесие в доминирующих стратегиях;
• решение игры по доминированию;
• равновесие в осторожных стратегиях.

Для некооперативных игр в развернутой форме также используются принципы оптимальности, основанные на равновесии Нэша, но учитывающие специфику динамического взаимодействия игроков. К основным из них относятся:

• равновесие, совершенное по под-играм;
• секвенциальное равновесие;
• сильное секвенциальное равновесие.

Примеры

• Дилемма заключённого
• Трагедия общин

См.также

• Кооперативная игра
• Теория игр
• Равновесие Нэша

Литература

• Петросян Л. А., Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М.: Высш. шк., Книжный дом «Университет», 1998. — С. 304. — ISBN 5-06-001005-8, 5-8013-0007-4
• Васин А. А., Морозов В. В. Теория игр и модели математической экономики. — М., 2005.