Игровые модели. Примеры

1.

ИГРОВЫЕ МОДЕЛИ

2.

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

3.

ПРИМЕРЫ (ВООБЩЕ):
Боевые действия армий в военном конфликте
Выборы в парламент при наличии нескольких
кандидатов на одно место
Межвидовая борьба в природе
Разнообразные спортивные игры
и др.

4.

ПРИМЕРЫ В ЭКОНОМИКЕ:
борьба фирм за рынки сбыта
явления олигополии
планирование рекламных компаний
формирование цен на конкурентных рынках
биржевая игра
и др.

5.

ЗАДАЧА:
провести научный анализ обобщенной конфликтной
ситуации и попытаться выработать разумные
правила поведения для ее участников.
Именно этим и занимается теория игр математическая теория конфликтных ситуаций.
В ней под игрой понимается математическая модель
конфликтной ситуации

6.

Теория игр впервые была систематически
изложена Дж. фон Нейманом и О. Моргенштерном
в 1944 году в книге «Теория игр и экономическое
поведение»

7.

ОСНОВНЫЕ СОСТАВЛЯЮЩИЕ
ЛЮБОЙ ИГРЫ
1) Множество конфликтующих сторон (игроков):
I={P1, P2,…,Pn}
2) Cовокупности множеств стратегий каждого из игроков
{Si}iєI
3) Cовокупности функций выигрыша каждого из игроков
{Hi}iєI

8.

ПОЯСНЕНИЯ:
Стратегия игрока - одна из возможных линий
поведения в течение одной партии (однократном
осуществлении игры)
Ситуация – набор стратегий всех игроков
Выигрыш игрока - степень удовлетворения его
интересов в данной ситуации

9.

ПРЕДПОЛАГАЕТСЯ:
Функции выигрыша и множества стратегий игроков
общеизвестны.
В соответствии с этой информацией каждый из
участников игры и организует свое поведение,
стремясь обеспечить себе максимально возможный
выигрыш при любых действиях партнеров

10.

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

11.

Наиболее изученный класс игр - класс
матричных игр

12.

ОПИСАНИЕ МАТРИЧНОЙ ИГРЫ
В игре участвуют 2 игрока: А и В
Каждый из игроков располагает конечным набором стратегий:
А1,…,Аm и В1,…,Вn - возможные стратегии игроков А и В
(Аi,Bj) – возможные ситуации в игре
Значения функций выигрыша НА и НВ игроков в каждой ситуации
равны по величине и противоположны по знаку, то есть
НА(Аi,Bj)=-HB(Ai,Bj)= aij
(выигрыш одного из игроков равен проигрышу другого)
(антагонизм!)

13.

ОЧЕВИДНО
задание матричной игры эквивалентно заданию всех
значений функции выигрыша одного из игроков
(например, игрока А) в виде так называемой платежной
матрицы или матрицы игры:
a11
a 21
H
...
a m1
a12
a 22
...
am2
... a1n
... a 2 n
... ...
... a m n

14.

В ЭТОЙ МАТРИЦЕ:
Строки – стратегии игрока А
Столбцы – стратегии игрока В
Элементы aij - выигрыши игрока А в ситуации, когда А
выбирает стратегию Аi, а В – стратегию Вj

15.

ПРИМЕР:
Каждый из двух игроков А и В независимо друг от
друга кладет на стол монету в 1 рубль или в 2 рубля.
Если монеты одинаковые, то выигрывает игрок А,
если разные - игрок В. Выигрыш равен сумме
достоинств монет. Необходимо построить
платежную матрицу игры

16.

ОТВЕТ:

17.

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

18.

ТОНКОСТЬ:
для многих естественных классов игр выбор
удовлетворительного принципа оптимальности
весьма затруднителен, не говоря уже о поиске
оптимальных стратегий игроков

19.

Для матричных игр основной принцип оптимальности
– принцип минимакса:
«поступайте так, чтобы при наихудшем для вас
поведении противника получить максимальный
выигрыш»
или:
«выбирайте наилучшее из наихудшего»

20.

РЕАЛИЗАЦИЯ ПРИНЦИПА МИНИМАКСА
Для игрока А:
- в каждой строке находим минимальный элемент;
- из этих минимальных элементов выбираем максимальный
α=maxi minj aij
Для игрока В:
- в каждом столбце находим максимальный элемент;
- из этих максимальных элементов выбираем минимальный
β=minj maxi aij

21.

