Петраков С.Н. Механизмы планирования в активных системах - неманипулируемость и множества диктаторства. М., 2001. 135 с

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 с.

101

105Левченков В.С. Элементы эргодической теории с приложениями к проблемам выбора. М.: Изд-во факультета ВМиК МГУ. 1997

106Лезина З.М. Манипулирование выбором вариантов: теория агенды // А и Т. 1985. N 4. С.5 - 22.

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

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

Мир, 1991.

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

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

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

С. 3 - 26. 5

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. С.36

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

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

119Фишберн П. Теория полезности для принятия решений. М.: Наука, 1978. - 352 с.

102

120Фокин С.Н. Разработка, исследование и применение процедур распределения моноресурса в социально-экономических системах в условиях неопределенности с учетом приоритетов потребителей (на

примере распределения машинного времени на ВЦ в отраслевых НИИ и КБ) / Диссертация на соискание ученой степени канд. техн. наук. М:

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

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

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

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

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

Наука, 1998. С.124-159

103

Приложение

Лемма 2.1.1. Рассмотрим произвольный rÎ Dρ0 , тогда:

		~					0		~	ρ	(rC(ρ ) ) },
a) "iÎM(ρ) { (ri			, r−i ) Î Dρ						} Û {ri	> xi
		~					0		~	ρ	(rC (ρ) )} .
б) "iÎR(ρ) {(ri , r−i ) Î Dρ								} Û {ri		< xi
Доказательство. Пусть			~				ρ
			ri		> xi (rC(ρ) ) . Тогда по определению П.1
Dρ0 = {r Rn :rC(ρ) ProjC(ρ ) Dρ ,
r		> x ρ		(r			),
M (ρ)		M (ρ )		C(ρ )
r	A(ρ )	< x ρ	(r			)}.
		A(ρ)		C(ρ)

(П.1)

(П.2)

(П.3) (П.4) (П.5)

0

~

~

) . Так как iÎM(ρ),

Taк как rÎ Dρ

, то rC(ρ)ÎProjC(ρ)Dρ. Обозначим r

= (ri , r−i

то

rC(ρ)

~

ρ ) ,

~

и (П.3),

(П.5)

выполнены.

Из

~

= r−i

= rC(

rA(ρ) = rA(ρ)

r−i

следует,

что

ρ

~

ρ) ) ,

а так как

~

ρ

~

, то

rM (ρ)\{i} > xM (ρ )\{i}) (rC(

ri > xi

(rC(ρ) )

~

ρ

~

0

rM (ρ) > xM (ρ) (rC(ρ) ) . Поэтому справедливо (П.4) и по определению

Dρ

получаем (П.1).

~

ρ

(rC (

ρ ) ) верно

~

Обратно, предположение, что при некотором ri

£ xi

0

0

(ri

,r−i ) Î DA

входит в противоречие с определением Dρ .

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

леммы.

Q. E. D.

Теорема

2.1.1.

I -

Пусть

множество

активных элементов,

функции

полезности

элементов

обобщенно

однопиковые.

Пусть

механизм

h : Rn ® Rn удовлетворяет А.2.1.1 и D=D0 , тогда он неманипулируем. Доказательство: Рассмотрим произвольный профиль ϕ ÎGSPn . В силу

теоремы 1.2.1 для неманипулируемости достаточно показать, что сообщение достоверной информации является равновесием Нэша, то есть

~	1	~	, r−i )) .
"i Î I, "ri	Î R ,ϕi (hi (r)) ³ ϕi (hi (ri
	~	1
Допустим, что существуют элемент iÎI и ri		ÎR такие, что
	~	, r−i )) .	(П.6)
ϕi (hi (r)) < ϕi (hi (ri

Так как B - разбиение, то существует единственный вектор ρÎ n, такой, что rÎDρ. Возможны три случая: i может принадлежать либо M(ρ), либо C(ρ), либо A(ρ). Рассмотрим последовательно три этиx случая.

104

~

1)

Пусть

~

i ÎC(ρ) ,

тогда

1

,ϕi (hi (r))

как

ri

единственный

"ri

Î R

= ϕi (ri ) ³ ϕi (hi (ri , r−i )) так

максимум ϕi (xi )

по xi.

и A.2.1.1, r > h (r) = xρ (r

2)

Если i ÎM(ρ) , то из определения D

ρ

) .

