<<

стр. 5
(всего 5)

СОДЕРЖАНИЕ


min(? , 1)
?i ? ( Z I R ) > 0 < si (t ) ? 0 + ? s1 ? si2 ? min(? ,1) ? 1 ,
i
s1 ? si2
max i
i?I
?i ? (O I L) > 1 > si (t ) ? 0 ,
?i ? (O I E ) > si (t ) = 1 ,
? i ? ( Z I E ) > s i (t ) = 0 .
Тогда ?t ? (0, ? ) > s (t ) ? S ? .
˜

Q. E. D.
Утверждение 3.2.4. ?s , s ? R , множество ??(s , s ) состоит из одного 1 2
1 2 2

элемента.
Доказательство: Пусть есть два вектора ? 1 , ? 2 ??? и пусть существует
j ? A( ?1 ) такой, что j ? A( ? 2 ) , тогда j ? C ( ? 2 ) либо j ? M ( ? 2 ) . Но
j ? M ( ? 2 ) невозможно, так как из того, что [ s1, s 2 ] ? Q?1 следует, что

[ s1, s 2 ] ? Q? 2 , что s j (t ) = 1, t ? [0, 1] .
˜ ˜
j ? C ( ? 2 ) . Рассмотрим вектор ? такой, что A( ? ) = A( ? 2 ) U { j} ,
˜ ˜
M ( ? ) = M ( ? 2 ) , C ( ? ) = C ( ? 2 ) \ { j} . Так как [ s1, s 2 ] ? Q , то ?2

C(? 2 )
, s? C ( ? 2 ) = s ?
2
[ s 1 , s 2 ] ? {s ? R n : sC ( ? 2 ) ? R }=
?C ( ? 2 )
˜
C (?)
, s j ? R1, s? C ( ? 2 ) = s ?
2
= {s ? R n : sC ( ? ) ? R }=
˜
?C ( ? 2 )
˜ ˜
C(?) ?
= {s ? R n : sC ( ? ) ? R , s j ? R1, s?C ( ? ) \{ j} = s?C ( ? ) \{ j}} .
˜ ˜ ˜




121
˜
Из того, что j ? A(? ) следует, что s j (t ) = 0 . Тогда [ s1, s 2 ] ? Q? .
˜

˜
Но ? C ( ? ) > ? C ( ? 2 ) , в то время, как ? 2 ? Argmax ? C ( ? ) . Получили
? ?˜
?

противоречие. Значит ? 2 ? Argmax ? C ( ? ) = 1 , множество ?? состоит из
˜
???
одного элемента.
Q. E. D.
Лемма 3.2.1. Gi (s ) не убывает по si для любых s ? R . n

Доказательство: Рассмотрим произвольные вектор s ? R n и АЭ i ? I .
Существует единственный вектор состояний ? ??n такой, что s ? S ? .
?
Если i ? C (? ) то Gi ( s) = gi ( s?C ( ? ) , sC ( ? ) ) . Рассмотрим произвольный

si? ? R1 . ?
si ? si ? 1 ,
Если то
? ?
Gi ( si? , s? i ) = gi ( s? C ( ? ) , sC ( ? ) \{i} , si? ) ? Gi ( s ) = gi ( s?C ( ? ) , sC ( ? ) ) так как g (s)
частично монотонна. При si? > 1 , вектор ( si , s?i ) принадлежит S ? ? , где
?
вектор ? ? таков, что C ( ? ?) = C ( ? ) \ {i} , M ( ? ?) = M ( ? ) U {i} , A( ? ?) = A( ? ) .
?
При таких si
? ?
Gi (si? , s?i ) = gi ( s?C ( ? ) , sC ( ? ) \{i}, 1) + ( si? ? 1) > Gi (s ) = gi ( s?C ( ? ) , sC ( ? ) ) .
? ?
Аналогично доказывается, что Gi (si , s?i ) ? Gi ( s ) при si ? si .
Если i ? C ( ? ) , то без потери общности положим i ? M (? ) . Из
? ? ?
i ? M (? ) следует, что si > 1 . Если si > si , то Gi (si , s?i ) ? Gi ( s) = si ? si > 0 .
Если si > si? > 1 , то Gi (si , s?i ) ? Gi ( s) = si ? si < 0 . Поэтому, при si? > 1
? ?
функция Gi (s ) не убывает.
Если si ? [0, 1] , то ( si? , s?i ) ? S ? ? , где ? ? определяется так, что
?
M ( ? ?) = M ( ? ) \ {i} , C ( ? ?) = C ( ? ) U {i} , A( ? ?) = A( ? ) . При этом
Gi (si , s?i ) =
? ?
= gi (s?C ( ? ) , sC ( ? ) \{i} , 1) + (si ? 1) > Gi ( si? , s?i ) = gi ( s?C ( ? ) \{i} , sC ( ? ) , si? ) .
Если si? < 0 , то ( si? , s?i ) ? S ? ? , где ? ? определяется так, что
M ( ? ?) = M ( ? ) \ {i} , C ( ? ?) = C ( ? ) U {i} , A( ? ?) = A( ? ) . Из предыдущего
? ?
пункта Gi (s) > gi ( s?C ( ? ) \{i} , sC ( ? ) , 0) > gi ( s? C ( ? ) \{i} , sC ( ? ) , 0) + si? ? 0 = Gi ( si? , s? i ) .