α - нижняя цена игры, или максимин.
Это гарантированный выигрыш игрока А при любой стратегии
игрока В.
Стратегия, соответствующая максимину, называется
максиминной стратегией (их может быть несколько).
β - верхняя цена игры, или минимакс.
Это - гарантированный проигрыш игрока В (β с обратным
знаком - гарантированный выигрыш игрока В).
Стратегия, соответствующая минимаксу, называется
минимаксной стратегией

22.

ВОПРОС:
Можно ли считать таким образом
найденные максиминные и
минимаксные стратегии игроков
безусловно оптимальными для них?

23.

Имеются две принципиально
различные ситуации:
1) α=β
2) α<β

24.

ПРИМЕР 1

25.

1 СИТУАЦИЯ:
α=β=v
общее значение v называют ценой игры,
соответствующие стратегии - оптимальными чистыми стратегиями,
их совокупность - решением.
При этом решение игры обладает очень важным свойством
устойчивости: если один из игроков придерживается своей
оптимальной стратегии, то для другого игрока не может
быть выгодным отклоняться от своей оптимальной
стратегии.
(седловая точка!)

26.

ПРИМЕР 2

27.

2 СИТУАЦИЯ
α<β
Пара, состоящая из максиминной и минимаксной стратегий
игроков, вряд ли может считаться вполне оптимальной для
них, т.к. не выполняется условие устойчивости
Как быть?

28.

СМЕШАННОЕ РАСШИРЕНИЕ ИГРЫ
Пусть матричная антагонистическая игра двух игроков А и В задана
платежной матрицей
a11 a12 ... a1n
a 21 a 22 ... a 2 n
H
... ... ... ...
a m1 a m 2 ... a m n
Предположим также, что игра состоит из большого числа партий.
Поэтому, стремясь к максимизации суммарного выигрыша, каждый игрок
может свои стратегии «смешивать», чередуя с какой-либо частотой.

29.

СМЕШАННЫЕ СТРАТЕГИИ
Смешанной стратегией игрока А назовем неотрицательный вектор вида:
SA=(p1,p2,…, pm),
где pi - вероятность применения игроком А стратегии Ai,
причем р1+р2+…+pm=1
Смешанной стратегией игрока В назовем неотрицательный вектор вида:
SВ=(q1, q2,…, qn),
где qj - вероятность применения игроком А стратегии Ai,
причем q1+q2+…+qn=1

30.

Пусть игроки А и В независимо друг от друга выбрали
соответственно стратегии SA и SB.
Тогда средний выигрыш игрока А составит:
HA(SA,SB)=∑i∑j aij*pi*qj
Cредний выигрыш игрока B:
HB(SA,SB)= -HA(SA,SB)
Руководствуясь принципом минимакса, каждый игрок
стремится в наибольшей степени увеличить свой
гарантированный средний выигрыш.

31.

ПОЛУЧАЕМ
αS=maxSA minSB HA(SA,SB) - значение гарантированного
среднего выигрыша игрока А в одной партии (аналог
нижней цены игры в случае чистых стратегий)
βS=minSB maxSF HA(SA,SB) - значение гарантированного
среднего проигрыша игрока В в одной партии (аналог
верхней цены игры в случае чистых стратегий)

32.

ОСНОВНОЙ РЕЗУЛЬТАТ ТЕОРИИ
МАТРИЧНЫХ ИГР (ТЕОРЕМА ФОН
НЕЙМАНА)
Для матричной игры с любой платежной матрицей Н
величины αS и βS существуют и равны между собой.
Более того, существует хотя бы одна пара смешанных
стратегий SA* и SB*, для которых выполняется:
Н(SA*,SB*)= αS = βS .

33.

Стратегии SA* и SB* называются оптимальными
смешанными стратегиями;
пара таких стратегий – решением игры в
смешанных стратегиях,
а общее значение vS для αS и βS - ценой такой
игры.
Если vS=0, то игра называется справедливой

34.

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

35.

СВОЙСТВО 1
Игры, заданные платежными матрицами
одинаковой размерности, элементы которых
связаны линейным соотношением имеют
одинаковые решения в смешанных стратегиях.
Цены таких игр связаны тем же соотношением

36.

СВОЙСТВО 2
Для любой матричной игры справедливо
двойное неравенство:
α≤vS≤β

37.

МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР.
МЕТОД 1. ИГРЫ 2Х2
a11 a12
.
H
a 21 a 22
р1=(а22–а21)/(а11+а22–а12–а21),
р2=1–р1
q1=(a22–a12)/(a11+a22–a12–a21),
q2=1–q1
vS=(a22·a11-a12·a21)/(a11+a22–a12–a21)

38.

ПРИМЕР
Найти оптимальные смешанные стратегии
игроков в игре про монеты. Справедлива ли эта
игра?

