Реферат: Теория игр, рафический метод в теории игр

Теорема 1 . Если игрок P1 придерживается своей оптимальной стратегии X *,

а P2 придерживается своей оптимальной стратегии Y *, то.

Теорема 2 . Любая матричная игра имеет решение в смешанных стратегиях.

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

Рассмотрим матричную игру с игроками P1 и P2 и платежной матрицей

1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный

выигрыш. Если игрок P1 выбрал стратегию , то его выигрышем может быть один из выигрышей , расположенный в i-ой строке платежной

матрицы, в зависимости от выбранной стратегии игроком P2. Предполагая поведение игрока P1 крайне осмысленным, необходимо считать, что игрок P2 сыграет наилучшим для себя образом и на выбор игроком P1 стратегии Xi выберет ту стратегию Yj, при которой выигрыш игрока P1 окажется минимальным.

Обозначим минимальный среди выигрышей через αi:

, (αi –показатель эффективности стратегии Xi ).

Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,

которая максимизирует показатель эффективности, т.е. для которой число αi максимально.

Обозначим:

Число α называется нижней ценой игры в чистых стратегиях , а стратегия

Xi0 , которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.

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

2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию , то выигрышем игрока P1 может быть один из выигрышей . Но так как игрок P2 предполагает, что игрок P1 играет наилучшим для себя образом, то выигрышем игрока P1 будет максимальное из этих чисел, обозначим βj:

(βj –показатель неэффективности стратегии Yj ).

Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj . В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β :

Число β называется верхней ценой игры в чистых стратегиях , а стратегия Yj0 , которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.

Теорема 3 . Для элементов платежной матрицы имеют место неравенства:

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:.

Пример . Найти решение игры, заданной платежной матрицей.

Решение:

Решим игру. Пусть – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.

Рассмотрим матрицу

min