122
Таким образом, G (s ) частично монотонна во всем R n .
Q. E. D.
Лемма 3.2.2. G (s ) непрерывна в R n .
Доказательство: Обозначим
C(?) ?
S ? = {? ? R n : sC ( ? ) ? [0, 1] , sM ( ? ) ? sM ( ? ) , s ? s A( ? ) } ,
A
где
?
?i ? M ( ? ), si ? si? ,
s M ( ? ) ? sM ( ? )
запись означает аналогично
?
s A( ? ) ? s A( ? ) означает ?i ? M ( ? ), si ? si? .
? ?
Функции s?C ( ? ) ? s? C ( ? ) и g (sC ( ? ) , s?C ( ? ) ) непрерывны в S ? .
Тогда G (s ) непрерывна как суперпозиция непрерывных функций.
Рассмотрим произвольный s ? R n . Из утверждения 3.2.2. найдется
?0 ? ? и ? 0 > 0 такие, что ?? ? (0, ? 0 ) и ?? ??0 > U? (s ) I S ? ? ? и
?? ??0 > U? (s ) I S ? = ? .
Положим ? k = min(? 0 , 1 k ), k = N . При таком определении ? k ,
?? k > 0, ?? ??0 > U ? ( s ) I S ? ? ? , то выберем для каждого ? ??0
s k , ? ? U ? k ( s) I S ? . Так как
sk, ?
последовательность такую, что
? ??0 , s k , ? ? S ? ,
sk, ? > s k >?
при и для всех то
C( ?)
sM, ( ? ) > sM ( ? ) , s k ,( ? ) > s A( ? ) , sC,(? ) ? [0, 1]
k? ? ? k
.
A? ?
? ?
sM ( ? ) ? sM ( ? ) , s A( ? ) ? s A( ? ) ,
По свойствам предельных переходов
C(?)
sC ( ? ) ? [0, 1] . То есть s ? S ? , ?? ??0 .
В силу непрерывности G (s ) на S ? можно
?? ??0 , ?? ? (0, ? 0 ) ?? ? (0, ? 0 ) ?? ( ? ) > 0 : ?s? ? U ? ( ? ) ( s) I S ? >
> G ( s) ? G ( s?) < ? .
Положим ? = min ? ? . Так как {S ? }???n образует разбиение R n , можно
?? 0
?

U (U ? ( s) I S ? ) =U? (s) .
записать Из утверждения 3.2.2
? ?? n


?? ??0 , ?? ? (0, ? 0 ), U ? (s ) I S ? = ? , то U (U? ( s) I S ? ) = U? (s) .
?? 0
?


123
?? ? (0, ? 0 ) ?? > 0 : ?s? ? U ? ( s ) > G ( s) ? G ( s?) < ? .
Q. E. D.
Лемма 3.2.3. Если g(s) непрерывна и частично монотонна, то ?r ? R n
?s ? R n такой, что G ( s) = r .
Доказательство: Возьмем произвольный r ? R n , тогда существует L > 0
такое, что ?i ? I , ri < L . В силу непрерывности g(s) ограничена и
?s ? S , g i ( s ) < M . L0 = max(L, M ) + 1 3 .
?M > 0 : ?i ? I , Обозначим
Определим следующие множества
? = {s ? R n : ?i ? I ,?3L0 < s < 3L0 } ,
? = {s ? R n : ?i ? I ,?3L0 ? s ? 3L0 } ,
?? = {s ? R n : ?K ? I : ? ? K ( s ) ? I , ?i ? K , si = 3L, ?i ? I \ K , si < 3L} .
Возьмем произвольный s ??? . Для этого s существует ? ??n такой, что
s ? S? . j ? K (s) , s j = 3L0 .
Рассмотрим некоторый АЭ тогда

