Математические методы. Теория игр

1.

Теория игр. Основы

2.

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

3.

Области применения теории игр
- экономика;
- политика;
- военные действия и т. д.

4.

Основные понятия
Конфликтная ситуация – это столкновение интересов двух
или более сторон.
Игра – это математическая модель конфликтных ситуаций, а
также система предварительно оговоренных правил и условий.
Партией называется частичная реализация правил и
условий игры. Результатом игры всегда является число v,
которое называется выигрышем, проигрышем или ничьей.
если υ > 0 – выигрыш
если υ < 0 – проигрыш
если υ = 0 – ничья

5.

КЛАССИФИКАЦИЯ ИГР
По числу игроков:
игры одного игрока,
двух игроков,
n игроков
По характеру выигрышей:
с нулевой суммой и
игры с ненулевой суммой
По количеству стратегий:
конечные и бесконечные
По количеству шагов:
одношаговые и многошаговые
По виду функций выигрышей:
матричные, биматричные,
непрерывные,
выпуклые, сепарабельные, типа
дуэлей и др.
По характеру
взаимоотношений:
бескоалиционные,
коалиционные и
кооперативные
5

6.

Основные понятия. Стратегии
Стратегией игрока называется совокупность правил, определяющих
выбор варианта действий при каждом личном ходе в зависимости от
сложившейся ситуации. В зависимости от стратегий игры делятся на
конечные и бесконечные.
Игра
называется
конечной,
если
у
каждого
игрока
имеется
в
распоряжении только конечное число стратегий (в противном случае игра
называется бесконечной).
Процесс игры состоит в выборе каждым игроком одной своей стратегии
В результате каждой партии игры складывается система стратегий
s = (s1, s2,…, sn), которая называется ситуацией
Множество всех ситуаций обозначается S = S1, S2, …, Sn и
представляет собой декартово произведение множеств, стратегий всех
игроков

7.

Наш пример
• Игра с нулевой суммой – это игра, в которой сумма
выигрышей игроков равна нулю (т.е. каждый игрок выигрывает
только за счет других). Самый простой случай – парная игра с
нулевой суммой – антагонистическая игра, здесь два
игрока четко играют друг против друга.
• Число игроков обозначим I, I=(1, 2, …, n).
• Бескоалиционной игрой называется система , в которой число
игроков I и стратегии игрока Si являются множествами, а
платежная функция Hi – функция на множестве S,
принимающая вещественные значения
n
• Игра с нулевой суммой:
H
i 1
i
(s) 0

8.

Понятие «антагонистическая игра»
Игра
Г I ,{S i }i I ,{H i }i I
называется антагонистической, если число игроков
в ней равно 2, а значения функций выигрышей этих
игроков в каждой ситуации равны по величине и
противоположны по знаку
H1 ( s) H 2 ( s)
•Следовательно, антагонистическая игра также
является игрой с нулевой суммой

9.

Матричная игра

10.

Пример: “камень-ножницы-бумага”
• Выигрыш победившего игрока составляет 1,
проигравшего -1
• Платежная матрица в этом случае имеет следующий
вид:

11.

Платёжная матрица
• Предположим, что нам известны
значения aij при каждой паре
стратегий. Эти значения можно
записать в виде прямоугольной
таблицы
(матрицы),
строки
которой
соответствуют
стратегиям Ai, а столбцы —
стратегиям Bj.
• Тогда, в общем виде матричная
игра может быть записана
следующей платежной матрицей
B1
B2
...
Bn
A1
a11
a12
…
a1n
A2
a21
a22
…
a2n
…
…
…
…
…
Am
am1
am2
…
amn

12.

Максиминные, минимаксные стратегии
Нижней чистой ценой игры называется
max min aij
j
i
Верхней чистой ценой игры называется
min max aij
j
i
Игра, для которой , называется игрой с
седловой точкой, где v называется ценой
игры.
Задача теории игр – поиск оптимальных стратегий (решений).
Решением игры называется пара оптимальных стратегий для игроков
А и В, значение цены игры.
Наличие седловой точки означает наличие равновесия в игре.

13.

ИГРА В МАТРИЧНОЙ ФОРМЕ
Стратегии игроков:
X X1
X2
Y Y1 Y2
Платежная матрица:
... X m
a11 a12
a21 a22
A
...
...
am1 am 2
... Ym
Нижняя цена игры:
v max min aij
Верхняя цена игры:
v min max aij
j
i
j
Условие существования
седловой точки:
i
... a1n
... a2 n
... ...
... amn
max min aij min max aij
i
j
j
i
13

14.

Антагонистическая игра: X , Y , F ( x, y)
Y – множество стратегий первого игрока,
– множество стратегий второго игрока,
X
F ( x, y ) – платежная функция или функция выигрыша.
Определение. Пару ( x* , y* ) X Y называют седловой точкой
функции F ( x, y ) на X Y , если
F ( x, y* ) F ( x* , y* ) F ( x* , y ) ( x, y ) X Y
или
max F ( x, y* ) F ( x* , y* ) min F ( x* , y )
x X
y Y
Графическая интерпретация
седловой точки:
14

