Теория игр

8.5.1 Общие понятия

 

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

Игра — это совокупность правил, описывающих сущность кон­фликтной ситуации. Эти правила устанавливают:

─ выбор образа действия игроков на каждом этапе игры;

─ информацию, которой обладает каждый игрок при осуществлении таких выборов;

─ плату для каждого игрока после завершения любого этапа игры.

Игру можно определить следующим образом:

─ имеются n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

─ сформулированы правила выбора допустимых стратегий, извест­ные игрокам;

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

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

 

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

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

 

8.5.2 Игры двух лиц с нулевой сум­мой

 

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

Если первый игрок имеет m стратегий, а второй — n стратегий, то говорят, что имеют дело с игрой m×n. Рассмотрим игру m×n. Пусть заданы множество стратегий: для первого игрока {А_I}, для второго игрока {B_j}, платежная матрица , где а_ij — выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий А_i и В_j соответственно. Каждый из игроков выбирает однозначно с вероятностью 1 некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры бу­дет в чистых стратегиях. Поскольку интересы игроков противопо­ложны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш.

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

. (32)

 

Первый игрок (при любых ответах противника) будет стремить­ся найти такую стратегию, при которой α_i, обращается в максимум:

(33)

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

Аналогично определим по каждому столбцу матрицы , найдем минимальное значение β _j:

(34)

 

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

Пример. Дана платежная матрица 3x4, которая определяет выигрыши игрока А. Вычислить нижнюю и верхнюю цены задан­ной игры.

Решение Представим нашу игру в виде следующей таблицы:

Если игрок А выбирает первую стратегию, он может получить выигрыш в размере 10, 4, 11 или 7 д. е. в зависимости от выбранной стратегии игроком В. При этом выигрыш игрока будет не меньше α₁ = min{10; 4; 11; 7} = 4 д. е. независимо от поведения игрока В. Аналогично при выборе игроком А второй стратегии гарантирован­ный выигрыш α₂ = min{7; 6; 8; 20} = 6 д. е. При выборе игроком А третьей стратегии выигрыш α₃ = min{6; 23; 1; 11} = 1 д. е.

Таким образом, минимальные значения а_i, i = 1,3 опреде­ляют минимально гарантированный выигрыш для игрока А, если он выбирает соответствующую стратегию i. Величина д.е. будет гарантированным выигрышем игрока А при любых стратегиях игрока В. Выбранная игроком А вторая стратегия называется максиминной стратегией, а соответствующее ее значение выигрыша α₂ = 6 д. е. будет нижней ценой игры.

Второй игрок стремится минимизировать свой проигрыш. Вы­брав первую стратегию β₁, игрок В может проиграть не более чем β₁ = max{10; 7; 6} = 10 д. е. независимо от выбора стратегии игроком А. Аналогично рассуждая, получим следующие результаты (д. е.):

β₂ = max{4; 6; 2} = 6; β₃ = max{11; 8; 1} = 11;

β₄ = max{7; 20; 11} = 20/

 

Игрок В выбирает стратегию β₂, которая минимизирует его мак­симальные проигрыши:

Величина β = 6 д. е. будет гарантированным проигрышем игро­ка В при любых стратегиях игрока A. Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проигрыша β₂ = 6 д. е. будет верхней ценой игры.

Следует отметить, что для любой матрицы выполняет­ся неравенство β ≥ α

Если β = α, т. е. верхняя цена равна нижней цене игры, то со­ответствующие чистые стратегии называются оптимальными, а про игру говорят, что она имеет седловую точку. Седловая точка явля­ется минимальным элементом соответствующей строки и макси­мальным элементом соответствующего столбца. Эта точка есть точ­ка равновесия игры, определяющая однозначно оптимальные стра­тегии. Оптимальность здесь означает, что ни один игрок не стре­мится изменить свою стратегию, так как его противник может на это ответить выбором другой стратегии, дающей худший для пер­вого игрока результат.

Величина С = β = α называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при ис­пользовании ими оптимальных стратегий. В нашем примере цена игры С = 6 д. е., оптимальная пара стратегий — А₂ и В₂.

 

8.5.3 Понятия «доминирующий столбец» и «доминируе­мая строка»

 

Если в платежной матрице А все элементы строки А_i = (а_i1, а_i2, ..., a_in) не меньше соответствующих элементов строки A_k = (a_k1, a_k2,…, a_kn), a no крайней мере один строго больше, то строка A_i- назы­вается доминирующей, а строка A_k — доминируемой.

Аналогичны понятия «доминирующий столбец» и «доминируе­мая строка».

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

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

 

Решение

Элемент a₃₂ = -1 является наименьшим в третьей строке и на­ибольшим во втором столбце, т. е. он является седловой точкой. Поэтому цена игры С= -1, а оптимальные стратегии игроков: первого — А₃, а второго — B₂.

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

В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате полу­чится матрица

В матрице A₁ первый и третий столбцы доминируют над вто­рым, следовательно, их можно изъять. В результате платежная ма­трица принимает вид

В матрице А₂ вторая строка доминирует. После вычеркивания получится матрица A₃, состоящая из одного элемента:

А₃ = (-1). Элемент матрицы А₃ и определяет решение задачи.

 

8.5.4 Понятие смешан­ной стратегии

 

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

(35)

где P_j — вероятность выбора i-й стратегии игроком и удовлетворяет следу­ющим условиям:

(36)

Аналогично смешанная стратегия игрока В представляет собой вектор

(37)

где q_j — вероятность выбора j-й стратегии игроком В — удовлетворяет дующим условиям;

Платежная матрица игры имеет следующий вид:

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

(38)

Игрок В выбирает стратегию q_j, дающую

(39)

 

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

Этот вывод следует из теоремы фон Неймана о минимаксе. Те­орема утверждает, что выражения (38), (39) имеют одно и то же значение M(P₀,Q₀), называемое ценой игры. Если и — опти­мальные решения для обоих игроков, каждому элементу платежной матрицы a_ij соответствует вероятность *. Следовательно, оп­тимальное ожидаемое значение игры

(40)

Цена игры заключена между нижней и верхней ценами, т. е. α≤М(Р₀, Q₀) ≤β.

Решить конечную игру — это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимак­се, а следовательно, получить величину ожидаемого платежа М(Р₀, Q₀) – цену игры.

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

Решение игры обладает одним важным свойством: если игрок А использует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока А не уменьшается. Стратегии, которые смешиваются для получе­ния оптимальной стратегии, будем называть полезными. Доказано, что у игры m×n существует такое оптимальное решение, что чис­ло полезных стратегий с каждой стороны не превосходит мини­мального из чисел тип. Известно несколько методов нахождения оптимальных стратегий в играх двух лиц с нулевой суммой. Рас­смотрим один из методов — метод линейного программирования для нахождения решения игр.