Книги, научные публикации Pages: | 1 | 2 |

Р О С С И Й С К А Я А К А Д Е М И Я Н А У К ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА С.Н. Петраков Механизмы планирования в активных системах: неманипулируемость и множества диктаторства П Р ...

-- [ Страница 2 ] --

Пример 3.2.4. Рассмотрим доопределение функции g : S Rn для механизма примера 2.1.1.

Если s S(c, c), то g(s) = G(s).

( ( Если = (c, m), то C( ) = {1} и I \ C( ) = {2}, и s-c, m)) = s2c, m) = 1.

C ( При этом G(s) для всех s S(c, m) определится следующим образом:

G1(s) g1(s1, 1) 0 s1 + 2 s1 + G(s) = = + = =.

G (s) g2(s1, 1) s2 -1 s +1+ s2 -1 s1 + s 2 1 Если = (c, m), то C( ) = и s(m, m) =, а G(s) для всех s S(m, m) определится следующим образом:

G1(s) g1(1, 1) s1 -1 s1 + G(s) = = + =.

G (s) g2 (1, 1) s2 -1 s + 2 При s S(m, c), аналогично получаем:

G1(s) g1(1, s2) s1 -1 s1 + 2s G(s) = = + =.

G (s) g2(1, s2) 0 s2 + 2 G1(s) s При s S(m, a), G(s) = =.

G (s) s + 2 G1(s) s При s S(c, a), G(s) = =.

G (s) s1 + s 2 G1(s) s При s S(a, a), G(s) = =.

G (s) s 2 G1(s) s1 + 2s При s S(a, c), G(s) = =.

G (s) s 2 G1(s) s1 + При s S(a, m), G(s) = =.

G (s) s 2 Приведем некоторые свойства функции G, доказательства которых можно найти в приложении.

Лемма 3.2.1. Gi(s) не убывает по si для любых s Rn.

Лемма 3.2.2. G(s) непрерывна в Rn.

Лемма 3.2.3. Если g(s) непрерывна и частично монотонна, то для любого r Rn существует s Rn такой, что G(s) = r.

Лемма 3.2.3 позволяет доказать справедливость следующего утверждения о существовании и структуре равновесия.

Теорема 3.2.1. Пусть процедура планирования g : S Rn непрерывна в S и частично монотонна в S. Тогда для любого GSPn с вектором точек пиков r Rn существуют равновесие Нэша s(r) и вектор состояний n такие, что s(r) = (s-C ( ),sC( )), где sC( ) [0, 1]C( ). При этом gC( )(s(r)) = rC( ), gM ( ) ( (r)) < rM ( ) и s gA( )(s(r)) > rA( ).

Как видно из теоремы 3.1.1, положение равновесия для каждого профиля зависит только от вектора точек пиков и не зависит от конкретного вида функций полезности.

Таким образом, мы ввели разбиение пространства Rn на множества S и, используя это разбиение, доопределили процедуру планирования g(s), s [0, 1]n на все Rn.

Это доопределение позволило нам доказать теорему 3.2.1 о существовании и структуре равновесия Нэша в механизме (S, g). В дальнейшем свойства, устанавливаемые утверждениями 3.2.1-3.2.3 и теоремой 3.2.1 понадобятся при построении достаточных условий существования эквивалентного прямого механизма.

з3. Существование эквивалентного прямого механизма Перейдем к построению достаточных условий существования эквивалентных прямых механизмов.

- Если задано отображение f : A B, то под записью f будем - понимать соответствие f : B 2A, такое, что a B выполняется - f ( f (a)) = a.

Наложим на отображение g : S Rn и связанное с ним отображение G : Rn Rn, определенное выше дополнительные условия.

А.3.3.1. Для любых r Rn и для любых n таких, что rC( ) gC( )(s-C( ), [0, 1]C( ) ), соответствие g(s-C( ), g-1(rC( ))) однозначно.

Здесь g -1() обозначает обратное соответствие g -1 : gC( ) (s-C( ), [0, 1]C( ) ) [0, 1]C( ) для n : C( ). Для n таких, что C( ) = и C( ) = I будем считать соответствие g(s-C( ), g-1(rC( ))) однозначным по определению.

Условие А.3.3.1 гарантирует наличие функции x (rC ( )) определенной в з 1 главы II для соответствующего прямого механизма x (rC( )) = g(s-C( ), g-1(rC( ))).

Пример 3.3.1. Для механизма примера 2.1.1 проверим выполнение предположения А.3.1.1. Рассмотрим = (c, m).

s1 + gC( )(s-C( ), sC( )) = g(s1, 1) =. Обратное соответствие s + g -1(rC( )) = g(c1 m)(r1) для всех r1 g1(1, [0, 1]) = [2, 3] задается, выражением g(-1 m)(r1) = r1 - 2. Очевидно, что оно однозначно. Если c, = (m, m), то C( ) = и А.3.3.1 выполнено по определению.

i Определим вектор состояния M n для любого i I таким i i образом, что C(M ) = I \{i} и M (M ) = {i}. Аналогично определим Ai n так, что C(Ai ) = I \{i}, A(Ai ) = {i}.

А.3.2.2. Для любых i I, r-i Rn-1 соответствие i - G(sM, GM (r-i)) однозначно и i I, r-i Rn-1 соответствие i i G(sA, GA1(r-i )) однозначно, где G-1 : Rn-1 Rn-1 и G-1 : Rn-1 Rn- i Ai Ai i i обозначают обратные соответствия для G-i (siM, s-i ) и G-i(siA, s-i).

- То, что соответствия GA1 : Rn-1 Rn и GA1 : Rn-1 Rn i i определены на всем Rn-1 доказывается аналогично лемме 3.2.3.

Условие А.3.3.2 и определяемое ниже условие А.3.3.3 позволяют гарантировать совпадение совокупностей D и D0.

Пример 3.3.2. Для механизма примера 2.1.1 проверим выполнение 1 предположения А.3.3.2. M = (m, c), M = (c, m), A1 = (a, c), A2 = (c, a).

s2 +1, s2 >1;

2s + [0, 1];

M1 G(s1, s2) = 1+ s2, s, s2 < 0.

s2 + s2, s2 < 0;

2s G(s1A, s2 ) =, s2 [0, 1];

s, s2 > 1.

s - Обратные соответствия G-11 : R1 R1 и GA1 : R1 R1 будут M - - определяться следующими выражениями GM11(r2) = r2 -1 и GA1(r2) = r M1 - для всех r2 R1. Графики соответствий G(s1, GM1(r2)) и G(s1A,GA1 (r2)) изображены на рис. 3.4 с обозначениями M1 и A соответственно, а сами соответствия определяются выражениями:

r > 2;

, r 2r - [1, 2];

M1 G(s1, G-11 (r2 )) = r, r M, r2 < 1;

r s A M G ( s ) s 1 2 - M - G ( s1A, G (r2 )) G ( s1, G (r2 )) A M 1 -1 - (r2 )) (r2 )) Рис. 3.4. Соответствия G ( s1A, G A1 и G (s1M, G M для примера 3.3. r < 0;

, r 2r [0, 1];

G(s1A,G-1(r2)) = r, r A >1.

r2, r M A Аналогично соответствия G(s2,G-12 (r2)) и G(s2, G-1 (r1)) M A изображены на рис. 3.5 с обозначениями M и A2 и задаются выражениями r > 3;

2, r r M1 G(s1,G-11 (r2 )) =, r2 [2, 3];

r - M r 1, r2 < 2;

s M M - G (s, G (r1 )) M G ( s ) M2 1 A A - G ( s, G (r1 )) A s 1 2 A M - 1 A2 - 2 2 M A Рис. 3.5. Соответствия G ( s, G (r1 )) и G ( s, G (r1 )) для примера 3.2. r >1;

1, r r [0, 1];

A2 G(s2, G-1 (r1)) = r, r A r 1, r2 < 0.

А.3.3.3. для любых i I и для любых s : si [0, 1] выполняется i i - Gi(siM,GM1 (GC(M ) (s))) Gi (s) Gi (siA,GA1(GC( Ai )(s))).

i i i Условия А.3.3.2 и А.3.3.3 позволяют гарантировать совпадение совокупностей D и D0.

Пример 3.3.3. Очевидно, оба неравенства:

M -1 A G2(s2, GM 2 (GC(M 2 )(s))) G2(s) G2(s2, G-1 (GC( A2 )(s))) и A M1 -1 G1(s1, GM1(GC(M1)(s))) G1(s) G1(s1A, GA1(GC( A1)(s))) не выполняются, например, в точке s = (0.5, 0.75), G(s) = (1.75, 1.25). Так M1 G1(s1,GM11 (GC(M 1)(s))) = 1.5 < G1(s) = 1.75 и G1(s) =1.75 < G1(s1A,GA1i (GC( A1i )(s))) = 2 ;

M G2(s2, GM12 (GC(M 2 )(s))) = 1< G2(s) =1.25 (см. рис. 3.6 и 3.7).

Далее покажем, что введенные условия А.3.3.1 - А.3.3.3 достаточны для существования эквивалентного прямого механизма.

Соответствующий прямой механизм будет характеризоваться своими B - разбиением и B0 совокупностью. Теорема 3.2.1 позволяет для соответствующего g(s) прямого механизма определить совокупность B множеств D 0 Rn, n таких, что D 0 = {r Rn : rC( ) = gC( )(s-C( ), [0, 1]C( ) ), rM ( ) > xM ( )(rC( )), rA( ) < xA( )(rC( ))}.

Лемма 3.3.1. Пусть выполнено А.3.3.1, тогда n, D 0 = G(S ).

Приведенная лемма 3.3.1 показывает, что при условии А.3.3. множества совокупности D 0 являются образами множеств совокупности S при отображении G : Rn Rn.

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

i Теорема 3.3.1. Пусть для всех элементов функции предпочтений GSP. Пусть g(s) непрерывна и частично монотонна в S и i выполнены предположения А.3.3.1-3.3.3, тогда верны следующие утверждения:

1) Существует выбор равновесия s : Rn S такой, что для каждого r Rn, s(r) -равновесие Нэша в механизме g : S Rn и для любых n и r D введенные в А.3.3.1 функции x (rC( ) ) = g(s(r)), где D = {r Rn : rM ( ) < gM ( )(s(r)), rC( ) = gC( )(s(r)), rA( ) > gA( )(s(r))}.

2) Разбиения B и B0 совпадают и соответствующий g(s) прямой механизм неманипулируем.

Таким образом, мы получили условия на непрямой механизм, достаточные для существования эквивалентного прямого механизма (Т.3.2.1). Несмотря на то, что эти условия накладываются на исходный непрямой механизм, проверка их в общем случае затруднительна. В следующем параграфе мы рассмотрим способы применения Т.3.2.1 для доказательства существования эквивалентного прямого механизма для частных случаев механизмов планирования.

з4. Существование эквивалентного прямого механизма для дифференцируемых процедур планирования и линейных процедур планирования Условия А.3.3.1-3.3.3 существования эквивалентного прямого механизма, хотя и являются достаточно общими, недостаточно конструктивны и требуют упрощения. Особенно простой вид они принимают для дифференцируемых и линейных процедур планирования.

