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

Лекция №14.

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

Основные понятия и определения.

Любая реальная конфликтная ситуация бывает очень сложной, ее анализ затруднен из-за наличия многих второстепенных факторов. Чтобы сделать возможным математический анализ ситуации, необходимо отвлечься от второстепенных факторов и построить упрощенную, схематизированную модель ситуации. Такая модель называется ИГРОЙ.

Игры бывают ПАРНЫЕ и МНОЖЕСТВЕННЫЕ. В первом случае число участников равно двум, во втором – более двух. Участники множественной игры могут образовывать КОАЛИЦИИ (постоянные или временные), когда их цели совпадают. Игра с двумя постоянными коалициями превращается в парную. Наибольшее практическое значение имеют парные игры.

Пусть имеется парная игра, в которой участвуют два игрока А и В с противоположными интересами. Под ИГРОЙ понимается мероприятие, состоящее из ряда действий, или ходов, сторон А и В. Каждая партия в игре заканчивается выигрышем только одного из игроков.

Чтобы игра могла быть подвергнута математическому анализу, необходимо четко сформулировать ПРАВИЛА ИГРЫ, под которыми понимается система условий, регламентирующая:

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

2. объем информации каждой стороны о поведении другой;

3. исход игры, к которому приводит каждая совокупность ходов.

Исход игры должен оцениваться КОЛИЧЕСТВЕННО. Если это не вытекает из сути игры, то можно условно выразить исход игры числом. Например, в шахматной игре выигрышу приписывается значение 1, проигрышу – 0, ничьей – 0,5.

Игра называется ИГРОЙ С НУЛЕВОЙ СУММОЙ, если один игрок выигрывает ровно столько, сколько проигрывает другой, т.е. сумма выигрышей сторон равна нулю. Таким образом, в игре с нулевой суммой интересы игроков прямо противоположны. Если а - выигрыш игрока А, b - выигрыш игрока В, то a+b=0, следовательно a=-b. Поэтому при анализе такой игры достаточно рассмотреть выигрыш одного из игроков. Пример игры с нулевой суммой – шахматная игра, а игры с ненулевой суммой – карточная игра с банкиром, который держит банк и забирает часть выигрыша себе.

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

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

СТРАТЕГИЕЙ игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе этого игрока в зависимости от сложившейся ситуации. Обычно, принимая участие в игре, игрок не следует каким-либо жестким, фиксированным правилам: выбор при каждом личном ходе принимается им в ходе игры в зависимости от конкретной сложившейся ситуации. Однако теоретически дело не изменится, если мы представим себе, что все эти решения приняты игроком заранее («если сложится такая-то ситуация, то я поступлю так-то...»). В принципе это возможно при любой игре. Если такая система решений будет принята, это будет означать, что игрок выбрал определенную стратегию. Теперь он может не участвовать в игре лично, а заменить свое участие списком правил, которые за него будет применять незаинтересованное лицо. Именно так играет в шахматы ЭВМ.

Игра называется КОНЕЧНОЙ, если у каждого игрока имеется только конечное число стратегий, и БЕСКОНЕЧНОЙ, если хотя бы у одного из игроков имеется бесконечное число стратегий.

Целью теории игр является определение оптимальной стратегии для каждого из игроков.

ОПТИМАЛЬНОЙ СТРАТЕГИЕЙ игрока называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (или минимально возможный средний проигрыш).

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

Игра называется игрой с ПОЛНОЙ ИНФОРМАЦИЕЙ, если результаты случайных ходов и предыдущих личных ходов полностью известны каждому игроку. В противном случае игра является игрой с НЕПОЛНОЙ ИНФОРМАЦИЕЙ. Например, шахматы и шашки – игры с полной информацией, а карточные игры – с неполной информацией.

Парная игра с нулевой суммой. Платежная матрица.

Рассмотрим парную конечную игру с нулевой суммой с игрокам А и В, которые имеют конечное число стратегий соответственно А₁, А₂,... А_m и В₁, В₂,... В_n. Такая игра называется игрой m x n. Исход каждой партии завершается выигрышем одного из игроков.

Обозначим a_ij - выигрыш игрока А, если он использует стратегию А_i, а игрок В стратегию В_j. Тогда выигрыш игрока В очевидно равен b_ij=- a_ij, так как игра с нулевой суммой. Поэтому в дальнейшем будем рассматривать лишь выигрыш одного из игроков. Если игра содержит кроме личных и случайные ходы, то выигрыш a_ij есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша. В дальнейшем будем обозначать a_ij как сам выигрыш (в игре без случайных ходов), так и его мат. ожидание (в игре со случайными ходами).

