Теория игр

Таблица 2.3

Стратегии	В1	В2	В3	В4	В5	Минимальная прибыль фирмы А
А1	4	8	7	5	4	4
А2	1	10	5	5	6	1
А3	2	4	3	6	2	2
А4	3	5	4	4	3	3
Максимальный убыток фирмы В	4	10	7	6	6

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

Если  игровая задача не имеет седловой точки, то на практике конкурирующие фирмы (игроки) используют смешанные стратегии, т.е. попеременно используют две или более стратегий. В этом случае использование фирмой А нескольких стратегий можно записать как сумму вероятностей использования каждой стратегии Sa= p1+ p2+ …+ pm .

Соответственно, использование нескольких стратегий фирмой В можно записать Sb= q1+ q2+ …+ qn . Поэтому в общем случае исследование игровой модели сводится к определению вероятностей использования конкретных стратегий каждой фирмой (игроком).

3. Графический  метод решения  игровых задач  с нулевой суммой

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

Воспользуемся табл. 2.1.

Строка (стратегия) А1 является доминирующей по отношению к строке (стратегии) А4 , так как содержит элементы, большие соответствующих элементов строки А4 . Соответственно строка А4 является поглощаемой и из дальнейшего рассмотрения удаляется (табл. 3.1).

Таблица 3.1

Первый  шаг упрощения  таблицы

Стратегии	В1	В2	В3	В4	В5
А1	5	8	7	5	4
А2	1	10	5	5	6
А3	2	4	3	6	2

Первый  столбец является доминирующим по отношению  ко второму, третьему и четвертому столбцам (поглощаемым). Поступаем аналогично (табл. 3.2).

 

Таблица 3.2

Второй  шаг упрощения  таблицы

Стратегии	В1	В5
А1	5	4
А2	1	6
А3	2	2

Еще раз рассматриваем  строки. Первая строка поглощает третью строку. Поглощаемые  строки (столбцы) содержат самые плохие стратегии. Окончательно получим (табл. 3.3).

Таблица 3.3

Третий  шаг упрощения  таблицы

Стратегии	В1	В5
А1	5	4
А2	1	6

Вероятность использования первой фирмой первой стратегии  обозначим через p1. Тогда вероятность  использования второй стратегии первым игроком будет p2 = 1- p1 . Ожидаемый выигрыш  фирмы А от применения

(3.1)

вторым  игроком первой стратегии  составит:

Аналогичным способом получим  ожидаемый выигрыш  фирмы А от применения вторым игроком:

(3.2)

В выражения (3.1) и (3.2) подставим  конкретные значения.

На  оси х отложим две точки 0 и 1. Через эти точки проведем прямые линии, параллельные оси у. Затем в первое выражение подставим 0 вместо p1, а потом - единицу. И по двум точкам построим прямую линию.

Аналогично  построим вторую прямую линию. Пересечение  двух прямых линий  и даст решение  задачи (рис. 3.1).

Рис. 3.1 . Графический способ определения стратегий  фирмы А

4p1 + 1= - 2p1 + 6

4p1 + 2p1 = - 1 + 6

6p1 = 5

p1 = 0,83

Итак, вероятность использования  первой стратегии  фирмой А составляет 0,83 (p₁ = 0,83), а второй стратегии p₂ = 1 - 0,83 - соответственно 0,17 (p₂ = 0,17).

Аналогично  определим оптимальную  стратегию поведения  фирмы В:

Пусть у1 - вероятность выбора второй игрой 5 стратегией, у2 - 6 стратегией. (p4 + p5 = 1, p5 = 1- p4)

(a11 - a12) · у1 + a12 = (5 - 4) у1 + 4 = у1 + 4;

(a21 - a22) · у1 + a22 = (1 - 6) у1 + 6 = -5 у1 + 6.

Рис. 3.2 . Графический способ определения стратегий  фирмы В

у₁ + 4 = -5 у₁ + 6