Будем говорить, что функция n - переменных g(s) дважды непрерывно дифференцируема на множестве S если в любой точке s (0;

1)n определены и непрерывны производные функции g(s) до второго порядка включительно и если si = {0;

1} то определены и непрерывны соответственно справа и слева правые и левые производные до второго порядка включительно.

Теорема 3.4.1. Пусть функции полезности АЭ из множества I обобщенно однопиковые, процедура планирования g : S Rn дважды непрерывно дифференцируема в S, для любых n и ~ ~ s-C( ) [0,1]-C( ) функции gC( )(sC( ), s-C( )) глобально обратимы на gi множестве sC( ) [0, 1]C( ), матрица Якоби J (s) = (s) имеет s j положительные диагональные миноры для всех s S. Тогда для механизма, определяемого S = [0, 1]n и процедурой g : S Rn, существует эквивалентный прямой механизм.

Доказательства следующих следствий 3.4.1-3.4.3 очевидны при использовании результатов о существовании обратной функции для непрерывной функции одного переменного [7], разрешимости систем линейных уравнений [1] и глобальной обратимости функций [4].

Рассмотрим дифференцируемые процедуры планирования.

Отметим, что дифференцируемость в замкнутом множестве предполагает, что окрестность точки определяется как пересечение окрестности в Rn и этого множества. Дифференцируемость в открытом множестве, например Rn, предполагает, что под окрестностью понимается, например, шар.

Поэтому, при переходе от g(s), определенной на S, к G(s) - ее доопределению на все Rn, на границе S функция G не будет дифференцируемой.

Следствие 3.4.1. Пусть n = 2, процедура планирования g(s) дважды непрерывно дифференцируема и удовлетворяет следующим условиям:

gi (s) > 0, s [0, 1]2 ;

si g1 g (s) (s) s1 s det g2 g2 > 0, s [0,1]2.

(s) (s) s1 s Тогда для механизма определяемого S = [0, 1]2 и процедурой g : S R2 существует эквивалентный прямой механизм.

Следствие 3.4.2. Пусть задана числовая матрица A размерности n n и механизм планирования с процедурой планирования x = As + x0, s [0,1]n, x0 Rn. Если все диагональные миноры матрицы A больше нуля, то для механизма определяемого S = [0, 1]n и процедурой x = As + x0, s [0,1]n существует эквивалентный прямой механизм.

Следствие 3.4.3. Пусть процедура планирования g : S Rn дважды gi непрерывно дифференцируема в S, и матрица Якоби J (s) = (s) s j положительно определена для всех s S. Тогда для механизма, определяемого S = [0, 1]n и процедурой g : S Rn, существует эквивалентный прямой механизм.

Данный результат накладывает достаточно сильные ограничения на процедуру планирования, так как положительно определенная матрица gi g j должна быть симметричной, то есть i, j I, =.

s si j Отметим, что условия натуральности системы [84] в применении к механизмам планирования схожи с условиями теоремы 3.4.1.

Результаты настоящего параграфа дают удобные достаточные условия существования эквивалентных прямых механизмов планирования и значительно расширяют класс механизмов планирования, для которых доказано существование эквивалентного прямого механизма.

В следующем параграфе мы используем условия теорем 3.4.1 3.4.3 для анализа влияния множества возможных сообщений на существование эквивалентного прямого механизма.

з5. Влияние множества возможных сообщений на существование эквивалентного прямого механизма Интересным представляется тот факт, что существование эквивалентного прямого механизма зависит не только от процедуры планирования, но и от множества возможных сообщений. Рассмотрим следующий пример.

Пример 5.1. Пусть механизм планирования в системе с двумя элементами выглядит следующим образом:

x1 = g1(s1, s2) = s1 + cos s2 ;

x2 = g2(s1, s2) = s1 + s2, s1, s1 [0, 1]2.

Множества разбиения B приведены на рис. 3.6, а множества совокупности B0 на рис. 3.7. При этом видно, что соответствующий прямой механизм манипулируем, а множества D(c, m), D(m, c), D(a, c) не совпадают со множествами D(0c, m), D(0m, c), D(0a, c) соответственно.

D(0 D( D(c, m) D(m, m) c, m) m, m) D( a, m) D(a, m) D(m, c) D( 1 m, c) D(c, c) D(0 ) c, c D(0a, c) D(a, c) D( m, a) 0 0 D(0a, a) D(c, a) 2 D(m, a) D(0 D(a, a) c, a) Рис. 3.6. Рис. 3.7.

Изменяя множество возможных сообщений исходного механизма 0, таким образом, что новое множество сообщений будет ST = [0, 1], получим, что для нового механизма, определяемого ST и процедурой g(s), выполнены условия А.3.3.1-3.3.3, которые гарантируют выполнение теоремы 3.3.1. Тем самым, для нового механизма существует эквивалентный прямой механизм. Множества разбиения B для механизма, определяемого ST и g(s), изображены на рис. 3.8.Х D(m, m) D(c, m) D(a, m) D(m, c) D(c, c) D(a, c) 0 D(c, a) 2 D(m, a) D(a, a) Рис. 3. Рассмотрим постановку следующей задачи о наибольшем множестве возможных сообщений, для которого при заданной процедуре планирования существует эквивалентный прямой механизм.

Пусть задан механизм планирования G = (S, g), g : S Rn, где S =. Функции полезности АЭ однопиковые с точками пика из [0,1] iI Rn. Функция полезности центра (x, r), где r - вектор точек пиков АЭ.

Эффективность функционирования АС K = min max (g(s*),r).

N rRn s*EG (r) Обозначим S - множество всех подмножеств S вида, Di ], где [di iI ~ 0 di Di 1. Определим подмножество S S подмножеств вида, Di ], где 0 di Di 1 таких, что для механизма G = (S, g), где [di iI ~ S S существует эквивалентный прямой механизм. Решением задачи будет множество S S такое, что S* Argmax min max (g(s*), r).

~ N rRn s*EG (r) SS Таким образом, для построения механизма, эквивалентного исходному необходимо решить задачу о наибольшем множестве возможных сообщений таком, что для построенного механизма существует эквивалентный прямой механизм. Для этого достаточно найти множества возможных сообщений такие, что выполнены условия А.3.3.1 3.3.3. При этом соответствующий G = (S*, g) прямой механизм будет неманипулируемым, а множество S * максимально в смысле эффективности механизма G.

Заключение В настоящей работе рассмотрен ряд подходов к изучению неманипулируемости механизмов управления в социально-экономических системах и определен класс активных систем (нетрансферабельными, обобщенно однопиковыми и сепарабельными функциями полезности АЭ) в которых существуют недиктаторские механизмы планирования [2,7,53].

Для активных систем с нетрансферабельными, сепарабельными и обобщенно однопиковыми функциями полезности АЭ предложен метод исследования неманипулируемости механизмов планирования, заключающийся в анализе множеств диктаторства и обобщающий методы, предложенные в работах [7,12,13,14,17,53].

На основе предложенного подхода получены условия неманипулируемости прямых механизмов планирования и условия существования эквивалентных прямых механизмов.

Приведем краткий перечень основных результатов настоящей работы и перспектив дальнейших исследований:

1. Получены достаточные условия неманипулируемости прямых механизмов планирования (Т.2.1.1);

2. Получены необходимые и достаточные условия коалиционной неманипулируемости прямых механизмов планирования (Т.2.2.1);

3. Получены достаточные условия неманипулируемости прямых механизмов планирования с векторными планами (Т.2.3.1);

4. Получены достаточные условия существования эквивалентного прямого механизма для непрямых механизмов планирования общего вида (Т.3.3.1);

5. Получены достаточные условия существования эквивалентных прямых механизмов для непрямых механизмов планирования, процедуры планирования которых дифференцируемы (Т.3.4.1) и как следствия получены условия существования эквивалентного прямого механизма для механизмов планирования частного вида:

- для механизмов с двумя АЭ, процедуры планирования которых дифференцируемы (Следствие 3.4.1);

- для механизмов, процедуры планирования которых линейны (Следствие 3.4.2);

- для дифференцируемых механизмов планирования с положительно определенной матрицей Якоби (Следствие 3.4.3).

6. Проанализировано влияние множества возможных сообщений элементов на существование эквивалентного прямого механизма.

На рис. 4.1 приведена схема результатов работы (доказанные другими авторами результаты изображены жирными линиями и затенением, оригинальные результаты - тонкими линиями). Так же на рис. 4.1 приведены перспективные задачи будущих исследований неанипулируемости механизмов планирования (изображены штриховыми линиямии, которые пронумерованы согласно следующему списку):

1. Получение достаточных условий существования эквивалентного прямого механизма, которые гарантируют существование эквивалентного прямого механизма для механизмов распределения ресурса и активной экспертизы;

2. Изучение возможности построения эквивалентного прямого механизма (Т.3.3.1) для случая, когда допускается коалиционное поведение;

3. Получение необходимости в связи результатов Т.2.1.1 и Т.1.2.13;

4. Изучение манипулируемости и коалиционной неманипулируемости для случаев, когда в качестве планов выбирается вектор Евклидова пространства;

5. Другие конструктивные достаточные условия существования эквивалентного прямого механизма;

6. Прикладные модели механизмов планирования.

7. Более общими по сравнению с исследованием неманипулируемости (в рамках общей модели, описанной в первой главе настоящей работы) являются задачи синтеза оптимальных механизмов планирования в активных системах и задачи реализуемости тех или иных соответствий группового выбора.

Неманипулируемость Неманипулируемость CW - функции выбора механизмов голосования вида c : (Rm)n Rm Неманипулируемость Неманипулируемость Неманипулируемость прямого механизма прямого механизма прямого механизма, активной экспертизы распределения ресурса удовлетворяющего (соотношение 1.4.1) (алгоритм 1.4.1) А.1.2.1, 1.2.2. (Т.1.2.13) 3 Достаточные условия Достаточные условия Необходимые условия неманипулируемости коалиционной коалиционной Т.2.1.1 и Т.2.3.1. неманипулируемости неманипулируемости Л.2.2.1 Л.2.2.2.,2.2.3.

Неманипулируемость Существование механизмов равновесия Нэша планирования вида Т.3.2. c : (Rm )n Rm Достаточные условия существования эквивалентного прямого механизма Т.3.3. Достаточные условия Достаточные условия Достаточные условия существования существования существования 1, эквивалентного эквивалентного прямого эквивалентного прямого прямого механизма для дифференцируемого дифференцируемого линейных процедур двухэлементного многоэлементного планирования (Т.3.4.1) механизма планирования механизма планирования (Т.3.4.2) (Т.3.4.3) Существование Существование эквивалентного прямого эквивалентного прямого механизма для МРР механизма для МАЭ Рис. 4.1. Схема результатов работы и задачи будущих исследований Литература 1 Abreu D. and Sen A. Subgame perfect Implementation: A Necessary and Sufficient Conditions. Review of Economic Theory, 1990. Vol. 50. P. 285-99.

2 Arrow K.J. Essays in the theory of risk-bearing. Amsterdam: North-Holland Publishing company, 1974. - 178 p.

3 Arrow K.J. Social choice and individual values. Chicago: Univ. of Chicago, 1951. - 204 p.

4 Arrow K.J., Radner R. Allocation of resources in large teams // Econometrica.

1979. Vol. 47. N 2. P.361 - 386.

5 Baryshnicov Y. Unifying impossibility theorems: a topological approach.

Adv. Applied Math, 14, 1993. P. 404- 6 Baryshnikov Y. Topological and discrete social choice: in search of a theory.

Social Choice and Welfare, 14, 1997. P. 199-209.

7 Border K. S., JordanJ. S. Straightforward Elections, Unanimity and Phantom Voters. Review of Economic Studies, 1983, P. 153-170.

8 Border K., Sobel J. Samurai accountant: a theory of auditing and plunder//Review of Economic Studies. 1987. Vol.54. P.525-540.

9 Burkov V.N., Enaleev A.K. Stimulation and decision-making in the active systems theory: review of problems and new results // Mathematical Social Sciences. 1994. Vol. 27. P. 271 - 291.

10 Burkov V.N., Lerner A.Ya. Fairplay in control of active systems / Differential games and related topics. Amsterdam, London: North-Holland publishing company, 1971. P. 325 - 344.

11 Burkov V.N., Novikov D.A., Petrakov S.N. Mechanism design in economies with private goods:trthtelling and feasible message sets. XIII Conference on system science, 1998. Vol.3 P.255- 12 Chichilinsky G. Fixed point theorems and social choice paradoxes. Econ.

Letters 3, 1979. P. 347- 13 Chichilinsky G. Interesting famiilies of sets and the topology of cones in economics. Bill Am Math Society, 29(2), 1993. P. 189- 14 Chichilinsky G., Heal G.M. The geometry of implementation: a necessary and sufficient condition for staightforwardness. Social Choice and Welfare, 14, 1997. P. 259-294.

15 Chichilinsky G. Social diversity, arbitrage and gains from trade: a unified perspective on resource allocation. American Economics Revive, 84 (2), 1994.

P. 427- 16 Chichilinsky G. Limited arbitrage is necessary and sufficient condition for the existence of a competitive equilibrium. Economical Theory, 5(1), 1995. P. 79 17 Chichilinsky G. Social Choice and the topology of space of preferences. Adv Math 37 (2), 1980. P. 165- 18 Chichilnisky G. Market arbitrage, social choice and the core. Social Choice and Welfare, 14, 1997. P. 161- 19 Chichilinsky G., Heal G.M. A necessary and sufficient conditions for resolution of social choice paradox. J Econ Theory, 31, 1983. P. 68- 20 Chichilinsky G., Heal G.M. Social Choice with infinite populations:

construction of a rule and impossibility results. Social Choice and Welfare, 14, 1997. P. 303- 21 Danilov V. Implementation via Nash Equilibria //Econometrica, Vol. 60.

1992. № 1, P. 43-56.

22 Dasgupta P., Hammond P., Maskin E. The implementation of social choice rules: some general results on incentive compatibility. Review of Economic Studies, 1979, The Symposium on Incentive Compatibility.

23 D'Aspermont C., Gerard-Varet L.A. Incentives and incomplete information// J.

of Public Economics. 1979. Vol. 11. N1. P.25-45.

24 Farmer R. Implicit contracts with asymmetric information and bankruptcy: the effect of interest rates on layoffs // Review of Economic Studies. 1985. Vol.

52. N 3. P. 427 - 442.

25 Fishburn P.C. ArrowТs impossibility result, concise proof and infinite voters. J Econ Theory, 2, 1970. P. 103- 26 Gibbard A. Manipulation of Voting Schemes: A General Result.

Econometrica, 1973. Vol. 45. P. 595-641.

27 Gibbard A. Straightforwardness of game forms with lotteries as outcomes // Econometrica. 1978. Vol. 46. N 3. P. 595 - 616.

28 Gjesdal F. Information and incentives: the agency information problem // Review of Economic Studies. 1982. Vol. 49. N 2. P. 373 - 390.

29 Green J., Laffont J.-J. Partially verifiable information and mechanism design // Review of Economic Studies. 1986. Vol. 53. N 4. P. 447 - 456.

30 Groves T. Efficient Collective Choice when Compensation is Possible.

Review of Economic Studies, 1979. Vol. 46. № 2. P. 227-241.

31 Groves T. Incentives in Teams. Econometrica, 1973. Vol. 43. № 4. P. 617 631.

32 Groves T., Ledyard J. O. Optimal Allocation of Public Goods: A Solution to the 'Free-Rider' Problem. Econometrica, 1977. Vol. 45. P. 783-809.

33 Groves T., Ledyard J. O. The Existence of Efficient and Incentive Compatible Equilibria with Public Goods. Econometrica, 1980. Vol. 48. № 6. P. 1487 1506.

34 Groves T., Loeb M. Incentives and public inputs // J. of Public Economy.

1975. Vol. 4. P. 211 - 226.

35 Groves T., Loeb M. Incentives in a divizionalised firm // Management Science. 1979. Vol. 25. N 3. P. 221 - 226.

36 Groves T., Radner R. The allocation of resources in a team // J. of Economic Theory. 1972. Vol. 4. N 2. P. 415 - 441.

37 Hammond P.J. Straightforward individual incentive compatibility in large economics // Review of Economic Studies. 1979. Vol. 46. N 2. P. 263 - 282.

38 Harris M., Townsend R. Resource allocation under asymmetric information // Econometrica. 1981. Vol. 49. N 1. P. 33 - 64.

39 Harsanyi J.C. Games with incomplete information played by "Bayesian" players // Management Science. Part I: 1967. Vol. 14. N 3. P. 159 - 182;

Part II: 1968. Vol. 14. N 5. P. 320 - 334;

Part III: 1968. Vol. 14. N 7. P. 486 - 502.

40 Holmstrom B. Moral hazard and observability // Bell J. of Economics. 1979.

Vol. 10. N 1. P. 74 - 91.

41 Hurwicz L. On informationally decentralized systems // Decision and organization. Amsterdam: North-Holland Press, 1972. P. 297 - 336.

42 Jackson M., Palfrey T., Srivastava S. Undominated Nash Implementation in Bounded Mechanisms. Mimeo, Northwestern University, 1991. To appear and Game and Economic Behavior.

43 Jackson M.O. Bayesian implementation // Econometrica. 1991. Vol. 59. N 2.

P. 461 - 477.

44 Jackson, M. Implementation in Undominated Strategies: A Look at Bounded Mechanisms. Forthcoming in Review of Economic Studies.

45 Kirman A., Sonderman D. ArrowТs therem, many agents and invisible dictators. J Econ Theory, 5, 1972. P. 267- 46 Kim S.K. Efficiency of an information system in an agency model // Econometrica. 1995. Vol. 63. N 1. P. 89 - 101.

47 Laffont J.-J., Maskin E. Nash and dominant strategy implementation in economic environment // J. of Mathematical Economy. 1982. Vol. 10. N 1. P.

17 - 47.

48 Marchak J., Radner R. Economic theory of teams. New Haven -London: Yale Univ. Press, 1976. - 345 p.

49 Mas-Collel A., Vives X., Implementation in economies with a continuum of agents // Review of Economic Studies. 1993. Vol. 60. N 3. P. 613 - 629.

50 McCelvey R. D. Game Forms for Nash Implementation of General Social Choice Correspondences. Social Choice and Welfare, 1989. № 6. P. 139-156.

51 Moore J. Implementation, Contracts and Renegotiation in Environment with Complete Information. Advances in Economic Theory. Vol.1. Cambridge:

Cambridge Univ. Press, 1992. P.182-281.

52 Moore, J., Repulo R. Subgame Perfect Implementation, Econometrica, 1988.

Vol. 46. P. 1191-220.

53 Moulin H. Generalized Condorcet-Winners for Single Peaked and Single Plateau Preferences. Social Choice Welfare, 1984. P. 127-147.

54 Moulin H. Serial cost-sharing of excludable public goods // Review of Economic Studies. 1994. Vol. 61. N 207. P. 305 - 325.

55 Moulin H., Shenker S. Serial cost sharing // Econometrica. 1992. Vol. 60. N 5.

P. 1009 - 1037.

56 Myerson R. Incentive compatibility and the bargaining problem // Econometrica. 1979. Vol. 47. N 1. P. 61 - 74.

57 Myerson R. Optimal coordination mechanisms in generalized principal - agent problems // J. of Mathematical Economy. 1982. Vol. 10. N 1. P. 67 - 81.

58 Palfrey T. Implementation theory / Handbook of Game theory. Vol.3.

(forthcoming).

59 Palfrey T., Srivastava S. Nash Implementation Using Undominated Strategies.

Econometrica, 1991. Vol. 59. P. 479-501.

60 Rasmussen H. Strategy-proofness of continuous aggregation maps. Social Choice and Welfare, 14, 1997. P. 249- 61 Repullo R. The Revelation principle under complete and incomplete information. Economic Organizations as Games. Oxford: Basil Blackwell,1986. P. 179 - 195.

62 Roberts K. The Characterization of Implementable Choice Rules. Aggregation and Revelation of Preferences. Amsterdam: North-Holland, 1979. P. 321-48.

63 Saari D. Informational geometry of social choice. Social Choice and Welfare, 14, 1997. P. 211-232.

64 Saijo T. Strategy space reduction in Maskin's Theorem: sufficient conditions for Nash implementation. Econometrica, 56. P. 693-700.

65 Saterthwaite M. Strategy - Proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions. Journal of Economic Theory, 1975. Vol. 10. № 2.P. 187-217.

66 Satterthwait M., Sonnenhschein H. Strategy - Proof Allocation Mechanisms at Differential Points. Review of Economic Studies, 1981. Vol. XLVIII. P. 587 597.

67 Sen A. Collective choice and social welfare. London: Holden - Day, 1970. - 254 p.

68 Sen A. Social choice theory / Handbook on mathematical economics. Vol. 3.

Amsterdam: North-Holland, 1986. P. 1073-1181.

69 Sprumont Y. The division problem with single-peaked preferences: a characterization of the uniform allocation rules // Econometrica. 1991. Vol.

59. N 2. P. 509 - 519.

70 Tatamatani (1991) 71 Thomson W. The manipulability of resource allocation mechanisms//Review of Economic Studies. 1984.Vol.51.N3.P.447-460.

72 Yamato (1993) 73 Zhou Y. A note on continuous social choice. Social Choice and Welfare, 14, 1997. P. 245- 74 Айзерман М.А., Алескеров Ф.Т. Выбор вариантов: основы теории. М.:

Наука, 1990. - 236 с.

75 Акофф Р., Эмери Ф. О целеустремленных системах. М.: Сов.радио, 1974.

- 272 с.

76 Ашимов А.А., Бурков В.Н., Джапаров Б.А., Кондратьев В.В.

Согласованное управление активными производственными системами.

М.: Наука, 1986. - 248 с.

77 Березовский Б.А., Барышников Р.М., Борзенко В.И., Кемпнер Л.М.

Многокритериальная оптимизация: математические аспекты. М.: Наука, 1989. - 128 с.

78 Бурков В.Н. Основы математической теории активных систем. М.:

Наука, 1977. - 255 с.

79 Бурков В.Н., Горгидзе И.И., Новиков Д.А., Юсупов Б.С. Механизмы распределения ресурса и затрат в рыночной экономике. М.: ИПУ РАН, 1997. - 50 с.

80 Бурков В.Н., Данев Б.И др. Большие системы: Моделирование организационных механизмов. М.: Наука, 1989.

81 Бурков В.Н., Еналеев А.К., Новиков Д.А. Механизмы функционирования социально-экономических систем с сообщением информации // А и Т. 1996. N 3. С. 3 - 25.

82 Бурков В.Н., Еналеев А.К. Оптимальность принципа открытого управления. Автоматика и телемеханика, 1985. № 3. C. 73-80.

83 Бурков В.Н., Еналеев А.К., Каленчук В.Ф. Оптимальность принципа открытого управления. Вычислительные процедуры планирования и их свойства // А и Т. 1986. N 9. С. 81 - 87.

84 Бурков В.Н., Еналеев А.К., Новиков Д.А. Механизмы функционирования социально - экономических систем с сообщением информации.

Автоматика и телемеханика, 1996. № 3, с. 3-25.

85 Бурков В.Н., Еналиев А.К., Лавров Ю.Г. Синтез оптимальных механизмов планирования и стимулирования в активных системах.

Автоматика и телемеханика, 1992. № 10. С. 113-120.

86 Бурков В.Н., Ириков В.А. Модели и методы управления организационными системами. М.: Наука, 1994. - 270 с.

87 Бурков В.Н., Кондратьев В.В. Механизмы функционирования организационных систем. М.: Наука, 1981.

88 Бурков В.Н., Кондратьев В.В., Цыганов В.В., Черкашин А.М. Теория активных систем и совершенствование хозяйственного механизма. М.:

Наука, 1984. - 272 с.

89 Бурков В.Н., Новиков Д.А. Введение в теорию активных систем. М.:

ИПУ РАН, 1996.

90 Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: Синтег, 1997. - 188 с.

91 Бурков В.Н., Новиков Д.А. Модели и механизмы теории активных систем в управлении качеством подготовки специалистов. М.: ИЦ, 1997.

- 158 с.

92 Бурков В.Н., Новиков Д.А. Управление организационными системами:

механизмы, модели, методы // Приборы и системы управления. 1997. N 4. С. 55 - 57.

93 Бурков В.Н., Опойцев В.И. Метаигровой подход к управлению иерархическими системами // А и Т. 1974. N 1. С. 103 - 114.

94 Гантмахер Ф. Р. Теория матриц.

95 Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. - 384 с.

96 Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976. - 328 с.

97 Гермейер Ю.Б., Моисеев Н.Н. О некоторых задачах теории иерархических систем управления / Проблемы прикладной математики и механики. М.: Наука, 1971. С.30-52.

98 Глотов В.А., Павельев В.В. Векторная стратификация. М.: Наука, 1984. - 132 с.

99 Горелик В.А., Кононенко А.Ф. Теоретико - игровые модели принятия решений в эколого-экономических системах. М. : Радио и связь, 1982. - 144 с.

100 Данилов В.И. Модели группового выбора (обзор) // Изв. АН СССР. Техн.

кибернетика. 1983. N 1. С. 143 - 164.

101 Данилов В.И., Сотсков А.И. Механизмы группового выбора. М.: Наука, 1991.

102 Интриллигатор М. Математические методы оптимизации и экономическая теория. М.: Прогресс, 1975. - 606 с.

103 Каленчук В.Ф. Разработка и исследование оптимальных процедур планирования в активных системах в условиях неопределенности. М.:

ИПУ РАН, 1990. - 22 с.

104 Клейнер Г.Б. Производственные функции: теория, методы, применение.

М.: Финансы и статистика, 1986. - 238 с.

105 Левченков В.С. Элементы эргодической теории с приложениями к проблемам выбора. М.: Изд-во факультета ВМиК МГУ. 106 Лезина З.М. Манипулирование выбором вариантов: теория агенды // А и Т. 1985. N 4. С.5 - 22.

107 Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем. М.: Мир, 1973. - 342 с.

108 Мулен Э. Кооперативное принятие решений: аксиомы и модели. М.:

Мир, 1991.

109 Нейман Д., Моргенштерн О. Теория игр и экономическое поведение.

М.: Наука, 1970. - 707 с.

110 Новиков Д.А. Механизмы стимулирования в динамических и многоэлементных социально-экономических системах // А и Т. 1997. N 6.

С. 3 - 26. 111 Новиков Д.А. Оптимальность правильных механизмов управления активными системами. I. механизмы планирования, II. Механизмы стимулирования. Автоматика и телемеханика, 1997, № 2-3.

112 Новиков Д.А. Оптимальность правильных механизмов управления активными системами. II. Механизмы стимулирования // А и Т. 1997. N 3. С. 161 - 167.

113 Новиков Д.А., Петраков С.Н. Реализуемость механизмов активной экспертизы и механизмов распределения ресурсов, XXXIX юбилейная научная конференция МФТИ. Тезисы докладов, 1996.

114 Опойцев В.И. Равновесие и устойчивость в моделях коллективного поведения. М.: Наука, 1977.

115 Орлов А.И. Устойчивость в социально-экономических моделях. М.:

Наука, 1979. - 124 с.

116 Петраков С.Н. Достаточные условия существования эквивалентного прямого механизма открытого управления для дифференцируемых процедур планирования, XL юбилейная научная конференция МФТИ.

Тезисы докладов. Выпуск 1. 28-29 ноября 1997. С. 117 Петраков С.Н. Необходимые условия неманипулируемости механизмов планирования, сформулмрованные в терминах "множеств диктаторства", XLI юбилейная научная конференция МФТИ. Тезисы докладов. Часть II.

27-28 ноября 1998. С. 118 Петраков С.Н. Эквивалентные прямые механизмы в теории активных систем // Управление большими системами: материалы научно практической конферении. М. СИНТЕГ, 1997. С. 119 Фишберн П. Теория полезности для принятия решений. М.: Наука, 1978.

- 352 с.

120 Фокин С.Н. Разработка, исследование и применение процедур распределения моноресурса в социально-экономических системах в условиях неопределенности с учетом приоритетов потребителей (на примере распределения машинного времени на В - в отраслевых НИИ и КБ) / Диссертация на соискание ученой степени канд. техн. наук. М:

ИПУ РАН, 1988. - 166 с.

121 Цыганов В.В. Адаптивные механизмы в отраслевом управлении. М.:

Наука, 1991. - 166 с.

122 Шрейдер Ю.А. Равенство, сходство, порядок. М.: Наука, 1971. - 254 с.

123 Малишевский А.В. Качественные модели в теории сложных систем. - М.:

Наука, 1998. С.124- Приложение Лемма 2.1.1. Рассмотрим произвольный r D 0, тогда:

a) iM( ) { (~i, r-i ) D 0 } {~i > xi (rC( ) ) }, (П.1) r r б) iR( ) {(~i, r-i ) D 0 } {~i < xi (rC ( ) )}. (П.2) r r ~ Доказательство. Пусть ri > xi (rC( ) ). Тогда по определению П. D 0 = {r : rC( ) ProjC( ) D, (П.3) Rn (П.4) rM ( ) > xM ( ) (rC( ) ), (П.5) rA( ) < x (rC( ) )}.

