2014-02-12
374
Основные характеристики игры.
В рассмотрении конечных антагонистических игр двух лиц с нулевой суммой принято, наряду с их определением, описанным выше, учитывать тот или иной принцип, которого придерживаются игроки. Ниже будут рассмотрены два таких принципа, наиболее часто встречающиеся в исследованиях и приложениях.
Принцип равной разумности. Согласно этому принципу, оба игрока имеют равные возможности в оценке любой ситуации и равные возможности в использовании этой оценки. Отметим, что элемент 
, будучи фиксированным, и представляет собой «игру», так как каждый из игроков играет, выбирая только одну какую-то свою стратегию (с этой точки зрения шахматы - это не игра). Реализация игры 
определяет выигрыш первого игрока, который называется также проигрышем второго игрока. Первый игрок стремится к большему выигрышу, а второй игрок стремится к меньшему проигрышу. Именно это и обуславливает выбор стратегий сторонами.
Если первый игрок выберет стратегию 
, то второй игрок, учитывая принцип равной разумности, выберет ту из своих стратегий, при которой выигрыш будет минимальным; поэтому первому игроку имеет смыл выбирать ту из своих стратегий, при которой этот минимум окажется максимальным; это означает, что число
является минимальным выигрышем, который может наступить в игре; оно называется нижней ценой игры.
Если второй игрок выберет стратегию 
, то первому игроку следует выбрать ту из своих стратегий, при которой выигрыш окажется максимальным; поэтому второй игрок будет выбирать ту из своих стратегий, при которой соответствующий максимум окажется
минимальным; это означает, что число
является максимальным проигрышем второго игрока; оно называется верхней ценой игры.
Можно доказать, что всегда имеет место соотношение: 
.
Если 
, то говорят, что игра имеет цену (которая равна 
), а матрица M имеет седловую точку (это как раз та клетка в платежной матрице, в которой стоит элемент, равный цене игры).
Предположим теперь, что игра повторяется несколько, скажем, N раз. В этом случае о каждой из стратегий каждого из игроков можно сказать, сколько раз именно к ней прибегал игрок; пусть 
раз первый игрок прибегал к стратегии и пусть 
раз второй игрок прибегал к стратегии , так что 
. Тогда наборы 
и 
, где
представляют собой объекты, которые выше были названы смешанными стратегиями игроков. Тем самым становится ясным смысл смешанной стратегии - это список частот, с которыми игрок обращается к своим стратегиям при многократном повторении игры.
Можно доказать, что всегда имеют место следующие соотношения:
.
Более того, среди смешанных стратегий и есть такие, на которых достигается следующее точное равенство:
.
В этом состоит основная теорема теории игр. Общее значение частей последнего равенства называется ценой игры; те смешанные стратегии, при которых это равенство достигается, называются оптимальными смешанными стратегиями.
Сформулируем, в заключение знаменитую теорему об активных стратегиях. Словами активная стратегия обозначают такую стратегию игрока, к которой он прибегает хотя бы один раз, реализуя свою оптимальную смешанную стратегию. Говоря более формально, стратегия называется активной, если в оптимальной смешанной стратегии число 
отлично от нуля.
Теорема об активных стратегиях. Если первый игрок придерживается своей оптимальной смешанной стратегии, а второй игрок придерживается какой-либо своей активной стратегии, то средний выигрыш первого игрока остается равным цене игры.
Л И Т Е Р А Т У Р А
[1] Конспект лекций.
[2] Харари Ф. Теория графов. “Мир”. М.-1995.
[3] Кристофидес Н. Теория графов. “Мир”. М.-1993.
[4] Феллер В. Введение в теорию вероятностей и ее приложения. “Мир”. М.-1990.
[5] Воробьев Н.Н. Основы теории игр. “Наука”. М.-1996.
[6] Михалевич В.С., Кукса А.М. Методы последова-тельной оптимизации. “Наука”. М.-1990.
[7] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. “Мир”. М.-1991.
