Теория игр. Оуэн (1971) (1186151), страница 23
Текст из файла (страница 23)
Если мы решим эту игру на разорение методами $ Ч.2, то мы получим значения о' и оптимальные стратегии в матричных играх Вь Число з, определенное формулой (5.3.13), обладает тем свойством, что вероятность гого, что игра будет продолжаться более г шагов, какие бы стратегии ни использовались, не превосходит з". Таким образом, если г достаточно велико, так что з" пренебрежимо мало, то мы можем .аппроксимировать стохасгичесную игру игрой, усеченной после г 'т', 8. Стохастиче«кие игри шагов. Именно в этом смысл последовательности векторов о", Кроме того, оптимальные стратегии хч' и у"" усеченных игр в пре- деле сходятся к оптимальным стационарным стратегиям стохасти- ческой игры.
—1 1+Г~2 ' — 2 1+ Г,/2 2 — 2+ Г,/2) з — 2+ Г~/2 1 + Г /2/ ' 1 -2+Г/2 (5.3.16). (5.3.17) (5.3.16) (5.3.19) Если мы используем индуктивные формулы (5.3.10) — (5.3.12), то в качестве начальных приближений к значениям получим оз (0,0,0,0), и' (0,33; — 0,13; — 0,29; — 0,5), оз (0,26; -0,19; — 0,29; — 0,53), пз (О 26.
0 19. 0 31. 0 55) оч=(0,26; — 0,19; -0,32; — 0,55), и пз есть вектор значений с точностью до двух десятичных знаков Теперь мы можем использовать оч для нахождения оптимальных 1Г.З,4. Пример. Игроки 1 и 11 имеют вместе пять единиц. На каждом шаге игры игрок 1 выбирает либо «герб», либо «решетку»; игрок П, не зная выбора игрока 1, делает аналогичный выбор. Если выборы совпадают, игрок П платит игроку ! либо три, либо одну единицу в зависимости от того, что было выбрано, «герб» или «решетка», Если выборы не совпадают, игрок 1 платит игроку 1Г две' единицы.
После каждого шага бросается монета для того„ чтобы определить, продолжать игру или закончить,ее; кроме того, игра заканчивается, как только один пз игроков разорится, Мы накладываем еще дополнительное условие, состоящее в том, что. ни один игрок не может платить больше, чем он имеет. Эту игру можно представить четырьмя игровыми элементами Гд, где /з — величина, которую имеет игрок 1 в начале данного шага, следующим образом: Гл У.
Многоигоговые игра 122 -стратегий в каждом игровом элементе. Действительно, имеем 2,72 — 1 — 2 0,84 ' 2 — 1,8Т) 2,0 1 > и эти матричные игры имеют соответственно следующие оптималь- ные стратегии: х'=(0,34; 0,66), хг =(0,38; 0,62), х'=(0,40; 0,60), х'=(0,50; 0,50)„ У. 4. РЕКУРСИВНЫЕ ИГРЫ Ч.4.1. Рекурсивные игры аналогичны играм на разорение и стохастическим играм, ио содержат некоторые усложнения, отсутствующие в других играх. Как и в стохастических играх, игровые элементы (позиции) могут повторяться; как и в играх на разорение, вероятности окончания на некотором шаге могут быть равны нулю.
Но эти два факта делают возможной не только бесконечную партию, но и ее осуществление с положительной вероятностью. Для .гого чтобы значения были конечны, выигрыш обычно определяется только после окончания игры. В случае бесконечной партии также может быть определен выигрыш а . Главная трудность в этих играх в противоположность стохастическим состоит в том, что аппроксимация рекурсивных игр усеченными обычно невозможна. Действительно, так как бесконечная партия может иметь положительную вероятность, не существует такого числа г, чтобы эффектом усечения после г шагов можно было бы пренебречь.
Кроме того, так как условие (5.3.3) заменяется более слабым условием в ~ да(1 г ! (5.4.1) Эти векторы дают оптимальные (стационарные) стратегии в сто- .хастнческой игре. У. в, Рекурсивные игра (5.4.3) (5.4.5) в бв 4вопв + ~ч~', рвсо (5.4.7) то мы увидим, что эти соотношения имеют решение, хотя, вообще говоря, и не единственное. Действительно, нетрудно показать, что функция ~(оо о„..., о,) =(ча! В„..., ча1В,) непрерывна (в действительности она удовлетворяет условию Липшица с константой 1). Кроме того, нетрудно показать, что если все ои принадлежат интервалу [..",." пипа",, гпахаЦ, с.
с. в с, с, в то все Ьсб а следовательно, и значения игр с матрицами Вк таки же принадлежат этому интервалу. По теореме Брауэра о неподвижной точке существует такой вектор о, что 1(о) = и. К сожалению, таких векторов может быть несколько, хотя во многих система уравнений, аналогичная (5.3.7) и (5.3.8), необязательно- будет иметь единственное решение. Аналогично, последовательность векторов о', определенная как в теореме Ч.З.З, необязательно будет сходиться к истинному значению игры. Приведем в качестве примера рекурсивную игру с единственным игровым элементом Г = . (5.4.2) В этом случае ясно, что если мы возьмем ов Ы вЂ” 1, то о', пв и т.
д. будут равны ов, а если мы возьмем ов = — 1, то о', ос и т.д. будут равны — 1. Следовательно, хотя последовательность значений сходится, она необязательно сходится к истинному значению игры, которое равно, очевидно, большему из двух чисел а и — 1. Точное определение заключается в следующем: рекурсивная игра состоит из конечного числа игровых элементов Гы задаваемых матрицами Аы элементы которых имеют вид а,' = с)свсав + ~я~ ~с(вссГ„ где с)ссс удовлетворяют условиям в У, армс=1, (5.4.4) д ~О. и= Если мы теперь рассмотрим соотношения о„= ча! Вы (5.4.6) где В» — матрица с элементами Гг, К Многошаговыг игры Ч.4.2. П р и м е р. Полковник Блотто, имея трн подразделения, должен захватить вражеский форпост, обороняемый двумя подразделениями. Он должен, однако, заботиться о том, чтобы в то время как он атакует вражеский форпост, противник не захватил его собственный лагерь. Атакующему для успеха необходимо иметь на одно подразделение больше обороняющих сил; если атакующие силы недостаточно велики, то они просто отступают в свой лагерь, и игра начинается снова на следующий день.
Выигрыш равен +1, если Блотто захватывает вражеский форпост, не теряя при этом свой лагерь, и равен — 1, если противник захватывает лагерь Блотто. Для бесконечной партии выигрыш предполагается равным нулю. Эту рекурсивную игру можно представить одним игровым элементом Г. Стратегии в Г соответствуют просто делению на атакующие и обороняющие силы; так, Блотто имеет четыре стратегии, соответствующие О, 1, 2, 3 атакующим подразделениям, а его противник — три стратегии. Матрица этой игры будет такова: Г Г Г Г Г 1 Г 1 — 1 1 — 1 — 1 (5.4.8) Можно показать, что значение этой игры равно +1, а з-оптимальные стратегии Блотто имеют вид (0,1 — 6 — бг,6,6г).
Чем меньше 6, тем больше у Блотто вероятность победы и тем больше математическое ожидание продолжительности игры. Таким образом, самое важное здесь, по-видимому, терпение. Однако если мы положим 6 = О, то игра может бесконечно повторяться. Таким облазом, у Блотто ие существует оптимальной стратегии. интересных приложениях они единственны.
Вообще говоря, вектором значений будет вектор, ближайший в некотором смысле к числу а . (Относительно более подробного изложения, а также доказа"тельств см. Эверетт (Ч.б) и Милнор и Шепли (Ч.10).) Наконец следует заметить, что могут существовать лишь е-оптимальные стратегии, а оптимальных стратегий может и не быть вовсе. При з- 0 математическое ожидание продолжительности игры может неограниченно возрастать; следовательно, математическое ожидание выигрыша будет иметь разрыв, так как при переходе к пре.дельной стратегии выигрыш будет меняться с и на а .
Чтобы проиллюстрировать некоторые из перечисленных выше .трудностей, приведем следующий пример (см. Эверетт [Ч. 6]). Этот пример представляет собой один из вариантов игр Блотто, называемых так по имени «главного героя» полковника Блотто. 125 1г. 5. Йифференциалвные игры У.4.3. Обобщения. Можно обсудить обобщения рекурсивных и стохастических игр в разных направлениях. Одна возможность могла бы состоять в том, чтобы допускать платежи в рекурсивных играх даже тогда, когда игра не кончается. Трудность здесь, конечно, состоит в том, что в некоторых ситуациях не будет существовать математического ожидания выигрыша. Здесь могут встретиться расходящиеся ряды, причем они могут либо расходиться и +оо или — оо, либо осциллировать.
В первых двух случаях мы -могли бы сказать, что математическое ожидание бесконечно, но гв случае осциллирующих рядов математического ожидания, конечно, не существует. Вторая возможность может состоять в том, что игровые элементы Г„имеют бесконечное число чистых стратегий. Так, Ги могут иметь вид игр на квадрате или даже более сложный вид. Эверетт 17.6) показал, что при некоторых разумных предположениях эти игры также имеют значение и е-оптимальнь|е стратегии; при этом а-оптимальные стратегии, однако, могут быть нестационарны. У.З. ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ Другое возможное обобщение стохастических н рекурсивных игр дают игры, в которых промежуток времени между ходамн убывает и, наконец, в пределе получается игра, в которой каждый игрок должен делать ход в каждый момент времени.
Ввиду того, что ходы совершаются непрерывно, естественно подозревать„что игровой элемент будет меняться весьма незначительно в течение малых промежутков времени; иначе говоря, игровой элемент меняется непрерывно. Так, если игровой элемент представлен точкой и евклидовом пространстве некоторой размерности, то обычно считают, что стратегии определяют движение этой точки (игрового элемента) посредством дифференциальных уравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
