Игровые методы принятия решений

Теория игр

Неопределенными могут быть не только условия, в которых работает предприятие

Теория игр

ЛПР приходится считаться не только со своими собственными целями,
но

Теория игр

Теория принятия решений в условиях конфликта
или математическая теория конфликтных ситуаций

Физическая и социальная природа конфликта

юридические лица,
воюющие стороны,
спортивные команды,

Задача теории игр

выработка рекомендаций по рациональному образу действий участников конфликта

Конфликтная ситуация

Чтобы сделать возможным математический анализ ситуации, надо построить упрощенную,

Игра – это модель конфликта

Принятие решений во взаимосвязанных ситуациях:
большинство

Конфликт

Любое явление, применительно к которому имеет смысл говорить о том,

Элементы игры

I - множество игроков
Kd ⊂ I – коалиции действий,

Элементы игры

Коалиции интересов - КI ⊂ I
Заинтересованность fK(А) –
каждая

Классификация игр

1) KI≥2 –
не менее 2-х заинтересованных сторон
2) Kd=1 –

Классификация игр

по количеству игроков - игры 2 и n игроков
по

Классификация игр

Антагонистическая игра – игра двух лиц с нулевой суммой.
Матричная игра

Матричные игры

I={I,II} I: X={xi}m
II: Y={yj}n
f1(x,y) – функция выигрыша

Матричные игры

Матрица игры:

Функция выигрыша

f1(xi,yj) – результат 1-го игрока,
когда он сделал ход

В антагонистической игре цели игроков противоположны:

Цель первого игрока –

Решить игру

Найти оптимальные стратегии каждого игрока и
оценить результат,

Пример

(х1,y2)→(x2,y2)
(x2,y2) – ситуация равновесия

Х1
Х2
Х3

y1 y2 y3

Ситуация равновесия

Если один игрок придерживается стратегии, соответствующей ситуации равновесия,

Ситуация равновесия

Пусть (x*,y*) – ситуация равновесия
f1(x,y) - выигрыш 1-го игрока
f2(x,y) -

Ситуация равновесия

f1(x,y*) ≤ f1(x*,y*)
f2(x*,y) ≤ f2(x*,y*) , *(-1):
-f2(x*,y) ≥ -f2(x*,y*), но
f1(x,y)

Ситуация равновесия

Точка, выигрыш в которой первого
игрока минимален по

Гарантированный результат

ν1= maxx miny fij –
гарантированный результат
1-го

Гарантированный результат

ν2= min max fij -
y x
гарантированный результат
2-го игрока

Гарантированные результаты

ν1=ν –
нижняя цена игры,
ν2= –

Th. Неравенство минимаксов

ν ≤ , или

≤

Доказательство

≤
- по свойству с.р.
Но если f(x)то min

Неравенство минимаксов

Если функция ограничена сверху константой, то и максимум этой

Ситуация равновесия

ν1= maxx miny fij
ν2= miny maxx fij
Если ν1=

Седловая точка

Пример

ν1=2

ν2=2

Седловая точка

Седловых точек в игре может быть несколько, причем

Принцип достижимости целей

Стремление игроков к ситуации равновесия, описываемой седловой точкой,

Существуют ли оптимальные решения в играх без седловых точек?

Теорема Неймана

Пример

6 8

__________________

2
4

= 4; =6.
ν∈ [4;6]
ν – цена

Игры с закрытой информацией

В играх без седловой точки свои

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

Правильное поведение состоит в том, чтобы стратегию

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

Случайная величина, значениями которой являются чистые стратегии игрока.

Смешанная стратегия
Р= - смешанная
стратегия первого игрока,

или вероятностное

Смешанная стратегия
Q=

- cмешанная
стратегия
второго игрока,