i

i

i C (ρ)

Так

как

Dρ0

= Dρ ,

то

по

лемме

2.1.1

для

любого

~

ρ

~

~

0

~

ri > xi

(rC(ρ) ), r =

(ri , r−i )Î Dρ = Dρ и

ϕi (hi (r )) = ϕi (hi (r)).

Если

~

ρ

(rC (ρ ) ) ,

то

~

0

= Dρ

и существует

ri

£ xi

(ri ,r−i )Ï Dρ

единственный вектор

~

n

~

Î Dρ . Если верно (П.6), то из

ρ ÎÃ такой, что

r

~

того, что ϕi(xi) не убывает по xi при xi<r следует, что при сообщении

~

ri ,

i-ый

активный

элемент

должен

получать

~

Поэтому

hi (r ) > hi (r) .

~

~

~

ρ

~

~

~

~

~

ρ

ρ

xi (rC(ρ ) ) > xi

(rC (ρ ) ) , xi

(rC(ρ ) ) > ri и i Î A(ρ) .

							~
		В силу того, что				ρ		(rC(ρ )
						xi
									~
что	~	(r		) > rˆ	> xρ (r		) . Из
	xρ		ρ)
	i	C(		i	i C (ρ )
что		0		Аналогично		rˆÎ D			0
	rˆÎ D~ .								ρ
		ρ

) > xρ (r				ρ )	)	существует	rˆ Î	1 такой,
~	i	C (					i	R
	(r		) > rˆ			и леммы 2.1.1		вытекает,
xρ
i	C(ρ)				i
и	rˆÎ D		0			0	как	D=D	0	то
			ρ	I D~ . Но так
						ρ

D0 I D0 = Æ . Получили противоречие и (П.6) не выполнено.

~

ρ ρ

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

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

механизм коалиционно неманипулируем.

Доказательство: Допустим, выполнены условия теоремы и механизм

~

n

~

J

h(r ) коалиционно манипулируем, тогда r R

, J I ,

$rJ Î R

такие, что

~

³ ϕ j (hj (rJ , r−J )) и

j J → ϕ j (hj (rJ , r−J ))

~

i J → ϕi (hi (rJ , r−J )) > ϕi (hi (rJ , r−J )) .

Из определения

однопиковых

функций

полезности

получаем

r R

n

~

J

, J I , $rJ Î R

такие, что

~

(П.7)

hJ (rJ , r−J ) < ρ >J hJ (rJ , r−J )) и

$j

~

)) < ρ > j hj

(rJ , r−J ) .

(П.8)

Î J I (A(ρ) U M (ρ)) : hj (rJ , r−J

105

~

n

~

=

~

~

Рассмотрим ρ ÎÃ

такой, что r

(rJ , r−J )Î Dρ

и ρ ¹ ρ .

~

Тогда найдется из (П.8)

множество

Æ Í K Í J \{ j*} , такое,

что

~

~

hJ \K (r) .

hK (r ) = hK (r) и hJ \K (r ) < ρ >J \K

~

~

Рассмотрим вектор r

= (hJ (r ), r−J ) . Из определения следует, что

~

=

~

0

~

, J )

~

~

r

(hJ (r ), r−J )Î D