A( ) ~ Taк как r D 0, то rC( )ProjC( )D. Обозначим r = (~i, r-i ). Так как iM( ), r ~ ~ ~ то rC( ) = rC( ), rA( ) = rA( ) и (П.3), (П.5) выполнены. Из r-i = r-i ~ следует, что rM ( )\{i} > xM ( )\{i}) (~C( ) ), а так как ri > xi (~C( ) ), то r r ~M ( ) > x M ( ) (~C( ) ). Поэтому справедливо (П.4) и по определению D r r получаем (П.1).

~ Обратно, предположение, что при некотором ri xi (rC ( ) ) верно (~i,r-i ) DA входит в противоречие с определением.

r D Аналогично доказывается, что имеет место второе утверждение леммы.

Q. E. D.

Теорема 2.1.1. Пусть I - множество активных элементов, функции полезности элементов обобщенно однопиковые. Пусть механизм h : Rn Rn удовлетворяет А.2.1.1 и D=D0, тогда он неманипулируем.

Доказательство: Рассмотрим произвольный профиль GSPn. В силу теоремы 1.2.1 для неманипулируемости достаточно показать, что сообщение достоверной информации является равновесием Нэша, то есть i I, ~i R1, (hi (r)) (hi (~, r-i )).

r ri i i ~ Допустим, что существуют элемент iI и ri R1 такие, что (hi (r)) < (hi (~i, r-i )). (П.6) r i i n Так как B - разбиение, то существует единственный вектор, такой, что rD. Возможны три случая: i может принадлежать либо M( ), либо C( ), либо A( ). Рассмотрим последовательно три этиx случая.

1) Пусть i C( ), тогда ~ R1, (hi (r)) = (ri ) (hi (~, r-i )) так как ri единственный ri i ri i i максимум (xi ) по xi.

i 2) Если i M( ), то из определения D и A.2.1.1, ri > hi (r) = xi (rC ( ) ).

Так как D 0 =, то по лемме 2.1.1 для любого D ~ ri > xi (rC( ) ), ~ = (~i, r-i ) D = D 0 и (hi (~)) = (hi (r)).

r r r i i ~ Если ri xi (rC ( ) ), то (~i,r-i ) D 0 = D и существует r ~ ~ единственный вектор ~ n такой, что r D. Если верно (П.6), то из ~ того, что (xi) не убывает по xi при xi hi (r). Поэтому r ~ ~ ~ xi (~C( ) > xi (rC ( ) ), xi (~C( ) > ri и i A( ~).

r ~) r ~) ~ ~) В силу того, что xi (rC( ) > xi (rC ( ) ) существует ri такой, R ~ ~ что xi (rC( ) ) > ri > xi (rC ( ) ). Из xi (rC( ) ) > ri и леммы 2.1.1 вытекает, ~ ~ что r D 0. Аналогично r D 0 и r D 0 D 0. Но так как D=D0 то ~ D 0 D 0 =. Получили противоречие и (П.6) не выполнено.

3) Случай, когда i A( ) рассматривается аналогично случаю 2).

Q.E.D.

Лемма 2.2.1. Пусть механизм h : Rn Rn удовлетворяет предположениям А.2.1.1, А.2.2.1 и для него D = D0, тогда этот механизм коалиционно неманипулируем.

Доказательство: Допустим, выполнены условия теоремы и механизм J h(~) коалиционно манипулируем, тогда r Rn, J I, ~J R r r такие, что j J (hj (~J, r-J )) (hj (rJ, r-J )) и r j j r i J (hi (~J, r-J )) > (hi (rJ, r-J )).

i i Из определения однопиковых функций полезности получаем J r Rn, J I, ~J R такие, что r hJ (~J, r-J ) < >J hJ (rJ, r-J )) и (П.7) r (П.8) j J (A( ) M ( )) : hj (~J, r-J )) < > hj (rJ, r-J ).

r j ~ Рассмотрим ~ n такой, что r = (~J, r-J ) D и ~.

r ~ Тогда найдется из (П.8) множество K J \{ j*}, такое, что hK (~) = hK (r) и hJ \K (~) < >J \K hJ \K (r).

r r ~ ~ Рассмотрим вектор r = (hJ (~), r-J ). Из определения следует, что r ~ ~ ~ r = (hJ (~), r-J ) D0 ( ~, J ) так как r = (~J, r-J ) D.

