1.98M
Category: mathematicsmathematics

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

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
English     Русский Rules