2.4. Элементы теории игр

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

Типичный конфликт характеризуется тремя основными составляющими:

1. Заинтересованными сторонами;

2. Возможными действиями этих сторон;

3. Интересами сторон.

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

Опишем некоторые основные понятия, используемые в этой теории.

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

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

- выработке принципов оптимальности, то есть того, какое поведение игроков следует считать оптимальным (разумным, целесообразным);

- выяснению реализуемости этих принципов, то есть установлению существования оптимальных в выработанном смысле ситуаций;

- отысканию этих реализаций.

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

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

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

Проиллюстрируем сказанное на примере одного из самых простых, но одновременно и наиболее изученных классов игр, на так называемых матричных играх. Исследование матричных игр интересно еще и потому, что к ним могут быть приближенно сведены многие игры более общего вида.

Рассмотрим следующий пример.

Пример 2. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного, зеленого или синего цветов, и расплачиваются друг с другом так, как показано в матрице игры

(напомним, что у этой 33-матрицы строки соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В.

Считая, что эта 33 игра повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков.

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

Запишем эти минимальные выигрыши в правом столбце таблицы:

A1	-2	2	-1	-2
A2	2	1	1	1
A3	3	-3	1	-3

Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре.

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

	B1	B2	B3
A1	-2	2	-1	-2
A2	2	1	1	1
A3	3	-3	1	-3
	3	2	1

Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

В рассматриваемой игре числа maxmin и minmax совпали:

= =1.

Выделенные стратегии A₂ и B₃ являются стратегиями игроков А и В,

в следующем смысле:

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

Тем самым, ситуация оказывается равновесной.

Число называетсянижней ценой игры.

Число называетсяверхней ценой игры.

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

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

Цена игры совпадает с элементом матрицы игры А, расположенным на пересечении-й строки и-го столбца – минимальным в своей строке и максимальным в своем столбце.

Этот элемент называют Седловой точкой матрицы А, или точкой равновесия, а про игру говорят, что она имеет седловую точку.

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

Замечание. Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

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

.

Пример: Найдите решение следующей матричной игры .

Решение:

			min
	1	4	1
	3	-2	-2
	0	5	0
mах:	3	5	0

- нижняя цена игры

- верхняя цена игры

Т.к. , то имеет место матричная игра в смешанных стратегиях,седловой точки нет.

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

1	4
3	-2
0	5

Получим,

(1)

(2)

(3)

1

4

Выделим верхнюю огибающую. Нижняя точка верхней огибающей является точкой пересечения прямых (1) и (2). Получим,

, значит.

Полагая , получим:

р	1	4
1-р	3	-2
0	0	5

, значит

Цена игры .

Ответ: ;;.