Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 52
Текст из файла (страница 52)
За основу здесь опять берутся две возможности поведения каждого из игроков, характерные для процесса Брауна. На каждом, например, Й+ 1-м повторении первый игрок может или применить накопленную прошлым $251 о числинных митодлх гишинии илтиичных иги 327 .'Я а,,л„о, й Я = шах ~', а;,й, Я = и, (й), 1<в<луйЧ ч~~' ,аы,„„р; Я = ппп .'й' а;~р; Я = и, (й). 1 ~ г < ~и ~ ~~ Тогда на й+1-м шаге образуется игра с платежной матрицей Д Д а; р;(й)п (й) о,(й) о (й) 1() а йл~о дл+о (315) Здесь первая строка и первый столбец соответствуют применению стратегий (р;(й)) и (я~(й)), а вторая строка и второй столбец — стратегиям ((й+1) и /(й+1).
Задача игроков на й+1-м ходу состоит в определении оптимального поведения в игре (315) и в определении цены игры. и Игра (315) всегда имеет седловую точку. Чтобы в этом убедиться, заметим, что в силу определения 1(й+1) и г'(й+1) имеет место неравенство и и о, (й) ) )Д Д аыр< Я й, Я ) о, (й). (316) опытом смешанную стратегию или чистую стратегию, макснмизирующую платеж при накопленной за й повторений смешанной стратегии второго игрока. Точно так же второй игрок на й+1-м повторении может или действительно использовать свою накопленную смешанную стратегию или применить чистую — минимизирующую платеж в предположении, что первый игрок применит свою накопленную стратегию. Итак, здесь оба игрока равноправно участвуют в образующейся на й+1-м повторении игре, имея каждый по две стратегии. Опишем эту игру.
Пусть (р,(й)) и (я,(й)) (при 1<(~п; 1<! ..т)— смешанные стратегии игроков, накопленные опытом прежних повторений; пусть матрица исходной рассматриваемой игры есть ~(ас~!~ (!<!<а; 1<1<т) и ((й+1) и 1(й+1) таковы, что 328 твогзиы о вешания лятлгоняствческях ягг (гл. ьЧ Поэтому могут быть только следующие случаи: а) о,(Й)=о,(й)=~~ацР;(й)а~(й)' здесь седловой точ- кой является совокупность стратегий (Р,(й)) и (й (й)); цена игры и, = о, (й) = о, (й); б) о, (й) > о, (Й) и а;,„+ „~м, „находится строго между о,(й) н о,(й); тогда седловой точкой будет совокупность стратегий1(й+1) н((й+1), а цена игры иэ=а,м „о,„„, находится между о,(й) и о,(й); в) о,(й) > о,(й)>а;„о „„,; тогда седловой точкой нз-за (316) бУдет (Р;(й));1(1+1), а ценой игРы иь — о,(й); г) а;, „,г„~о >о,(й) > о,(й); здесь из-за (316) седло- вой точкой является пара 1(й+ 1); (н~(й)); цена игры и =о,(й).
Суммируя все случаи, видим, что определение опти- мальных стратегий зависит только от взаимного располо- жения величин о,(й), о,(й) н а;„+о~,„+о, причем всегда о,(й) (иэ(о,(й). Определение величины ~~~,'~а,уР,(й)у~(й) для всех этих операций не требуется и, значит, не нужно для итера- ционного процесса. Оптимальные стратегии сторон в игре (315) будем обо- значать через (Р;(й)) и (д~(й)). Таким образом, например, в случае а) Р;(й) =Р (й). й' (й) =а;(й), а в случае б) р;(Й)=0 при 1~1(й+1); р~„(й)=1; й (Й) = 0 пРи 1~1(й+ 1); ЙУ,„~м(й) = 1.
Для окончательного оформления итерационного про- цесса необходимо определить, как происходит пополнение опыта нахождения оптимальных смешанных стратегий, т. е. как совершается переход от (Р; (ЙИ (Ку (Й)) " (Р~ (Й+ 1Н ° (д (й+ 1)) и каково его начало. Аналогично методу Брауна имеем Р( (й+ 1) = — Р; (й) + — Р (Й) ~~(й+ 1) =,—,,~~(й)+ +1й~(й). з 251 о численных мзтохлх гешзния млтгичных игг 329 За начало процесса, т. е. за (р,(1)) и (д (1)), можно брать любые смешанные или чистые стратегии. По этому поводу можно лишь заметить следующее. 1) Если о=шахш(па~ близко к о=ш)пгпахаы, т.
е. с ! ! с игра близка к игре с седловой точкой, то за начальные стратегии рационально брать наилучшие чистые гаранти- рующие стратегии игроков. Близость о и и должна изме- ряться, видимо, относительно шах аы — ш!нам. ьу ьу 2) Если о не близко к о, или нежелательно опреде- лять эти величины, то можно взять за (р~(!)) и (д (!)) !1 равномерные распределения ~ †, ..., †) и ~ †, Разумеется, это относится к случаю, когда нет никаких приближенных соображений об оптимальных стратегиях.
Если же есть некие приближения, то их и следует взять за начало процесса (сходимость его не доказана). Процесс будет илн бесконечен или окончится на слу- чае а), когда его продолжение будет означать повторение все время одних и тех же стратегий (р,(й)), (д,(й)) и цены игры и=о,(л)=о,(й), а, значит, может быть оборвано ввиду нахождения точнйх оптимальных стратегий и цены игры. Интересно отметить, что, начиная с некоторого й, ситуация б) не может иметь места, если истинная цена игры не совпадает ни с одним членом матрицы а;, так как о,(А) и о,(й) будут достаточно близки к этой цене игры, если процесс сходится. Под величиной, оценивающей ошибку выработки опти- мальных стратегий и под самими приближениями опти- мальных процессов, можно понимать, как и в методе Брауна, или о, (й) — о, (й) с соответственно (р; (й)) и (уг(й)), или же в соответствии с (313) ш!по, (1) — тахо,(!) с<ь с<э и те (р,(1,)) и (д~(1,)), которые реализуют этн минимум и максимум.
Целесообразно также, видимо, при неедннственности !(й+1) или 1(й+1) брать в условной игре (315) на й+1-м шаге для реализации соответственно о,(й) и о,(й) равновероятную смесь этих !(й+1) или !(Й+1). Тогда в (315) вместо чистых !(й+1) и !(й+1) появятся соот- рртствующие осредяения этих величин, 330 ткогнмы о гвшкнин антагонистнчкскнх ягг [гл. пг й 26. Примеры аналитического решения игр в смешанных стратегиях Большое количество примеров дано в книге Карлина.
Учитывая это, рассмотрим здесь лишь четыре примера. 1. Простейшей игрой является игра с матрицей аы ам ! гты паа (318) в которой каждый из игроков располагает лишь двумя ') Некоторые такого рода изменения описаны в уже упомннавшейся книге Юдина н Гольштейна. Как видно из описания, предложенный итеративный процесс мало отличается от метода Брауна. Однако он основан на более осторожном поведении игроков и обеспечивает стремление иа к цене игры, что, видимо, более приемлемо, если итеративный процесс рассматривать как сравнитеЛьно разумное поведение игроков в реальной многократно повторяющейся конфликтной ситуации.
Пользуясь этой же идеологией„ можно, конечно, пробовать и другие варианты поведения игроков при формировании условий игры на й+ 1-м повторении или другие (вместо (317)) формулы присоединения опыта этой попытки к предыдущим'). Например, 1(я+1) и ((й+1) могут определяться не как реализующие соответствующие экстремумы, а как равиовероятиая смесь нескольких !' или г', которые наиболее близки к этим экстремумам нли вообще случайно выбираемы. В обоих этих случаях игры, аналогичные (315), могут уже решаться не в чистых, а в смешанных стратегиях, однако это не приведет к значительному усложнению процесса, поскольку игры 2 х 2 (т.
е. с двумя стратегиями у игроков) легко решаются аналитически в общем виде. В заключение этого раздела отметим, что метод Брауна получил прямое продолжение и на непрерывные игры при произвольных компактных пространствах стратегий в работе Дж. Данскина «Итеративный метод решения непрерывных игр» (в сб. «Бесконечные антагонистические игры»). $261 поимегы гашения яго 331 стратегиями. Мы уже сталкивались с такой игрой при рассмотрении итерационных методов решения игр в $25. Решим игру (318) в общем виде.
Прежде всего, если !пах [ш(п(адд; а„); ш!п(а„; а„)) —— =ппп(шах(адо а„); шах(а„; а„)), (319) аыРо + ам (1 — Ро) = аыРо+ адд (1 — Ро) = о (320) ад!По+ада(1 — 9о) =адово+а„(1 — до) =о. / Здесь Р, и до — вероятности выбора своей первой стратегии соответственно первым и вторым игроками; вторые стратегии применяются, конечно, с вероятностями 1 — р, и 1 — а,. Из (320) без труда получим а„— а,д Ро = а,д+а„— адд — а„ Ф а — а о= (321) а,д+а„— а„— а„ оо до во= Э ад, +а„— а„— адд Если из (321) получается р, или д„не удовлетворяющие неравенствам 0<Р,<1; 0<до<1, то это означает, что игра имеет седловую точку в чистых стратегиях, т. е. выполнено (319).
П. Решим игру с платежной функцией (модель 1Ч) 117 = ~ шах (х! — Рдуд; О] (322) в о при,)~ хо=У; ~ у; —.п. д=! д=! то игра имеет седловую точку в чистых стратегиях; оптимальные стратегии первого игрока (выбирающего строки)— те строки, для которых реализуется максимум в правой части; аналогично определяется и оптимальная стратегия второго игрока. Если (319) не выполнено, то по теореме Х1.11 крайние оптимальные стратегии сторон и цена игры о должны определяться из уравнений 332 тногннм о гншннии ннтнгонистичнскит игг (гн. ш Как уже отмечалось ранее, эта функция выпукла по у=(у,), и потому (теорема ХЧП) цена игры равна мини- максу для нападения, т. е. по (247): о = гпах (323) При этом оптимальной стратегией защиты является чистая стратегия У1= (324) Остается, следовательно, отыскать оптимальную стратегию нападения. Покажем, что таковой является страте- 1 гия, состоящая в том, что с вероятностью 1,= Р1~,— 1 1, Р/ все средства нападения направляются на (-й пункт защиты.
Действительно, при такой стратегии нападения платеж для любой стратегии у защиты, очевидно, равен щах (У вЂ” Р;у;; 0]) 1 1 Х',— 1 Р! Но это и означает, что выбранная стратегия оптимальна для нападения. П1. Рассмотрим матричную игру вида йхй с матрицей а,У У ... У У а,У ... У У У ... У (325) $261 пгимегм гашения ягг 333 Эта игра тесно связана с предыдущей. Действительно, положив в (322) а=Ф и р,=! — аь получим, что (325) есть игра с платежной матрицей типа (322), если только все силы защиты и нападения могут распределяться только сосредоточенно, т. е. все направляются на какой-то один пункт. Точнее, (325) получается из (322), если стратегии нападениЯ обазательно имеют вид У;=М, Уз — — О пРи 1чь1; аналогично и стратегии защиты имеют только вид х,= У; х, = О прн ! ~ з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
