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

Раздел "Теория игр" представлен тремя онлайн-калькуляторами :

1. Оптимальные стратегии игроков . В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры . Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
   1. Минимакс . Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
   2. Симплекс-метод . Используется для решения игры в смешанных стратегиях методами линейного программирования.
   3. Графический метод . Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
   4. Итерационный метод Брауна-Робинсона . Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
   Например, задание может звучать как "указать оптимальные стратегии игроков для игры, заданной платежной матрицей" .
   Во всех методах применяется проверка на доминирующие строки и столбцы.
2. Биматричная игра . Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
3. Игры с природой . Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда , Сэвиджа , Гурвица .
   Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
   Для критерия Гурвица укажите уровень оптимизма λ . Если в условиях данный параметр не задан можно использовать значения 0, 0.5 и 1 .

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

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

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица .

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока - n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

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

Составим платёжную матрицу:

Если первый игрок выбирает i -ю чистую стратегию, а второй игрок - j -ю чистую стратегию, то выигрыш первого игрока составит a ij единиц, а проигрыш второго игрока - также a ij единиц.

Так как a ij + (- a ij ) = 0 , то описанная игра является матричной игрой с нулевой суммой.

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

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

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

Сначала определим величину выигрыша первого игрока, если он использует i -ю чистую стратегию. Если первый игрок использует i -ю чистую стратегию, то логично предположить, что второй игрок будет использовать такую чистую стратегию, благодаря которой выигрыш первого игрока был бы минимальным. В свою очередь первый игрок будет использовать такую чистую стратегию, которая бы обеспечила ему максимальный выигрыш. Исходя из этих условий выигрыш первого игрока, который обозначим как v 1 , называется максиминным выигрышем или нижней ценой игры .

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

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

При решении задач на цену игры и определение стратегии для определения этих величин у второго игрока следует поступать следующим образом. Из каждого столбца выписать значение максимального элемента и уже из них выбрать минимальный. Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название - минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует "минимакс", то независимо от выбора стратегии первым игроком, он проиграет не более v 2 единиц.

Пример 1.

.

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

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

Итак, гарантированный выигрыш первого игрока:

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

.

Первый игрок использует такую свою чистую стратегию, чтобы проигрыш второго игрока был максимальным. Этот проигрыш обозначается так:

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

.

Ещё пример из этой же серии.

Пример 2. Дана матричная игра с платёжной матрицей

.

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

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

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

Седловая точка в матричных играх

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

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

В этом случае матричная игра имеет решение в чистых стратегиях .

Пример 3. Дана матричная игра с платёжной матрицей

.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока - вторая чистая стратегия, а минимаксная стратегия второго игрока - третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

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

Пример 4. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

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

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

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

Если первый игрок использует чистые стратегии с вероятностями , то вектор называется смешанной стратегией первого игрока. Иначе говоря, это "смесь" чистых стратегий. При этом сумма этих вероятностей равна единице:

.

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

.

Если первый игрок использует смешанную стратегию p , а второй игрок - смешанную стратегию q , то имеет смысл математическое ожидание выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):

.

Пример 5. Дана матричная игра с платёжной матрицей

.

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

Решение. Согласно формуле математического ожидания выигрыша первого игрока (проигрыша второго игрока) оно равно произведению вектора смешанной стратегии первого игрока, платёжной матрицы и вектора смешанной стратегии второго игрока:

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

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

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

,

.

В таком случае для функции E существует седловая точка , что означает равенство .

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

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

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

Функция цели в прямой задаче линейного программирования:

.

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

Функция цели в двойственной задаче:

.

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

,

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

В соответствии определениям предыдущего параграфа и координатами оптимальных планов, в силе следующие смешанные стратегии первого и второго игроков:

.

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

,

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

Нам, практикам, остаётся лишь использовать эту формулу для решения матричных игр в смешанных стратегиях. Как и формулы для нахождения оптимальных смешанных стратегий соответственно первого и второго игроков:

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

Пример 6. Дана матричная игра с платёжной матрицей

.

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

.

Находим линейную форму оптимальных планов как сумму найденных координат.

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

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

Из истории теории игр

