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

 

 

3.Решение  игр в смешанных стратегиях.  
                       Решение игр в смешанных стратегиях.  
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 1 α ≠ β, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.  
Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂, ..., A_m с вероятностями p₁, p₂, ..., p_i, ..., p_m причем сумма вероятностей равна 1:  
 
                                      
Смешанные стратегии игрока А записываются в виде матрицы  
                         
или в виде строки S_A = (p₁, p₂, ..., p_i, ..., p_m)  
 
Аналогично смешанные стратегии игрока В обозначаются:  
        , или,       S_B = (q₁, q₂, ..., q_i, ..., q_n), 
где сумма вероятностей появления стратегий равна 1: 
                                                  
Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S^*_A , S^*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: 
 
                                                                 
 
 
                               α ≤ v ≤ β     
где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S^*_A = (p^*₁, p^*₂, ..., p^*_i, ..., p^*_m) и S^*_B = (q^*₁, q^*₂, ..., q^*_i, ..., q^*_n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.  
Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.  
Эта теорема имеет большое практическое значение — она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.  
Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.  
 
Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S^*_A = (p^*_1, p^*₂) и S^*_B = (q^*₁, q^*₂). 
Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'_A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.  
Пусть игра задана платежной матрицей 
                                 
Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию 
                                  , 
а игрок В — чистую стратегию B₁ (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a₁₁ p^*₁+ a21 p^*₂= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B₂, т.е. a₁₂ p^*₁+ a₂₂ p^*₂= v. Учитывая, что p^*₁+ p^*₂= 1, получаем систему уравнений для определения оптимальной стратегии S'_A и цены игры v: 
                                    
Решая эту систему, получим оптимальную стратегию 
                                      
и цену игры 
                                           
Применяя теорему об активных стратегиях при отыскании S^*_B- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А₁ или А₂) средний проигрыш игрока В равен цене игры v, т.е. 
 
                                                                
 
                                                
Тогда оптимальная стратегия определяется формулами: 
 
                                                    
 
                                      
         Пример 1. 
Игра «поиск»  
Игрок А может спрятаться в одном из двух убежищ (I и II); игрок В ищет игрока А, и если найдет, то получает штраф 1 ден. ед. от А, в противном случае платит игроку А         1 ден. ед. Необходимо построить платежную матрицу игры.  
Решение. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I – обозначим эту стратегию через A₁ или в убежище II — стратегия A₂ .  
Игрок В может искать первого игрока в убежище I — стратегия B₁ , либо в убежище II — стратегия B₂. Если игрок А находится в убежище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий (A₁, B₁), то игрок А платит штраф, т.е. a₁₁ = - 1. Аналогично получаем a₂₂ = - 1 (A₂, B₂). Очевидно, что стратегии (A₁, B₂) и (A₂, B₁) дают игроку А выигрыш 1, поэтому a₁₂ = a₂₁ = 1. Таким образом, для игры "поиск" размера 2×2 получаем платежную матрицу 
                                      
Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной в примере 1. 
Пример 2. 
Найти оптимальные стратегии игры, приведенной в примере 1. 
Решение. Игра "поиск" задана платежной матрицей без седловой точки: 
 
                                       
 
                                    
Поэтому ищем решение в смешанных стратегиях; для игрока А средний выигрыш равен цене игры v (при B₁ и B₂); для игрока В средний проигрыш равен цене игры v (при A₁ и B₂). Системы уравнений в данном случае имеют вид: 
                                       
           
 
Решая эти системы, получаем            
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средний выигрыш равен 0. 
                                                   
               

 

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

Определение. Смешанной стратегией игрока А называется применение чистых стратегий с вероятностями соответственно, причем  

Аналогично определяется смешанные стратегии  игрока В, как применение чистых стратегий с вероятностями соответственно, причем  

 

Основная теорема  теории игр (Теорема Неймана).

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

Пусть

пара оптимальных стратегий.

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

Теорема об активных стратегиях:

Если один из игроков придерживается своей активной стратегии, то выигрыш  остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

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

Рассмотрим  матричную игру 2x2. Платежная матрица такой игры имеет вид:

Если седловой точки нет, то решением являются смешанные стратегии , которые находятся из решения систем уравнений: 

 

(1)        и           (2) 

 

Замечание.  Для решения системы (2)  достаточно выбрать два уравнения, т.к. после решения системы (1) цена игры v уже найдена. Можно взять первое и третье уравнения либо второе и третье уравнения.

Игры 2x2, 2xn, mx2 можно решать графически. Игры большей размерности сводятся к решению задач линейного программирования для игроков А и В. 

 

 

 

4. Геометрическая  интерпретация игры 2x2, 2xn, mx2. 

 

Решение игры с матрицей (2x2) можно найти графически. Для этого на оси абсцисс отложим отрезок, длина которого равна единице. Левый конец отрезка (точка х=0) соответствует стратегии , правый - стратегии . Промежуточные точки х соответствуют некоторым смешанным стратегиям ( ), где х₁=1-х, х₂=х.

Из концов выбранного отрезка  восстановим перпендикуляры и будем  откладывать на них выигрыш при  соответствующих чистых стратегиях. Если игрок В принимает стратегию В₁, то выигрыш при использовании чистых стратегий А₁ и А₂ будет соответственно а₁₁ и а₂₁. Отложим эти точки на перпендикулярах к оси абсцисс и соединим прямой В₁В₁. Если игрок А применяет смешанную стратегию, то его выигрышу соответствует некоторая точка М, лежащая на этой прямой.

Аналогично можно построить  прямую В₂В₂, соответствующую стратегии В₂ игрока В. 

 

 Ломанная В₁КВ₂ – нижняя граница выигрыша, полученного игроком А. Точка К, в которой он максимален, определяет цену игры и ее решение.

Замечание. Можно рассмотреть задачу  минимизации верхней границы выигрыша для игрока В, поменяв местами при решении игроков А и В.

Если игра задана матрицей (2хn), то можно найти ее решение, используя геометрическую интерпретацию. Каждой из n стратегий игрока В соответствует прямая. Построив эти прямые, находят нижнюю границу выигрыша. Точка К,  лежащая на нижней границе, для которой величина выигрыша наибольшая, определяет цену игры и ее решение. При этом определяются активные стратегии игрока В (соответствующие им прямые пересекаются в точке К).

Аналогично может быть решена игра с матрицей (mx2), только в этом случае определяют верхнюю границу выигрыша и на ней находят минимум. 

 

5. Типовые  задачи.

Задача 1. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Однако можно предположить, что его величина характеризуется тремя возможными состояниями (В₁, В₂, В₃). С учетом этих состояний анализируются три возможных варианта выпуска данной модели (А₁, А₂, А₃). Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счете различный эффект. Прибыль (тыс.тенге), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей: 

 

 

 

В А	В1	В2	В3
А1	22	22	22
А2	21	23	23
А3	20	21	24

 

 

Требуется найти объем  выпуска модели одежды, обеспечивающий среднюю величину прибыли при  любом состоянии спроса.

Решение. 

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

В А	В1	В2	В3
А1	22	22	22	22
А2	21	23	23	21
А3	20	21	24	20
	22	23	23

 

 

Здесь нижняя цена игры

верхняя цена игры

Таким образом  (цена игры). Игра имеет седловую точку (А₁;В₁), соответствующую А₁ варианту выпуска модели одежды. Объем выпуска модели соответствующий данному варианту, обеспечивает прибыль в 22 тыс. тенге при любом состоянии спроса. 

 

Задача 2. Решить графически игру, заданную платежной матрицей 

 

В А	В1	В2	В3	В4
А1	2	3	1	4
А2	4	2	3	1

 

 

Решение. Имеем . Следовательно, матрица не имеет седловой точки. Выберем систему координат XOY. На оси ОХ отложим единичный отрезок [0;1]. Левый конец отрезка соответствует стратегии А₁, правый - стратегии А₂. Промежуточные точки соответствуют смешанным стратегиям. Через точки А₁ и А₂ проведем прямые, перпендикулярные оси ОХ, на них будем откладывать выигрыши игрока А при различных стратегиях игрока В. Если игрок В примет стратегию В₁, то выигрыши игрока А при стратегиях А₁ и А₂ будут, соответственно, 2 и 4. Отложим эти отрезки на прямых А₁ и А₂. Обозначим полученные точки через В₁, и соединим их прямой В₁В₁.

Аналогично строим прямые В₂В₂; В₃В₃; В₄В₄.  Ломаная В₃ МВ₄ является нижней границей выигрыша. Наибольшая ордината соответствует точке М, в которой пересекаются прямые В₃В₃ и В₄В₄. Это значит, что оптимальными стратегиями игрока В  являются стратегии В₃ и В₄.  Тогда стратегии В₁ и В₂ неактивные, следовательно q₁ = 0 и q₂ = 0.

Рассматриваем платежную  матрицу  .

Для нахождения оптимальных  стратегий игрока А и цены игры v решим систему уравнений:

     откуда    

 

Оптимальные стратегии для  игрока В определим из системы уравнений  

 

    откуда  

Ответ:     S_A=(0,4;0,6);     S_B=(0;0;0,6;0,4);     v=2,2

Таким образом, игрок А применяет стратегию А₁ с вероятностью 0,4; стратегию А₂ с вероятностью 0,6. Игрок В применяет стратегию В₃ с вероятностью 0,6; стратегию В₄ с вероятностью 0,4, а стратегии В₁ и В₂ применять не будет.