Q = (q1, q2, …,

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

Применение смешанной стратегии - это гибкая тактика,
при

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

Любая чистая стратегия является частным случаем смешанной:
например,

Алгоритм решения игры

Упростить игру.
Найти гарантированные результаты для каждого игрока.
Если существует седловая

Решение игр 2х2
А=

- платежная матрица

Решение игры будем искать
в смешанных

Решение игр 2х2

Это значит, что первый игрок будет применять свою первую

Пример

P1
p2

q1 q2

Мν=6p1q1+2p1q2+4p2q1+8p2q2
p2=1-p1, q2=1-q1

Мν= 6p1q1+2p1(1-q1)+4(1-p1)q1+8(1-p1)(1-q1)=

ν∈ [4;6]

=-6p1-4q1+8+8p1q1=
=8(p1-1/2)(q1-3/4)+5
Ответ:
P={1/2; 1/2}; Q={3/4; 1/4}; ν=5

Решение игр 2х2

Решим игру в общем виде с точки зрения второго

Решение игр 2х2

(а11-а21)⋅q1+(a12-а22)⋅q2=0,
затем, учитывая, что q2=1-q1,
получим
(а11-а21-а12+а22)⋅q1+(a12-а22)=0.
Отсюда

С точки зрения первого игрока

а11⋅p1+a21⋅p2=ν - при первой стратегии

Пример

Матрица игры А=
Составим систему уравнений для второго игрока:
6q1+2q2=ν
4q1+8q2=ν

Пример

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

Решение примера методом Крамера

А= ,
ее определитель ⏐А⏐=6⋅8-4⋅2=40.
Тогда

Решение примера методом Крамера

Вероятности P можно найти аналогично,
но

Решение игр 2×n и m×2

Если один из игроков

Решение игр 2×n

У первого игрока - 2 стратегии,
у второго

Решение игр 2×n

Матрица игры:
p2=1-p1
ν1=a11 p1+a21 p2= a21+(a11-a21)p1
ν2=a12 p1+a22 p2= a22+(a12-a22)p1

Графо-аналитический метод

Линейные функции ν1, ν2,…,νn отражают зависимость
среднего выигрыша

Гарантированный результат первого игрока
ν= max min{a2j+(a1j – a2j)p1}
i j

Чтобы обеспечить себе гарантированный результат,

первый игрок должен выделить
нижнюю

Решение игры

Соответствующая абсцисса равна вероятности применения первым игроком
его первой стратегии,

Пример

Решить игру А=

=1,

=3

Решаем ее с точки зрения

6
5
4
3
2
1
0

ν 4

ν2

ν3

ν1

0 Р1* 1 р1

ν

Решение игры

Верхняя точка границы

образована пересечением прямых ν3 и ν2
(р1*,

Для 2-го игрока

стратегии y1 и y4 – неактивные, т.к. не

Решение игр m×2

У 1-го игрока m стратегий,
у 2-го

Решаем с точки зрения того игрока, который имеет 2 стратегии, т.е.

Средний проигрыш 2-го игрока

ν1=a11 q1+a12 q2=a11+(a11 - a12)q1
…
νm=am1q1+am2q2=am1+(am1 - am2)q1

Гарантированный результат второго игрока

Средний проигрыш 2-го игрока

В семействе прямых, описывающих средний проигрыш 2-го

Смешанная стратегия 1-го игрока

Активными стратегиями первого игрока будут те, которые

Пример

Матрица игры

Средний проигрыш 2-го игрока
ν1=4q1+2q2 = 4q1 +2(1-q1)= 2+2q1,
ν2=2 q1+5q2=

Смешанная стратегия 2-го игрока

(q1*, ν) ∈ ν1∩ν3 ⇒
2+2q1=4-q1,

0

Смешанная стратегия 1-го игрока

Из матрицы А*

p1=

=

=

Ответ: Q=(2/3; 1/3), ν=10/3, P=(1/3;

Решение игр mxn

X={xi}m – стратегии 1-го игрока
Y={yj}n – стратегии 2-го

Первый игрок

Найдем сначала оптимальную стратегию Р.
Она должна обеспечить

Пусть ν>0

Чтобы это выполнялось, достаточно, чтобы все элементы матрицы

для любого j

Введем обозначения: xi=pi/ν, тогда

Выбор должен быть максимально возможным, следовательно,

Второй игрок

Все аналогично решению игры для первого игрока, только второй

для любого i.

для любого i.

Заменим yj=qj/ν, тогда

Σyj=1/ν

Требуется

Симметричные игры

Опр. Квадратная матрица А={aij} называется кососимметричной, если aij= -

Tеорема

Значение симметричной игры равно нулю.
Кроме того, если х

Пример

По теореме ν=0;
т.к. P=Q,
то
найдем

Средний выигрыш 1-го игрока

-р2+2р3=0 → р2=2р3
р1 -3р3=0 →

Метод итераций Брауна-Джонсона

Разыгрывается мысленный эксперимент, в котором 1-ый и 2-ой применяют

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

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

Например,
размещение заказа на разных предприятиях
установление цены на продукцию
оснащение производства современным

Тактические задачи

- В задачах поиска наилучших способов использования потенциала системы

Физическая смесь стратегий

В задачах выбора рациональных параметров («технических»)
случайный подбор

- создание уникальных систем;
строительство капитальных сооружений;
крупносерийное производство и
другие долгосрочные

Модель комплектации вычислительного центра

Предполагается организовать ВЦ коллективного пользования, который может

Обработка требует определенного времени, зависящего от характеристик используемой ЭВМ, сложности

Цели

1 –ый игрок (организаторы ВЦ)
стремится увеличить приток средств от

400р3+700р4=ν1= 700-300р3
500р3+200р4=ν4= 200+300р3
800р3+100р4=ν5= 100+700р3

Решение

Р=(0; 0; 5/6; 1/6)
ν=450
Количество ЭВМ оценивается с помощью методов ТМО

Замечание

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

После того, как с помощью матричной игры оценили личные стратегические

Обоснование решений с использованием биматричных игр

Антагонистические игры не описывают конфликты с

Игры двух лиц с произвольной суммой (бескоалиционные)

1-ый игрок: {хi}m=Х
2-ой игрок: {yj}n=Y
A={aij}

Решение игры

С точки зрения первого игрока его средний выигрыш

Решение игры

A=

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

Мν1=

∑aij qj ≤ ∑∑aijpiqj ,
j i j
n
∑qj=1, для

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

Мν2=

M m n m
∑bij pi ≤ ∑∑bijpiqj

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

Пример

А= В=
р1= =
р2= = ν1= - 4/7
Р=(1/7; 6/7).

Для 2-го игрока

Матрица В содержит выигрыши 2-го игрока, цель которого

A={aij}, B={bij}
(A,B)={(aij,bij)}

ОБОЗНАЧЕНИЯ

Редко удается предсказать исходы Б. игр

Отсутствие связи между платежами сторон (нет

В неантагонистической игре отклонение игрока от с.р. может по-разному повлиять на

Теорема Нэша

Каждая биматричная игра имеет по крайней мере одну ситуацию

Только равновесные ситуации могут быть предметом результативных переговоров

Необходим анализ игры

Пример 1. Переговоры по сокращению объема продукции

y1 y2

x1
x2

1 – настаивать

Пример 2. Переговоры о масштабах сокращения объема продукции

Альтернативы
1 – выпуск на

В отсутствие контроля
ни одна из сторон не пойдет

Б. Действенные меры контроля
(разработана система штрафов за нарушение договоренностей)

(3;3)

Ситуация Равновесия по Нэшу -

схема анализа, когда никакое кооперирование не

Во многих случаях полезны и даже необходимы контакты и соглашения между

Кооперативная игра

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

«Справедливый дележ» по Нэшу

«начало отсчета» - (ν1*, ν2*) - минимальный результат,

Мультипликативная целевая функция φ(ν1, ν2) моделирует допустимую компенсацию уменьшения одних

Если кто-то из игроков не удовлетворен компромиссным решением, он может

Применение стратегии угроз
(реальная или провозглашенная в качестве возможной альтернатива

Эффективность стратегии угрозы

определяется
результатом истинного воздействия на физический объект (изменение состояния

Пример

(1;4) (-2;-4)
(-3;-1) (4;1)

4

-3

-4

1

4

Пусть стратегия угроз 1-го – х2
Тогда 2-ой

Решение

φ(ν1,ν2)=- (ν1)↑2+3ν1+18
φ’(ν1)=-2ν1+3=0
ν’1=1,5; ν’2=3,5

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