История теории игр как самостоятельной дисциплины начинается в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу "Теория игр и экономическое поведение" ("Theory of Games and Economic Behavior"). Хотя примеры теории игр встречались и раньше: трактат Вавилонского Талмуда о разделе имущества умершего мужа между его жёнами, карточные игры в 18-м веке, развитие теории шахматной игры в начале 20-го века, доказательство теоремы о минимаксе того же Джона фон Неймана в 1928 году, без которой не было бы никакой теории игр.

В 50-х годах 20-го века Мелвин Дрешер и Мерил Флод из Rand Corporation первыми экспериментально применили дилемму заключённого, Джон Нэш в работах о состоянии равновесия в играх двух лиц развил понятие равновесия Нэша.

Рейнхард Сэлтен в 1965 году опубликовал книгу "Обработка олигополии в теории игр по требованию" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), с которой применение теории игр в экономике получило новую движущую силу. Шагом вперёд в эволюции теории игр связан с работой Джона Мейнарда Смита "Эволюционно стабильная стратегия" ("Evolutionary Stable Strategy", 1974). Дилемма заключённого была популяризована в книге Роберта Аксельрода "Эволюция кооперации" ("The Evolution of Cooperation"), опубликованной в 1984 году. В 1994 году именно за вклад в теорию игр Нобелевской премии были удостоены Джон Нэш, Джон Харсаньи и Рейнхард Сэлтен.

Теория игр в жизни и бизнесе

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

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

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

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

Одна из самых простых конфликтных ситуаций, которая может быть записана и решена в теории игр - дуэль, представляющая собой конфликт двух игроков 1 и 2, имеющих соответственно p и q выстрелов. Для каждого игрока существует функция, указывающая вероятность того, что выстрел игрока i в момент времени t даст попадание, которое окажется смертельным.

В итоге теория игр приходит к такой формулировке некоторого класса столкновений интересов: имеются n игроков, и каждому нужно выбрать одну возможность из стого определённого набора, причём при совершении выбора у игрока нет никаких сведений о выборах других игроков. Область возможных выборов игрока может содержать такие элементы, как "ход тузом пик", "производство танков вместо автомобилей", или в общем смысле, стратегию, определяющую все действия, которые нужно совершить во всех возможных обстоятельствах. Перед каждым игроком стоит задача: какой выбор он должен сделать, чтобы его частное влияние на исход принесло ему как можно больший выигрыш?

Математическая модель в теории игр и формализация задач

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

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

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

Реальная конфликтная ситуация не всегда, а игра (в понятии теории игр) - всегда - протекает по определённым правилам , которые точно определяют:

1. варианты действий игроков;
2. объём информации каждого игрока о поведении партнёра;
3. выигрыш, к которому приводит каждая совокупность действий.

Примерами формализованных игр могут служить футбол, карточная игра, шахматы.

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

Для игры характерна неопределённость результата . Причины неопределённости можно распределить по следующим группам:

1. комбинаторные (как в шахматах);
2. влияние случайных факторов (как в игре "орёл или решка", кости, карточные игры);
3. стратегические (игрок не знает, какое действие предпримет противник).

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

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

Классификация игр

1. Классификация по числу игроков (игра двух и более лиц). Игры двух лиц занимают центральное место во всей теории игр. Основным понятием теории игр для игры двух лиц является обобщение весьма существенной идеи равновесия, которая естественно появляется в играх двух лиц. Что же касается игр n лиц, то одна часть теории игр посвящена играм, в которых сотрудничество между игроками запрещено. В другой части теории игр n лиц предполагается, что игроки могут сотрудничать для взаимной пользы (см. далее в этом параграфе о некооперативных и кооперативных играх).
2. Классификация по числу игроков и их стратегиям (число стратегий не менее двух, может быть бесконечностью).
3. Классификация по количеству информации относительно прошлых ходов: игры с полной информацией и неполной информацией. Пусть есть игрок 1 - покупатель и игрок 2 - продавец. Если у игрока 1 нет полной информации о действиях игрока 2, то игрок 1 может и не различить две альтернативы, между которыми ему предстоит сделать выбор. Например, выбирая между двумя видами некоторого товара и не зная о том, что по некоторым признакам товар A хуже товара B , игрок 1 может не видеть различия между альтернативами.
4. Классификация по принципам деления выигрыша : кооперативные, коалиционные с одной стороны и некооперативные, бескоалиционные с другой стороны. В некооперативной игре , или иначе - бескоалиционной игре , игроки выбирают стратегии одновременно, не зная, какую стратегию выберет второй игрок. Коммуникация между игроками невозможна. В кооперативной игре , или иначе - коалиционной игре , игроки могут объединяться в коалиции и предпринимать коллективные действия, чтобы увеличить свои выигрыши.
5. Конечная игра двух лиц с нулевой суммой или антогонистическая игра – это стратегическая игра с полной информацией, в которой участвуют стороны с противоположными интересами. Анатагонистическими играми являются матричные игры .