(ρ

так как r

= (rJ , r−J )Î Dρ .

~

С другой стороны r = (rJ , r−J )Î Dρ и выполнено (П.7), тогда

~

=

~

0

(

ρ, K)

так как r = (rJ , r−J )Î Dρ .

r

(hJ (r ), r−J )Î D

Тогда

0

0

~

¹ Æ . При

этом,

c j (ρ, K) ¹'c'

в силу

Dc(ρ, K )

I Dc(

ρ

, J )

(П.8),

а

~

поскольку

j

Î J ,

откуда

следует,

что

c j (ρ, J ) ='c' ,

c j (ρ, K) ¹ c j

(ρ, J )

и $ρ, ρ : Dρ I Dρ ¹ Æ . Получили противоречие.

~

~

~

h : Rn ® Rn

Q.E.D.

Лемма

2.2.2.

Пусть

механизм

удовлетворяет

А.2.1.1 и

неманипулируем, тогда D = D0 .

Доказательство:

Допустим,

$ρ1, ρ 2 ÎÃn

такие,

что

ρ1 ¹ ρ 2

и

0

I Dρ2

¹ Æ .

Тогда существуют

~

0

I Dρ 2

и

r

Î Dρ1

такие,

что

Dρ1

r Î Dρ1

~

rC(ρ1) = rC (ρ1) .

~

Рассмотрим

множество

K = {i Î I

K

IC(ρ

1

) = Æ .

ri ¹ ri } ,

Рассмотрим

возрастающую

последовательность

ik Î K, k =

1,

K

.

Определим последовательность точек r k ,

что r0 = r ,

k =

0,

K

таких,

k +1

k

~

K

~

r

=

(r−ik , rik

) . При таком определении r

= r .

Lk

= [rk−1, r k ] ,

Определим

последовательность

отрезков

Lk Î Dρ01

r0 = r Î Dρ1 , а

k =

1,

K

. Все отрезки

по лемме 2.1.1. Так как

K

~

r

= r

Î Dρ2 ,

то

найдется

номер

k Î{0, ...,

K

}

такой,

что

k−1

~

r

Î Dρ1 , r

k

1

.

Î Dρ , где ρ ¹ ρ

~

В

силу

того, что

механизм

h : Rn ® Rn

неманипулируем,

h

(rk−1) = h

−1

(r k ) .

Пусть

существует

j I

такой,

что

ik−1

ik

106

hj (r	k−1	) ¹ hj (r	k	) , тогда либо	1	¹ c , либо	~	1	¹ c .
					ρ j		ρ j ¹ c , например,	ρ j

Рассматривая коалицию { j, ik−1} , при положении истинной точки пиков - r k−1 получаем, что ей выгодно сообщать r k . Аналогично, если ρ~ 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 I (A(ρ) U M (ρ)) .

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

1,

K

.

r−′k1

Рассмотрим

D(ρ, k1) .

"r Î D(ρ, k1) $r′Î Dρ

такой,

что

= r−k1 .

Тогда из

коалиционной

манипулируемости

следует,

что

hk (r′) = hk

(r) . Докажем, что h(r¢) = h(r) .

1

1

hj (r′) ¹ hj (r) .

Допустим, что

h(r¢) ¹ h(r)

и

j I

такой,

что

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

ρ j ¹ c

и (2) ρ j = c .

1.

Пусть ρ j ¹ c и

rj

< ρ > j

hj (r) . Если

hj (r) < ρ > j hj (r′) , то при

истинной точке пиков r′ и функции полезности

ì

2

¢

¢

< ρ > j

x j ;

ï-

¢

¢

x j - rj

, rj

ï

hj (r ) - rj

ϕ j (x j ) = í

1

¢

< ρ > j

¢

ï-

, x j

h

(r) - r¢

x j - rj

rj .

ï

j

î

j

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

Если hj (r′) < ρ > j

hj (r) , то аналогично получаем, что при точке

пиков r и функции полезности

ì-

2

x j - rj

, rj < ρ > j x j ;

ï

¢

ï

hj (r) - rj

ϕ j (x j ) = í

1

, x j < ρ > j rj .

ï-

x j - rj

h

¢

¢

ï

î

j

j

и сообщение r′ .

выгодно образование коалиции { j, k1}

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

107

2.

Если

ρ

j

= c , то

h

j

(r′) ¹ r

j

= r′

и при истинной точке

пиков

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 однопиковая и сепарабельная, тогда любой элементарный механизм

e : RJi ® R Ji неманипулируем.

Доказательство: Допустим

механизм

e(r)

манипулируем, тогда

найдутся точки пика r

i

Î R

Ji

~i

Î R

Ji

~i

)) > ϕi (e(r

i

)) .

и r

