Тырсин А.Н. - Системный анализ. Модели и методы (без обложки)

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

6.3.1. Основные понятия матричных игр

Введем основные понятия матричных игр.

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

-возможные действия каждого из игроков;

-объем информации (степень информированности) каждой стороны о поведении всех других сторон;

-исход игры при данном варианте действия.

Игрок – одна из заинтересованных сторон в игровой ситуации.

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

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

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

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

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

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

-все игроки разумны в равной степени;

-поведение игроков направлено на достижение своих целей и противодействие другим игрокам в достижении их целей.

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

91

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

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

Количество стратегий игры. По этому критерию игры делятся на конечные и бесконечные. В конечной игре каждый из игроков имеет конечное число возможных стратегий. Если хотя бы один игрок имеет бесконечное число возможных стратегий, то игра является бесконечной.

Взаимоотношения сторон. Согласно данному критерию игры делятся на кооперативные, коалиционные и бескоалиционные. Если игроки не имеют право вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалиционным; если игроки могут вступать в соглашения,

создавать коалиции – коалиционной. Кооперативная игра – это игра, в

которой заранее определены коалиции.

Характер выигрышей. Этот критерий позволяет классифицировать игры с нулевой и с ненулевой суммой. Игра с нулевой суммой предусматривает условие: «сумма выигрышей всех игроков в каждой партии равна нулю». Игры двух игроков с нулевой суммой относят к классу антагонистических. В противном случае имеем игру с ненулевой суммой.

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

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

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

Если функция выигрышей каждого игрока является непрерывной, игра считается непрерывной. Если функция выигрышей выпуклая, то и игра – выпуклая.

Количество ходов. По этому критерию игры делятся на одношаговые и многошаговые. Одношаговые игры заканчиваются после одного хода каждого игрока. Многошаговые игры бывают позиционными, стохастическими, дифференциальными и др.

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

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

92

Пусть игрок 1 имеет m стратегий Ai (i =1, , m), а игрок 2 – n стратегий Bj (j = 1, , n). Игра может быть названа игрой m n. Тогда имеем платежную матрицу игры двух лиц с нулевой суммой (табл. 6.1).

Таблица 6.1. Платежная матрица матричной игры m n

Игрок 2	B1	B2		Bn
Игрок 1					i
A1	a11	a12		a1n	1
A2	a21	a22		a2n	2
Am	am1	am2		amn	m
j	1	2		n

Игра G, описываемая платежной матрицей

a11	a12	...	a1n
a21	a22	...	a2n		,	(6.1)
G ...	...	...	...
	am2	...
am1			amn

заключается в следующем. Игрок 1 выбирает стратегию Ai (i-я строка матрицы G), а игрок 2 выбирает стратегию Bj (j-й столбец матрицы G). После этого игрок 1 получает выигрыш aij. Игрок 2 получает выигрыш aij. Если выигрыш отрицателен, то это говорит о проигрыше этого игрока.

Величины i, (i =1, , m) и j, (j = 1, , n) – соответственно минимальные значения элементов aij по строкам и максимальные – по столбцам.

Оценки игры. Рассмотрим матричную игру, представленную матрицей выигрышей (6.1) [28]. Применяется принцип получения максимального гарантированного результата при наихудших условиях. Игрок 1 стремится принять такую стратегию, которая должна обеспечить максимальный проигрыш игрока 2. Соответственно игрок 2 стремится принять стратегию, обеспечивающую минимальный выигрыш игрока 1. Требуется рассмотреть оба этих подхода.

Подход игрока 1. Он должен получить максимальный

гарантированный результат при наихудших условиях: i min aij .

j

Чтобы этот гарантированный эффект в наихудших условиях был максимальным, нужно из всех i выбрать наибольшее значение. Обозначим его и назовем чистой нижней ценой игры («максимин»):

max i max min aij .

ii j

93

Таким образом, максиминной стратегии отвечает строка платежной матрицы G, которой соответствует элемент . Какие бы стратегии ни применял игрок 2, игрок 1 максиминной чистой стратегией гарантирует себе выигрыш не меньше чем . Таково оптимальное поведение игрока 1.

Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каждой j-й чистой стратегии

он отыскивает величину своего максимального проигрыша j	max aij в
	i

каждом j-м столбце, то есть определяет максимальный выигрыш игрока 1, если игрок 2 применит j-ю чистую стратегию. Из всех своих n j-х чистых стратегий он отыскивает такую, при которой игрок 1 получит минимальный выигрыш, то есть определяет чистую верхнюю цену игры

(«минимакс»): min j min max aij .
j	j i