Предположим, что s j = 3L0 , тогда
G j ( s ) = 3L0 ? s ? + g j ( sC ( ? ) , s?C ( ? ) ) > 3L0 ? 1 ? 2 M = 3 max( L, M ) + 1 ? 1 ? 2M >
?
j
> max( L, M ) > L > r j .

Аналогично получим оценку G j (s ) < ? L < r j при s j = ?3L0 . Таким
s ???
образом для любого найдется такой, что
j?I
r
sign (G j ? r j ) = sign( s j ? 0) ? 0 , так как L0 > 0 , и векторные поля G ( s ) ? r
r
и s ? 0 направлены не противоположно на ?? . При этом для любого
s ??? существует j?I такой, что G j (s ) ? r j ? 0 и s j ? 0 . Из того, что
векторные поля на ?? в ноль не обращаются и не противоположно
направлены следует [8], что они гомотопны и имеют одинаковое
r
вращение ? ((s ? 0), ??) = 1 . По теореме о нуле векторного поля [8]
r
существует s ? R такой, что G ( s) ? r = 0 и G ( s) = r .
n

Q. E. D.
Теорема 3.2.1. Пусть процедура планирования g : S > R n непрерывна в S
и частично монотонна в S. Тогда для любого ? ? R n с вектором точек
пиков r ? R n существуют равновесие Нэша s? (r ) и вектор состояний

124
C (?)
?
? ??n такие, что s ? (r ) = ( s? C ( ? ) , sC ( ? ) ) , где sC ( ? ) ? [0, 1] . При этом

gC ( ? ) ( s? (r )) = rC ( ? ) , g M ( ? ) (s? (r )) < rM ( ? ) и g A( ? ) ( s? (r )) > rA( ? ) .
Доказательство: В силу того, что рассматриваемое отображение
g : S > Rn удовлетворяет условиям леммы 3.2.3,
?r ? R n ?s ? R n : G ( s) = r . Тогда ?? ??n : s ? S ? . Рассмотрим вектор
?
s* = ( sC ( ? ) , s?C ( ? ) ) и получим следующие результаты:
?
rC ( ? ) = GC ( ? ) ( s) = GC ( ? ) ( sC ( ? ) , s?C ( ? ) ) = g C ( ? ) ( sC ( ? ) , s?C ( ? ) ) = gC ( ? ) ( s? ( r )) ,
? ? ?
rM ( ? ) = GM ( ? ) (s) = g M ( ? ) ( sC ( ? ) , s?C ( ? ) ) + sM ( ? ) ? sM ( ? ) > g M ( ? ) (sC ( ? ) , s?C ( ? ) ) =

= g M ( ? ) ( s? (r )),

rA( ? ) < g A( ? ) ( s? ( r )) .

Пусть i ? A(? ) , тогда ri ? g ( s? (r )) . При этом si? = si? = 1 и в силу
частичной монотонности для любых si ? [0, 1] , gi ( si , s? i ) ? g ( s? ) < ri . Из
?
gi (si , s?i ) ? gi (s? ) < ri
?
того, что следует, что
? i ( gi (s? ), ri ) ? ? i ( gi (si , s?i ), ri ) .
?
Рассматривая аналогичным образом
i ? C (? ) , i ? A(? ) убеждаемся, что s ? - равновесие Нэша при данном r.
Таким образом, утверждение доказано.
Q. E. D.
Лемма 3.3.1. Пусть выполнено А.3.3.1, тогда ?? ??n , D ? = G ( S ? ) .
0

Доказательство: Пусть s ? S ? тогда по определению G (s) имеем
C( ?)
? ?
GC ( ? ) (s ) = gC ( ? ) ( s?C ( ? ) , sC ( ? ) ) ? gC ( ? ) ( s? C ( ? ) , [0, 1] ),
? ? ?
GM ( ? ) ( s) = g M ( ? ) ( s? C ( ? ) , sC ( ? ) ) + sM ( ? ) ? sM ( ? ) > g M ( ? ) ( s?C ( ? ) , sC ( ? ) ) =
? ?
= xM ( ? ) ( gC ( ? ) ( s? C ( ? ) , sC ( ? ) )) ,




