Решение игры в смешанных стратегиях. Основная теорема теории игр

Решение игры в смешанных стратегиях. Основная теорема теории игр

Мы знаем, что если нижняя цена игры α равна верхней β  (максимин равен минимаксу), то игра имеет седловую точку и по крайней мере одно решение в чистых стратегиях.

А если α≠β? Можно доказать, что и в этом случае решение всегда есть, только оно лежит не в области чистых, а в области смешан­ных стратегий. Решением игры называется такая пара стратегий — в общем случае смешанных, систематическое применение которых обеспечивает каждой стороне макси­мально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптималь­ной стратегии (в то время как другая продол­жает придерживаться своей), то это ни в коем случае не может быть выгодно для отступаю­щего: это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конеч­ная игра имеет решение (возможно, в области смешанных стратегий). Это положение назы­вается основной теоремой теории игр.

Введем специальное обозначение для сме­шанных стратегий. Пусть К применяет свои стратегии К₁, К₂, К₃ с частотами соответст­венно р₁, р₂, р₃ (p₁+p₂+p₃=1). Эту смешанную стратегию будем обозначать:

Аналогично смешанную стратегию игрока С будем обозначать:

где q₁+q₂+ q₃ =1

Решение игры — пару оптимальных стра­тегий — будем обозначать S*_k и S*_c , а соответ­ствующий ему выигрыш (цену игры) v.

Очевидно, что цена игры v не может быть мень­ше нижней и больше верхней цены:

α ≤ v ≤  β .

В первом примере мы путем нестрогих соображений догадались, что решение игры должно быть:

а цена игры v = 0. Проверим это. Пусть мы («красные») держимся своей стратегии S*_k, т. е. ищем С в убежище I и II одинаково часто, че­редуя эти стратегии случайным образом. Мо­жет ли С улучшить свое положение (повысить свой выигрыш), отступая любым образом от своей стратегии S*_с? Очевидно, нет. А если од­ностороннее отступление от стратегии S*_k при­дет в голову нам (в то время как разумный С будет держаться стратегии S*_c), то это нам то­же не может быть выгодно. Значит, мы и в са­мом деле нашли решение игры и ее цену v = 0. Правда, эта игра была довольно простой! Уже второй пример дает игру, решение которой не так очевидно. Из того, что в нем α≠β, сле­дует только, что решение нужно искать в сме­шанных стратегиях.

Но каково это решение? Какова цена игры? Выгодна ли игра «красным», или «синим», или никому из них?

• ТЕОРИЯ ИГР

• Чем занимается теория игр    
• Парная игра с нулевой суммой. Цена игры      
• Игра в нормальной форме. Матрица игры    
• Примеры конечных игр. Принцип минимакса    
• Седловая точка. Чистая цена игры    
• Решение игры в смешанных стратегиях. Основная теорема теории игр