такие, что ϕi (e(r

Пусть

ri Î D

ρ

i ,

где

ρi ÎÃJi .

Тогда

в силу

определения

~i

элементарного

механизма и

того,

что

e(r

i

)

выполняется

) ¹ e(r

e−C (ρi )(ri ) < ρ i > −C

такая, что e j (ri ) ¹ e

Обозначим

r−iC(ρi ) < ρ i >−C(ρi )

						~i	)
(ρi ) e−C(ρi )(r
	~i		) .
j (r
	e	K			~i		i
			= e(rK			, rJi
e			i	)	(ri ) <		ρ
	−C (ρ

	и найдется компонента плана j Î Ji
\K ) ,		Æ Í K Í Ji .		В силу того, что
i		~i	)	и сепарабельности
	>−C (ρi ) e−C(ρi ) (r

функции

полезности

ϕ i (xi ) , для любого

j Î J

i

\ C(ρi ) выполняется

1

ϕ i (e ) ³ ϕ i (e{ j1} ) . По индукции получаем,

что ϕ i (e ) ³ ϕ i (eJi \C (ρi ) ) и

далее ϕ

i

(e

) ³ ϕ

i

(e

Ji

) = ϕ

i

~

(e(r )) . Получили противоречие.

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

Q.E.D.

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

108

и удовлетворяет условию А.2.3.1, тогда механизм h(r) , r R J	является
неманипулируемым.	r−i RJ−i
Доказательство: Докажем, что при каждом фиксированном

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

Рассмотрим

произвольный

вектор

r

R J−i

и произвольный

rJi RJi

. Пусть r = (rJi

J−i

, rJ−i )

принадлежит некоторому множеству Dρ и

рассмотрим

~

~

J

~

Для

каждого

~

~

(ρ) = {ρ

ρ−Ji =ρ−Ji } .

ρ (ρ)

определены

функции

&&&

~

(r

~

) ,

принимающие

постоянные

x ρ

−C (ρJi )

C(

ρJ−i )

значения при

заданном

r

R J−i

,

поэтому

будем

считать,

что

для

~ ~

J−i

ρ

каждого ρ (ρ)

определены числа x

&&&

~

.

−C (ρJi

)

~

Поскольку верно

D = D0 и из А.3 для любого

ρ J , i I ,

и

~

J )

найдется

r Dρ

такой,

что

J Ji

r Dc(ρ,

~

~

ρ

x

c(ρ, J )

= x

(rC(

ρ ) )

верно,

что

для

всех

j Ji

существуют

(rC(c(ρ , J )) )

~

числа xρj j R{ j} такие, что для любого ri

R Ji

такого, что rji < ρ j > xρj j

выполняется

h

j

(r) = x

ρ j

.

Из

односвязности

множеств

Proj

D

ρ

j

C (ρ)

следует, что для всех

rj

таких, что

xρj

j

< ρ j

> rji

для любого

ρ 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 , то ОПВ не выполнено. В

j I

противном случае ОПВ выполнено.

109

Доказательство: очевидно из свойств 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) ,	то	"ri ³ h(r) ,	h(ri , r−i ) = h(r)	и	"ri	< h(r) ,
			~	~		~
~
h(ri , r−i ) < h(r) ;		то	"ri £ h(r) ,	h(ri , r−i ) = h(r)	и	"ri > h(r) ,
2) если	ri < h(r) ,
			~	~		~
~
h(ri , r−i ) > h(r) .
Доказательство: докажем			эту лемму	следующим	способом:		будем
рассматривать последовательное изменение сообщения						~
						ri Î[d, D]

некоторого активного элемента с номером i I . При этом возможны три варианта: активный элемент выходит из некоторого множества El разбиения E и возможно переходит в множество El−1 , либо в множество

El+1 , то есть, если i Î El и k Î El−1 , а j Î El+1 , то либо ril−1			~	£ ri , либо
			£ ri
~	. Если элемент	i находится между двумя	множествами
ri £ ri £ ril+1

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

еще одно множество		El разбиения E , состоящее из одного элемента
El ={i} . При этом, возможно, что номер i				лежит либо выше, либо ниже
множества Ω(r) в упорядочении, задаваемом						t ÎT E . Также, возможно
~		~
два варианта: ri > ri и ri < ri .
Обозначим		δ = max α ,		λ =		min α .	Обозначим
			α Ω(r)			α Ω(r)
= {α Θ :α > δ } и L ={α ÎQ :α > λ}. Все возможные варианты сведем
в следующую таблицу
			~			~
			ri > ri			ri < ri
	i		3			2
	i Ω		1			1
	i Λ		2			3

где одинаковыми числами обозначены симметричные ситуации. Таким образом, достаточно рассмотреть три случая:

1) i Ω , ~ri < ri ;

110