14. ЭЛЕМЕНТЫ ТЕОРИИ ИГР

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

Под термином «игра» понимается совокупность предварительно оговоренных правил и условий, а термин «партия» связан с частичной возможной реализацией этих правил. Если п партнеров (игроков) Р1, Р2, ..., Рп участвуют в данной игре, то основное содержание теории игр состоит в изучении следующей проблемы: как должен вести партию j-й партнер (j=1, …, п) для достижения наиболее благоприятного для себя исхода?

В дальнейшем предполагается, что в конце партии каждый игрок Pj получает сумму vj, называемую выигрышем. При этом подразумевается, что каждый игрок руководствуется лишь целью максимизации общей суммы выигрыша. Числа vj (j=1, …, п) могут быть положительными, отрицательными или равными нулю. Если vjgt;0, то это соответствует выигрышу j-гo игрока, если vjlt;0, – проигрышу, при vj=0 – ничейный исход.

В большинстве случаев имеем игры с нулевой суммой, т. е. v1+v2+...+vn=0. В этих играх сумма выигрыша переходит от одного партнера к другому, не поступая из внешних источников. Игра с нулевой суммой предусматривает, что сумма выигрышей всех игроков в каждой партии равна нулю. Примерами игры с нулевой суммой служат многие экономические задачи. В них общая сумма выигрыша перераспределяется между игроками, но не меняется.

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

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

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

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

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

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

Постановку задачи можно записать так:

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

Пример 2 («игра в три пальца»). Игроки А и В одновременно и независимо друг от друга показывают 1, 2 или 3 пальца. Размер выигрыша определяется общим количеством показанных пальцев. При этом, если число пальцев четное, выигрывает игрок А, нечетное, – игрок В.

Такую игру двух игроков можно представить в виде матрицы

=,

где индекс i элементов аij (i,j=1,2,3) означает количество пальцев игрока А, а индекс j – количество пальцев игрока В. Например, а13 означает, что одновременно и независимо друг от друга игрок А показал 1 палец, а игрок В – 3 пальца. Количество пальцев для элемента а13=4 указывает на выигрыш 4 единиц игроком А. Элемент а32=-5 указывает на проигрыш 5 единиц игроком А или выигрыш 5 единиц игроком В.

Мы рассмотрели примеры матричных игр 2-го и 3-го порядков. В общем случае матричная игра задается прямоугольной матрицей размерности m?п.

А=.

Каждый элемент аij матрицы является действительным числом и представляет собой сумму выигрыша, уплачиваемую игроком В игроку А, если А выбирает стратегию, соответствующую i-й строке, а В выбирает стратегию, соответствующую j-му столбцу.

Матричную игру часто записывают в развернутой форме (см. табл. 1), называемой платежной матрицей.

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

?=аij.                                                  (1)

Верхней чистой ценой игры (минимаксом) называется число ?, определяемое по формуле

?=аij.                                                 (2)

Стратегии игроков, соответствующие максимину (минимаксу), называются максиминными (минимаксными).

Пример 3. Найти максиминную и минимаксную стратегии игроков в матричной игре .

¦ Данную игру представим в виде платежной матрицы (табл. 2).

игроку А целесообразно выбрать такую стратегию (строку), для которой достигается максимальный выигрыш независимо от того, какой столбец выбрал игрок В, т. е. ?=аij=?i=max(-3, 3, 1, 2)=3. Максиминной стратегией игрока А является A2.

Аналогично, пользуясь формулой (2), определяем минимаксную стратегию игрока В. Поскольку он выбирает стратегии по столбцам, то какие бы стратегии ни выбирал игрок А, в худшем случае игрок В может проиграть соответственно стратегиям В1, B2, B3, В4: 5, 7, 8, 9. Однако игрок В стремится минимизировать свой проигрыш, а потому выбирает стратегию, соответствующую минимальному из чисел 5, 7, 8, 9, т. е. минимаксу:

?=аij=?=min(5, 7, 8, 9)=5.

Из платежной матрицы видно, что минимаксной стратегией игрока В является B1.                                                                                     ?