15.

Определение эффективных стратегий
W ( x) min F ( x, y )
y Y
- оценка эффективности стратегии x первого
игрока, или гарантированный результат
v max min F ( x, y ) - наилучший гарантированный результат для
x X y Y
первого игрока (нижняя цена игры)
x X
- максиминная стратегия первого игрока, если
*
v min F ( x* , y )
y Y
M ( y) max F ( x, y) - оценка эффективности стратегии y второго
x X
игрока, или гарантированный результат
v min max F ( x, y) - наилучший гарантированный результат для
y Y x X
y Y
*
второго игрока (верхняя цена игры)
- минимаксная стратегия второго игрока, если
v max F ( x, y* )
x X
15

16.

Справедливо неравенство:
v v
Теорема. 1) Для того, чтобы функция F ( x, y ) на X Y имела
седловую точку, необходимо и достаточно, чтобы было
выполнено равенство
max min F ( x, y) min max F ( x, y).
x X
y Y
y Y
x X
(1)
2) Пусть выполнено равенство (1). Пара ( x* , y * ) тогда и только
тогда является седловой точкой, когда x* максиминная,
а y * – минимаксная стратегии первого и второго игроков
соответственно.
16

17.

Чистые и смешанные стратегии
!!! Чистой стратегией называют ход, выбранный с
вероятностью 1.
Смешанной стратегией игрока А называется вектор
m
р ( р1 ,...... рm ) рi 0 (i 1, m),
p
i 1
i
1
Смешанной стратегией игрока В называется вектор
q (q1 ,......qn ) q j q ( j 1, n),
m
n
q
j 1
n
j
1
f ( p, q) aij p. i q j платежная функция.
i 1 j 1
Рi (0,0,0,...,1,0...) чистая стратегия
Пара стратегий
р ,q
если
называется оптимальной,
f ( p, q ) f ( p , q ) f ( p , q).

18.

Активные стратегии
Активной стратегией называется стратегия, входящая
в оптимальную смешанную стратегию с ненулевой
вероятностью.
q1 q2 qn
p1 a11 a12 a1n
p2 a21 a22 a2 n
pm am1 am 2 amn
pi вероятность применения игроком i ой стратегии
a11 p1 a21 p2 am1 pm v
a q a q a q v
1n n
11 1 12 2

19.

Решение матричной игры 2 2
p1 a11
p2 a21
q1
a22
a12
q2
a11 p1 a21 p2 v
a12 p1 a22 p2 v
p2 1 p1
a11 p1 a21(1 p1) v
a12 p1 a22 (1 p1) v
p1(a11 a21) a21 v
p1(a12 a22 ) a22 v
p1(a11 a21) a21 p1(a12 a22 ) a22
p1(a11 a21) a21 v
a22 a21
p1
аналитический метод решения
a11 a21 a12 a22
Для q : a11q1 a12 (1 q1) v
i

20.

Геометрическая интерпретация
игры 2 2
Пусть имеется два игрока А и В. У каждого из игроков по две стратегии
(А1 и А2 у игрока А, В1 и В2 у игрока В). Игра с нулевой суммой.
По оси абсцисс отложим отрезок А1А2, то есть точка А1 изображает
стратегию А1 (х=0), А2 – стратегию А2, все промежуточные точки –
смешанные стратегии. На оси ординат откладываем выигрыш
первого игрока, если второй применил стратегию В1. Аналогично
строим второй график, если второй график выбрал стратегию В2.

21.

y
B1
y
M1
B2
M2
B2
B1
a21
q1
a12
a11
q2
p2
p2
A1
x
p1
A2
A1
a22
x
p1
A2
q1=a11p1+a21p2
q2=a12p1+a22p2
(ордината точки М1 и М2, соответственно)
А1 А2 1
В соответствии с принципом минимакса оптимальная стратегия SА*
такова, что минимальный выигрыш игрока А (при наихудшем
поведении игрока В) обращается в максимум.

22.

y
B1
B2
N
B2
B1
p2
A1
SA*
(p1*, p2* )
x
p1
A2
Решение игры графическим способом
Отрезок В1N – минимальный выигрыш игрока А при
использовании любой смешанной стратегии,
если игрок В выбрал стратегию В1. Аналогично,
отрезок В2N – выигрыш игрока А,
если игрок В выбрал стратегию В2.
Следовательно, оптимальную стратегию определяет
точка N, то есть минимальный выигрыш достигает
максимума

23.

Квадратная матрица

24.

Прямоугольная матрица

25.

Пример

26.

Решение

27.

Пояснение
приравниваем v1=v4
4-8x= -1+3x; 11x=5; x=5/11
1-x= 1-5/11= 6/11
v= -1+3x = -1+3*(5/11)= 4/11
• a11=4; a12= -1; v=4/11; подставляем в формулу, получаем
q1=3/11. Аналогично q4=8/11.
• q2 и q3 = 0, поскольку эти столбцы не соответствуют точке
перечения v1=v4