Методы и модели теории игр

3.4.1. Основные понятия теории игр

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

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

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

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

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

Ходом в теории игр называется выбор одного из предусмотренных правилами действия и его реализацию.

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

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

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

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

В зависимости от причин, вызывающих неопределенность исходов, игры можно разделить на следующие основные группы:

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

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

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

- Игра называется парной, если в игре участвуют два игрока.

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

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

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

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

- Одношаговые игры, когда игрок выбирает одну из стратегий и делает один ход.

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

- Деловые игры имитируют организационно-экономические взаимодействия в различных организациях и предприятиях. Преимущества игровой имитации перед реальным объектом таковы:

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

- Переменный масштаб времени;

- Повторение имеющегося опыта с изменением установок;

- Переменный охват явлений и объектов.

Элементами игровой модели являются:

- Участники игры.

- Правила игры.

- Информационный массив, отражающий состояние и движение моделируемой системы.

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

3.4.2. Постановка игровых задач

Рассмотрим конечную парную игру с нулевой суммой. Игрок А имеет m стратегий (А₁ А₂ А_m), а игрок В – n стратегий (В₁, В₂ Вn). Такая игра называется игрой размерностью m х n. Пусть а_ij - выигрыш игрока А в ситуации, когда игрок А выбрал стратегию А_i, а игрок В выбрал стратегию В_j. Выигрыш игрока в данной ситуации обозначим b_ij. Игра с нулевой суммой, следовательно, а_ij= - b_ij. Для проведения анализа достаточно знать выигрыш только одного из игроков, допустим А.

Если игра состоит только из личных ходов, то выбор стратегии (А_i, В_j),однозначно определяет исход игры. Если игра содержит также случайные ходы, то ожидаемый выигрыш – это среднее значение (математическое ожидание).

Предположим, что значения а_ij известны для каждой пары стратегий(А_i, В_j). Составим прямоугольную таблицу, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. Эта таблица называется платежной матрицей.

Цель игрока А максимизировать свой выигрыш, а цель игрока В минимизировать свой проигрыш.

Будем считать все а_ij> 0.

Таким образом, платежная матрица имеет вид:

	В1	В2		Вj		Вn
А1	a11	a12		a1j		a1n	a1
А2	а21	а22		а2j		a2n	a2
Аi	аi1	аi2		аij		аin	ai
Аm	am1	аm2		аmj		amn	am
	b1	b2		bj		bn

Задача состоит в определении:

1) Наилучшей (оптимальной) стратегии игрока А из стратегий А₁ А₂ А_m;

2) Наилучшей (оптимальной) стратегии игрока В из стратегий В₁, В₂ Вn.

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

3.4.3. Методы решения игровых задач

Принцип минимакса

Проанализируем последовательно каждую стратегию игрока А. Если игрок А выбирает стратегию А₁, то игрок В может выбрать такую стратегию В_j, при которой выигрыш игрока А будет равен наименьшему из чисел a_1j. Обозначим его a₁:

a₁=min a_1j

^j

то есть a₁ – минимальное значение из всех чисел первой строки.

Это можно распространить на все строки. Поэтому игрок А должен выбрать ту стратегию, для которой число a_i - максимально.

a =max a_i

a =max min a_ij

^{i j}

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

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

Обозначим через b_j максимальное значение в каждом столбце:

b_j =max a_ij

ⁱ

Наименьшее значение b_j обозначим b.

b = min max a_ij

^{j i}

b называется верхней границей игры. Принцип, диктующий игрокам выбор игрокам соответствующих стратегий, называется принципом минимакса.

Существуют матричные игры, для которых нижняя цена игры равна верхней, такие игры называются играми с седловой точкой. В этом случае g=a=b называется чистой ценой игры, а стратегии А^*_i, В^*_j, позволяющие достичь этого значения - оптимальными. Пара (А^*_i, В^*_j)называется седловой точкой матрицы, так как элемент a_ij .= g одновременно является минимальным в i-строке и максимальным в j- столбце. Оптимальные стратегии А^*_i, В^*_j, и чистая цена являются решением игры в чистых стратегиях, т. е. без привлечения механизма случайного выбора.

Пример 1.

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

	В1	В2	В3	В4
А1					a1=2
А2					a2=1
А3					a3=4
	b1=9	b2=6	b3=8	b4=7

Здесь a₁=min a_1j=min(5,3,8,2) =2

^j

b₁= max a_i1 = max(5,1,9) =9 и так далее.

a =max min a_ij= max(2,1,4) =4

^{i j}

b = min max a_ij =min(9,6,8,7) =6

^j

таким образом, нижней цене игры (a=4) соответствует стратегия А₃.Выбирая эту стратегию, игрок А достигнет выигрыша не менее 4 при любом поведении игрока В. Верхней цене игры (b=6) соответствует стратегия игрока В. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен 4 (a₃₃).

Пример 2.