6 у₁ = 2

у₁ = 0,33

Вероятность использования первой стратегии фирмой В составляет 0,33 (у₁ = 0,33), а второй стратегии у₂=1- 0,33 - соответственно 0,67 (у₂ = 0,67).

3.1 Решение задач  графическим методом

Пример 1: Рассмотрим игру заданной платежной матрицей:

Решение:

Проверим  есть ли седловая точка :

? = max (2,2,3,2) = 3

? = min (7,6,6,4,5) = 4 ? ? ?

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

Невыгодные стратегии для первого  игрока:	4, 2
Невыгодные стратегии для второго  игрока:	1, 2, 3

Пусть p₁ - вероятность с которой первый игрок должен применять 1 стратегию, p₃ - вероятность применения 3 стратегией, p₃ = 1- p₁ .

Ожидаемый выигрыш 1 игрока, если второй выбрал 4 стратегию:

p1 · 4 + (1 - p1) · 3 = p1 + 3;

 

Ожидаемый выигрыш 1 игрока, если второй выбрал 5 стратегию:

p1 · 2 + (1 - p1) · 5 = -3 p1 + 5;

p₁ + 3 = -3 p₁ + 5

4 p₁ = 2

p₁ = 1/2 , p₃ =1/2 .

Первому игроку для получения  гарантированного выигрыша 3,5 (1/2+3) рекомендуется чередовать стратегии 1 и 3.

Рассмотрим  второго игрока.

Пусть p4 - вероятность выбора вторым игроком 4 стратегией, p5 - 5 стратегией. (p4 + p5 = 1, p5 = 1- p4)

Ожидаемые проигрыш второго игрока, если первый выберет 1 стратегию.

p4 · 4 + (1- p4) · 2 = 2 p4 + 2

Ожидаемые проигрыш второго игрока, если первый выберет 3 стратегию.

 

p4 · 3 + (1- p4) · 5 = -2 p4 + 5

2 p₄ + 2 = -2 p₄ +5

4 p₄ =3

p₄ =3/4

p₅ =1/4

? = 3/4 · 2 + 2 = 3,5

Ответ : Из 4 игр 3 надо сыграть 4 стратегией, 1 игру - 5 стратегией, и тогда проигрыш будет не больше 3,5, для первого игрока 1 надо сыграть 2 стратегией и 1 - второй стратегией.

Пример 2: Решить игру, заданную матрицей

 

Решение:

Проверим  если ли седловая точка:

? = max (2,4) = 4

? = min (6,5) = 5 ? ? ?

седловой точки нет, игра в чистой стратегии не решается. Найдем смешанную стратегию игроков. Т.к. игровая матрица задана первоначально в размерности 2?2, значит убирать столбцы или строки не нужно.

Ожидаемый выигрыш 1 игрока если второй выбрал 1 стратегию:

А1 · 2 + (1 - А1) · 6 = -4А1 + 6;

Ожидаемый выигрыш 1 игрока если второй выбрал 2 стратегию:

А1 · 5 + (1 - p1) · 4 = А1 + 4;

- 4 А₁ + 6 = А₁ + 4

- 4 А₁ + А₁ = 4 - 6

- 5 А₁ = - 2

А₁ = 2/5 , А₂ = 3/5.

Первому игроку для получения  гарантированного выигрыша 4,

(2/5+4) рекомендуется играть 1 стратегией.

Рассмотрим  второго игрока.

Пусть В1 - вероятность выбора второй игрой 4 стратегией,

(В1 + В2 = 1, В2 = 1- В1)

Ожидаемый проигрыш второго  игрока, если первый выберет 1 стратегию.

В1 · 2 + (1- В1) · 5 = - 3 В1 + 5

Ожидаемый проигрыш второго  игрока, если первый выберет 2 стратегию.

В1 · 6 + (1- В1) · 4 = 2 В1 + 4

