Основные понятия и определения

⇐ ПредыдущаяСтр 5 из 6Следующая ⇒

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

Для задания правил необходимо определить:

1)Варианты действия игроков;

2)Объем информации каждого игрока о поведении противника;

3) Выигрыш, к которому приводит совокупность действий игроков;

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

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

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

Решить антагонистическую задачу (игру) значит для каждого игрока указать стратегию, удовлетворяющую условию оптимальности, то есть игрок А должен получить максимальный выигрыш, а игрок В должен получить минимальный проигрыш.

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

Предположим, что для пары стратегий А _i и B_j выигрыш известен – ν _ij, тогда можно составить прямоугольную таблицу (матрицу), в которой показаны все стратегии игроков и соответствующие выигрыши. Такая матрица называется платежной.

	B₁	B₂
А₁	5	-4
А₂	4	3
А₃	2	1

Положительные числа в клетках матрицы означают выигрыш игрока А и следовательно проигрыш игрока В. Отрицательное число означает проигрыш игрока А и следовательно выигрыш игрока В.

Решение игры с седловой точкой

	B₁	B ₂
А₁	5	-4
А₂	4	3
А₃	2	1

Рассмотрим подробнее игровую матрицу. У игрока А имеется 3 стратегии, а у игрока В – 2 стратегии. Нужно определить какую стратегию нужно выбрать игроку А, чтобы его выигрыш был максимальным, проигрыш игрока В был бы минимальным.

	B ₁	B₂	min
А₁	5	-4	-4
А₂	4	3	3
А₃	2	1	1
max	5	3

Для этого введем несколько понятий:

Нижняя цена игры: Сначала находим минимумы в каждой строке, заносим их в таблицу.

Из полученных минимумов находим максимум: α=maxmin ν _ij;

α=3 – это гарантированный выигрыш игрока А при любой стратегии игрока В.

Верхняя цена игры: Сначала находим максимум в каждом столбце, определяем минимальное число: β=minmax ν_ij;

β=3 – гарантированный проигрыш игрока В при любой стратегии игрока А.

Если α=β=ν, то в этом случае выбранные стратегии называются оптимальными, а саму игру называют игрой с седловой точкой. В этом случае у игрока А стратегия А₂ и у игрока В стратегия В₂. При выборе других стратегий выигрыш игрока А будет меньше, а проигрыш игрока В больше.

Задача

Найти седловую точку матрицы:

	B ₁	B₂	B₃	min
А₁	1	2	1	-1
А₂	3	-5	-1	5
А₃	-1	7	-2	-2
max	3	7	1

α =1;

β = 1; cедловая точка А₁;В₃, а выигрыши ν_1А=ν_3В=1.

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

Смешанные стратегии

Рассмотрим пример

	B ₁	B₂	min
А₁	5	8	5
А₂	6	4	4
max	6	8

α=5; β=6; α≠β;

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

1) Определение цены игры методом подбрасывания монеты;

2) Определение относительных частот применения смешанных стратегий;

3) Использование частот и вероятностей, полученных при многократной игре;

Определение цены игры методом подбрасывания монеты

	B ₁	B₂	min
А₁	5	8	5
А₂	6	4	4
max	6	8

Пусть смешанная стратегия игрока А определяется подбрасыванием монеты:

А₁ – «орел», А₂ – «решка».

Средний выигрыш игрока А против первой стратегии игрока В:

а против второй:

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

Определение относительных частот применения смешанных стратегий

	B ₁	B₂
А₁	5	8	3
А₂	6	4	2
	1	4

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

a) Рассмотрим стратегии игрока В. Из первой строки вычитаем числа второй, тогда частоту применения первой стратегии примем равной 4, а частоту второй стратегии 1, то есть стратегии игроком В₁ и В₂ должны применятся в отношении 4:1.

Отметим, что если число, характеризующее относительную частоту окажется отрицательным, то на знак не обращают внимания.

б) Аналогичным образом определяются частоты применения стратегий игрока А и они относятся как 2:3.

в) Найдем цену игры при применении против первой стратегии игрока В. Она будет равна:

А цена игры против второй стратеги равна:

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

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

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

Для игрока А: Р=(р₁…р _m), где р₁ +…+ р _m =1.

P_i ≥0 – частота применения стратегии А _i.

Для игрока В: Q =(q ₁ … q_n), где q ₁ +…+ q_n =1.

q_j ≥0 – частота применения стратегии В _j.

В этом случае ν(P ⁰ Q ⁰) называют ценой игры и обозначают через ν и .

Пример

Рассмотрим решение игры (смотри таблицу).

		q	1-q
		B ₁	B₂
p	А₁	- 5	8	-5
1-p	А₂	4	-7	-7
		4	8

В данном примере седловая точка отсутствует, тогда оптимальная цена игры -5≤ ν ≤4.

Припишем строкам вероятности р и 1-р.

Умножив столбец поэлементно на первый столбец и сложив произведения получим линейную зависимость:

W ( p )=-5 p +4(1- p )=-9 p +4 (1)