39.

МЕТОД 2. УПРОЩЕНИЕ ИГР С ПОМОЩЬЮ
ОТБРАСЫВАНИЯ ДОМИНИРУЕМЫХ
СТРАТЕГИЙ
Стратегия Аi игрока А называется доминирующей над
стратегией Аk (а стратегия Аk доминируемой стратегией Аi),
если все элементы i-й строки платежной матрицы не меньше
соответствующих элементов k-й строки
Стратегия Вj игрока В называется доминирующей над
стратегией Вl (а стратегия Вl - доминируемой стратегией Вj),
если все элементы j-го столбца платежной матрицы не
больше соответствующих элементов l-го столбца

40.

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

41.

ПРИМЕР:

42.

МЕТОД 3. ГРАФИЧЕСКИЙ МЕТОД
Применяется для решения игр 2хn и mx2

43.

МЕТОД 4. СВЕДЕНИЕ ИГРЫ К ЗАДАЧЕ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задача ЛП для игрока А
Найти неотрицательные значения x1, x2,…, xm, которые удовлетворяют
линейным ограничениям – неравенствам
и обращают в минимум целевую функцию L=x1+x2+…+xm

44.

Задача ЛП для игрока В
Найти неотрицательные значения у1, у2,…, уn, которые удовлетворяют
линейным ограничениям – неравенствам
и обращают в максимум целевую функцию L=у1+у2+…+уn

45.

Пусть (x1*,x2*,…,xm*) - некоторое решение первой задачи,
L* - минимальное значение целевой функции.
Тогда цена игры vS=1/L*, а компоненты оптимальной
стратегии игрока А равны: pj*=xj*/L*
Пусть (у1*,у2*,…,уn*) - некоторое решение второй задачи,
L* - максимальное значение целевой функции .
Тогда цена игры vS=1/L*, а компоненты оптимальной
стратегии игрока В равны: qi*=yi*/L*

46.

ВАЖНОЕ ДОПОЛНЕНИЕ
Формулы справедливы только, когда цена игры >0.
Если это не так, то предварительно необходимо
преобразовать исходную матрицу, прибавив, например, ко
всем элементам модуль наименьшего отрицательного
элемента.

47.

МЕТОД 5. МЕТОД БРАУНАРОБИНСОН
Основная идея:
Разыгрывается «мысленный» эксперимент, в котором игроки А и В
поочередно применяют друг против друга свои стратегии, стремясь
выиграть побольше.
При этом каждый игрок при выборе очередной стратегии ориентируется
не на оптимальный выигрыш относительно последней стратегии
противника, а на оптимальный «накопленный» выигрыш за все
предыдущие ходы.
Приближенные оптимальные стратегии игроков определяются
относительными частотами применения ими чистых стратегий.

48.

ПРИМЕР:
Найти приближенное решение игры, заданной матрицей

49.

РЕАЛИЗАЦИЯ МЕТОДА
k
Ai
B1
B2
B3
Bj
A1
A2
A3
v*
v*
vS
1
2
3
4
5
6
7
8
9
10
11
12
1
A3
7
5
4*
B3
8*
2
4
4.00
8.00
6.00
2
A1
10*
11
12
B1
11*
11
11
5.00
5.50
5.25
3
A1
13*
17
20
B1
14
20*
18
4.33
6.67
5.55
4
A2
22
21*
22
B2
20
24*
23
5.25
6.00
5.63
5
A2
31
25
24*
B3
28*
26
27
4.80
5.60
5.20
6
A1
34
31*
32
B2
34*
30
32
5.17
5.67
5.32
7
A1
37*
37
40
B1
37
39*
39
5.29
5.86
5.58
8
A2
46
41*
42
B2
43
43
44*
5.13
5.50
5.31
9
A3
53
46*
46
B2
49*
47
49
5.11
5.37
5.24
10
A1
56
52*
54
B2
55*
51
54
5.20
5.50
5.35
…
…
…
…
…
…
…
…
…
…
…
…

50.

ОТВЕТ:
SA≈(0.5, 0.3, 0.2), SB≈(0.3, 0.5, 0.2), VS≈5,35
Для сравнения точное решение:
SA*=(0.4, 0, 0.6), SB*=(0.2, 0.8, 0), vS=5.4

51.

ДВА ВЫВОДА О МЕТОДЕ БРАУНА
1) Метод Брауна позволяет сравнительно просто
находить приближенные решения матричных игр,
причем трудоемкость метода с увеличением
размерности игры возрастает незначительно
2) Сходимость приближенных решений,
рассчитанных методом Брауна, к точному решению
происходит довольно медленно