Дана платежная матрица. Найти нижнюю и верхнюю цены игры.

	В1	В2	В3
А1				a1=1
А2				a2=2
А3				a3=3
	b1=5	b2=6	b3=3

a =max min a_ij= max(1,2,3) =3

b = min max a_ij =min(5,6,3) =3

Следовательно, a =b=g=3. Седловой точкой является пара (А^*₃, В^*₃). Если матричная игра содержит седловую точку, то ее решение находится по принципу минимакса.

Решение игр в смешанных стратегиях

Если платежная матрица не содержит седловой точки (a<b), то игрок А стремится увеличить выигрыш, а игрок В – уменьшить проигрыш. Если информация о действиях противной стороны отсутствует, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией.

Для применения смешанных стратегий требуются следующие условия:

1) В игре отсутствует седловая точка.

2) Игроками используется случайная смесь чистых стратегий с соответствующими вероятностями.

3) Игра многократно повторяется в одних и тех же условиях.

4) При каждом из ходов игрок не информирован о выборе стратегии другим игроком.

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

В теории игр доказано, что любая парная игра с нулевой суммой имеет по крайней мере одно решение в смешанных стратегиях, отсюда следует, что каждая конечная игра имеет цену g. g - средний выигрыш, приходящийся на одну партию, удовлетворяющий условию a<=g<=b. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии.

Стратегии игроков в их оптимальных смешанных стратегиях называются активными.

Теорема об активных стратегиях.

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

Введем обозначения:

Р₁ Р₂ … Р_m - вероятности использования игроком А стратегий А₁ А_{2 …..} А_m;

_m

SР_i=1

ⁱ⁼¹

Q₁ Q₂ …Q_n вероятности использования игроком В стратегий В₁, В_2….. Вn

_n

S Q_i=1

ⁱ⁼¹

Смешанную стратегию игрока А запишем в виде:

А₁ А_{2 ….} А_m

S_A=

Р₁ Р₂ … Р_m

Смешанную стратегию игрока B запишем в виде:

B₁ B_{2 ….} B_n

S_B=

Q₁ Q₂ … Q_n

Зная платежную матрицу А, можно определить средний выигрыш (математическое ожидание) М(А,P,Q):

_{m n}

М(А,P,Q)=S Sa_ij Р_i Q_j

^{j=1 i=1}

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

a =max minМ(А,P,Q)

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

b = min maxМ(А,P,Q)

Обозначим через Р_А^* и Q_В^* векторы, соответствующие оптимальным смешанным стратегиям, при которых выполняется:

max minМ(А,P,Q) = min maxМ(А,P,Q)= М(А,P_А^*,Q_В^*)

При этом выполняется условие:

maxМ(А,P,Q_В^*) <=maxМ(А,P_А^*,Q_В^*)<= maxМ(А,P_А^*,Q)

Решить игру – это означает найти цену игры и оптимальные стратегии.

Геометрический метод определения цены игры и оптимальных стратегий

(Для игры 2Х2)

На оси абсцисс откладывается отрезок длиной 1.Левый конец этого отрезка соответствует стратегии А₁, правый – стратегии А₂.

По оси ординат откладываются выигрыши а₁₁ и а₁₂.

По линии, параллельной оси ординат из точки 1 откладываются выигрыши а₂₁ и а₂₂.

Если игрок В применяет стратегию В₁, то соединяем точки а₁₁ и а₂₁, если – В_2, то – а₁₂ и а₂₂.

Средний выигрыш изображается точкой N, точка пересечения прямых В₁В₁ и В₂В₂.Абсцисса этой точки равна Р₂, а ордината цене игры - g.

Прямая В₁В₁ называется стратегией В_1. Ордината любой точки отрезка В₁ В₁ равна величине выигрыша игрока А при применении им стратегии А₁, А₂, с соответствующими вероятностями Р₁ и Р₂.

Ординаты точек отрезка В₂ В₂ равны среднему стратегий А₁, А₂, с соответствующими вероятностями Р₁ и Р₂. Ломаная В₁NВ₂ – это нижняя граница выигрыша, получаемая игроком А. В точке N он максимален (g).

В₁

N В₂

В_{2 g}

В₁

Рис.3.9.

Пример.

Найти оптимальную смешанную стратегию руководителя предприятия и гарантированный средний выигрыш при выборе из двух новых технологий А₁, А₂. Известны выигрыши каждого вида технологий по сравнению со старой технологией. Матрица игры имеет вид

	В1	В2
А1	0,4	0,9	a1=0,4
А2	0,6	0,5	a2=0,5
	b1=0,6	b2=0,9

a= max (0,4, 0,5)=0,5

b= min (0,6, 0,9)=0,6

a не равна b

0,9

0,6

0,5

0,4 g=0,55

р₁=0,625 р₂=0,375

Оптимальная стратегия

А₁ А₂

S_A=

_{0,375 0.625}

g=0,55

По сравнению с прежней технологией выигрыш составляет 55%.