125
? ?
G A( ? ) (s ) < x A( ? ) ( gC ( ? ) (s?C ( ? ) , sC ( ? ) )).
0 0
Таким образом G ( s ) ? D ? и G ( S ? ) ? D? .
C(?)
Пусть теперь r ? D ? , докажем, что существует sC ( ? ) ? [0, 1]
0
такой,
?
что gC ( ? ) ( s? C ( ? ) , sC ( ? ) ) = rC ( ? ) . При этом из условия А.3.3.1 следует, что
? ?
gC ( ? ) ( s?C ( ? ) , sC ( ? ) ) = x ? (rC ( ? ) ) . Определим s M ( ? ) = rM ( ? ) ? xM ( ? ) (rC ( ? ) )
?
s A( ? ) > s A( ? )
0
по определению D ? . Аналогично определим и по
0
определению S ? такой s принадлежит S ? . Таким образом, D? ? G ( S ? )
0
и поэтому D? = G ( S ? ) .
Q. E. D.

Лемма 3.3.2. Пусть выполнены условия 3.3.1-3.3.3, тогда для любого i ? I
справедливы
?1 i
а) ?? ??n : i ? M ( ? ), ?r ? D? выполняется ri > Gi ( siM , GM i (r?i )) ,
0

? ?
i i
б) ?? ??n : i ? C ( ? ), ?r ? D? выполняется Gi ( siM , GM1i ( r?i )) ? ri ? Gi ( siA , G A1(r?i )) ,
0
i

? i
в) ?? ??n : i ? A( ? ), ?r ? D? выполняется Gi (siA , GA1 (r?i )) > ri .
0
i


Доказательство: Рассмотрим некоторые ? ??n и r ? D ? . По лемме
0

3.2.3 существует s ? S ? такой, что G ( s) = r .
i
i ? M (? ) , si > siM
а) Пусть тогда и
i i i
Gi ( siM , s?i ) = Gi ( s) ? si + siM < Gi ( s ) = ri G?i ( siM , s?i ) = r? i .
и Тогда
? ?
i i i
G ( siM , s?i ) = G ( siM , GM1i (r? i )) и ri > Gi ( siM , GM1i (r?i )) .
б) Если i ? C (? ) , то si ? [0, 1] . По условию А.3.3.3 можно записать, что
?1 ?
i i
Gi (siM , GM i (r?i )) ? Gi (s ) = ri ? Gi (siA , GA1 (r?i )) .
i

в) Случай, когда i ? A(? ) доказывается аналогично а).

Q. E. D.
Теорема 3.3.1. Пусть для всех элементов функции предпочтений
? i ? GSP . Пусть g (s) непрерывна и частично монотонна в S и


126
выполнены предположения А.3.3.1-3.3.3, тогда верны следующие
утверждения:
1) Существует выбор равновесия s? : Rn > S такой, что для
каждого r ? R n , s ? (r ) - равновесие Нэша в механизме g : S > R n и для
? ??n r ? D? введенные
любых и в А.3.3.1 функция

x ? ( rC ( ? ) ) = g ( s? ( r )) , где


D? = {r ? R n : rM ( ? ) < g M ( ? ) ( s? (r )), rC ( ? ) = g C ( ? ) ( s? (r )), rA( ? ) > g A( ? ) ( s? (r ))} .
2) Разбиения B и B0 совпадают и соответствующий g (s) прямой
механизм неманипулируем.
Доказательство: 1) из теоремы 3.2.1 для любого r ? R n существует
равновесие Нэша s ? ( r ) и при этом найдется ? ??n такой, что
C(?)
?
s ? (r ) = (s?C ( ? ) , sC ( ? ) ) , sC ( ? ) ? [0, 1]
где и при этом
C(?)
?
rC ( ? ) = gC ( ? ) ( s? (r )) ? gC ( ? ) ( s?C ( ? ) , [0, 1] ),

rM ( ? ) > g M ( ? ) ( s? ( r )), rA( ? ) < g A( ? ) ( s? ( r )) .
C(?)
?
Так как при выполнении А.3.3.1 ?rC ( ? ) ? gC ( ? ) ( s?C ( ? ) , [0, 1] )

x ? ( rC (? ) )
определена и единственна функция такая, что
? ?
g (s ? (r )) = xC ( ? ) (rC ( ? ) )
xC ( ? ) (rC ( ? ) ) = rC ( ? ) . При этом в силу
C(?)
x ? (rC (? ) ) ?
rC ( ? ) ? gC ( ? ) ( s?C ( ? ) , [0, 1]
единственности для всех ).
C(?)
?
r ? D? , rC ( ? ) ? gC ( ? ) ( s?C ( ? ) , [0, 1]
Тогда если то ),
? ?
rM ( ? ) > x M ( ? ) (rC ( ? ) ) , rA( ? ) < x A( ? ) (rC ( ? ) ) и первое утверждение теоремы
0
доказано. Кроме этого видно, что D? ? D ? .
2) Так как для любого r ? Rn s? (r ) - равновесие Нэша в механизме
g : S > R n , то B является разбиением R n и поэтому для любых
?1, ? 2 ??n верно D? 1 I D? 2 = ? . Докажем, что для любых ?1, ? 2 ??n