Чистая верхняя цена игры показывает, какой максимальный выигрыш может гарантировать игрок 1, применяя свои чистые стратегии, выигрыш, не меньший, чем . Игрок 2 за счет выбора своих чистых стратегий не допустит, чтобы игрок 1 мог получить выигрыш, больший, чем . Таким образом, минимаксная стратегия отображается столбцом платежной матрицы G, в котором находится элемент . Она является оптимальной чистой, гарантирующей стратегией игрока 2, если он ничего не знает о действиях игрока 1. Нетрудно показать, что .

Чистая цена игры – цена данной игры, если нижняя и верхняя ее

цены совпадают: max min aij min max aij .
i j	j i

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

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

	1	0	4
	5	3	8
G
	7	2	1

и указать максиминную и минимаксную стратегии. Решение. Определим нижнюю и верхнюю цены игры:

1 = 1, 2 = 3, 3 = 1, = 3; 1 = 7, 2 = 3, 3 = 8, = 3.

Таким образом, = = = 3 – чистая цена игры при стратегиях A2 и B2. Игра имеет седловую точку.

Пример 6.2. Дана матрица игры

G	3	5	8	6	11
						.
	8	4	12	7	9

94

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

Решение. Определим нижнюю и верхнюю цены игры:

1 = 3, 2 = 4, = 4; 1 = 8, 2 = 5, 3 = 12, 4 = 7, 5 = 11, = 5.

Таким образом, = 4 < = 5. Седловой точки не существует. Поэтому ситуации равновесия в чистых стратегиях нет.

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

Пример 6.3. Пусть в примере 6.2 игроку 1 стало известно, что игрок 2 принял минимаксную стратегию. Игрок 1 должен выбрать оптимальную стратегию при условии, что В2 – стратегия игрока 2.

Решение. Оптимальной стратегией для игрока 1 в этом случае будет не максиминная А2, дающая игроку 1 выигрыш α = 4, а та стратегия,

которая соответствует max ai2 5 . Поэтому максимальный выигрыш

i

игрока 1 будет равен верхней цене игры β = 5 , поэтому он выберет свою оптимальную стратегию А1, зная, что игрок 2 выбрал свою стратегию В2. Таким образом, рассмотренный пример дает результат, отличный от результата при игре с седловой точкой.

Стратегия матричной игры является оптимальной, если ее

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

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

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

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

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

95

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

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

Смешанная стратегия игрока – это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Перечислим условия применения смешанных стратегий:

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

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

-игра многократно повторяется в сходных условиях;

-при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

-допускается осреднение результатов игр.

Применяются следующие обозначения смешанных стратегий.

Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий A1, A2, … , Am с соответствующими вероятностями p1, p2, , pm:

A1

A2

Am

,

m

p

1, 0 p 1.

S

i

1

p

p

p

i

2

m

i 1

1

Для игрока 2:

S

B1

B2

Bn

,

n

q

1, 0 q

1,

2

j

j

q

q

q

2

n

j 1

1

где qj – вероятность применения чистой стратегии Bj.

Чистые стратегии игрока являются единственно возможными несовместными событиями. Например, в случае, когда pi = 1, для игрока 1 имеем чистую стратегию

	A1		A2		Ai		Am
S								.
1		0	0		1		0

В матричной игре, зная матрицу G (она относится и к игроку 1, и к игроку 2), при заданных векторах p и q можно определить средний математическое ожидание выигрыша игрока 1:

m n

M(G,p,q) aij pi q j ,

i 1 j 1

где pi и qj – компоненты векторов p и q.

Путем применения своих смешанных стратегий игрок 1 стремится максимально увеличить свой средний выигрыш, а игрок 2 – довести этот эффект до минимально возможного значения.

96

Игрок 1 стремится достигнуть min max M(G, p, q) .

q p

Игрок 2 добивается того, чтобы max minM(G,p,q) .

p q

Обозначим p0 и q0 – векторы, соответствующие оптимальным смешанным стратегиям игроков 1 и 2, то есть, при которых будет выполнено равенство

min max M(G, p, q) max min M(G, p, q) M(G, p0 , q0 ) .

q

p

p

q

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

1)p0 – оптимальная смешанная стратегия игрока 1;

2)q0 – оптимальная смешанная стратегия игрока 2;

3)цена игры.

Смешанные стратегии будут оптимальными (p0 и q0), если они образуют седловую точку для функции M(G,p,q) , то есть

M(G,p,q0 ) M(G,p0 ,q0 ) M(G,p0 ,q) .

Существует основная теорема матричных игр (без доказательства).

Теорема 6.1. Для матричной игры с любой матрицей G величины

