Игровые модели

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

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

Эта запись означает, что игрок А выбирает одну из строк этой матрицы, а игрок В, не зная выбора А, выбирает один из столбцов матрицы. Число на пересечении выбранных строки и столбца определяет выигрыш первого игрока (соответственно проигрыш второго). Например, если А выбрал вторую строку, а В – третий столбец, то А выиграл 5 единиц, а В их проиграл. Если же А выбрал третью строку, а В – второй столбец, то А проиграл 2 единицы, а В их выиграл.

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

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

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

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

Е(х,у)=4(1-х)у+х(1-у)=х+4у-5ху. (11.17)

Нас интересует величина max min E(x,y). Имеем

_{x y}

Е_у=4-5х, (11.18)

откуда Е_у>0 при , E_y=0 при х= и Е_у<0 при . Значит,

(график на рис. 11.7). Следовательно,

(11.19)

и оптимальной смешанной стратегией для А будет выбор первой строки с частотой и второй строки – с частотой . Средний проигрыш В, обозначаемый F(x,y), очевидно равен –Е (х, у). Нас интересует величина где

F(x,y)=5xy-x-4y. (11.20)

Имеем F_x=5y-1, откуда F_x< 0 при , F_x = 0 при y = и F_x>0 при < у ≤ 1. Значит,

(график на рис. 11.8). Следовательно,

(11.21)

и оптимальной стратегией для А будет выбор первого столбца с частотой и второго столбца – с частотой .

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

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

; (11.22)

при этом величину Е(х,у) можно трактовать как математическое ожидание выигрыша, а величину v = определить как цену игры.

Рассмотрим теперь общий случай прямоугольной матрицы

.

При любой допустимой стратегии игрока A: x₁ ≥ 0, ...,х_m ≥ 0, x₁ +x₂+…+x_m=1 и любой допустимой стратегии игрока В: y₁ ≥ 0, ...,y_m ≥ 0, y₁ +y₂+…+y_m=1 математическое ожидание выигрыша равно

(11.23)

Множество допустимых стратегий x = (x₁,…,x_n) игрока А обозначим через X, а множество допустимых стратегий у=(у₁,...,y_n) игрока В обозначим через Y.

Рассмотренные выше примеры являются частными случаями общих теорем [18] для игр с прямоугольными матрицами (прямоугольными играми); из них, в частности, вытекает:

1. Величины существуют и равны между собой; при этом величина

(11.24)

является ценой игры.

2. Всякая прямоугольная игра имеет цену; каждый игрок в прямоугольной игре всегда имеет оптимальную стратегию.

3. Пусть Е – математическое ожидание выигрыша в прямоугольной игре с матрицей С, имеющей цену v. Тогда для того, чтобы элемент х^* =(х₁^*,...,х^*_m)Î Х был оптимальной стратегией для игрока А, необходимо и достаточно, чтобы для всякого j =1, 2,...,n базисного вектора y^(j) = имело место неравенство

v ≤ E (x^*, y^(j)). (11.25),

Аналогично для того чтобы элемент у^* =(y^*₁,...,y^*_n)ÎY был оптимальной стратегией для игрока В, необходимо и достаточно, чтобы для всякого элемента базисного вектора x⁽ⁱ⁾ = имело место неравенство

E (x⁽ⁱ⁾, y^*) ≤ v. (11.26)

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

¹ Идея примера взята из книги Вильямса [8], которая также может служить хорошим введением в теорию игр.

Представим себе, что существование такого вида рыб, питающихся у поверхности воды, зависит от наличия трех видов летающих насекомых, которые обозначим через т₁,т₂ и m₃ соответственно; насекомые появляются в зоне захвата с частотами 15п, 5п и п (т. е. насекомых т₂ в 5 раз больше чем m₃, а насекомых т₁ в 3 раза больше чем т₂).

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

На основании изложенных утверждений достаточно найти неотрицательные числа х₁,х₂,х₃, y₁,y₂,y₃ и число, удовлетворяющее следующим условиям:

x₁+x₂+x₃=l, y₁+y₂+y₃=1, (11.27)