Классический пример из теории игр - дилемма заключённого

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

Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:

Таким образом, если оба заключённых не признаются, они получат по 1 году каждый. Если оба признаются, то каждый получит по 8 лет. А если один признается, другой не признается, то тот, который признался отделается тремя месяцами заключения, а тот, который не признается, получит 10 лет. Приведённая выше матрица правильно отражает дилемму заключённого: перед каждым стоит вопрос - признаться или не признаться. Игра, которую окружной прокурор предлагает заключённым, представляет собой некооперативную игру или иначе - бескоалиционную игру . Если бы оба заключённых имели возможность сотрудничать (то есть игра была бы кооперативной или иначе коалиционной игрой ), то оба не признались бы и получили по году тюрьмы каждый.

Примеры использования математических средств теории игр

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

Пример формализации некооперативной (бескоалиционной) игры двух лиц

В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.

Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.

Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.

Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i =1,2) две чистые стратегии:

• сойти в Дувре (стратегия s i1 (i =1,2) );
• сойти на промежуточной станции (стратегия s i2 (i =1,2) )

В зависимости от того, какую из двух стратегий выберет каждый из двух игроков, будет создана особая комбинация стратегий как пара s = (s 1 , s 2 ) .

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

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

Пример формализации и решения кооперативной (коалиционной) игры n лиц

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

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

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

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

Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами ", которое при переходе по ссылке открывается в новом окне.

Характеристическая функция обозначается как v и область её определения состоит из возможных подмножеств множества N . v (T ) - значение характеристической функции для того или иного подмножества, например, доход, полученный коалицией, в том числе, возможно, состоящей из одного игрока. Это важно по той причине, что теория игр требует проверить наличие супераддитивности для значений характеристической функции всех непересекающихся коалиций.

Для двух непустых коалиций из подмножеств T 1 и T 2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:

А супераддитивность так:

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

В среднем их выручка за один вечер составляла:

• у скрипача 600 единиц;
• у гитариста 700 единиц;
• у певицы 900 единиц.

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

• скрипач + гитарист зарабатывали 1500 единиц;
• скрипач + певица зарабатывали 1800 единиц;
• гитарист + певица зарабатывали 1900 единиц;
• скрипач + гитарист + певица зарабатывали 3000 единиц.

Решение. В этом примере число участников игры n = 3 , следовательно, область определения характеристической функции игры состоит из 2³ = 8 возможных подмножеств множества всех игроков. Перечислим все возможные коалиции T :

• коалиции из одного элемента, каждая из которых состоит из одного игрока - музыканта: T {1} , T {2} , T {3} ;
• коалиции из двух элементов: T {1,2} , T {1,3} , T {2,3} ;
• коалиция из трёх элементов: T {1,2,3} .

Каждому из игроков присвоим порядковый номер:

• скрипач - 1-й игрок;
• гитарист - 2-й игрок;
• певица - 3-й игрок.

По данным задачи определим характеристическую функцию игры v :

v(T{1}) = 600 ; v(T{2}) = 700 ; v(T{3}) = 900 ; эти значения характеристической функции определены исходя из выигрышей соответственно первого, второго и третьего игроков, когда они не объединяются в коалиции;

v(T{1,2}) = 1500 ; v(T{1,3}) = 1800 ; v(T{2,3}) = 1900 ; эти значения характеристической функции определены по выручке каждой пары игроков, объединившихся в коалиции;