верно также, что D 0 1 I D 0 2 = ? . Допустим, что это не так, тогда
? ?

127
?1, ? 2 ??n : D0 1 I D0 2 ? ?
найдутся различные и следовательно
? ?

?1 = ? 2 .
j?I
найдется такой, что Рассмотрим варианты а)
j j

? 1 = c, ? 2 = m; ? 1 = c, ? 2 = a; в) ? 1 = m, ? 2 = a . Все остальные
б)
j j j j j j
варианты сводятся к этим трем и кроме этого доказательства вариантов б)
и в) аналогичны, поэтому рассмотрим варианты а) и б).
? ?
i i
а) для ?1 , i ? C ( ?1 ) , ?r? ? D 0 1 , Gi ( siM , GM1i (r?i )) ? ri? ? Gi (siA , G A1 (r?i ))
? ?
i
?
? i
A2 , i ? C ( ? 2 ) , ?r ?? ? D 0 2 , Gi ( siM , GM1i (r??i )) < ri?? . И если
?
и для
?

D0 1 I D0 2 ? ? r ? D0 1 I D0 2 .
то найдется Из того, что
? ? ? ?
?1
i
r ? D0 1 , ri ? Gi ( siM , GM i (r?i )) r ? D0
а из того, что следует
? M2
?1
i
ri ? Gi (siM , GM i (r?i )) . Получили противоречие.
б) Воспользуемся теми же соображениями, что и в а), при этом
неравенства для r ? D 0 1 и r ? D 0 2 и будут выглядеть следующим
? ?
образом:
? ?
i i
? ?
ri > Gi ( siM , GM1i (r?i )) ? Gi ( siA , G A1 (r?i )) > ri .
i

Получаем противоречие и случай б) доказан.
0
D? ? D ? ,
Из части 1) доказательства имеем при этом
??1, ? 2 ??n выполнено D 0 1 I D 0 2 = ? . Допустим, что D ? ? D ? для
0
? ?

некоторого ? ??n , тогда существует r ? D ? такой, что r ? D? . Так как
0


B - разбиение R n , то найдется ? ? ??n такой, что r ? D? ? , но так как
D ? ? ? D ? ? , то r ? D? I D ? ? и D 0 1 I D 0 2 ? ? . Получили противоречие,
0 0 0
? ?

значит B = B 0 .
Все условия теоремы 3.1.1 выполнены, поэтому соответствующий
g : S > Rn прямой механизм неманипулируем и существует
эквивалентный ему прямой механизм g (s? (r )) .
Q. E. D.


128
Лемма 1. Пусть A - квадратная матрица размерности n? n . Для
заданного вектора ? ??т ?1 определим квадратную матрицу A?
размерности n? n как матрицу, составленную из элементов матрицы
AI |C (? ) и E I | ?C (? ) , где AK | J , K , J ? I обозначает подматрицу
размерности K ? J матрицы A со столбцами, соответствующими
элементам множества J , и строками, соответствующими элементам
множества K .
Справедливо следующее равенство

[ ]
?1 det( AC (? ) U{i}|C (? ) U{i} )
A{i}|{i} ? A{i}| I \{i} A? \{i}| I \{i} AI \{i}|{i} =
?
.
I
det( AC (? )|C (? ) )
Доказательство.
? (?1)il + jk M l , k ( AC (? )|C (? ) )
[A ] ? , l ? C (? );
?
?1
?
=? det( AC (? )|C (? ) )
I \{i}| I \{i} k , l
? i +j
?(?1) l k ? l , k , l ? C (? ).
?

[ ]?1
? ?
Тогда A{i}|{i} ? A{i}| I \{i} AI \{i}| I \{i} AI \{i}|{i} =


(?1)il + jk M l , k ( AC (? )|C (? ) )
?
= ai , i ? al , i =
ai , k
det( AC (? )|C (? ) )
k ?C (? )
l?C (? )

(?1) il + jk M l , k ( AC (? )|C (? ) ) det( AC (? )U{i}|C (? )U{i} )
?
= ai, i ? al , i = .
ai, k
det( AC (? )|C (? ) ) det( AC (? )|C (? ) )
k?C (? )
l?C (? )
Q.E.D.

