Русская Википедия:Некооперативная теория игр
Некооперативная игра — термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.
Некооперативная игра в нормальной форме
Некооперативной игрой в нормальной форме называется тройка <math>\Gamma = \left\langle I,\left\{ S_i\right\}_{i\in I},\left\{ H_i\right\}_{i\in I}\right\rangle</math>, где <math> \ I </math> — множество участников игры (сторон, игроков); <math>\ S_i</math> — множество стратегий участника <math> \ i \in \ I </math>; <math>\ H_i</math> — функция выигрыша участника <math>\ i</math>, определенная на множестве ситуаций <math>\ S = \prod_{i \in I} S_i</math> и отображающая его во множество действительных чисел.
Некооперативная игра в нормальной форме предполагает следующий порядок разыгрывания.
1. Игроки одновременно и независимо друг от друга выбирают из множеств <math>\ S_i</math> свои стратегии. Вектор стратегий <math> \ s=(s_1, s_2, ..., s_n) </math> всех игроков представляет собой ситуацию в игре.
2. Каждый игрок получает выигрыш, определяемый значением функции <math>\ H_i(s)</math>, на этом взаимодействие между ними прекращается.
Нормальная форма игры описывает статическое взаимодействие игроков, не предусматривая возможности последовательных ходов, накопления информации о действиях соперника и повторяющегося взаимодействия. Для моделирования этих аспектов используется развернутая форма игры.
Некооперативная игра в развернутой форме
Некооперативная игра в развернутой форме с множеством игроков <math> \ I </math> представляется с использованием ориентированного дерева (дерева игры) следующим образом.
Вершины дерева представляют собой состояния (позиции), в которых может оказываться игра, ребра — ходы, которые могут использовать игроки. Предполагается, что в каждой позиции может совершать ход не более одного игрока. Выделяется три вида позиций в игре:
- начальная, представляемая корнем дерева (вершиной, не имеющей входящих ребер);
- промежуточные, имеющие входящие и выходящие ребра;
- терминальные, имеющие только входящие ребра.
Начальная и промежуточные позиции образуют множество нетерминальных позиций.
Для каждой вершины дерева <math> \ v </math>, соответствующей нетерминальной позиции, определен игрок <math>\ i</math>, совершающий в ней ход и множество ходов этого игрока <math>\ S_v</math>. Каждому ходу <math>\ s \in \ S_v</math> соответствует ребро, выходящее из вершины <math>\ v</math>.
Для учёта несовершенства информации, имеющейся у игроков, нетерминальные вершины могут объединяться в информационные множества.
Для каждой вершины <math>\ v</math>, соответствующей терминальной позиции, определены функции выигрыша всех игроков <math>\ H_i(v)</math>.
Игра предполагает следующий порядок разыгрывания:
1. Игра начинается из начальной позиции.
2. В любой нетерминальной позиции <math>\ v</math> игрок, имеющий в ней право хода, выбирает ход <math>\ s \in \ S_v</math>, в результате чего игра попадает в следующую позицию, в которую входит ребро, соответствующее ходу <math>\ s</math>. Если эта позиция является нетерминальной, то повторяется п. 2.
3. Если игра попадает в терминальную позицию <math>\ v</math>, то все игроки получают выигрыши <math>\ H_i(v)</math>, и игра завершается.
Принципы оптимальности
Основным принципом оптимальности стратегий для некооперативных игр в нормальной форме является равновесие Нэша, основанное на невозможности отклонений участников от выбранных стратегий. К настоящему времени разработано семейство принципов, основанных на равновесии Нэша, и называемых очищениями равновесия Нэша (Nash equilibrium refinements), наиболее часто используемыми среди которых являются:
Менее универсальными, используемыми в отдельных классах некооперативных игр, являются следующие принципы:
- ε-равновесие;
- равновесие в доминирующих стратегиях;
- решение игры по доминированию;
- равновесие в осторожных стратегиях.
Для некооперативных игр в развернутой форме также используются принципы оптимальности, основанные на равновесии Нэша, но учитывающие специфику динамического взаимодействия игроков. К основным из них относятся:
Примеры
См. также
Литература
- Шаблон:Книга
- Шаблон:Книга
- Васин А.А. Некооперативные игры в природе и обществе. М.: Макс Пресс, 2005, 412 с. ISBN 5-317-01306-2.