max minM(G,p,q) и min max M(G, p, q)

p q q p

существуют и равны между собой: = = .

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

6.3.3. Частные случаи решения задач в смешанных стратегиях

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

97

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

A1

A2

B1

B2

S

, S

2

.

1

p

p

q

q

2

2

1

1

a11

a12

Значит, имеется платежная матрица G

. При этом

a21

a22

a11 p1 a21 p2 ; a12 p1 a22 p2 ;

p1 p2 1.

Решив систему из трех последних уравнений, получаем оптимальные

значения p0 ,

p0

и :

1

2

p

0

a22 a21

;

1

a11

a22 (a12 a21 )

p

0

1 p0

a11 a12

;

2

1

a11

a22 (a12 a21 )

a p0

a

p0

a11a22 a12 a21

.

21

11

1

2

a11 a22 (a12 a21 )

Вычислив , находим q0

и q0 из решения системы двух уравнений:

1

2

a11q1 a12 q2 ;

q1 q2 1.

Имеем: q0

a12

; q

0

1 q0

a11

, при a

a .

1

a11 a12

2

1

a11 a12

11

12

Задача решена, т.к. найдены векторы p0

p0

, q0

q0

и цена игры .

1

1

0

0

p2

q2

Решим задачу графически. Алгоритм решения весьма прост (рис. 6.1):

1.По оси абсцисс откладывается отрезок единичной длины.

2.По оси ординат откладываются выигрыши при стратегии A1.

3.На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии A2.

4.Концы отрезков обозначаются для a11 – b11, a12 – b21, a22 – b22, a21 – b12 и проводятся две прямые (b11 b12) и (b21 b22).

5.Определяется ордината точки пересечения с. Она равна . Абсцисса

точки с равна p2 (p1 = 1 – p2).

Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр m n, состоящем в том, что в любой игре m n каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства

98

можно получить известное следствие: в любой игре 2 n и m 2 каждая

оптимальная стратегия S10	и S02	содержит не более двух активных
стратегий. Значит, любая игра 2 n и m			2 может быть сведена к игре
2 2. Следовательно, игры	2 n	и m 2	можно решить графическим
методом.

Рис. 6.1. Оптимальная смешанная стратегия

Если матрица G игры имеет размерность m n, где m > 2 и n > 2, то для определения оптимальных смешанных стратегий используют линейное программирование или итеративные алгоритмы [20].

Пример 6.4. Выбрать оптимальный режим работы новой системы ЭВМ, состоящей из двух ЭВМ типов A1 и A2. Известны выигрыши от внедрения каждого типа ЭВМ в зависимости от внешних условий, если сравнить со старой системой. При использовании ЭВМ типов A1 и A2 в зависимости от характера решаемых задач B1 и B2 (долговременные и краткосрочные) будет разный эффект. Предполагается, что максимальный выигрыш соответствует наибольшему значению критерия эффекта от замены вычислительной техники старого поколения на ЭВМ A1 и A2.

Дана матрица игры (табл. 6.2), где A1 и A2 стратегии руководителя; B1 и B2 стратегии, отражающие характер решаемых на ЭВМ задач.

Требуется найти оптимальную смешанную стратегию руководителя и гарантированный средний результат у, то есть определить, какую долю времени должны использоваться ЭВМ типов A1 и A2.

99

Таблица 6.2. Платежная матрица матричной игры 2 2

	Игрок 2	B1	B2	i
	Игрок 1
	A1	0,3	0,8	0,3
	A2	0,7	0,4	0,4
	j	0,7	0,8

Решение. Запишем условия в принятых индексах:

a11 = 0,3; a12 = 0,8; a21 = 0,7; a22 = 0,4.

Определим нижнюю и верхнюю цены игры:

1 = 0,3, 2 = 0,4, = 0,4; 1 = 0,7, 2 = 0,8, = 0,7.

Получаем игру без седловой точки, так как

max min aij a22 0,4	< min max aij a21 0,7 .
i j	j i

Максиминная стратегия руководителя вычислительного центра – A2. Для этой стратегии гарантированный выигрыш равен = 0,4 (40%) по сравнению со старой системой. Решение для определения , p1 и p2 проведем графически (рис. 6.2).

Рис. 6.2. Графическая интерпретация алгоритма решения

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

1.По оси абсцисс отложим отрезок единичной длины.

2.По оси ординат отложим выигрыши при стратегии A1.

3.По вертикали в точке 1 отложим выигрыши при стратегии A2.

4.Проводим прямую (b11 b12), соединяющую точки a11, a21.

5.Проводим прямую (b21 b22), соединяющую точки a12, a22.

100