Теорема 3.4.1. Пусть функции полезности АЭ из множества I
обобщенно однопиковые, процедура планирования g : S > R n
дважды
? ??n
непрерывно дифференцируема в для любых и
S,
?C ( ? )
˜ функции gC ( ? ) (sC ( ? ) , ˜? C ( ? ) ) глобально обратимы на
s? C ( ? ) ? [0, 1] s

?g i
C( ?)
sC ( ? ) ? [0, 1] J (s ) =
множестве , матрица Якоби имеет
( s)
?s j
s ? S . Тогда для
положительные диагональные миноры для всех

129
механизма, определяемого S = [0, 1]n и процедурой g : S > R n ,
существует эквивалентный прямой механизм. ?
Доказательство. 1) Проверим выполнение условия С.1. Рассмотрим
произвольный вектор r ? R n и произвольный ? ??n и пусть
C (?)
?
rC ( ? ) ? gC ( ? ) (s?C ( ? ) , [0, 1] ).
?
rC ( ? ) = gC ( ? ) ( s? C ( ? ) , sC ( ? ) )
Уравнение имеет единственное
решение в силу условия теоремы.
Тогда соответствие
? ?
g (s?C ( ? ) , g ?1 (rC ( ? ) ))
однозначно и условие С.1 выполнено.
2) Проверим выполнение условия С.2. Доказательство проведем по
индукции. Легко показать, что для механизмов g (s ) с одним АЭ,
удовлетворяющих условиям теоремы, условия С.1-С.3 выполнены. Пусть
i i
для механизмов g I \{i} ( siA , s I \{i} ) , g I \{i} (siM , sI \{i} ) с количеством АЭ
I ? 1 условия С.2-С.3 выполнены. Докажем, что для механизма g (s) ,
удовлетворяющего условиям теоремы, выполнены условия С.2-С.3.
i
g I \{i} ( siA , s I \{i} )
Рассмотрим механизм и векторы состояний
? ??n ?1 для этого механизма. Тогда по теореме 1 для механизма
g I \{i} ( siA , s I \{i} ) множества диктаторства D? , ? ??n ?1 нормальны и
i



образуют разбиение R n ?1 .
r?i ? R n ?1 такой, что G ( s A , GM1i (r?i ))
? i
Допустим, существует
неоднозначно. Так как множества диктаторства образуют разбиение
R n ?1 , то существует единственный вектор состояний ?? ??n ?1 такой, что
r?i ? D?? = G ( S?? ) . Тогда система уравнений
? ?
? ?
i
r?i = g I \{i} ( siA , sC (?? ) , s?C (?? ) ) + E I \{i}|?C (?? ) ( s?C (?? ) ? s?C (?? ) )
имеет несколько различных решений. Найдем решение подсистемы
данной системы уравнений:
rC (?? ) = gC (?? ) ( siA , sC (?? ) , s? C (?? ) ) .
?
i

?




130
В силу условий теоремы данная подсистема уравнений имеет
?
единственное решение, т.е. существует единственный sC (?? ) такой, что

rC (?? ) = g ( siM , s? C (?? ) , sC (?? ) ) . При этом однозначно определяется решение
?
i
?
?
подсистемы
r?C (?? ) = g ? C (?? ) (siM , s? C (?? ) , sC (?? ) ) + s?C (?? ) ? s? C (?? )
??
?
i
?
?
?
?? ??
i
s?C (?? ) = g ?C (?? ) ( siM , s?C (?? ) , sC (?? ) ) ? r?C (?? ) ? s?C (?? ) .
? ?
Таким образом, уравнение
r?i = g I \{i} (siA , sC (?? ) , s?C (?? ) ) + E I \{i}|?C (?? ) ( s?C (?? ) ? s? C (?? ) )
? ? ?
i

?
i
имеет единственное решение и отображение G ( s M , s? i ) глобально
?
i
G ( s M , GM1i (r?i ))
обратимо, а значит, однозначно. Аналогично
? i
доказывается однозначность соответствия G ( s A , G A1 (r? i )) .
i


3) Необходимо доказать, что ?i ? I , ?s ? R 2 : si ? [0, 1] выполнено
?1 ?
i i
Gi ( siM , GM i (GC ( M i ) (s ))) ? Gi ( s) ? Gi ( siA , G A1 (GC ( Ai ) ( s))) .
i