- 3 В₁ + 5 = 2 В₁ + 4

- 3 В₁ - 2 В₁ = 4 - 5

- 5 В₁ = - 1

В₁ = 1/5 , В₂ = 4/5.

? = 1/5 · 2 + 4 = 4

Ответ : Из 2 игр 2 надо сыграть 1 стратегией, 1 игру - 2 стратегией, и тогда проигрыш будет не больше 4.

Пример 3: Решить игру, заданную матрицей

Проверим  если ли седловая точка:

? = max (7,6) = 7

? = min (10,9,9) = 9 ? ? ?

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

Невыгодная стратегия для второго  игрока:	3

Ожидаемый выигрыш 1 игрока, если второй выбрал 1 стратегию:

p₁ · 7 + (1 - p₁) · 10 = -3p₁ + 10;

Ожидаемый выигрыш 1 игрока, если второй выбрал 2 стратегию:

p1 · 9 + (1 - p1) · 6 = 3 p1 + 6;

-3p₁ + 10 = 3 p₁ + 6

-3p₁ - 3p₁ = -10 + 6

-6p₁ = -4

p₁ = 2/3 , p₂ =1/3 .

Первому игроку для получения  гарантированного выигрыша 7, (2/3+7) рекомендуется играть 1 стратегией.

Рассмотрим  второго игрока.

Ожидаемые проигрыш второго  игрока если первый выберет 1 стратегию.

p4 · 7 + (1- p4) · 9 = -2 p4 + 9

Ожидаемые проигрыш второго  игрока если первый выберет 2 стратегию.

p4 · 10 + (1- p4) · 6 = 4 p4 + 6

-2p₄ + 9 = 4 p₄ + 6

-2p₄ - 4p₄ = 6 - 9

-6p₄ = -3

р₄ = 1/2 , p₅ =1/2 .

Ответ : Из 2 игр (для первого) 2 надо сыграть 3 стратегией и 1 - 3 стратегией, (для второго) 1 надо сыграть 2 стратегией и 1 - 2 стратегией.

Пример 4: Решить игру, заданную матрицей

Проверим  если ли седловая точка:

? = max (5,4,2,1) = 5

? = min (6,8) = 6 ? ? ?

седловой точки нет, игра в чистой стратегии не решается. Найдем смешанную стратегию игроков.

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

Невыгодная стратегия для первого  игрока:	2,3

Ожидаемый выигрыш 1 игрока, если второй выбрал 1 стратегию:

p₁ · 6 + (1 - p₁) · 1 = 5 p₁ + 1;

Ожидаемый выигрыш 1 игрока, если второй выбрал 2 стратегию:

p₁ · 5 + (1 - p₁) · 8 = -3 p₁ + 8;

5 p₁ + 1 = -3 p₁ + 8

5 p₁ + 3p₁ = 8 - 1

8 p₁ = 7

p₁ = 7/8 , p₂ =1/8 .

Рассмотрим  второго игрока.

Ожидаемые проигрыш второго игрока, если первый выберет 1 стратегию.p4 · 6 + (1- p4) · 5 = p4 + 5

Ожидаемые проигрыш второго игрока, если первый выберет 2 стратегию.

p4 · 1 + (1- p4) · 8 = -7 p4 + 8

p₄ + 5 = -7 p₄ + 8

p₄ + 7 p₄ = 8 - 5

8 p₄ = 3

р₄ = 3/8 , p₅ =5/8 .

= .

Ответ : Из 4 игр (для первого) 7 надо сыграть 8 стратегией и 1 - 8, (для второго) 3 надо сыграть 8 стратегией и 5 - 8.

4. Сведение задач теории игр к задачам линейного

программирования

Предположим, что цена игры положительна ( > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Свойство 1. Тройка (хо, о, ) является решением игры = (Х,,А) тогда и только тогда, когда (хо, о, к +а) является решением игры (Х,,кА+а), где а любое вещественное число, к 0.