Удаление доминируемых стратегий

Определение: Стратегия называется строго домuнuруемой стратегией игрока i, если существует стратегия такая, что для произвольной обстановки выполняется неравенство

Определение: Стратегия называется строго недомuнuруемой стратегией игрока i, если для произвольной стратегии найдется обстановка такая, что

Использование строго доминируемых стратегий представляется неразумным способом поведения, ведь, независимо от поведения противников, можно получить больший выигрыш, используя одну из строго недоминируемых стратегий.

Первое, что можно сделать для сужения множеств альтернатив игроков – это убрать из рассмотрения строго доминируемые чистые стратегии. После удаления из игры доминируемых стратегий одного из игроков может оказаться, что одна или несколько стратегий другого игрока, недоминируемых в исходной игре, становятся доминируемыми в новой игре. Тогда процесс удаления можно повторять до тех пор, пока все стратегии всех игроков будут недоминируемыми.

Легко показать, что для любой дискретной игры множество строго недоминируемых стратегий для каждого игрока не пусто. Действительно, поскольку отношение доминирования транзитивно, а стратегий конечное число, всегда найдется недоминируемая стратегия.

Множество недоминируемых стратегий непусто и в случае бесконечных компактных множеств стратегий и функций выигрыша, непрерывных по всем переменным.

Точно так же, как для чистых стратегий, можно определить и доминирование смешанных стратегий. Одна смешанная стратегия доминируется другой, если для произвольного профиля смешанных стратегий остальных игроков ожидаемая полезность от использования первой смешанной стратегии ниже, чем от использования второй стратегии.

Удаление доминируемых стратегий, тем не менее, довольно слабая концепция решения, так как во многих практически интересных играх все стратегии строго недоминируемы. Ее применение к анализу игры оправданно на первоначальном этапе, когда, за счет исключения из рассмотрения доминируемых стратегий, исследование игры упрощается.

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

для всех

где .

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

, (5)

В этом случае называется множеством сложных равновесий в игре .

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

Разрешимость по доминированию игры означает, что после конечного числа раундов исключений все стратегии каждого игрока станут для него эквивалентными (но не обязательно для всех – см. пример 2). Если функция выигрыша для всех игроков взаимно однозначных на X_N, то множество сложных равновесий (если оно существует) состоит из одного элемента. Следовательно, в таких разрешимых по доминированию играх сложное поведение игроков детерминировано.

Сложное равновесие обобщает равновесие в доминирующих стратегиях в следующем смысле.

Лемма 4. если в игре Г множество D равновесий в доминирующих стратегиях не пусто, то игра Г разрешима по доминированию и D есть множество сложных равновесий.

Доказательство сразу следует из леммы 2. Если только у одного игрока i есть доминирующая стратегия, то, очевидно, D_i(u_i) является i-ой компонентой множества сложных равновесий, если последнее существует.