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

7.1. Предмет теории игр

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

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

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

Теория игр берет начало от работ Э.Бореля (1921 г.), а принципиальным этапом в ее становлении как самостоятельного научного направления стала монография Дж.Неймана, вышедшая в 1944 г.

7.2. Терминология и классификация игр

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

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

Ситуация называется конфликтной, если в игре участвуют стороны, интересы которых полностью или частично противоположны.

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

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

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

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

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

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

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

3. Матричные игры и понятие седловой точки

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

Предположим, имеется два игрока А и В. Они вступают в игру. У каждого из игроков на определенном этапе есть возможность выбора. Предположим также, что у каждого из игроков есть определенный набор стратегий:

игрок А → имеет m стратегий, т.е. i=(1…m);

игрок B → имеет n стратегий, т.е. j=(1…n).

Допустим, что при i-ой стратегии игрока A и j-ой стратегии игрока В результатом игры будет число а_ij, т.е. платеж. В результате, при реализации первым игроком всех m стратегий, а вторым - всех n стратегий по всем платежам можно составить матрицу игры:

.

С

троки матрицы отражают платежи по отношению к первому игроку А (а_ij>0, если он выигрывает, а_ij<0, если проигрывает) при условии выполнения какой-то одной определенной стратегии (обозначим ее А_i) и при произвольных ответах второго игрока (стратегиях, которые можно обозначить как В_j). Столбцы отражают результаты игры для игрока А при условии, что второй игрок В будет придерживаться постоянства одной стратегии (т.е. В_j=const) , а игрок А стратегию меняет.

Стратегия игрока, соответствующая строке игрока А или столбцу игрока В, называется чистой стратегией.

Матрицу А размерностью mn называют конечной игрой размерностью mn.

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

	В1(н/ч)	В2 (ч)
A1 (н/ч)	1	-1
А2 (ч)	-1	1

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

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

.

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

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

.

Такой принцип выбора стратегии получил название “принцип максимина”. С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий игрока В. Его наибольший проигрыш при переборе всех возможных стратегий составит β=max(a_ij). Следовательно, ему надо выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т.е. обеспечить

.

Такой принцип выбора стратегии называется “принцип минимакса”. Логика игры позволяет утверждать, что всегда выполняется неравенство . Особый интерес представляет случай, когда это неравенство становится равенством, т.е. . В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрыша одного и проигрыша второго игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (равновесного) состояния, от которого невыгодно отклоняться ни одному из игроков (т.е. не совершать ошибочных действий). Понятие “оптимальность” здесь означает, что ни один разумный (осторожный) игрок не будет стремиться изменить свою стратегию, так как его противник, в принципе, может этим воспользоваться и выбрать такую стратегию, которая даст худший для первого результат. Стратегии i^* и j^* , образующие седловую точку, называются оптимальными, а значение v=a_i^*_j^* называют ценой игры.

Очевидно, что не всякая игра будет иметь седловую точку. Скорее наоборот, отсутствие седловой точки может быть правилом, а ее наличие – исключением. Примером игры, имеющей седловую точку, является игра с платежной матрицей:

.

Запишем для игрока А вектор-строку минимальных выигрышей по всем трем его стратегиям (т.е. по трем строкам): α=(1; 5; -3). Для игрока В запишем вектор-строку из максимальных проигрышей по всем четырем его стратегиям (столбцам): β=(8; 10; 5; 17). Теперь запишем максимин для игрока А, т.е. максимальный выигрыш из минимально возможных: α_max=5, а для игрока В запишем значение минимакса, т.е. минимальный проигрыш из максимально возможных по всем его стратегиям: β_min=5. Видим, что в данном случае имеется седловая точка v= а₂₃=5. Следовательно, для игры с приведенной выше матрицей решение игры будет: i=2; j=3; v=5 (для игрока А оптимальной будет вторая стратегия А₂, для игрока В оптимальна третья стратегия В₃, цена игры равна 5). При любом отклонении от оптимальной стратегии другой игрок будет иметь шанс “наказать” противника и выиграть больше цены игры (при ошибке игрока В) или проиграть меньше цены игры (при ошибке игрока А).