r r ~ С другой стороны r = (rJ, r-J ) D и выполнено (П.7), тогда ~ ~ r = (hJ (~), r-J ) D0 (, K) так как r = (rJ, r-J ) D.

r 0 ~, Тогда Dc(, K ) Dc( J ). При этом, c (, K) 'c' в силу j (П.8), а c ( ~, J ) ='c', поскольку j J, откуда следует, что j ~ c (, K ) c ( ~, J ) и, ~ : D D. Получили противоречие.

j j Q.E.D.

Лемма 2.2.2. Пусть механизм h : Rn Rn удовлетворяет А.2.1.1 и неманипулируем, тогда D = D0.

1 2 1 Доказательство: Допустим,, n такие, что и ~ D 01 D 2. Тогда существуют r D 01 D 2 и r D 1 такие, что ~ rC( 1) = rC ( 1).

~} Рассмотрим множество K = {i I ri ri, K C( ) =.

Рассмотрим возрастающую последовательность ik K, k =1, K.

k Определим последовательность точек r, k = 0, K таких, что r0 = r, K k +1 ~ ~ r = (r-ki, ri ). При таком определении r = r.

k k k Определим последовательность отрезков Lk = [rk-1, r ], k =1, K. Все отрезки Lk D 01 по лемме 2.1.1. Так как r0 = r D 1, а K ~ r = r D 2, то найдется номер k {0,..., K } такой, что ~ rk-1 D 1, rk D, где ~.

В силу того, что механизм h : Rn Rn неманипулируем, k hik-1 (rk-1) = hik -1 (r ). Пусть существует j I такой, что 1 hj (rk-1) hj (rk ), тогда либо c, либо ~ j c, например, c.

j j Рассматривая коалицию { j, ik-1}, при положении истинной точки пиков - k-1 k r получаем, что ей выгодно сообщать r. Аналогично, если ~ j c.

Q.E.D Лемма 2.2.3. Пусть механизм h : Rn Rn удовлетворяет А.2.1.1 и коалиционно неманипулируем, тогда выполнено А.2.2.1.

Доказательство: Из условий леммы леммы 3.2.1 следует, что D = D0.

Рассмотрим произвольный n и произвольное подмножество J I. Обозначим K = J (A( ) M ( )).

Рассмотрим возрастающую последовательность ik K, k =1, K.

Рассмотрим D(, k1). r D(, k1) r D такой, что r-k1 = r-k1. Тогда из коалиционной манипулируемости следует, что hk1 (r ) = hk1 (r). Докажем, что h(r ) = h(r).

Допустим, что h(r ) h(r) и j I такой, что hj (r ) hj (r).

Рассмотрим два случая: (1) c и (2) = c.

j j 1. Пусть c и rj < > hj (r). Если hj (r) < > hj (r ), то при j j j истинной точке пиков r и функции полезности - x - rj, rj < > x ;

j j j h (r ) - rj j (x ) = j j - x - rj, x < > rj.

j j j h (r) - rj j выгодно образование коалиции { j, k1} и сообщение r.

Если hj (r ) < > hj (r), то аналогично получаем, что при точке j пиков r и функции полезности - x - rj, rj < > x ;

j j j hj (r) - rj (x ) = j j - x - rj, x < > rj.

j j j hj (r ) - rj выгодно образование коалиции { j, k1} и сообщение r.

Тогда hj (r ) = hj (r).

2. Если = c, то hj (r ) rj = rj и при истинной точке пиков j выгодно образование коалиции { j, k1} и сообщение r.

Таким образом, h(r) = h(r ) при любых r D(, k1), r D таких, что r-k1 = r-k1. Тогда r-k1 < >-k1 h-k1 (r) и rk1 = hk1 (r), откуда следует, что r Dc(, k1) и D(, k1) Dc(, k1).

Так как c(c(, {k1}), {k2}) = c(, {k1, k2}), а D(c(, {k1}),{k2}) = D(,{k1, k2}), то аналогично предыдущему случаю получаем:

Dc(, {k1, k2}) D(, {k1, k2}).

Продолжая по индукции, получаем J I D(, J ) Dc(, J ).

Q.E.D.

Лемма 2.3.1. Пусть функция полезности активного элемента i I однопиковая и сепарабельная, тогда любой элементарный механизм Ji e : RJi R неманипулируем.

Доказательство: Допустим механизм e(r) манипулируем, тогда Ji ~i Ji найдутся точки пика ri R и r R такие, что (e(~i )) > (e(ri )).

r i i i Пусть ri D i, где Ji. Тогда в силу определения элементарного механизма и того, что e(ri ) e(~i ) выполняется r i e-C ( i )(ri ) < > e-C( i )(~i ) и найдется компонента плана j Ji r i -C ( ) такая, что e (ri ) e (~i ).

r j j i Обозначим eK = e(~K, rJii \K ), K Ji. В силу того, что r i i i r-C( i ) < >-C( i ) e-C ( i ) (ri ) < >-C ( i ) e-C( i ) (~i ) и сепарабельности r i i функции полезности (xi ), для любого j1 Ji \ C( ) выполняется i i i i i (e ) (e{ j1}). По индукции получаем, что (e ) (eJi \C ( ) ) и i i i далее (e ) (eJi ) = (e(~)). Получили противоречие.

r Таким образом утверждение леммы верно.

Q.E.D.

Теорема 2.3.1. Пусть функции полезности активных элементов однопиковые и сепарабельные, прямой механизм h : RJ RJ ограничен J и удовлетворяет условию А.2.3.1, тогда механизм h(r), r R является неманипулируемым.

Доказательство: Докажем, что при каждом фиксированном r-i RJ-i механизм hi (ri, r-i ) является неманипулируемым для i - го активного элемента.

J-i Рассмотрим произвольный вектор rJ-i R и произвольный rJi RJi. Пусть r = (rJi, rJ-i ) принадлежит некоторому множеству D и ~ ~ рассмотрим ( ) = { ~ J ~-Ji = }. Для каждого ~ ( ) -Ji ~ определены функции x- C ( ~Ji ) (rC( J-i ) ), принимающие постоянные J-i значения при заданном rJ-i R, поэтому будем считать, что для ~ каждого ~ ( ) определены числа x- C ( ~.

) Ji Поскольку верно D = D0 и из А.3 для любого J, i I, ~ J Ji и ~ Dc(, J ) найдется r D такой, что r ~ ~ xc(, J ) (~C(c(, J )) ) = x (rC( ) ) верно, что для всех j Ji существуют r j Ji i j числа x R{ j} такие, что для любого ri R такого, что rj < > x j j j j выполняется hj (r) = x. Из односвязности множеств ProjC ( ) D j j i следует, что для всех rj таких, что x < > rj для любого j j j выполнено hj (r) = rj.

Таким образом, механизм hi (ri, r-i ) является элементарным для i -го элемента и в силу произвольности i, механизм h(r) является неманипулируемым.

Q.E.D.

Лемма 2.3.1. ММ выполнено.

Доказательство: очевидно из свойств 2.3.1-2.3.3 Q.E.D.

Лемма 2.3.2. НСМ выполнено.

Доказательство: очевидно из свойств 2.3.1-2.3.3.

Q.E.D.

Лемма 2.3.3. Если d = 0 и D > R, то ОПВ не выполнено. В jI противном случае ОПВ выполнено.

Доказательство: очевидно из свойств 2.3.1-2.3.3.

Q.E.D.

Лемма 2.3.4. ПО выполнено.

Доказательство: очевидно из свойств 2.3.1-2.3.3.

Q.E.D.

Лемма 2.1.13. Для любого r [d, D]n, верны следующие утверждения:

1) если ri > h(r), то ~ h(r), h(~i, r-i ) = h(r) и ~ < h(r), ri r ri h(~i, r-i ) < h(r) ;

r 2) если ri < h(r), то ~ h(r), h(~i, r-i ) = h(r) и ~ > h(r), ri r ri h(~i, r-i ) > h(r).

r Доказательство: докажем эту лемму следующим способом: будем ~ рассматривать последовательное изменение сообщения ri [d, D] некоторого активного элемента с номером i I. При этом возможны три варианта: активный элемент выходит из некоторого множества El разбиения E и возможно переходит в множество El-1, либо в множество ~ El+1, то есть, если i El и k El-1, а j El+1, то либо ril-1 ri ri, либо ~ ri ri ril +1. Если элемент i находится между двумя множествами разбиения, то этот случай сводится к предыдущему, поскольку он задает еще одно множество El разбиения E, состоящее из одного элемента El ={i}. При этом, возможно, что номер i лежит либо выше, либо ниже E множества (r) в упорядочении, задаваемом t T. Также, возможно ~ ~ два варианта: ri > ri и ri < ri.

Обозначим = max, = min. Обозначим (r) (r) = { : > } и ={ : > }. Все возможные варианты сведем в следующую таблицу ~ ~ ri > ri ri < ri i 3 i 1 i 2 где одинаковыми числами обозначены симметричные ситуации. Таким образом, достаточно рассмотреть три случая:

~ 1) i, ri < ri ;

~ 2) i, ri < ri ;

~ 3) i, ri < ri.

1) Рассмотрим первый случай. Возможны два варианта: есть явные диктаторы, такие, что j E (r), rj [Wtt(, jE, Wtt(, jE-1] и h(r) = rj ;

(б) ) ) явных диктаторов нет, то есть j E (r), rj >Wtt(, jE-1 и h(r) =Wtt(, jE-1.

) ) а) Пусть (r) = (r ), тогда для рассматриваемого случая выполнены следующие соотношения:

(r), min (W t, E, rt-1( ) ) = W t, E = W t-1, и rt-1( ) > W t-1, (П.9) -1 - где = min ;

(r) max min (rt-1( ), W t,-E ) = rt-1( ) W t-1 ;

(П.10) max min (rt-1( ), W t,-E ) = W t,-E W t-1. (П.11) 1 Без потери общности предполагаем, что меняется сообщение - активного элемента (r) с наименьшим номером t ( ), то есть ~- rt-1( -1) rt ( ) rt-1( ). Для случая (а) верно, что rt -1( ) [W t, W t-1].

~ I) Считаем сначала, что rt-1( -1) < r. При этом порядок активных ~ элементов будет задаваться той же перестановкой t, а разбиение E, для ~ нового вектора r = (~t-1( ), r-t-1( ) ) будет задаваться следующими r ~ ~ ~ соотношениями: l = l, l = 1, (r) -1, (r) = { }, (r)+1 = (r) \ { } и ~ l+1 = l, l = (r) +1, E. Тогда отрезки диктаторства для всех элементов из множеств l, l { (r), (r) +1} не изменятся, для элемента с номером ~ ~ - t ( ) отрезок диктаторства [W t, E, W t, E ] = [W t, W t-1], а для элементов с - номерами j : t( j) \{ } отрезок диктаторства ~ ~ [Wtt(, jE, Wtt, jE-1] = [W t, W t ].

) ( ) ~-1 ~- Если rt ( ) W t, то rt ( ) [W t, W t-1] и ~- h(~) = rt ( ) < h(r) = rt-1( ).