v(T{1,2,3}) = 3000 ; это значение характеристической функции определено по средней выручке в случае, когда игроки объединялись в тройки.

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

Как выполняются условия супераддитивности в этом примере? Определим, как игроки образуют непересекающиеся коалиции T 1 и T 2 . Если часть игроков входят в коалицию T 1 , то все остальные игроки входят в коалицию T 2 и по определению эта коалиция образуется как разность всего множества игроков и множества T 1 . Тогда, если T 1 - коалиция из одного игрока, то в коалиции T 2 будут второй и третий игроки, если в коалиции T 1 будут первый и третий игроки, то коалиция T 2 будет состоять только из второго игрока, и так далее.

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

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

Некоторые определения игры

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

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

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

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

Игра, определяемая матрицей А , имеющейm строк иn столбцов, называется конечной парной игрой размерностиm * n ;

где i =
- стратегия первого игрока, имеющегоmстратегий; j =- стратегия второго игрока, имеющегоnстратегий; ij – выигрыш первого игрока поi -й стратегии при использовании вторымj -й стратегии (или, что то же самое, проигрыш второго по своейj -й стратегии, при использовании первымi -й);

А =  ij – платежная матрица игры.

1.1 Игра с чистыми стратегиями

Нижняя цена игры (для игрока первого)

 = max (min  ij ). (1.2)

i j

Верхняя цена игры (для второго игрока):

= min (max  ij ) . (1.3)

J i

Если  =  , игра называется с седловой точкой (1.4), или игра с чистыми стратегиями. При этомV =  =  называют ценной игры (V - цена игры).

Пример. Дана платежная матрица игры 2 лиц А. Определить оптимальные стратегии для каждого из игроков и цену игры:

(1.4)

max 10 9 12 6

i

min 6

j

- стратегия первого игрока (строки).

Стратегия второго игрока (столбцы).

- цена игры.

Таким образом, игра имеет седловую точку. Стратегия j = 4 – оптимальная для второго игрока, стратегияi =2 - для первого. Имеем игру с чистыми стратегиями.

1.2 Игры со смешанными стратегиями

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

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

Х = (х 1 …х i …х m ) – смешанная стратегия первого игрока.

У = (у 1 …у j …у n ) – смешанная стратегия второго игрока.

x i , у j – относительные частоты (вероятности) использования игроками своих стратегий.

Условия использования смешанных стратегий

. (1.5)

Если Х * = (х 1 * ….х i * …х m *) – оптимальная стратегия, выбранная первым игроком;Y * = (у 1 * …у j * …у n *) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.

(1.6)

Для того чтобы число V было ценой игры, ах * иу * - оптимальными стратегиями, необходимо и достаточно выполнение неравенств

(1.7)

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

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

Пример . Найти решение игры, определяемой платежной матрицейА .

А = (1.8)

y 1 y 2 y 3

Решение:

Составим двойственную пару задач линейного программирования.

Для первого игрока

(1.9)

у 1 +у 2 +у 3 = 1 (1.10)

Освобождаясь от переменной V (цена игры), разделим левую и правую часть выражений (1.9), (1.10) наV . Приняву j /V за новую переменнуюz i , получим новую систему ограничений (1.11) и целевую функцию (1.12)

(1.11)

. (1.12)

Аналогично получим модель игры для второго игрока:

(1.13)

х 1 +х 2 +х 3 = 1 . (1.14)

Приведя модель (1.13), (1.14) к форме без переменной V , получим

(1.15)

, (1.16)

где
.

Если нам необходимо определить стратегию поведения первого игрока, т.е. относительную частоту использования его стратегий (х 1 ….х i …х m ), мы будем использовать модель второго игрока, т.к. эти переменные находятся в его модели выигрыша (1.13), (1.14).

Приведем (1.15), (1.16) к канонической форме

(1.17)

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

Задача:
Матричная игра задана следующей платежной матрицей:

	Стратегии "B"
Стратегии "A"	B 1	B 2
A 1	3	5
A 2	6	3 2

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

Шаг:1

Определим нижнюю цену игры - α

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

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец (Выделен желтым цветом см. Табл.1).

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

Таблица 1

	Стратегии "B"
