Д.А. Кривошеин, Л.А. Муравей, Н.Н. Роева, О.С. Шорина, Н.Д. Эриашвили, Ю.Г. Юровицкий, В.А. Яковлев
Экология и безопасность жизнедеятельности
Учебное пособие для вузов / Под ред. Л.А. Муравья. – М.: ЮНИТИ-ДАНА, 2000. - 447 с.
Раздел 3. Моделирование в экологии
Глава 11. Оптимизационные и игровые модели
11.3. Игровые модели
Часто возникают ситуации, в которых различные участники
имеют не совпадающие между собой интересы. Математические модели и методы для
исследования таких так называемых конфликтных ситуаций получили название теории
игр [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 при ,
Ey=0 при х= и Еу<0
при . Значит,
(график на рис. 11.7). Следовательно,
(11.19)
и оптимальной смешанной стратегией для А будет выбор
первой строки с частотой и второй строки – с
частотой . Средний проигрыш В, обозначаемый F(x,y),
очевидно равен –Е (х, у). Нас интересует величина где
F(x,y)=5xy-x-4y. (11.20)
Имеем Fx=5y-1, откуда Fx< 0
при , Fx
= 0 при y = и Fx>0
при < у ≤ 1. Значит,
(график на рис. 11.8). Следовательно,
(11.21)
и оптимальной стратегией для А будет выбор первого
столбца с частотой и второго столбца – с частотой .
При оптимальных смешанных стратегиях выигрыш А и
соответственно проигрыш В в пять раз меньше максимально возможного при
одиночной игре.
Отметим также, что в рассмотренном примере мы показали
существование оптимальных стратегий и установили равенство
; (11.22)
при этом величину Е(х,у) можно трактовать как
математическое ожидание выигрыша, а величину v = определить как цену игры.
Рассмотрим теперь общий случай прямоугольной матрицы
.
При любой допустимой стратегии игрока A:
x1 ≥ 0, ...,хm ≥ 0, x1
+x2+…+xm=1
и любой допустимой стратегии игрока В: y1
≥ 0, ...,ym ≥ 0, y1 +y2+…+ym=1 математическое ожидание выигрыша равно
(11.23)
Множество допустимых стратегий x = (x1,…,xn) игрока А обозначим через X, а
множество допустимых стратегий у=(у1,...,yn)
игрока В обозначим через Y.
Рассмотренные выше примеры являются частными случаями общих
теорем [18] для игр с прямоугольными матрицами (прямоугольными играми); из них,
в частности, вытекает:
1. Величины существуют
и равны между собой; при этом величина
(11.24)
является ценой игры.
2. Всякая прямоугольная игра имеет цену; каждый игрок
в прямоугольной игре всегда имеет оптимальную стратегию.
3. Пусть Е – математическое ожидание выигрыша
в прямоугольной игре с матрицей С, имеющей цену v.
Тогда для того, чтобы элемент х* =(х1*,...,х*m)Î
Х был оптимальной стратегией для игрока А, необходимо и достаточно,
чтобы для всякого j =1, 2,...,n базисного вектора y(j) = имело место неравенство
v
≤ E (x*, y(j)). (11.25),
Аналогично для того чтобы элемент у* =(y*1,...,y*n)ÎY был оптимальной стратегией для игрока В, необходимо
и достаточно, чтобы для всякого элемента базисного вектора x(i) = имело место неравенство
E
(x(i), y*) ≤ v. (11.26)
Покажем теперь на двух примерах, как можно применить эти
утверждения для вычисления цен и определения оптимальных стратегий для
прямоугольных игр. В качестве таких примеров рассмотрим стратегии ловли на
удочку и питания рыбы[2].
Представим себе, что существование такого вида рыб,
питающихся у поверхности воды, зависит от наличия трех видов летающих
насекомых, которые обозначим через т1,т2 и m3 соответственно; насекомые появляются в зоне
захвата с частотами 15п, 5п и п (т. е. насекомых т2
в 5 раз больше чем m3, а насекомых т1
в 3 раза больше чем т2).
Допустим, что рыбак В ловит рыбу А на
насекомых одного из этих видов, насаживая их на крючок. Тогда матрица стратегий
С ловли на удочку и питания рыб имеет следующий вид (табл. 11.1):
На основании изложенных утверждений достаточно найти
неотрицательные числа х1,х2,х3, y1,y2,y3 и число, удовлетворяющее следующим
условиям:
x1+x2+x3=l,
y1+y2+y3=1, (11.27)
v ≤ -2x1,
-2y1 ≤ v,
v
≤ -6x2, -6у2
≤ v,
v
≤ -30x3, -30у3
≤ v.
Заменим последние шесть неравенств на равенства. Тогда имеем
х1=у1=, x2=y2= , x3=у3=. (11.28)
Подставляя эти значения в равенства (11.27), получим
v
=. (11.29)
. (11.30)
(11.31)
Таким образом, цена игры для рыбы будет отрицательной и
равной . Она показывает, что в конце
концов рыба будет поймана. При этом оптимальная стратегия рыбака совпадает со
стратегией питания (также оптимальной) рыбы и оптимальная стратегия уменьшает
вероятность поимки рыбы в каждом конкретном случае.
Несколько усложним задачу. Предположим, что рыболов иногда
использует приманку т4, которая может быть принята по ошибке
за одно из трех насекомых, но которая вдвое чаще вызывает подозрение у рыб.
Тогда матрица С стратегий ловли на удочку и питания рыб примет вид табл. 11.2:
Теперь достаточно найти неотрицательные числа х1,х2,х3,
y1,y2,y3,y4
и число v, удовлетворяющие следующим условиям:
x1+x2+x3=l,
y1+y2+y3+y4=1, (11.27)
v ≤ -2x1, -y4
–2y1 ≤ v,
v ≤ -6x2,
-3y4 – 6у2 ≤ v,
v ≤ -30x3,
-15y4 – 30у3
≤ v.
v ≤ -x1 –3x2 –15 x3
Левая система неравенства переопределена, а правая
недоопределена (в левой неизвестных больше, чем неравенств, а в правой меньше).
Заметим, что если последнее неравенство в правой колонке
-15y4
–30у3 ≤ v.
будет выполнено при у3=0, то оно будет выполнено и при всех у3>0.
Следовательно, полагая у3 = 0, правую систему неравенств
можно заменить системой трех линейных уравнений
-y4 –2y1
= v, -3y4
– 6у2 = v, -15y4 – 30у3 = v
с тремя неизвестными y1, у2,
у4. Ее решение, очевидно, имеет вид
Подставляя полученные выражения в равенство (11.32), где у3
=0, получим , т. е. цена игры для
рыбы отрицательна и равна
, (11.33)
что несколько меньше, чем в предыдущем случае. Оптимальная
стратегия рыбалки имеет вид
(11.34)
Изучим теперь оптимальную стратегию для рыбы, так как у3,
= 0, то и x3 = 0, т. е. насекомые
m3 слишком опасны для жизни. Тогда из
системы четырех неравенств выпадают третье и четвертое, которое при x3 = 0 является следствием двух первых (их
полусуммой). Таким образом, для определения x1,
х2 и v имеем систему трех
уравнений с тремя неизвестными
x1
+ x2 + x3
= 1, v = -2x1,
v = -6x2,
откуда
и, с учетом x3 = 0,
(11.35)
Значит, оптимальная стратегия для рыбы равна
(11.36)
цена же ее в силу (11.35) равна , т. е. совпадает с (11.34), что,
вообще говоря, вытекает из общей теории.
Модели, основанные на теории игр, представляют собой
интересный, но пока еще недостаточно изученный подход к решению стратегических
экологических задач. Разработка теории для более сложных игр с ненулевой суммой
и игр многих лиц, где между игроками могут создаваться коалиции, должна найти
эффективное применение в экологических проектах, связанных с планированием и
оценкой различных воздействий на окружающую среду.
[2]
Идея примера взята из книги Вильямса [8], которая также может служить хорошим
введением в теорию игр.
|