(1) – это средний выигрыш игрока А при применении игроком В первой стратегии.

Умножив столбец поэлементно на второй столбец и сложив произведения получим:

W ( p )=8 p +(-7)(1- p )=15 p -7 (2)

(2) – это средний выигрыш игрока А при применении игроком В второй стратегии.

Приравняем (1) и (2)

-9 p +4=15 p -7

Отсюда ; .

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

Подставив в зависимости (1) и (2) соответственно p ₁ и p ₂ получим цену игры

; (3)

Теперь припишем столбцам вероятности q и 1- q. Умножив строку (q ,1- q) на первую строку и сложив произведения, получим

W ( q )=(- 5) q +8(1- q )=-13 q +8 (4)

(4) – средний выигрыш игрока В при применении игроком А первой стратегии.

Аналогично со второй строкой

W ( q )=4 q +(-7)(1- q )=11 q -7 (5)

(5) – средний выигрыш игрока В при применении игроком А второй стратегии.

Приравнивая зависимости (4) и (5) получим:

-13 q +8=11 q -7

Отсюда ; , т.е. оптимальная смешанная стратегия игрока В – это . Подставив в зависимости (4), (5) соответственно q ₁ и q ₂, получим цену игры игрока В.

; (6)

Сравнивая (3) и (6) находим, что – это и есть оптимальная цена игры, которая возможна при оптимальной смешанной стратегии и .

Таким образом, оптимальная цена игры и действительно .

4. Решение игры 2 n

Самым удобным способом для определения оптимальной стратегии игроков в игре 2 n является графическим способом.

Пример

	B ₁	B₂	B ₃	B ₄
А₁	-1	1	-1	2
А₂	0	-1	2	-2

Отложим на двух вертикальных осях платежи сначала первой стратегии В₁(-1,0) и соединим их линией, а затем остальные стратегии игрока В. Отметим утолщенной линией нижнюю границу графика. Затем найдем наивысшую точку этой линии. Линии пересекающиеся в этой точке соответствуют тем чистым стратегиям, которые должен применить игрок В в своей смешанной стратегии. На графике в этой точке пересекаются линии, соответствующие стратегиям В₁ и В₄. Таким образом остается матрица по первой и четвертой стратегиям игрока В:

Решим методом определения относительных частот применения смешанных стратегий. Получим:

- игрок А должен применить стратегии А₁ и А₂ в отношении 2:3, тогда цена игры:

	B ₁	B₂
А₁	-1	2	3
А₂	0	-2	2
	1	4

- игрок В должен применять стратегии В₁ и В₄ в отношении 4:1, тогда

Т.о. оптимальная цена игры .

5. Решение игры m 2

Используя метод вероятностей применения стратегий, решить игру 3 2.

Припишем вероятности столбцов для q; 1- q, в результате получим линейные зависимости

W ( q )=1 q +4(1- q )=4-3 q (1)

W ( q )=3 q +(-2)(1- q )=5 q –2 (2)

W ( q )=0· q +5(1- q )=5-5 q (3)

Изобразим данные линейные зависимости графически:

Возьмем верхнюю огибающую. Точка С – точка с наименьшим выигрышем (W), точка пересечения прямых (1) и (2). Приравняем первую и вторую зависимости и определим вероятности:

;

Цена игры в этом случае:

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

Примеры решения задач

Задача 1

Найти решение игры, определяемой матрицей

Решение:

Данная игра седловой точки не имеет: α=2, β=3.

Поэтому ищем решение в смешанных стратегиях:

Ответ: общее решение имеет вид:

; ; .

Задача 2

Найти решение игры 2 2 с использованием понятия равновесия по Нэшу

Решение:

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

Определим точку Нэша

(x^H, y^H) – координаты точки равновесия по Нэшу.

Таким образом, оптимальные стратегии в данной игре следующие

;

Цена игры в точке Нэша

Ответ: общее решение имеет вид:

; ; .

Примеры заданий

Вариант 0

Зная платежную матрицу

определить нижнюю и верхнюю цены игры и найти решение игры.

Вариант 1

Игра задана платежной матрицей. Определить седловую точку.

Вариант 2

Игра задана платежной матрицей. Определить седловую точку.

Вариант 3

Игра задана платежной матрицей. Определить верхнюю цену игры.

Вариант 4

Игра задана платежной матрицей. Определить нижнюю цену игры.

Вариант 5

Игра задана платежной матрицей. Определить нижнюю верхнюю цены игры.

Вариант 8

Игра задана платежной матрицей. Определить седловую точку.

Вариант 9

Игра задана платежной матрицей. Определить вероятности P₁ и P₂ применения стратегий А₁ и А₂для оптимальной смешанной стратегии игрока А.

Вариант 10

Игра задана платежной матрицей. Определить вероятности q₁ и q₂ применения стратегий В₁ и В₂ для оптимальной смешанной стратегии игрока В.

Вариант 11

Игра задана платежной матрицей. Определить цену игры, если вероятности P₁ и P₂ применения стратегий А₁ и А₂ для оптимальной смешанной стратегии игрока A равны 0,6 и 0,4.