Предположим, что известны a_ij для любой пары (А_i В_j). Эти значения записываются в таблицу, называемую ПЛАТЕЖНОЙ МАТРИЦЕЙ.

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

Пример 1. Игра «поиск».

Имеется два игрока А и В, игрок А прячется, а В его ищет. В распоряжении игрока А имеется два убежища (I и II), любое из которых он может выбрать по своему усмотрению. Условия игры таковы: если В найдет А в том убежище, где А спрятался, то А платит ему штраф 1 руб.; если В не найдет А (т. е. будет искать в другом убежище), то он сам должен заплатить А такой же штраф. Требуется построить платежную матрицу.

Решение. Игра состоит всего из двух ходов, оба - личные. У нас (А) две стратегии:

А₁ — прятаться в убежище I, А₂ — прятаться в убежище II. У противника (В) тоже две стратегии:

В₁ — искать в убежище I, В₂,— искать в убежище II. Модель этой задачи представляется игрой 2х2. Ее матрица имеет, вид табл. 7.1.

Таблица 1

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

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

Действительно, допустим, что мы (игрок А) выбрали какую-то стратегию (скажем, А ₁ ) и придерживаемся ее. Тогда, уже по результатам первых нескольких партий, противник догадается о нашей стратегии, начнет всегда искать в убежище I и выигрывать. То же будет, если мы выберем стратегию А ₂. Нам явно невыгодно придерживаться одной какой-то стратегии; чтобы не оказаться в проигрыше, мы должны чередовать их. Однако, если мы будем чередовать убежища I и II в какой-то определенной последовательности (скажем, через одну партию), противник тоже догадается об этом и ответит наихудшим для нас образом. Очевидно, надежным способом, гарантирующим нас от верного проигрыша, будет такая организация выбора в каждой партии, когда мы сами его наперед не знаем. Например, можно бросить монету, и, если выпадет герб, выбрать убежище I, а если решка - убежище II.

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

Таким образом, мы подошли к одному из существенных понятий теории игр - к понятию смешанной стратегии, то есть такой, в которой отдельные «чистые» стратегии чередуются случайным образом с какими-то вероятностями. В данном примере из соображений симметрии ясно, что стратегии А ₁ и А ₂ должны применяться с одинаковыми вероятностями; в более сложных примерах решение может быть далеко не тривиальным.

Пример 2. Игра «вооружение и самолет».

В нашем распоряжении имеются три вида вооружения: А ₁, А ₂ ., А ₃; у противника - три вида самолетов: В ₁, В ₂, В₃. Наша задача - поразить самолет; задача противника - сохранить его непораженным. Наш личный ход - выбор типа вооружения; личный ход противника - выбор самолета для боевых действий. В данной игре имеется еще и случайный ход - применение вооружения. Вооружением А ₁ самолеты В ₁, В ₂, В ₃ поражаются соответственно с вероятностями 0,5, 0,6, 0,8; вооружением А ₂. - с вероятностями 0,9, 0,7, 0,8; вооружением А ₃, - с вероятностями 0,7, 0,5, 0,6. Построить матрицу игры и проанализировать ситуацию.

Решение. Матрица игры 3х3 имеет следующий вид.

Таблица 2

где выигрыш - вероятность поражения самолета (мы стремимся его максимизировать, а противник - минимизировать). Станем сначала на точку зрения игрока А и переберем одну за другой все его стратегии. На А ₁ противник ответит нам В ₁, и мы выиграем 0,5; на А₃ – В ₂, и мы выиграем 0,7; на А ₃ - снова В ₂, и мы выиграем1ё 0,5. Очевидно, некоторое преимущество над другими имеет стратегия А ₂ - при ней мы выиграем больше, а именно 0,7.

Станем теперь на точку зрения противника. Пусть он выбирает В ₁ - мы отвечаем ему А ₂ ., и он отдает 0,9; на В ₂ мы отвечаем ему А ₂ ., и он отдает 0,7; на В ₃ – А ₃, и он отдает 0,8. Естественно, он предпочтет В ₂, чтобы отдать только 0,7.

Мы видим, что в данном примере стратегии А ₂. и В₂ с выигрышем 0,7 являются наивыгоднейшими сразу для обеих сторон; игроку А выгоднее всего выбирать стратегию А ₂, игроку В - стратегию В ₂, и максимальный выигрыш А совпадает с минимальным проигрышем В. Достигнуто как бы положение равновесия: если А выберет стратегию А ₂ ., то В не может найти лучшего выхода, чем В ₂, и наоборот: если В выберет стратегию В ₂, то А не может найти лучшего выхода, чем А ₂.

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