ТЕОРИЯ ИГР

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

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

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

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

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

У первого игрока три стратегии (варианта действия): А₁ (записать 1), А₂ (записать 2) и А₃ (записать 3); у второго игрока также три стратегии: В₁, В₂, В₃.

Задача первого игрока - максимизировать свой выигрыш, задача второго игрока - минимизировать свой проигрыш.

Матрица игры, или платежная матрица, имеет вид

.

Найдем наилучшую стратегию первого игрока. Если игрок выбрал стратегию А₁, то в худшем случае он получит выигрыш . Соответственно при выборе стратегии
А₂ - , А₃ - . Предвидя такую возможность, первый игрок должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш

.

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

Аналогично определяется наилучшая стратегия второго игрока. Второй игрок при выборе стратегии В₁ в худшем случае получит проигрыш . При выборе стратегий В₂ и В₃ проигрыш составит, соответственно, ; . Он выбирает стратегию, при которой его проигрыш будет минимальным и составит

.

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

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

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

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

.

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

.

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

Графический метод решения матричных игр

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Решение матричных игр сведением к

задаче линейного программирования

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

Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей

.

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

, .

Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения

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

где

, .

По условию. Разделим обе части этого равенства на v.

.

Оптимальная стратегия игрока А должна максимизировать величину v, следовательно, функция

должна принимать минимальное значение.

Таким образом, получена задача линейного программирования. Решая ее, находим значения , и величину 1/v, затем отыскиваются значения .

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

, .

Рассмотрим задачу отыскания оптимальной стратегии игрока B, для которой имеют место ограничения

Преобразуем систему ограничений, разделив все члены неравенств на v.

где

, .

По условию . Разделим обе части этого равенства на v.

.

Оптимальная стратегия игрока В должна минимизировать величину v, следовательно, функция

должна принимать максимальное значение.

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

Игры с природой

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

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

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия

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

2. Критерий максимума. Он выбирается из условия

.

Критерий является оптимистическим, считается, что природа будет наиболее благоприятна для человека.

3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

,

где a — степень оптимизма и изменяется в диапазоне [0, 1].

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

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

.

Элементы матрицы рисков находятся по формуле

,

где — максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия определяется выражением

.

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