Рассмотрим набор промежуточных поверхностей
?in ?
G ? siA + , sC ( Ai ) ? , sC ( Ai ) ? [0, 1]n ?1
? ?
m
? i n +1 ?
G ? siA + , sC ( Ai ) ?
и докажем, что поверхность лежит выше
? ?
m
?in ?
поверхности G ? siA + , sC ( Ai ) ? , т.е. для любых i ? I и s ? R n таких, что
? ?
m
? n n + 1?
si ? ? , ? выполнено неравенство
?m m ?
?i ?
)
(
? A n + 1 ?1 ?
Gi ? si + , G i n +1 GC ( M i ) ( s) ? ? Gi ( s) ?
? ?
m sA +
? ?
m
?i ?
( )
?A ?
n ?1
? Gi ? si + , G i n GC ( Ai ) ( s ) ? .
? ?
m s+ A
? ?
m



131
Рассмотрим некоторый фиксированный s?i ? R n ?1 и найдем
разность

)
(
?in ?
?( s? i , si ) = Gi ( s?i , si ) ? Gi ? siA + , G ?Ai n GC ( Ai ) (s?i , si ) ? .
1
? ?
m s+
? ?
m

В силу того, что для любого s I \{i} ? R n ?1 найдется единственный
? ??n ?1 такой, что s I \{i} ? S? ,
2
? n ?? n? ? n? ? n?
J I |{i}? sI \{i}, ?? si ? ? ? M1? si ? ? ? G ( sI \{i} , si ) ? G? s I \{i}, ? ?
? m ?? m? ? m? ? m?
2
? n ?? n? ? n?
? J I |{i}? sC (? ) , s? C (? ) , ?? si ? ? + M1 ? si ? ? .
?
? m ?? m? ? m?
Рассмотрим механизм планирования с n ? 1 АЭ, определяемый
? n?
процедурой планирования g (s I \{i} ) = g I \{i} ? s I \{i} , ? , s I \{i} ? [0, 1]n ?1 .
?
? m?
s I \{i} ? [0, 1]n ?1
?
Механизм планирования удовлетворяет
g (s I \{i} ) ,
условиям теоремы, и в силу индуктивного предположения
G ( s I \{i} ) = GI \{i} ? siA + n , s I \{i} ?
? i
? ?
соответствующая ему функция
? ?
m
?
удовлетворяет С.1-С.3. Множества диктаторства механизма g (s I \{i} )
?
?
нормальны и D? = G ( S? ) .
? n n + 1?
GI \{i} (s?i , si ) ? D?? , где вектор
?
Пусть для некоторого si ? ? ,
m m?
? ?
?? ??n ?1 существует и единствен в силу того, что выполнено С.2.
GC (?? ) (s ) = gC (?? ) ( sC (?? ) , s? C (?? ) ) , ??
?
? ?
G? C (?? ) (s ) = g ? C (?? ) (sC (?? ) , s?C (?? ) ) +
?

+ ( s?C (?? ) ? s? C (?? ) ) . В силу того, что функция G ( s?i , si ) непрерывна и
?
?

?in ?
возрастает по si , а функция G ? siA + , sC ( Ai ) ? глобально обратима,
? ?
m
? ??
? n n + 1?
S ?? = ?si ? ? , G ( s?i , si ) ? D?? ?
множества точек являются
?
?m m ?
? ?


132
объединением замкнутых, непересекающихся отрезков
? n n + 1?
[ sik , sik +1 ] ? ? , k +1
? , k ? Q , si < si
k
[11].
?m m ?
si ? [ si0 , s1 ]
[ si0 , s1 ]
Пусть отрезок таков, что для любых
i i
??
?
G ( sI \{i}, si ) ? D?? и si0 и s1 являются граничными точками множества S .
i

? n?
Обозначим rI0\{i} = GI \{i} ( s?i , si0 ) , в силу однозначности GI \{i} ? s I \{i} , ?
? m?
?0 n?
существует и единствен s I \{i} ? S?? такой, что rI0\{i} = GI \{i} ? s I \{i}, ? . В
0
? m?
силу того, что g (s) дважды непрерывно дифференцируема на компакте,
? ?
существуют константа M 2 > 0 и окрестность ? 2 > 0 такие, что для
?
любого r ? U? 2 (rI0\{i} ) I D?? выполнена следующая оценка
?
?1
? ?? ?
n0
?1
G i n (rI \{i} ) ? s 0\{i} ? ? J I \{i}| I \{i} ( , s I \{i} )? (rI \{i} ? rI0\{i} ) +
I
? ?
m
siA +
m
?
+ M 2 ( rI \{i} ? rI0\{i} ) 2 .
Аналогично, найдутся M 2 > 0 и окрестность ? 2 > 0 такие, что для
? n n + 1? 1
любых si ? ? , < ? 2 будет справедлива следующая оценка:
,
m m? m
? ?

(GI \{i} (s))? ? m , s0\{i} ? ?
n
G ?Ai
1
? ?
n I
? ?
+
si
m
?1
? ?? ?? ? ??
?n ?n
? ? J I \{i}| I \{i} ? , sI \{i} ?? ? J I \{i}| I \{i}? , s I \{i} ?? ( si ? si ) +
0
?m ??
?m ??
? ?
+ BI \{i}| I \{i} ( s 0\{i} ? sI \{i} )( si ? si0 ) + M 2 ( si ? si0 ) 2 ,
?
I
где BI \{i}| I \{i} - матрица с элементами, ограниченными константой, не
зависящей от s I \{i} .
Аналогично, найдутся M 2 > 0 и окрестность ? 3 > 0 такие, что для
? n n + 1? 1
любых si ? ? , < ? 3 будет справедлива следующая оценка:
,
m m? m
? ?



133
? ?
( )?n 0 ?
? ?1 n?
Gi ? G i n GI \{i} ( s) , ? ? Gi ? , sI \{i} ? +
? siA + m? ?m ?
? ?
m
?1
? ?? ?? ? ? ??
?n ?n ? ??
?n
+ ? J{i}| I \{i}? , s I \{i} ?? ? J ? \{i}| I \{i} ? , sI \{i} ?? ? J I \{i}|I \{i}? , s I \{i} ?? ( si ? si ) +
0
I
?m ?? ? ?m ?? ?m ??
? ?
+ C{i}| I \{i} ( sI \{i} ? s I \{i} )( si ? si0 ) + M 3 ( si ? si0 ) 2 ,
0 ?
где g (s) - матрица с элементами, ограниченными константой, не
зависящей от A .
Тогда
?( s ?i , si ) ? ?( s ?i , si0 ) ? J {i}|{i} ? n , s I \{i} ?( si ? si0 ) ?
? ?
?m ?
?1
? ? ?? ??
? ?n ?n ?
n
??
J I \{i}| I \{i}? , s I \{i} ? ( si ? si ) ?
0
? J{i}| I \{i} ? , sI \{i} ? ? J I \{i}| I \{i} ? , sI \{i} ??
?m ?? ?m ?? ?m ?
? C{i}| I \{i} ( s 0\{i} ? sI \{i} )( si ? si0 ) ? ( M1 + M 3 )( si ? si0 ) 2 .
?
I
В силу того, что все диагональные миноры матрицы J (s)
положительны, отображение g (s) непрерывно дифференцируемо, а
множество S замкнуто, найдутся константы A и A такие, что для
любого подмножества АЭ K ? I для диагональной матрицы J K K (s )

выполнены следующие ограничения: A ? J K K (s ) ? A , s ? S .
Выберем число промежуточных поверхностей m таким образом,
? ?
? ?
1 1A 1 1A 1
?
< min? ? 2 , ? 2 , ? 3 , ? , тогда для всех
что ,
4 A M 3 + M1 4 A n max Ci ,
? ?
m ? ?
j
? ?
j?I \{i}

отрезков [ si0 , s1 ] ? S?? справедлива следующая оценка:
i

?( s?i , s1 ) ? ?( s?i , si0 ) ?
i

? ?
? n?
det ? J I |{i}? sC (? ) , s?C (? ) , ? ?
?
? m ?C (? )U{i}|C (? ) U{i} ?
?
? ? ?s > 0 .
1
i
? ?
2 ? n?
det ? J I |{i} ? sC (? ) , s?C (? ) , ? ?
?
? m ?C (? )|C (? ) ?
?
? ?

134
Таким образом, на каждом из множеств S?? , ? ??n ?1 приращение
?( s?i , s1 ) строго положительно, откуда в силу непрерывности G (s )
i
получаем, что для любого sI \{i } ? R n?1 выполнено неравенство

( ) ( )
? i n +1 ? ? ?
?sA + ? ? G (s ) ? G ? s Ai n , G ?1 ?
?1
Gi i , G Ai n +1 GC ( M i ) (s ) n GC ( Ai ) ( s ) ?
? ? i? i
i Ai
s+ m s+
m
? ? ? ?
m m
,
из которого следует, что для механизма x = g (s) , s ? S выполнено
условие С.3, для этого механизма выполнены условия теоремы 1 и для
него существует эквивалентный прямой механизм.
Q.E.D.




135

<<

стр. 5
(всего 5)

СОДЕРЖАНИЕ