Теория игр. Оуэн (1971) (1186151), страница 24
Текст из файла (страница 24)
Точнее говоря, мы можем дать следующее определение: игровой элемент представляется набором и вещественных чисел (хь ..., х„), называемых переменными состояниями. В каждый момент времени г игрок ! выбирает набор р вещественных чисел у = (Чггь ..., ~рр), подчиненных, вообще говоря, некоторым ограничениям, обычно имеющим вид ае ~ ере '= йь где а, и в; — константы. Аналогично, игрок !1 выбирает набор а чисел ф =(фь ..., фе). Векторы <р и ф называются управляющими нервменньеми. Управляющие переменные влияют затем на изменение переменных состояния в соответствии с системой дифференциальных уравнений (называемых кинематическими уравнениями) (5.5.1) х,=г,(х1 ф, ф), 1=1, ..., и, где х; — правая производная от к, по времени. Гл.
'г'. Многошигогмг игры дифференциальная игра продолжается в соответствии с кинематическими уравнениями до окончания, которое наступает, когда переменные состояния достигают границы некоторого замкнутого подмножества %' в п-мерном пространстве; эта граница называется терминальной поверхностью. В практических приложениях это может означать, что игрок ! достаточно близок к игроку П, чтобы поймать его, или же что закончился определенный период времени (если игра должна закончиться после определенного момента времени, то время, конечно, также является переменной состояния).
Выигрыш может быть нескольких типов, наиболее общими из которых являются терминальный и интегральный выигрыши, а также нх комбинации. Если игра начинается в момент 1= О и заканчивается в момент 1 = Т в точке (оь ..., у,), то терминальный выигрыш есть просто функция б(уь ..., уи), определенная на терминальной поверхности игры, а интегральный выигрыш имеет вид т ~ К(х„..., х„)г(1. о Наиболее общий тип выигрыша, который мы будем здесь рассматривать, будет иметь вид функции б плюс интеграл вида (5.5.2). Основное уравнение. Как и в случае дискретных многошаговых нгр, метод решения дифференциальных игр состоит в замене игровых элементов их значениями с последующим решением рекуррентных уравнений для этих значений.
(Эти уравнения теперь будут дифференциальными.) Предположим теперь, что такие значения существуют; значение игры, которая начинается в точке х =(хь ..., х,), будет обозна- чатьсЯ чеРез )г(хь ..., х„). ПРедположим, что в момент 1 = О игрок 1 выбирает управляюшую переменную ф, а игрок П вЂ” управляющую переменную гр. В этом случае после малого интервала времени Ж мы увидим, что переменные состояния будут приближенно равны х+ Ьх, где Лхг=)'~(х; $, $)М, (5.5.3) и (если игра имеет интегральный выигрыш) общий выигрыш будет приближенно равен К(хь ..., х„)М.
(5.5.4) Игра начинается снова из точки х+ Лх, определенной формулой (5.5.3), и с уже достигнутым выигрышем (5.5.4). Если, начиная с момента ЛГ, используются оптимальные стратегии, то общий выигрыш будет равен К (х„..., х„) Л! + )г (х + Лх). У. 5. дифференциальные игры Однако мы знаем, что У(х+ Ьх) ы У(х)+ ~~'.~~ У,(х) Лх, (где У; — частные производные от, У по х;), или и У(х+ Лх) ем У(х)+ ~ У,(х)~,(х; ф, ф) И. е-з Следовательно, предполагая, что ф и ф — оптимальные выборы управляющих переменных в момент 1 = О, мы имеем 1'(х) гм К (х) М+ У (х) + ~ 1', (х) ~, (х; ф, ф) М, нли, полагая цг- О, К (х)+ йг Уг(х)1,(х; ф, ф) = О, (5.5.5) или, что эквивалентно, шах ппп(К(х)+ ~ У,(х)), (х; <р, ф)) =О. (5,6.6) Ф Ф Уравнение (5.5.5) или эквивалентное ему уравнение (5.5.6) изве- стно как основное уравнение.
В уравнении (5.5.6) обычно воз- можно переставить порядок двух операторов шах и т!и, хотя на практике могут встретиться множества меньшей размерности (син- гулярные поверхности), на которых это не так. Таким образом, обычно достаточно чистых стратегий; рандомизация обычно необ- ходима только в конечном числе точек в любой партии игры. Уравнения траекторий. После того как получено основное урав- нение (5.5.5), можно (как и в играх иа разорение) двигаться назад вдоль траекторий дифференциальных уравнений с терми- нальной поверхности (как ранее мы двигались вдоль траекторий разностных уравнений). Действительно, К+ Х УА=О.
Если мы продифференцируем левую часть этого равенства по хь то получим сумму членов Кг+ Х Мн (5.5.7) (где К~ — — дК(дх, и )0= дух~), (5.5.8) (5.5.9) (5.5.10) Гм У. Многошаговые игры Рассмотрим члены (5.5.9), предполагая, что управляющие переменные ~ри ограничены константами.
Мы знаем, что фа будут либо внутри, либо на границе своего интервала ограничений. Если это внутренняя точка, то д (К + ~хи~ УА)(д<ра = О, дфа/дх1 — — О. Мы видим, что член (5.5.9) равен нулю; аналогично равен нулю член (5.5.10). Рассмотрим теперь член (5.5.8). Имеем дУг д'У дУг дх дх, дх дх и поэтому дУг дУ~ дхг дУд Х вЂ” ",~=Х вЂ”.. —.= —.. (5.5.!1) Обозначим правую часть этого уравнения через Ур Если мы прибавим эту величину к выражению (5.5.7) и приравняем результат нулю, то получим уравнения $у= — [Кг(х; ф, ф)+ ~а~~ гггм(х; ф, ф)~, (55.12) которые вместе с системой хг=)~(х; ф, ф) (5.5.13) называются уравнениями траекторий дифференциальной игры.
Эти 2п уравнений вместе со значением функции О в качестве конечных условий представляют собой формальное решение игры. Иногда удобнее использовать обратное время т = Т вЂ” 1 вместо прямого ( (так как фактически для систем (5.5.12) и (5.5.13) мы имеем задачу с конечными значениями, а не с начальными значениями). 7.5.1. Пример. Игроки 1 и П управляют движением точки в евклидовой плоскости, причем каждый сообщает ей свою составляющую скорости, величина которой зависит от положения точки, а направление полностью находится в распоряжении игрока.
Скорость точки равна векторной сумме этих составляющих. Игра заканчивается, когда точка достигнет оси х; выигрыш равен времени, необходимому для завершения игры, плюс величина хаз/8„где ха — абсцисса точки, в которой заканчивается партия. потому что ф выбираются так, чтобы максимизировать выражение в скобках.
Если же, с другой стороны, фа лежит на границе, то (за исключением точек сингулярности) ф„будет оставаться на гра- нице, так что тг.5. дигрференяииевиые игры Если мы обозначим через и = у и ее = х + у величины составляющих скорости, которыми управляют соответственно игроки 1 и 11, то получим кинематические уравнения х = у соз ф+ (х + у) соз ф, у = у Б!и ф+ (х+ у) Б!и ф и выигрыш ~ Ж+хо2~8 о Таким образом, для всех х и у мы имеем К = 1. Ясно, что если и > ш, то игрок 1 всегда может продолжать игру неограниченно. Поэтому мы будем интересоваться только точками в положительном квадранте.
Основное уравнение для этой игры будет следующим: у()г~созф+$~2Б!пф)+(х+у)()г~созф+)гез!пф)= — 1. (55.14) Для того чтобы максимизировать первое слагаемое левой части (5.5.14), мы должны положить соз ф= (5.5.15) )ггуе+ р2 Б1пф= (5.5.!6) ~ 1+~2 а чтобы минимизировать второе слагаемое — положить созф= — созф, (5.5.1 7) Б!П ф = — Б!П ф. (5.5.18) Если мы подставим эти значения в (5.5.14), то после упрощений получим У)г~ + К2 — 1/х. (5.5.19) Кроме того /Н СОБ то /12 = СОБф+ СОБф, /2! Б!Пф~ 122 = Б!Пф+ Б1Пф, и после подстановки в эти выражения (5.5.15) — (5.5.19) мы получим уравнения траекторий Г~ = 1/х, )ге= О, х = — х')го у = — ХЧг2.
Если вместо прямого времени мы введем обратное время т = Т вЂ” !, то мы получим уравнения траекторий в обратном времени о о о о )г1 1/х )г2 О х х~)г1 у х~г2 о где 1', — производная У, по т и т. д. Га 1г. Многоогагоеые игры Кроме того, мы имеем начальные условия, а именно при т = 0 х==х„у=О, )г! = хо/4 )гг = )г'!/хг хог/(б' Из этих условий следует, что мы должны иметь хо ~ 2; это условие в свою очередь означает, что никакая траектория не заканчивается в точке хе > 2. Если мы продифференцируем У! по т, то получим го ! о У1= — х= УР 1,г !> это уравнение имеет решение )г, = С!е'+ С,е-', откуда в свою очередь 1 х= Сге ~ — С1е 8а (4+аз) е ~+(4-а ) е $г е-х Ег 4+ а' 4 — а' 8а 8а (5.5,20) Для того чтобы найти у, заметим, что о о у/х = уг/)гп откуда, учитывая, что )'г постоянна вдоль любой оптимальной траектории, получаем г(у/г(х = ) гг (0)/)г и Далее, )гг(0) задано, а )г, можно найти как функцию х; это преобразование дает нам уравнение ггх Г !баг — х' 16 — а" которое имеет решение Г !ба' у=С вЂ” 1гг — х .
гб — о' Положив хо —— а и разрешив начальные условия относительно С! и См мы получим Гл, )>. Многошаговыг игры 132 Учитывая, что при у = 0 будет х = а, находим Сз. Таким образом, имеем а' >ь)'!ба' — 16х' — а'х' у= — > или, что эквивалентно, х'+ "'(- .) = .з >>з 16а' у)6-а>/ !6-а> (5.5.21) иначе говоря, оптимальная траектория представляет собой окружность с центром на осн у (см. рис.
У. 5.1). Значение )г(х, у) можно найти, разрешая (5.5.21) относительно а, а затем разрешая (5.5.20) относительно т; тогда У(х, у) = т+ аэ/8. Можно также найти оптимальные стратегии: оба игрока пытаются следовать касательной к окружности (5.5.21). Игрок 1 (максимизирующий) толкает вверх (от осн х); игрок !1 толкает вниз (к оси х), Задачи !. Показать, что в рекурсивных играх вектор значений не является единственным векторои, удовлетворяющим функпиональному уравнению (5.3.7), и, кроме того, метод последовательных приближенна, использованный в стохастнческих играх, может н ве сходиться к вектору значений.
Для доказательства использовать рекурсивную игру с двумя элементами: ,>+20 Г, >, г,-(-10), г,=~ г, +20~. г, г 1О Г,. г Г, = ~-10 )з 0 — !О ~, 1О Г,>г Гз=(Гз+!), Гз=(Гз — 2), которая имеет лавушки, отображение (5.3.7), определяющее значение игры, не имеет неподвижной точки. б) Если все выигрыши в игре неотрнцательны и игра не имеет ловушек, то существует значение игры в) Если выигрыши в игре как положительны, так и отрицательны, то игра может и не иметь значения, даже если в ней нет ловушек. Привести пример, (При «наилучших» стратегиях значение будет осцнллировать.) 2. Обобщить результаты, полученные для рекурсивных игр, на игры, в которых выигрыш определен для каждой партии, даже есле игра и не заканчивается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
