Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 51
Текст из файла (страница 51)
в. г»р вяв частота появления стратегии 1, при этом как раз и совпадает с числом 1, (в(й), равных )„поделенным на й. Такое предполагаемое первым игроком поведение втов рого приводит с его точки зрения к платежу а ~~' ап„ко»=» торый он и стремится максимизировать, выбирая на й+ 1-м повторении чистую стратегию 1„+,, для этой стратегии справедливо ~а, и= шах ~ан,=й о,(й) (306) ° =1 в+~ ' 1см» ° =1 (деление на й ничего не меняет в выборе). Аналогично, второй игрок на й+1-м шаге выбирает ?в+, так. что ,Я~а,,? — — ш(п Яа,,г=о,(й)й.
» 1 ~ в+1 1</Ф»»=г Истинный платеж при (й+ 1)-м выборе, очевидно, равен Ф+ 1 аг, а средний платеж — — Ъ' апп=о*(й). Однако в+1'в+в В)1» аа »= » эта величина не учитывается в итеративном процессе. Существует еще второй вариант итеративного процесса, в котором первый игрок поступает также, а второй делает свой й+1-й шаг только тогда, когда ему становится известным й+1-й шаг первого игрока. В этом случае второй игрок пользуется вместо (30?) соотношением А+1 Й+ 1 ~ а;,? — — ппп ~ а~а=(й+1)о,(й+1). (308) »»1 в в+1 м!с»»=1 322 таоевмы о»ешании «нтлгоиистических иг» 1гл. ш В первом варианте процесса», и 1, выбираются произвольно. Как уже было сказано, в первом варианте » и » « » ~ч' ап,=~» а; г (Й), а ~апг=~~' а,~цй), т=! где гх(й) н 1;(й) †относительн частоты появления 1-й н 1-2 стратегий в Й повторениях игры, 1;(Й) и гт(й) есть некоторые смешанные стратегии.
Поэтому из теоремы ХХХ1Х имеем, если о — цена игры: ~» и о,(й)= шах ~~.",аыг (Й))о) пнп )г ~а,,1,(й)=о»(й). »к~~» г=» »<!<т 1=» (310) Если бы при каких-то й, и й, было бы о, (й,) = о, (й,) = о, то, очевидно, и соответствующйе (гт(й,)) и (1;(й,)) были бы оптимальными стратегиями.
Для второго варианта процессса рассуждения аналогичны. Дж. Робинсон доказала, что (311) 1пп о, (й) = 1пп о, (й) = о, » а» » а т. е. что воображаемые платежи о,(й) и о,(й) стремятся к истинной цене игры о. Доказательство утверждения (311) дано в статье Дж. Робинсон «Итеративный метод решения игр» (в сб. «Матричные игры») и в книге Карлика. Этим утверждением заканчивается описание итеративного метода решения игр, Оценка скорости сходимости этого метода дана Г. П.
Шапиро в статье «Замечание о вычислительном методе в теории игр» (в том же сборнике). Показано, что 1 ,(Й) — ~,(й)=0 (Й "+ -'). (312) Согласно этой оценке скорость сходимости, сама по себе небольшая, падает с увеличением размерности игры (п +т). На практике скорость сходимости метода в том виде, как он сформулирован выше, также сравнительно э 25) о численных матодлх»зшзния млтгичных иге 323 мала, хотя, конечно, гораздо больше, чем по (3(2); предяоло- 1 жительно скорость сходимости должна иметь порядок й На практике заметна также значительная «пульсация» метода, состоящая в том, что о,(й) и э»(й) сходятся к о весьма немонотонно. Несмотря на эти недостатки, значение итеративного метода велико, ибо он прост и в какой-то мере отражает жизненную практику невольного приобретения опыта игроками в результате многих повторений конфликтных ситуаций.
Даже само предположение о равновероятности повторения противником своих прошлых стратегий довольно точно соответствует бытующему весьма часто предложению Лапласа о равиовероятностн неопределенных факторов, в качестве которых можно здесь принимать повторение того или иного из прежних решений. Выбор наилучших чистых стратегий на каждом шаге является уже естественным следствием предположения о равновероятности использования противником прежних решений. Таким образом, ситуация с итеративным методом есть отражение некоторой реальной ситуации накопления опыта, выражающегося в постепенной выработке «хороших» стратегий (г1(Й)) и (1;(Й)).
Сходимость метода свидетельствует и о сходнмости соответствующих реальных процессов «обучения», а плохая сходимость свидетельствует, видимо, о недостаточной разумности этого процесса. «Неразумность»такого накопления опыта является естественным следствием непредусмотрительности обоих игроков (расчет на прошлое — недооценка возможностей второго игрока). Поэтому опыт применения смешанных стратегий появляется, вопреки стремлению каждого из игроков использовать только чистые стратегии. Сравнительно малая скорость сходимости итеративного метода связана, видимо, еще со следующим обстоятельством. Если, например, первый игрок уже получил оптимальную смешанную стратегию, то он отнюдь не останавливается на ней, а продолжает попытки выиграть у противника больше, если последний еще не достиг оптимальной стратегии (невольно, конечно).
и тем самым опять может Не 324 тзогзмы о вешании лнтхгонястичзских ягг (гл. 1т ухудшить свое положение. Даже если противник достиг оптимальной стратегии, то неоднозначность выбора чистой стратегии первым игроком в этих условиях опять продолжает процесс и может увести его от седловой точки. В этом и состоит причина «пульсаций». Для уменьшения количества лишних повторений можно использовать при суждении о возможности окончания процесса не величину о,(й) — о,(й), а Ь(й)= ппп о,(з) — шах о,(з))0.
(313) 1«в«а 1<в«» При прекращении процесса за приближенную цену игры следует считать величину ~ ~ пцп о, (з)+ гпах о, (з)~, (314) » 1<»С»в 1<В«»в а за оптимальные стратегии — те (г~(зв)) и (1,(з,)), для номеров итераций которых реализуются соответственно ппп и,(з) и шах ов(з). 1~»«»в 1«в~». На примере игры с матрицей 2 1 0 2 0 3 1 3 3 (шах ппп = 0; ппп шах = 2) в книге Карлина проиллюстрирован итеративный метод; мы используем его для того, чтобы показать, как можно ускорить процесс, применяя (313) вместо о,(й) — и,(й).
Итеративный процесс описывается табл. 1 (при втором варианте его и начале процесса 1,=1), где 1~(й)= ~~'., ав,1=1~(й — 1)+ави. в=1 с;(Й)= ~ ап«,=с,(А — 1)+а«в«. в 1 Из табл. 1 хорошо видна «пульсация» и связанная с ней сильная немонотонность ив (л) — о, (л). Наилучшая разница получилась на 15-м шаге (0,133), но на следующем оиа резко ухудшилась. Такая нестабильность и означает плохую сходимость разности о,(й) — ов(й).
В то же 9 251 о числннных мнтодах Рншанин мхтгичных игг 325 Таблица 1 с, (а) сР (а) Р,(а) Р, (а) с„с, (и Р,(а) Р1 (а) Р> (а) время истинная цена игры (1,000) получается для ос(А) уже при с(= 3, а о,(й) при 1=11 равна 0,909, что также достаточно близко. Посмотрим (табл. 2), как ведут себя в этом же примере величины (313). Таблица 2 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 2 4 6 8 7 8 8 1О 12 14 13 12 14 16 18 20 19 18 1 1 1 1 4 7 7 7 7 7 10 13 13 13 13 13 16 19 0 3 6 9 6 3 6 9 12 15 12 9 12 15 18 21 18 15 0,000 0,500 0,333 0,250 0,8 00 0,500 0,857 0,875 0,778 0,700 0,909 0,750 0,923 0,929 0,867 0,812 0,941 0,833 0 1 2 3 4 4 4 5 6 7 8 8 8 9 10 11 12 12 3 3 3 3 3 6 9 9 9 9 9 12 15 15 15 15 15 18 — 3 0 3 6 9 б 3 б 9 12 15 12 9 12 15 !8 21 18 3, 000 1,500 1, 000 1,500 1,800 1,000 1,286 1,125 1,000 1,200 1,364 1,000 1,154 1,071 1,0 00 1,125 1,235 1, 000 3,00 1,00 0,667 1,250 1,000 0,500 0,329 0,250 0,222 0,500 0,455 0,250 0,231 0,142 0,133 0,313 0,294 0,167 326 теОРемы О Решении АнтАГОнистических НГР [Гл.
РР При И=17 получаем Ай=0,059, что дает оценку точности, в два раза лучшую, чем минимальная О,(/«)— — О,(й) = 0,133. Если же считать достаточной оценку 0,133, то при использовании (322) она уверенно достигается уже при й=8 (вместо 15). Оценка цены игры по (323) при этом уже при й=8 даст величину 0,937, а на 14-м шаге — 0,964. Таким образом, применение (313) — (314) значительно «облагораживаег» итеративный процесс и, возможно, увеличивает быстроту сходимости. Такой подход и отражает, видимо, первоначальную идею Брауна. Интересно посмотреть, как ведет себя в этом примере истинный средний платеж О'(/«+1). Имеем: 0; 0; 0; 0; 3/5; 0; 3/7; 0; 0; 0; 3/!1; 0; 3/13; 0; 0; 0; 3/17; О.
Таким образом, О*(й+1) не стремится к цене игры. Это обстоятельство лишний раз показывает на неразумность поведения игроков в реальной ситуации (когда платежом будет, конечно, о'(й)) по способу, характерному для итеративного процесса Брауна; а между тем дело часто происходит именно так. С другими примерами применения метода Брауна и рядом модификаций, позволяющих практически улучшить сходимость, можно познакомиться в книге Е. Г. Гольштейна и Д. Б.
Юдина «Новые направления в линейном программированиим Варьируя поведение игроков во время повторений, можно получать различные итеративные процессы решения игр и в то же время изучать эффективность соответствующего поведения в многократно повторяющихся конфликтных ситуациях; в изучении такого поведения смысл есть тогда, когда это поведение проще предписываемого точным решением рассматриваемой игры. В качестве одного из примеров таких итерационных процессов можно предложить следующий, основанный на несколько более осторожном поведении !канСдого игрока, считающего противника столь же разумным и активным, как и он сам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