v ≤ -2x₁, -2y₁ ≤ v,

v ≤ -6x₂, -6у₂ ≤ v,

v ≤ -30x₃, -30у₃ ≤ v.

Заменим последние шесть неравенств на равенства. Тогда имеем

х₁=у₁= , x₂=y₂= , x₃=у₃= . (11.28)

Подставляя эти значения в равенства (11.27), получим

v = . (11.29)

. (11.30)

(11.31)

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

Несколько усложним задачу. Предположим, что рыболов иногда использует приманку т₄, которая может быть принята по ошибке за одно из трех насекомых, но которая вдвое чаще вызывает подозрение у рыб. Тогда матрица С стратегий ловли на удочку и питания рыб примет вид табл. 11.2:

Теперь достаточно найти неотрицательные числа х₁,х₂,х₃, y₁,y₂,y₃,y₄ и число v, удовлетворяющие следующим условиям:

x₁+x₂+x₃=l, y₁+y₂+y₃+y₄=1, (11.27)

v ≤ -2x₁, -y₄ –2y₁ ≤ v,

v ≤ -6x₂, -3y₄ – 6у₂ ≤ v,

v ≤ -30x₃, -15y₄ – 30у₃ ≤ v.

v ≤ -x₁ –3x₂ –15 x₃

Левая система неравенства переопределена, а правая недоопределена (в левой неизвестных больше, чем неравенств, а в правой меньше). Заметим, что если последнее неравенство в правой колонке

-15y₄ –30у₃ ≤ v. будет выполнено при у₃=0, то оно будет выполнено и при всех у₃>0. Следовательно, полагая у₃ = 0, правую систему неравенств можно заменить системой трех линейных уравнений

-y₄ –2y₁ = v, -3y₄ – 6у₂ = v, -15y₄ – 30у₃ = v

с тремя неизвестными y₁, у₂, у₄. Ее решение, очевидно, имеет вид

Подставляя полученные выражения в равенство (11.32), где у₃ =0, получим , т. е. цена игры для рыбы отрицательна и равна

, (11.33)

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

(11.34)

Изучим теперь оптимальную стратегию для рыбы, так как у₃, = 0, то и x₃ = 0, т. е. насекомые m₃ слишком опасны для жизни. Тогда из системы четырех неравенств выпадают третье и четвертое, которое при x₃ = 0 является следствием двух первых (их полусуммой). Таким образом, для определения x₁, х₂ и v имеем систему трех уравнений с тремя неизвестными

x₁ + x₂ + x₃ = 1, v = -2x₁, v = -6x₂,

откуда

и, с учетом x₃ = 0,

(11.35)

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

(11.36)

цена же ее в силу (11.35) равна , т. е. совпадает с (11.34), что, вообще говоря, вытекает из общей теории.

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

Контрольные задания

1. Рассмотрим задачу об «оптимальном рационе» в случае трех продуктов питания (например, хлебные, молочные и мясные продукты) и трех полезных веществ (углеводы, белки, жиры). Ценовой вектор с = (с₁, с₂, c₃) (руб.) примерно равен (10; 20; 50), а вектор b = (b₁, b₂, b₃) минимально необходимого месячного потребления полезных веществ (кг) равен (1,2; 4; 1,5). Будем предполагать также, что матрица имеет вид .

Решить задачу f₁(x)= → min при ограничениях Ах ≤ b, х ≥ 0.

2. При тех же ограничениях решить задачу f₂(x) = х₂ → max .

3. Решить двухкритериальную задачу f₁(x)→min, f₂(x)→max, заменяя ее минимизацией суперкритерия f(x)=Θf₁(x)-(1-Θ)f₂(x). Рассмотреть случаи .

4. Привести геометрическую интерпретацию задач 1–3.

5. Рассмотреть задачу поиска в случае трех районов и соотношения = 1 : 2 : 3. Найти условия на параметры p₁, р₂, p₃, при которых задача имеет решение в каждом из районов, т.е. t₁ = Т, t₂=Т, t₃ = Т , и в случае, когда время поиска в каждом из районов одно и то же (t₁ = t₂ = t₃ = T/3).

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

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