Стратегии "A"	B 1	B 2	Минимумы строк
A 1	3	5	3 *
A 2	6	3 2	3 2

В нашем случае нижняя цена игры равна: α = 3 , и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A 1

Шаг:2

Определим верхнюю цену игры - β

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

Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу (Выделена желтым цветом см. Табл.2).

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

Таблица 2

	Стратегии "B"
Стратегии "A"	B 1	B 2	Минимумы строк
A 1	3	5	3 *
A 2	6	3 2	В нашем случае верхняя цена игры равна: β = 5 , и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник (игрок "B") должен придерживаться стратегии B 2 Шаг:3 Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β , платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях. Смешанная стратегия , это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать S A =

где B 1 , B 2 - стратегии игрока "B", а q 1 , q 2 - соответственно вероятности, с которыми эти стратегии применяются, причем q 1 + q 2 = 1.

Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S A * и S B * соответственно. Пара оптимальных стратегий образует решение игры.

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

Шаг:4

где: p 1 , p 2 - вероятности (частоты) с которыми применяются соответственно стратегии A 1 и A 2

Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "B" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "В" использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок "В" будет пользоваться чистой стратегией B 1 , то средний выигрыш v составит:

k 11 p 1 + k 21 p 2 = v (1)

где: k ij - элементы платежной матрицы.

C другой стороны, если предположить, что игрок "В" будет пользоваться чистой стратегией B 2 , то средний выигрыш составит:

k 12 p 1 + k 22 p 2 = v (2)

Приравняв левые части уравнений (1) и (2) получим:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

А с учетом того, что p 1 + p 2 = 1 имеем:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

Откуда несложно найти оптимальную частоту стратегии A 1 :

p 1 =

k 22 - k 21 k 11 + k 22 - k 12 - k 21

(3)

В данной задаче:

p 1 =

3 2 - 6 3 + 3 2 - 5 - 6

=

9 13

Вероятность р 2 найдем вычитанием р 1 из единицы:

p 2 = 1 - p 1 =

1

-

9 13

=

+

6

·

где: q 1 , q 2 - вероятности (частоты) с которыми применяются соответственно стратегии B 1 и B 2

Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A 1 , то средний выигрыш v составит:

k 11 q 1 + k 12 q 2 = v (4)

Поскольку цена игры v нам уже известна и учитывая, что q 1 + q 2 = 1 , то оптимальная частота стратегии B 1 может быть найдена как:

q 1 =

v - k 12 k 11 - k 12

(5)

В данной задаче:

q 1 =

51 13 - 5 3 - 5

=

7 13

Вероятность q 2 найдем вычитанием q 1 из единицы:

q 2 = 1 - q 1 =

1

-

7 13

=

6 13

Ответ:

Нижняя цена игры:	α =	3
Верхняя цена игры:	β =	5
Цена игры:	v =	51 13

Оптимальная стратегия игрока "А" :	S A * = A 1 A 2 9 13 4 13
Оптимальная стратегия игрока "B" :	S B * = B 1 B 2 7 13 6 13

Геометрическая интерпретация (графическое решение):

Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a 1 и a 2 соответствующие нашим стратегиям A 1 и A 2 . Предположим теперь, что игрок "B" будет пользоваться стратегией B 1 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a 1 .
Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a 2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B 1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p 2 (частоте), с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу k (см. Рис.1).

Рисунок 1.
График зависимости выигрыша k от частоты р 2 , при использовании противником стратегии B 1 .

Предположим теперь, что игрок "B" будет пользоваться стратегией B 2 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B 2 . Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу, но только для стратегии B 2 (см. Рис. 2).

Рисунок 2.
v и оптимальной частоты р 2 для игрока "А" .

В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша . Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1 и B 2 . Обратите внимание, что если выбрать частоту p 2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока "B", кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p 2 , в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p 1 , нашей оптимальной смешанной стратегии, это длина отрезка [p 2 ; 1] на оси абсцисс. (Это потому, что p 1 + p 2 = 1 )

Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3.

Рисунок 3.
Графическое определение цены игры v и оптимальной частоты q 2 для игрока "В" .

Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q 1 , это длина отрезка [q 2 ; 1] на оси абсцисс.