r ~-1 ~- Если rt ( ) < W t, то min (~t-1( ), W -1) = rt ( ) < W t и, r следовательно, ~ max min (rt-1( ), W t,-E ) = max rt-1( ) rt-1( ), ~ ~ max min (rt-1( ), W t,-E ) = max W t,-E rt-1( ), 1 ~ max min (rt-1( ), W t,-E ) = W t < rt-1( ), (r)\{ } ~- min (~t-1( ), W t-1) = rt ( ) < W t < rt-1( ).

r Тогда h(~) rt-1( ) = h(r) r.

~- II) Рассмотрим теперь случай, когда rt-1( -1) = rt ( ) < rt-1( ). Новое ~ ~ ~ разбиение E таково, что l = l, l = 1, (r) - 2, (r)-1 = { } (r)-1, ~ ~ (r) = (r) \ { } и l = l, l = (r) +1, E. Новые отрезки диктаторства определятся следующим образом ~ ~ ~ l, l = 1, (r) - 2, [W t, E, W t,-E ] = [W t, E, W t,-E ], 1 ~ ~ ~ (r)-1, [W t, E, W t,-E ] = [W t, W t -2 ], ~ ~ ~ (r), [W t, E, W t,-E ] = [W t, W t ], ~ ~ ~ l, l = (r) +1, E, [W t, E, W t,-E ] = [W t, E, W t,-E ].

1 Таким образом, для всех { (r), (r) -1} отрезки диктаторства останутся без изменений. Тогда будут верны следующие утверждения:

~ ~- max min (~t-1( ), W t,-E ) = rt ( ) = rt-1( ) rt-1( ), (П.12) r \ (r)- ~ ~ max min (~t-1( ), W t,-E ) = W t,-E = W t,-E rt-1( ). (П.13) r 1 1 Чтобы определить подобные соотношения для (r) и (r)-1, рассмотрим два случая:

~ ~ ~-1 ~- - если rt ( ) < W t, то (r)-1, min (~t-1( ), W t,-E ) = rt ( ) = r ~ ~ ~- = rt ( ) < rt ( ) и (r), min (~t-1( ), W t,-E ) = rt ( ). При этом из r -1 - (П.12) h(~) rt-1( ) = h(r) r ;

~ ~ ~-1 ~- - если W t-1 rt ( ) W t, то rt ( ) [W t, W t, E ] и (r)-1, - ~ ~- min (rt-1( ), W t -1) = rt ( ) < rt-1( ), а (r), ~ ~- min (~t-1( ), W t,-E ) = rt ( ). Тогда из (*), r ~- h(~) = rt ( ) = h(r) r.

Таким образом, если rt-1( ) = h(r), для всех ~- r rt-1( -1) rt ( ) rt-1( ), h(~) h(r).

б) Теперь рассмотрим случай, когда явных диктаторов нет, то есть j E (r), rj >Wtt(, jE-1 и h(r) =Wtt(, jE-1. Тогда выполнены следующие ) ) соотношения (r), min (W t, E, rt-1( ) ) = W t, E = W t-1, и rt-1( ) > W t-1, где -1 - = min, (П.14) (r) max min (rt-1( ), W t,-E ) = rt-1( ) W t-1, (П.15) max min (rt-1( ), W t,-E ) = W t,-E W t-1. (П.16) 1 ~- Рассмотрим сначала случай, rt-1( ) < rt ( ) r. При этом, rt-1( -1) < W t-1. Иначе, если rt-1( -1) W t-1, то min (rt-1( ), W t-1) W t-1 и (r) Argmax min (rt-1( ), W t, E ).

- ~- I) Если W t-1 < rt ( ), то min (rt-1( ), W t-1) = W t-1 и при новом разбиении ~ ~ E перестановка t сохранится. Новое разбиение E будет таким, что ~ ~ ~ l = l, l = 1, -1, (r) = { }, (r)+1 = (r) \ { }, ~ ~ l+1 = l, l = (r) +1, E. Для элементов из множества (r)+1 отрезок ~ ~ диктаторства [W t, E, W t, E ] = [W t, W t ]. Так как W t W t-1, то - ~ max min (rt-1( ), W t, E ) W t- - ~ max min (rt-1( ), W t, E ) W t- - ~ max min (rt-1( ), W t, E ) W t- - \{ } ~ max min (rt-1( ), W t, E ) < W t = W t-1.

- { } Поэтому h(~) = W t-1 = h(r) r.

~ II) Если W t-1 r W t, то ~- h(~) = rt ( ) W t-1 = h(r) r.

~ ~ III) Если r < W t, то min (r, W t ) = r < W t W t-1 и верны следующие соотношения:

~ max min (rt-1( ), W t, E ) W t- - ~ max min (rt-1( ), W t, E ) W t- - ~ max min (rt-1( ), W t, E ) W t- - \{ } ~ max min (rt-1( ), W t, E ) < W t W t-1.

- { } Тогда h(~) W t-1 = h(r) r.

Резюмируя случай 1), получаем, что если t(i) (r), то при ~ ~ ri (r )-1 ri h(r), h(~) h(r). Симметричный случай: ri (r )+1 ri h(r), r h(~) h(r).

r ~- 2) Рассмотрим случай, когда l и rt-1(i ) rt ( ) rt-1( ).

l - ~- а) Пусть rt-1(i ) < rt ( ) rt-1( ). При этом, отрезок диктаторства при l- новом разбиении определяется как [W t, W t -1] и W t -1 W t и min (r, W t -1) = W t -1 W t h(r). Тогда h(~) = h(r) r.

~- б) Если rt-1(i ) = rt ( ) rt-1( ), то новое разбиение будет таким, что l - l = l, l = 1, ( (r) -1) ;

{ }, (r)+1;

~ (r) (r) =,.

(r) (r)+ l ~ { }, l+1;

(r) = l, l+1, l = (r), E.

~ Рассмотрим l такой, что l- ~ max min (~t-1( ), W t, E ) = max min (rt-1( ), W t, E ).

r -1 - I) Если l -1 = (r), то новый отрезок диктаторства для элементов из ~ множества (r) будет следующим:

~ ~ [W t, E, W t, E ] = [W t, W t-1].

- Тогда ~ max min (~t-1( ), W t, E ) = max min (rt-1( ), W t, E ).

r ~ -1 - (r ) (r ) Так как множество \ { } беднее множества, то ~ max min (~t-1( ), W t,-E ) max min (rt-1( ), W t,-E ).

r 1 \{ } \{ } Тогда h(~) = h(r).

r II) Если l -1 > (r), значит меняется нижняя граница отрезка диктаторства для элементов из l-1 и верхняя граница диктаторства для элементов из множества l-2. Так как при этом l-1, l-2 и ~ ~ ~-1 > min (r, W t, E ) W t, E rt ( ), то -1 - h(~) = h(r).

r Резюмируя случай два и симметричный ему случай, получаем: если ~- и rt-1(i ) rt ( ) rt-1( ), то h(~) = h(r) и если и r l- ~- r rt-1(i ) rt ( ) rt-1( ), то h(~) = h(r).

l + 3) Рассматривается аналогично случаю 2). Если если и ~- r rt-1(i ) rt ( ) rt-1( ), то h(~) = h(r) и если и l + ~- r rt-1(i ) rt ( ) rt-1( ), то h(~) = h(r).

l - Пусть необходимо показать, что если ri > h(r), то ~i h(r), r ~ h(~i, r-i ) = h(r) и ri < h(r), h(~i, r-i ) < h(r). Если ri > h(r), r r ~ рассмотрим произвольный ri h(r). Пусть m = {l {1,..., E }: t(i)l}.

Тогда m > (r).

Если (r) = m -1, то из случая 2) получаем утверждение. Если ~ (r) < m -1, то рассматриваем ri1 = rim-1, по случаю 2) ri1 ri ri, h(~i, r-i ) = h(r). Далее, если (r) < m - 2, рассмотрим ri2 = rim-2. Из 2), r ~ ri2 ri ri1, будет выполнено h(~i, r-i ) = h(r) и т.д., пока (r) = m - k, и r ~ rik ri rik-1, h(~i, r-i ) = h(r). Таким образом доказано утверждение:

r если ri > h(r), то ~i h(r), h(~i, r-i ) = h(r).

r r Аналогично доказываются остальные утверждения леммы.

Q. E. D.

Лемма 2.1.14. ММ выполнено.

Доказательство. Следует из определения ММ, при условии, что функции полезности элементов являются однопиковыми и леммы 2.1.13.

Q. E. D.

Лемма 2.1.15. НСМ выполнено.

Доказательство: очевидно из определения ММ, при условии, что функции полезности элементов являются однопиковыми и леммы 2.1.13.

Q. E. D.

Лемма 2.1.16. ОПВ выполнено.

Доказательство: Рассмотрим тождественную перестановку t T, то есть такую, что t(i) = i и разбиение E такое, что E1 = {1,..., n -1} и E2 = {n}.

При этом отрезки диктаторства определятся следующим образом:

t, E, E [Wjt, E, W ] = [Wnt-1, 1] и [Wnt, E, Wnt- 1 ] = [0, Wnt-1].

j- t При этом либо (а) Wnt-1 > 0, либо (б) Wn-1 < 1. Рассмотрим случай t, E а). Положим ri = 0, i = 1, n -1 и rn = Wnt-1. Тогда rn [Wn, E, Wnt- 1 ] и h(r) = rn ri, i = 1, n -1.

Аналогично рассматривается случай (б). ОПВ не выполнено.

Q. E. D.

Лемма 2.1.17. ПО выполнено.

Доказательство: Очевидно ПО эквивалентно утверждению, что h(r)[min ri, max ri ].

iI iI Допустим, ПО не выполнено, тогда без потери общности предполагаем, ~ ~ что h(r) < min ri, тогда рассмотрим r [d, D]n r [d, D]n такой, что iI ~ r rj = min ri. Из леммы III.1.13 получаем, что h(~) = h(r) < rj, j I. С iI ~ ~, E ~ другой стороны, [Wjt, E, Wjt- 1 ] = [0, 1] и h(~) = rj, j I. Получили r противоречие, ПО выполнено. Q. E. D.

Утверждение 3.2.1. Совокупность множеств {S } n есть разбиение Rn.

Доказательство: Необходимо доказать, что s Rn существует единственный вектор n такой, что s S и s S.

Пусть s Rn. Для каждого i =1, n определим, i I по i следующей процедуре. Возможны три взаимоисключающих случая: (1) si < 0 ;

(2) si [0;

1] ;

(3) si >1. В первом случае положим = a, во i втором - = c, в третьем - = m.

i i Эта процедура однозначно определяет n. Из определения вектора следует, что sA( ) < sA( ), sM ( ) > sM ( ) и sC( ) [0, 1]C( ).

1 Значит s S. Пусть существует два различных вектора, n 1 такие, что s S, s S. Вектора, отличаются хотя бы в одной 1 1 компоненте j I так что. С точностью до перестановки j j 1 номеров векторов возможны лишь три случая: (1) = a, = c ;

(2) j j 1 2 1 2 1 = a, = m ;

(3) = c, = m. В первом случае из значений, j j j j следует, что s < 0, s [0, 1]. Аналогично получаем противоречия во j j втором и третьем случаях.

Q. E. D.

Утверждение 3.2.2. Для любого s Rn существует множество векторов состояний 0 и число > 0 такие, что (0, ), 0, U (s) S и 0, U (s) S.

