Процессы управления и устойчивость



жүктеу 30.48 Mb.
Pdf просмотр
бет55/57
Дата27.12.2016
өлшемі30.48 Mb.
1   ...   49   50   51   52   53   54   55   56   57

мягких ограничениях на стратегию убегающего игрока, оптимальной

стратегией поведения для догоняющего игрока будет радиальная.

Объяснены причины допустимости ограничений для E. Получает-

ся, что оптимальная траектория игрока P полностью определяется

траекторией игрока E.

Литература

1. Петросян Л.А. Дифференциальные игры преследования. Л.: Изд-

во ЛГУ, 1977. 222 с.

2. Оглоблин Я.В. Об одной особенности оптимального поведения

в игре простого преследования с "линией смерти"// Процессы

управления и устойчивость: Труды 34-й научной конференции ас-

пирантов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова.

– СПб.: Изд-во СПбГУ, 2003. С. 563–568.

596


Слобожанин Н.М., Федосеев Д.Д., Чумак Л.И.

Санкт-Петербургский государственный университет

Простейшая модель игры на выживание

в случае (2, 4)–динамики

Прежде всего сформулируем общую постановку задачи [1].

Рассматривается игра двух лиц Γ на целочисленной решетке Z

n

.

Пусть имеется отображение D : Z



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

, где T и A определяются заранее.



Предполагается, что игрокам известна вся информация об игре,

то есть рассматриваемая игра является игрой с полной информа-

цией. Поэтому, по теореме Цермело – Неймана, в ней существует

ситуация равновесия по Нэшу. Целью данной работы является опре-

деление чистых оптимальных стратегий игроков в некотором част-

ном случае. Частный случай предполагает, что множество A есть

дополнение множества (Z

n

)



+

до Z


n

, метрика ρ есть равномерная

метрика, U (0) есть единичная окрестность точки 0, функция D(x)

определяется следующим образом: D(x) есть множество всех точек

y ∈ Z

n

таких, что существует единственный индекс i



1

такой, что

|x

i

1



− 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

3



| четное и число |S

4

+S



5

| четное,

то в игре Γ выигрывает второй игрок, в любом другом случае вы-

игрывает первый игрок.

Доказательство. Вообще говоря, множества S

i

зависят от но-



мера хода, но для удобства доказательства этот номер указывать

не будем. Конечной целью игры является попадание в единичную

окрестность U (0), поэтому если игра заканчивается победой кого-

либо из игроков, то |S

2

+S

3



|=0 и |S

4

+S



5

|=0 одновременно. Следова-

тельно, можно предположить, что для победы необходимо каждым

своим ходом передавать противнику четное число |S

2

+S

3



| и четное

число |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

+S



3

| и |S


4

+S

5



|. Рассмотрим ход равный 4. В этом случае число

|S

4



+S

5

| станет нечетным. Игрок 2, уменьшая любую координату из



множеств S

4

или S



5

на 4, возвращает четность числу |S

4

+S

5



|.

598


Заметим, что если один из игроков увеличит координату на 2

или на 4, то другой игрок может вернуть ситуацию, уменьшив эту же

координату на ту же величину, поэтому этот случай в доказательстве

опущен.


Осталось доказать, что в случае невыполнения условий теоремы,

выигрывает игрок 1. Возможна следующая полная группа условий:

1. |S

2

+S



3

| – четное, |S

4

+S

5



| – нечетное;

2. |S


2

+S

3



| – нечетное, |S

4

+S



5

| – четное;

3. |S

2

+S



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

< t, w(t) ∈ dz) =

B

2(2b−z)



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

(z) = P(w(t) ∈ dz) =



1

2πt



e

z2



2t

dz.


Используя строго марковское свойство винеровского процесса, а

также то, что процесс, выходя из точки x, начинается заново, полу-

чим:

601


P (τ

B

< t, w(t) ∈ da) =



P sup



0

w(s) > B, w(1) ∈ da|w(t) ∈ dz) p

t

(z)da dz =



=

−∞



P

sup


0w(s) > B|w(t) ∈ dz) P(w(1) ∈ da|w(t) ∈ dz)p

t

(z)dz =


=

−∞



P

sup


0w(s) > B|w(t) ∈ dz) P w(1 − t) ∈ d(a − z) p

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

< t, w(1) ∈ da) =



1



e

−4B2+4aB−a2

2

−B2+4Bt−at



2t(1−t)


−∞

e

−y



2

dy da+


+

1



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

(s) = w(s) + cs.



Проводя аналогичные рассуждения и используя формулы 1.0.5 и

1.2.8 главы 2 из [1], получим

602


P(τ

B

∈ dt, w



c

(1) ∈ da) = e

c2

2



+ac

B

2πt



3/2

1 − t



e

−B2+2aBt−ta2

2t(1−t)

da dt.


Важным вопросом для практики является также нахождение

времени последнего достижения уровня для случайного процесса

λ

x

= sup{t, X(t) = 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(ξ



, v)



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



= ϕ

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.


Каталог: bitstream
bitstream -> С. торайғыровтың публицистикасы
bitstream -> Қ атыстық сын есімдердің лексикалық тіркесімділігі
bitstream -> «Қазақ» газетіндегі ұлт-азаттық көтеріліс туралы мақалалардың маңызы
bitstream -> Бегімбай К. М. Дизайн және бейнелеу өнері салаларына
bitstream -> Грам м атические форм ы вы раж ения ком паративны Х отнош ений в научно-популярной лингвистической литературе
bitstream -> СҮттің Қоректік сапасы және сүттегі микроорганизмдер
bitstream -> Қазақ халқының ою-өрнектерінің Қолданылуы
bitstream -> Л. Н. Гумилев атындағы ЕҰу хабаршысы


Поделитесь с Вашими друзьями:
1   ...   49   50   51   52   53   54   55   56   57


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет