Процессы управления и устойчивость
жүктеу/скачать 30,48 Mb. Pdf көрінісі
|
|
мягких ограничениях на стратегию убегающего игрока, оптимальной стратегией поведения для догоняющего игрока будет радиальная. Объяснены причины допустимости ограничений для E. Получает- ся, что оптимальная траектория игрока P полностью определяется траекторией игрока E. Литература 1. Петросян Л.А. Дифференциальные игры преследования. Л.: Изд- во ЛГУ, 1977. 222 с. 2. Оглоблин Я.В. Об одной особенности оптимального поведения в игре простого преследования с "линией смерти"// Процессы управления и устойчивость: Труды 34-й научной конференции ас- пирантов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова. – СПб.: Изд-во СПбГУ, 2003. С. 563–568. 596
Слобожанин Н.М., Федосеев Д.Д., Чумак Л.И. Санкт-Петербургский государственный университет Простейшая модель игры на выживание в случае (2, 4)–динамики Прежде всего сформулируем общую постановку задачи [1]. Рассматривается игра двух лиц Γ на целочисленной решетке Z n .
n → 2
Z n \φ. Назовем D(x) функ- цией достижимости. Содержательно D(x) мы интерпретируем как множество, в которое игрок может попасть за один ход из точки x. Задача заключается в том, чтобы перевести управляемый объект, находящийся в заданной точке x, в окрестность U (0) точки 0, задава- емую некоторой метрикой ρ. Пусть игроки 1, 2 управляют объектом (ходят) строго поочередно, и управление (ход) заключается в изме- нении координат объекта в рамках, задаваемых функцией достижи- мости. При этом предполагается, что движение объекта происходит только по отрезкам целочисленной решетки и единичный отрезок проходится за единицу времени. Выигрыши игроков определяются следующим образом. В случае, если объект переведен в окрестность U (0) за время t≤T , тот игрок, который совершил последний ход, по- лучает выигрыш равный C, где C∈N , другой игрок в этом случае получает выигрыш равный 0. Оба игрока получают выигрыш −C, C∈N , C>C в случае, если за время T объект не переведен в окрест- ность точки 0 или если объект попал в подмножество A множества Z n
Предполагается, что игрокам известна вся информация об игре, то есть рассматриваемая игра является игрой с полной информа- цией. Поэтому, по теореме Цермело – Неймана, в ней существует ситуация равновесия по Нэшу. Целью данной работы является опре- деление чистых оптимальных стратегий игроков в некотором част- ном случае. Частный случай предполагает, что множество A есть дополнение множества (Z n ) + до Z
n , метрика ρ есть равномерная метрика, U (0) есть единичная окрестность точки 0, функция D(x) определяется следующим образом: D(x) есть множество всех точек y ∈ Z n
1 такой, что |x i
− y i 1 | = 2 или 4, а для всех остальных i = i 1 : |x i − y
i | = 0.
Предполагается, что начальная точка x = (x 1 , . . . , x n ) ∈ (Z
n ) + . 597
Определение. Стратегию игрока будем называть неаварийной, если из всякой точки (x 1 , . . . , x n ) /
∈ A такой, что x 1 + . . . + x n ≤ T ,
ход игрока в соответствии с этой стратегией приводит в точку (x 1 , . . . , x n ) такую, что x 1 + . . . + x n ≤ T и (x
1 , . . . , x n ) /
∈ A. Определение. Будем говорить, что в игре Γ выигрывает иг- рок i, если x 1 + . . . + x n ≤ T и управляемый объект переводится в окрестность U (0) после хода игрока i. Определение. Будем говорить, что координата x j точки x∈Z n принадлежит множеству S i , i = 0, 5, если остаток от деления ее значения на 6 равен i. Теорема. Если число |S 2 +S
| четное и число |S 4 +S 5 | четное, то в игре Γ выигрывает второй игрок, в любом другом случае вы- игрывает первый игрок. Доказательство. Вообще говоря, множества S i зависят от но- мера хода, но для удобства доказательства этот номер указывать не будем. Конечной целью игры является попадание в единичную окрестность U (0), поэтому если игра заканчивается победой кого- либо из игроков, то |S 2 +S
|=0 и |S 4 +S 5 |=0 одновременно. Следова- тельно, можно предположить, что для победы необходимо каждым своим ходом передавать противнику четное число |S 2 +S
| и четное число |S
4 +S 5 |. Докажем это предположение. Для этого рассмотрим все возможные варианты. Сначала рассмотрим ходы игрока 1, когда он уменьшает значение координат. Вариант 1: игрок 1 уменьшает координату из множества S 0 или
S 1 на 2 или на 4. Тогда игрок 2 дополняет суммарное уменьшение координаты за ход до 6. Вариант 2: игрок 1 уменьшает координату из множества S 2 или
S 3 . В этом случае текущая четность числа |S 2 +S 3 | изменится – оно станет нечетным, следовательно, как минимум одно из множеств S 2 и S
3 будет непустым. В случае хода равного 2, игрок 2 повторяет ход противника. Если же ход игрока 1 равен 4, то игрок 2 дополняет суммарное уменьшение координаты до 6. Вариант 3: игрок 1 уменьшает координату из множества S 4 или S 5 . Рассмотрим ход равный 2. В этом случае текущие числа |S 2 +S 3 | и |S
4 +S 5 | станут нечетными. Тогда игрок 2, уменьшая любую ко- ординату из множеств S 4 или S
5 на 2, возвращает четность числам |S 2
3 | и |S
4 +S 5 |. Рассмотрим ход равный 4. В этом случае число |S 4 +S 5 | станет нечетным. Игрок 2, уменьшая любую координату из множеств S 4 или S 5 на 4, возвращает четность числу |S 4 +S
|. 598
Заметим, что если один из игроков увеличит координату на 2 или на 4, то другой игрок может вернуть ситуацию, уменьшив эту же координату на ту же величину, поэтому этот случай в доказательстве опущен.
Осталось доказать, что в случае невыполнения условий теоремы, выигрывает игрок 1. Возможна следующая полная группа условий: 1. |S 2
3 | – четное, |S 4 +S
| – нечетное; 2. |S
2 +S 3 | – нечетное, |S 4 +S 5 | – четное; 3. |S 2
3 |, |S
4 +S 5 | – нечетные. Однако эти случаи уже возникали и были разобраны выше, когда в качестве первого игрока выступал игрок 2. Теорема доказана. Замечание 1. Так как это игра с полной информацией, то в ней существует равновесие по Нэшу. Равновесная ситуация (σ 1 , σ 2 ) устроена следующим образом: если σ 1 – выигрышная стратегия пер- вого игрока, то σ 2 – любая неаварийная стратегия второго игрока, и наоборот. Замечание 2. Можно заметить, что если в условии разрешить изменение координаты также на 1 и на 3, то рассматриваемая игра представляет собой обобщение известной игры Ним, алгоритм реше- ния которой получен. Литература 1. Котина С.О., Слобожанин Н.М., Федосеев Д.Д., Чумак Л.И. Про- стейшая модель игры на выживание // Процессы управления и устойчивость: Труды 36-й научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова. – СПб.: Изд- во СПбГУ, 2005. С. 507–509. 2. Слобожанин Н.М. Информация и управление в динамических иг- рах. СПб.: Изд-во СПбГУ, 2002. 308 с. 599
Смирнова В.А. Санкт-Петербургский электротехнический университет Применение распределения функционалов в финансовой математике Стохастическая финансовая математика в своих методах исполь- зует подходы и результаты широкого класса математических дисци- плин: линейная алгебра, линейное и нелинейное программирование, исследование операций, математическая статистика. Однако, без- условно, на первом месте в этом ряду стоит стохастический анализ, или общая теория случайных процессов. В 1900 году в тезисах Парижской академии наук французский математик и экономист Луи Башелье впервые опубликовал мате- матическое описание стохастического процесса, называемого сейчас процессом броуновского движения. В приложении к некоторым проблемам стохастические методы выходят на первый план. В первую очередь это относится к тем во- просам, которые связаны с премиями по рисковым ценным бумагам, эволюция цен которых происходит под действием случая. Так, на- пример, в [5] изучается распределение времени первого достижения уровня броуновским процессом и броуновским процессом с линей- ным сносом, которое используется для вычисления цены американ- ского опциона. Американский опцион – это контракт, который обязывает про- давца продать товар по фиксированной цене в определенный срок, а покупателю дает право купить товар до срока, обозначенного в контракте. Предположим, что в опционном контракте оговорено, что в конце срока цена акции окажется не выше уровня a, покупатель же хочет купить акции в момент. когда их рыночная цена достигнет уровня B. Математическая постановка задачи звучит так: найти распреде- ление времени первого достижения винеровским процессом уровня 600
B при условии, что в конце промежутка изменения времени он на- ходится на уровне a. Предполагается, что t ∈ [0, 1], a < B, w(0) = 0. Несмотря на наличие большого количества формул в справоч- нике [1], эта постановка задачи оказалась новой. Непосредственный результат получен автором, а в работе [3] он получается как след- ствие общих теорем для броуновского моста. Обозначим τ B = min{t ∈ [0, 1], w(t) ≥ 0}; B > 0. Очевидно, что P(τ B > t) = P max 0≤s≤t
w(s) < B . Если sup
t∈[0,1] w(t) < B, то положим τ B = ∞. Имеем ([5], стр. 248) P max
0≤s≤t w(s) ∈ db; w(t) ∈ dz = 2(2b − z) t √ 2πt exp − (2b − z)
2 2t db dt, b > 0, z < b,
P(τ B
∞ B
t √ 2πt exp − (2b − z)
2 2t db dt = ϕ(t, B, dz), P(τ B ∈ dt, w(t) ∈ dz) = ϕ t (t, B, dz), ϕ(t, B, dz) = ∞ B 2(2b−z) t √ 2πt exp −
(2b − z) 2 2t db dt = 1 √ 2πt e − (2b−z)2 2t dz. Эта же формула есть в [1] (стр. 162, формула 1.1.8). Обозначим p t
1 √ 2πt e − z2 2t dz.
Используя строго марковское свойство винеровского процесса, а также то, что процесс, выходя из точки x, начинается заново, полу- чим: 601
P (τ B
∞ ∞
0 w(s) > B, w(1) ∈ da|w(t) ∈ dz) p t (z)da dz = = ∞ −∞ P sup
0 t (z)dz =
= ∞ −∞ P sup
0 t (z)dz =
= B ∞ ϕ(t, B, dz) d da a−z −∞ 1 2π(1 − t) e − y2 2(1−t)
dy+ + ∞ B 1 2π(1 − t) e − (a−z)2 2(1−t) p t (z)dz. Произведя стандартные вычисления, получим P (τ B
1 √ 2π e −4B2+4aB−a2 2 −B2+4Bt−at √ 2t(1−t)
−∞ e −y 2 dy da+
+ 1 √ 2π e − a2 2 ∞ B−at √ 2t(1−t) e −y 2 dy da. Взяв от этого выражения производную по t, получим плотность рас- пределения P (τ
B ∈ dt, w(1) ∈ da) = B 2πt
3/2 √ 1 − t e −B2+2aBt−ta2 2t(1−t) da dt.
Рассмотрим эту же задачу для винеровского процесса с линейным сносом. Используем для этого подход, предложенный в [3]. w c
Проводя аналогичные рассуждения и используя формулы 1.0.5 и 1.2.8 главы 2 из [1], получим 602
P(τ B ∈ dt, w c (1) ∈ da) = e − c2
+ac B 2πt 3/2 √ 1 − t e −B2+2aBt−ta2 2t(1−t) da dt.
Важным вопросом для практики является также нахождение времени последнего достижения уровня для случайного процесса λ x
Если X не посещает x совсем, положим λ x = 0. Если X – воз- вратная диффузия, то λ x = ∞ почти наверное для любого x. В частности, это верно для винеровского процесса. Для винеровского процесса с линейным сносом ([1], стр. 89) P x
y ∈ dt) =
|c| √ 2πt exp c(y − x) − c 2 2 − (x − y) 2 2t dt, и P x (λ y = 0) = P x (H y = ∞) = 1 − e
−2c(x−y) , c(x − y) > 0 0, c(x − y) < 0. Литература 1. Бородин А.Н., Салминен П. Справочник по броуновскому движе- нию. СПб.: Лань, 2000. 640 с. 2. Бородин А.Н. Распределение функционалов от броуновского дви- жения с линейным сносом // Кольца и модули. СПб.: Изд-во СПб- ГУ, 2003. 3. Бородин А.Н. Распределение специальных неоднородных функ- ционалов // Записки научных семинаров ПОМИ РАН, 2004. Т. 320. C. 5–29. 4. Либер А.В., Смирнова В.А. Распределение функционалов от бро- уновского движения с линейным сносом // Записки научных се- минаров ПОМИ РАН, 1997. Т. 244. C. 205–217. 5. Shreve Steven. Stochastic calculus and finance. Carnegie Mellon University, 1997. 364 p. 603
Смирнова Н.В., Тарашнина С.И. Санкт-Петербургский государственный университет Упрощенное модифицированное N-ядро в кооперативных ТП-играх n лиц Кооперативной игрой с трансферабельными полезностями (ТП- игрой) называется пара (N, v), где N – конечное множество игроков, v : P → R 1 – характеристическая функция (х.ф.), P – множество всех коалиций из N , v(ø) = 0. Класс ТП-игр является довольно изученным [1]. В этих играх известно множество решений, каждое из которых обладает как до- стоинствами, так и недостатками. Универсального решения, кото- рое всегда существовало бы, удовлетворяло всем необходимым свой- ствам и не имело недостатков, пока не предложено. Среди реше- ний кооперативных игр известны такие решения, как C-ядро, вектор Шепли, N-ядро, введенное Шмайдлером в 1969 году, модифициро- ванное N-ядро (M-ядро) [2]. В данной статье рассмотрено решение, предложенное в [3] – упрощенное M-ядро (SM-ядро), учитывающее конструктивную и превентивную силу коалиции и более легкое в по- строении, нежели N-ядро или M-ядро. Рассмотрим кооперативную ТП-игру игру (N, v), v : P → R 1 , где P – множество всех коалиций из N , v(ø) = 0, v(S) + v(T ) ≤ v(SU T ), S, T ∈ P , S ∩ T = ø, N – множество игроков. Х.ф. v : P → R 1 отражает конструктивную силу коалиции S. Рассмотрим также иг- ру с х.ф. v ∗ (S) = v(N ) − v(N \S), S ∈ P , двойственную к данной игре. Эта функция отражает превентивную силу коалиции S. Для каждого фиксированного вектора x эксцессом коалиции S назовем величину e(x, v, S) = x(S) − v(S). Двойственным эксцессом коалиции S назовем величину e(x, v
∗ , S) = x(S) − v ∗ (S).
П. Зюдхолтер определил так называемый би-эксцесс [2] ¯ e(x, v) = e(x, v, S) − e(x, v, T ), 604 S, T ∈ P , S = P , и ввел понятие модифицированного N-ядра (M- ядра).
М-ядро определяется как единственный вектор ξ ∗ на множе- стве эффективных (коллективно-рациональных) распределений та- кой, что для любого эффективного x вектор ¯ e(ξ ∗
lex ¯ e(x, v). В отличие от предложенной П. Зюдхолтером разности эксцессов всевозможных коалиций будем рассматривать сумму ¯ e(x, v, S) := e(x, v, S) + e(x, v ∗ , S), S ∈ P. Тогда e(x, v
∗ , S) = x(S) − v ∗ (S) =
x(N ) − x(N \S) − v(N ) + v ∗ (N \S) = −e(x, v, N \S). Получаем, что e(x, v, S) − e(x, v, N \S) = e(x, v, S) + e(x, v ∗ , S) = ¯ e(x, S). Таким образом, SM-ядро отличается от M-ядра тем, что рас- сматриваются разности не всех возможных непересекающихся коа- лиций, а только разности эксцессов каждой коалиции и ее дополня- ющей. В связи с чем все вычислительные процедуры значительно упрощаются. Упрощенное модифицированное N-ядро (SM-ядро) будет таким образом определяться, как единственный вектор на множестве эф- фективных распределений такой, что для любого эффективного x ¯ e(ξ ∗ , v)
lex ¯ e(x, v). Будем рассматривать игру в 0-1 редуцированной форме: v(i) = 0, i ∈ N, v(N ) = 1. Чтобы проиллюстрировать предложенное решение, рассмотрим пример.
Пример 1. "Рынок перчаток". В игре участвуют 3 игрока: иг- рок 1 обладает правой перчаткой, игроки 2 и 3 обладают каждый по одной левой перчатке. Выигрыш коалиции равен количеству пар перчаток, которые может собрать коалиция, т.е v(1) = v(2) = v(3) = v(23) = 0, v(12) = v(13) = v(123) = 1. Рассмотрим следующие реше- ния данной игры: С-ядро: c = (1, 0, 0), N-ядро: ν = (1, 0, 0), M-ядро: µ = ( 1 2
1 4 , 1 4 ), Вектор Шепли: ϕ = ( 2 3 , 1 6 , 1 6 ), SM-ядро: µ ∗ = (
2 3 , 1 6 , 1 6 ). 605 Дадим интерпретацию данным решениям. N-ядро назначает иг- року 1 весь выигрыш и ничего остальным двум игрокам, но игроки 2 и 3, объединившись, могут помешать получить игроку 1 положи- тельную прибыль. Другими словами, они вместе обладают такой же блокирующей силой, как и игрок 1. M-ядро позволяет учесть пре- вентивную силу коалиции и назначает вектор выигрышей ( 1 2
1 4 , 1 4 ). Вновь введенное решение SM-ядро также учитывает превентивную силу коалиций, однако приписывает превентивной силе меньший вес, нежели M-ядро. Вектор выигрышей, получаемых игроками в соот- ветствии с SM-ядром, равен ( 2 3
1 6 , 1 6 ). Игроки 2 и 3 здесь получа- ют выигрыши, большие 0, но меньшие, чем предписанные M-ядром. Непосредственно из формул видно, что здесь SM-ядро совпадает с вектором Шепли. В [3] было показано, что в случае, когда число игроков n = 3, SM-ядро совпадает с вектором Шепли: µ ∗
= ϕ 1 = v(N ) − v(23) 3 + v(12) + v(13) 6 , µ ∗ 2 = ϕ 2 = v(N ) − v(13) 3 + v(12) + v(23) 6 , µ ∗ 3 = ϕ 3 = v(N ) − v(12) 3 + v(13) + v(23) 6 . Поэтому возникает вопрос, будет ли это выполняться в случае n игроков. Утвердительный ответ позволил бы говорить о новой трак- товке и новых свойствах вектора Шепли. Утверждение. В кооперативной ТП-игре в случае n игроков SM-ядро не совпадает с вектором Шепли, за исключением n = 3. жүктеу/скачать 30,48 Mb. Достарыңызбен бөлісу:
|