Доказательство: Рассмотрим произвольную точку s Rn и произвольное > 0. Обозначим U (s) - - окрестность точки s.

~ Для каждой точки s U (s) найдется единственный вектор ~ (~)n такой, что s S (~). Обозначим через совокупность s s ~ { (~)}sU. Множество n конечно и n при любых > 0.

s Поэтому, конечно для любых > 0.

~ Единственность вектора (~) для каждого s U (s) позволяет s записать, U (s) S и, U (s) S =.

Обозначим 0 =. Докажем, что > 0 такой, что > (0, ), 0, U (s) S и 0, U (s) S. Для этого необходимо показать, что одновременно верны следующие утверждения:

1 1) > 0 : (0, ), 0 U (s) S ;

0 2 2) > 0 : (0, ), 0 U (s) S =.

0 Из определения 0 =, любой 0 принадлежит всем >, > 0 и поэтому 0, > 0 (0, ) 0 : U (s) S.

Первое утверждение доказано.

Допустим не верно второе утверждение и > 0 (0, ) 0 : U (s) S. Это эквивалентно тому, что 0 > 0, (0, ) такое, что 0 строго принадлежит.

0 Положим (k) =, k = 1, 2,... Для любого (k) найдется 0 k k k (k)(0, (k)) такое, что найдется (k) \0. Так как может принимать лишь конечное множество значений из n, k последовательность принимает некоторое значение ~ n бесконечное число раз.

k j Существует подпоследовательность { } такая, что k j j N, = ~. Рассмотрим произвольный j N. Для (k ) найдется 0 j (k )(0, (k )) такое, что ~ (k j ) \0. Тогда j 0 j ~ j N, U (k j )(s) S.

Так как ~ 0 =, то найдется > 0 такое, что ~.

e> Возможно лишь < (k ) иначе, U (k j )(s) U (s) и из j ~ ~ U (k j )(s) S будет следовать, что U (s) S и ~.

В силу того, что стремится к нулю при j стремящемся к k j бесконечности, для данного найдем номер l такой, что >.

kl ~ Обозначим =. Вектор ~ (kl ) и U (kl ) (s) S. Из kl неравенства > следует, что U (s) U (s). Поэтому из того, что ~ ~ U (kl ) (s) S вытекает U (s) S. Получили противоречие.

Вторая часть утверждения доказана и справедливо утверждение 3.2.2.

Q. E. D.

Утверждение 3.2.3. Пусть s1 s2 Rn. s1 S и s2 S и 1 {c,..., c}, тогда > 0 и : t (0, ) s(t) = s1(1- t) + s2t S и {c,..., c}.

Доказательство: Пусть s1, s2 Rn, s1 S, {c,..., c}, s2 S.

1 Найдем n и > 0.

1 C( ) s1 S = {s Rn : sM ( ) = s 1, sA( ) = s 1, sC( ) [0, 1] }.

1 1 1 M ( ) A( ) Компоненты si, i C( ) могут располагаться либо строго внутри отрезка [0, 1], либо на его концах. Введем обозначения: Z C( ) - множество всех АЭ i C( ) таких, что s1 = 0 ;

аналогично i 1 O = {i C( ) : s1 = 1} и K = {i C( ) : s1 (0, 1)}.

i i Множество координат i таких, что si2 лежит левее s1 обозначим i через L. Для любого j L любая точка отрезка [s1, s2 ] лежит левее точки s1 по j - координате. Аналогично определим R = {i I : s1 < si2} и i E = {i I : s1 = si2}.

i Пусть i I такова, что s1 {0, 1}, то есть i K (-C( )), тогда i очевидно найдется > 0 такое, что i K (-C( )) U (s1) {0, 1} =.

i min(, 1) Положим = и возьмем ~ такой, что при малых t s1 - si max i iI si(t) остается внутри (0, 1), i C( ~). То есть C( ~) = (Z R) (O L) K (Z E) (O E). M ( ~) = (O R) M ( ) состоит из всех координат i таких, что либо i M ( ) либо si(t) при t > 0 уходит вправо от точки 1 и попадает в область si >1. Аналогично A( ~) = (Z L) A( ). Легко показать, что такое задание ~ соответствует некоторому возможному вектору состояний, то есть M ( ~) A( ~) C( ~) = I.

Пусть i таково, что s1 = 0 и s1 > si2, то есть i (Z L), тогда при i i любом t (0, 1], si (t) < 0. Аналогично t (0, 1], i (O R) si (t) > 1.

Для всех t (0, ) верны следующие оценки min(, 1) i A( ) si(t) s1 + s1 - si2 s1 + < 0, i i i s1 - si max i iI i M ( ) si(t) > s1 - > 0, i min(, 1) i (Z R) 0 < si (t) 0 + s1 - si2 min(,1) 1, i s1 - si max i iI i (O L) 1 > si(t) 0, i (O E) si (t) = 1, i (Z E) si (t) = 0.

~ Тогда t (0, ) s(t) S.

Q. E. D.

Утверждение 3.2.4. s1, s2 R2, множество (s1, s2 ) состоит из одного элемента.

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

j 2 j C( ). Рассмотрим вектор ~ такой, что A( ~) = A( ) { j}, 2 M ( ~) = M ( ), C( ~) = C( ) \ { j}. Так как [s1, s2] Q, то C( ) [s1, s2 ] {s Rn : sC( ) R, s-C( ) = s 2 } = 2 -C( ) C ( ~) ~) = {s Rn : sC( R, s R1, s-C( ) = s 2 } = j -C ( ) ~ C( ~) ~) ~)\{ ~)\{ = {s Rn : sC( R, s R1, s-C( j} = s-C( j}}.

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

j 2 Но - C( ~) > - C( ), в то время, как Argmax - C( ). Получили ~ противоречие. Значит Argmax - C( ) =1, множество состоит из ~ одного элемента.

Q. E. D.

Лемма 3.2.1. Gi (s) не убывает по si для любых s Rn.

Доказательство: Рассмотрим произвольные вектор s Rn и АЭ 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 ( ) {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 > функция Gi (s) не убывает.

Если si [0, 1], то (si, s-i ) S, где определяется так, что M ( ) = M ( ) \{i}, C( ) = C( ) {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( ) {i}, A( ) = A( ). Из предыдущего пункта.

Gi(s) > gi (s-C( )\{i}, sC( ), 0) > gi (s-C( )\{i}, sC( ), 0) + si - 0 = Gi (si, s-i ) Таким образом, G(s) частично монотонна во всем Rn.

Q. E. D.

Лемма 3.2.2. G(s) непрерывна в Rn.

Доказательство: Обозначим A S = { Rn : sC( ) [0, 1]C( ), sM ( ) sM ( ), s sA( )}, где запись sM ( ) sM ( ) означает i M ( ), si si, аналогично sA( ) sA( ) означает i M ( ), si si.

Функции s-C( ) - s-C( ) и g(sC( ), s-C( )) непрерывны в S.

Тогда G(s) непрерывна как суперпозиция непрерывных функций.

Рассмотрим произвольный s Rn. Из утверждения 3.2.2. найдется 0 и > 0 такие, что (0, ) и 0 U (s) S и 0 0 U (s) S =.

Положим = min(, 1 k), k = N. При таком определении, k 0 k > 0, 0 U (s) S, то выберем для каждого k последовательность sk, такую, что sk, U k (s) S. Так как sk, s при k и для всех 0, sk, S, то k k sM, ( ) > sM ( ), sk,( ) > sA( ), sC,( ) [0, 1]C( ).

A По свойствам предельных переходов sM ( ) sM ( ), sA( ) sA( ), sC( ) [0, 1]C( ). То есть s S, 0.

В силу непрерывности G(s) на S можно 0, (0, ) (0, ) ( ) > 0 : s U ( )(s) S 0 G(s) - G(s ) <.

Положим =. Так как {S } n образует разбиение Rn, можно min записать (U (s) S ) =U (s). Из утверждения 3.2. n 0, (0, ), U (s) S =, то (U (s) S ) = U (s).

(0, ) > 0 : s U (s) G(s) - G(s ) <.

Q. E. D.

Лемма 3.2.3. Если g(s) непрерывна и частично монотонна, то r Rn s Rn такой, что G(s) = r.

Доказательство: Возьмем произвольный r Rn, тогда существует L > такое, что i I, ri < L. В силу непрерывности g(s) ограничена и M > 0 : i I, s S, gi (s) < M. Обозначим L0 = max(L, M ) +1 3.

Определим следующие множества = {s Rn : i I,-3L0 < s < 3L0}, = {s Rn : i I,-3L0 s 3L0}, = {s Rn : K I : K(s) I, i K, si = 3L, i I \ K, si < 3L}.

Возьмем произвольный s. Для этого s существует n такой, что s S. Рассмотрим некоторый АЭ j K(s), тогда s = 3L0.

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

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

Q. E. D.

Теорема 3.2.1. Пусть процедура планирования g : S Rn непрерывна в S и частично монотонна в S. Тогда для любого Rn с вектором точек пиков r Rn существуют равновесие Нэша s(r) и вектор состояний n такие, что s(r) = (s-C( ),sC( )), где sC ( ) [0, 1]C ( ). При этом gC( )(s(r)) = rC( ), gM ( )(s(r)) < rM ( ) и gA( )(s(r)) > rA( ).

Доказательство: В силу того, что рассматриваемое отображение g : S Rn удовлетворяет условиям леммы 3.2.3, r Rn s Rn : G(s) = r. Тогда n : s S. Рассмотрим вектор s* = (sC( ), s-C( )) и получим следующие результаты:

rC( ) = GC( )(s) = GC( )(sC( ), s-C( ) ) = gC( )(sC( ), s-C( )) = gC( )(s(r)), rM ( ) = GM ( )(s) = gM ( )(sC( ), s-C( )) + sM ( ) - sM ( ) > gM ( )(sC( ), s-C( )) = = gM ( )(s(r)), rA( ) < gA( )(s(r)).

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

Таким образом, утверждение доказано.

Q. E. D.

Лемма 3.3.1. Пусть выполнено А.3.3.1, тогда n, D 0 = G(S ).

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

Таким образом G(s) D 0 и G(S ) D 0.

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

Q. E. D.

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

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,GM1 (r-i)) и ri > Gi(siM,GM1 (r-i)).

i i б) Если i C( ), то si [0, 1]. По условию А.3.3.3 можно записать, что i i -1 Gi(siM,GM (r-i)) Gi (s) = ri Gi (siA,GA1(r-i )).

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

Q. E. D.

Теорема 3.3.1. Пусть для всех элементов функции предпочтений GSP. Пусть g(s) непрерывна и частично монотонна в S и i выполнены предположения А.3.3.1-3.3.3, тогда верны следующие утверждения:

1) Существует выбор равновесия s : Rn S такой, что для каждого r Rn, s(r) - равновесие Нэша в механизме g : S Rn и для любых n и r D введенные в А.3.3.1 функция x (rC( ) ) = g(s(r)), где D = {r Rn : rM ( ) < gM ( )(s(r)), rC( ) = gC( )(s(r)), rA( ) > gA( )(s(r))}.

2) Разбиения B и B0 совпадают и соответствующий g(s) прямой механизм неманипулируем.

Доказательство: 1) из теоремы 3.2.1 для любого r Rn существует равновесие Нэша s (r) и при этом найдется n такой, что s(r) = (s-C( ), sC( )), где sC( ) [0, 1]C( ) и при этом rC( ) = gC( )(s(r)) gC( )(s-C( ), [0, 1]C( ) ), rM ( ) > gM ( )(s(r)), rA( ) < gA( )(s(r)).

Так как при выполнении А.3.3.1 rC( ) gC( )(s-C( ), [0, 1]C( ) ) определена и единственна функция x (rC( )) такая, что xC( ) (rC( )) = rC ( ). При этом g(s(r)) = xC ( )(rC( )) в силу единственности x (rC( )) для всех rC( ) gC( )(s-C( ), [0, 1]C( ) ).

Тогда если r D, то rC( ) gC( )(s-C( ), [0, 1]C( ) ), rM ( ) > xM ( )(rC( )), rA( ) < xA( )(rC ( )) и первое утверждение теоремы доказано. Кроме этого видно, что D D 0.

2) Так как для любого r Rn s(r) - равновесие Нэша в механизме g : S Rn, то B является разбиением Rn и поэтому для любых 1 2 1, n верно D D =. Докажем, что для любых, n 1 верно также, что D01 D0 2 =. Допустим, что это не так, тогда 1 найдутся различные, n : D01 D0 2 и следовательно 1 найдется j I такой, что =. Рассмотрим варианты а) j j 1 2 1 2 1 = c, = m;

б) = c, = a;

в) = m, = a. Все остальные j j j j j j варианты сводятся к этим трем и кроме этого доказательства вариантов б) и в) аналогичны, поэтому рассмотрим варианты а) и б).

i i 1 1 - а) для, i C( ), r D01, Gi(siM,GM1 (r-i )) ri Gi (siA,GA1(r-i )) i i i 2 A и для, i C( ), r D0 2, Gi(siM,GM1 (r-i )) < ri. И если i D01 D0 2 то найдется r D01 D0 2. Из того, что i - r D01, ri Gi(siM,GM (r-i)) а из того, что r D0 2 следует i M i - ri Gi(siM,GM (r-i )). Получили противоречие.

i б) Воспользуемся теми же соображениями, что и в а), при этом неравенства для r D01 и r D0 2 и будут выглядеть следующим образом:

i i - ri > Gi(siM,GM1 (r-i)) Gi(siA,GA1(r-i)) > ri.

i i Получаем противоречие и случай б) доказан.

Из части 1) доказательства имеем D D 0, при этом 1, n выполнено D01 D0 2 =. Допустим, что D 0 D для некоторого n, тогда существует r D 0 такой, что r D. Так как B - разбиение Rn, то найдется n такой, что r D, но так как D D 0, то r D 0 D 0 и D01 D0 2. Получили противоречие, значит B = B0.

Все условия теоремы 3.1.1 выполнены, поэтому соответствующий g : S Rn прямой механизм неманипулируем и существует эквивалентный ему прямой механизм g(s(r)).

Q. E. D.

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

Справедливо следующее равенство -1 det(AC( ) {i}|C( ) {i}) A{i}|{i} - A{i}|I \{i}[A I \{i}|I \{i}] AI \{i}|{i} =.

det(AC( )|C( )) Доказательство.

+ jk (-1)il Ml, k (AC( )|C( )), l C( );

- det(AC( )|C( )) [AI \{i}|I \{i}] = k, l il + jk (-1), l C( ).

l, k - Тогда A{i}|{i} - A{i}|I \{i}[AI \{i}|I \{i}] AI \{i}|{i} = (-1)il + jk Ml, k (AC( )|C( )) = ai, i - ai, k al, i = det(AC( )|C( )) kC( ) lC( ) (-1)il + jk Ml, k (AC( )|C( ) ) det(AC( ) {i}|C( ) {i}) = ai, i - ai, k al, i =.

det( AC( )|C( )) det(AC( )|C( )) kC( ) lC( ) Q.E.D.

Доказательство. 1) Проверим выполнение условия С.1. Рассмотрим произвольный вектор r Rn и произвольный n и пусть rC( ) gC( )(s-C( ), [0, 1]C ( ) ).

Уравнение rC( ) = gC( )(s-C( ), sC( )) имеет единственное решение в силу условия теоремы.

Тогда соответствие g(s-C( ), g -1(rC( ))) однозначно и условие С.1 выполнено.

2) Проверим выполнение условия С.2. Доказательство проведем по индукции. Легко показать, что для механизмов g(s) с одним АЭ, удовлетворяющих условиям теоремы, условия С.1-С.3 выполнены. Пусть i i для механизмов gI \{i}(siA, sI \{i}), gI \{i}(siM, sI \{i}) с количеством АЭ I -1 условия С.2-С.3 выполнены. Докажем, что для механизма g(s), удовлетворяющего условиям теоремы, выполнены условия С.2-С.3.

i Рассмотрим механизм gI \{i}(siA, sI \{i}) и векторы состояний n-1 для этого механизма. Тогда по теореме 1 для механизма i gI \{i}(siA, sI \{i}) множества диктаторства D, n-1 нормальны и образуют разбиение Rn-1.

i Допустим, существует r-i Rn-1 такой, что G(sA, GM1 (r-i)) i неоднозначно. Так как множества диктаторства образуют разбиение Rn-1, то существует единственный вектор состояний n-1 такой, что r-i D = G(S ). Тогда система уравнений i r-i = gI \{i}(siA, sC( ), s -C( )) + EI \{i}|-C( ) (s-C( ) - s -C( )) имеет несколько различных решений. Найдем решение подсистемы данной системы уравнений:

i rC( ) = gC( )(siA, sC( ), s -C( ) ).

В силу условий теоремы данная подсистема уравнений имеет единственное решение, т.е. существует единственный C( ) такой, что i rC( ) = g(siM, s -C( ), C( )). При этом однозначно определяется решение подсистемы i r-C( ) = g-C( )(siM, s -C( ), C( )) + -C( ) - s-C( ) i -C( ) = g-C( )(siM, s -C( ), C( )) - r-C( ) - s -C( ).

Таким образом, уравнение i r-i = gI \{i}(siA, sC( ), s -C( )) + EI \{i}|-C( )(s-C( ) - s -C( )) i имеет единственное решение и отображение G(sM, s-i ) глобально i обратимо, а значит, G(sM, GM1 (r-i )) однозначно. Аналогично i i доказывается однозначность соответствия G(sA, GA1(r-i)).

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

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

m s + m Рассмотрим некоторый фиксированный s-i Rn-1 и найдем разность i n (s-i, si ) = Gi(s-i, si) - GisiA +, G-Ai n (GC( Ai )(s-i, si)).

m s + m В силу того, что для любого sI \{i} Rn-1 найдется единственный n-1 такой, что sI \{i} S, n n n n s JI |{i} sI \{i}, - - M1 si - G(sI \{i}, si) - GsI \{i}, i m m m m n n n JI |{i} sC( ), s -C( ), si - - + M1si.

m m m Рассмотрим механизм планирования с n -1 АЭ, определяемый n процедурой планирования (sI \{i}) = gI \{i}sI \{i},, sI \{i} [0, 1]n-1.

m Механизм планирования (sI \{i}), sI \{i} [0, 1]n-1 удовлетворяет условиям теоремы, и в силу индуктивного предположения i n соответствующая ему функция (sI \{i}) = GI \{i} siA +, sI \{i} m удовлетворяет С.1-С.3. Множества диктаторства механизма (sI \{i}) нормальны и D = (S ).

n n + Пусть для некоторого si, GI \{i}(s-i, si) D, где вектор m m n-1 существует и единствен в силу того, что выполнено С.2.

C( ) (s) = gC ( )(sC( ), s -C( )), -C( )(s) = g-C( )(sC( ), s -C( )) + + (s-C( ) - s -C( )). В силу того, что функция G(s-i, si ) непрерывна и i n возрастает по si, а функция GsiA +, sC( Ai ) глобально обратима, m n n + множества точек S =, G(s-i, si) D являются s m i m объединением замкнутых, непересекающихся отрезков n n + [sik, sik +1],, k Q, sik < sik +1 [11].

m m Пусть отрезок [si0, s1] таков, что для любых si [si0, s1] i i G(sI \{i}, si) D и si0 и s1 являются граничными точками множества S.

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

+ M2(rI \{i} - rI0\{i}) Аналогично, найдутся M2 > 0 и окрестность > 0 такие, что для n n +1 любых si,, < будет справедлива следующая оценка:

m m m n G-Ai n (GI \{i}(s))-, s0\{i} I si + m m - n n, sI (si - si0) + J m, sI \{i} JI \{i}|I \{i} \{i} I \{i}|I \{i} m + BI \{i}|I \{i}(s0\{i} - I \{i})(si - si0) + M (si - si0)2, I где BI \{i}|I \{i} - матрица с элементами, ограниченными константой, не зависящей от sI \{i}.

Аналогично, найдутся M2 > 0 и окрестность > 0 такие, что для n n +1 любых si,, < будет справедлива следующая оценка:

m m m n n 1 GiG-Ai n (GI \{i}(s)), Gi, sI \{i} + m m si + m - n n n + \{i} JI \{i}|I \{i}, sI \{i} - si0) + J I\{i}|I, sI \{i} (si J m, sI \{i} {i}|I \{i} m m 0 + C{i}|I \{i}(sI \{i} - I \{i})(si - si0) + M3(si - si )2, где g(s) - матрица с элементами, ограниченными константой, не зависящей от A.

Тогда (s-i, si ) - (s-i, si0) J{i}|{i} n, sI \{i} (si - si0) - m - n n n (si - J{i}|I \{i}, sI \{i} J I\{i}|I \{i}, sI \{i} JI \{i}|I \{i}, sI \{i} - si0) - m m m - C{i}|I \{i}(s0\{i} - I \{i})(si - si ) - (M1 + M3)(si - si0)2.

I В силу того, что все диагональные миноры матрицы J (s) положительны, отображение g(s) непрерывно дифференцируемо, а множество S замкнуто, найдутся константы A и A такие, что для любого подмножества АЭ K I для диагональной матрицы JK K (s) выполнены следующие ограничения: A JK K (s) A, s S.

Выберем число промежуточных поверхностей m таким образом, 1 1 A 1 1 A что < min,,,,, тогда для всех 2 2 m 4 A M3 + M1 4 A n max Ci, j jI \{i} отрезков [si0, s1] S справедлива следующая оценка:

i (s-i, s1) - (s-i, si0) i n det JI|{i}sC( ), s -C( ), m C( ) {i}|C( ) {i} si > 0.

n det JI|{i}sC( ), s -C( ), m C( )|C( ) Таким образом, на каждом из множеств S, n-1 приращение (s-i, s1) строго положительно, откуда в силу непрерывности G(s) i получаем, что для любого выполнено неравенство sI \{i} Rn- i i n +1 n 1 Gi siA +, G-Ai n+1(GC(M )(s)) Gi (s) Gi siA, G-Ai n (GC( Ai )(s)) i m s + m s + m m, из которого следует, что для механизма x = g(s), s S выполнено условие С.3, для этого механизма выполнены условия теоремы 1 и для него существует эквивалентный прямой механизм.

Q.E.D.

Pages: | 1 | 2 |

Книги, научные публикации

Blog