Автоматика и телемеханика, № 2, 2021

Интеллектуальные системы управления,

анализ данных

(Федеральный исследовательский центр

“Информатика и управление” РАН, Москва)

ТОПОЛОГИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

ОБ АГРЕГИРОВАНИИ ИНФОРМАЦИИ

В ИЕРАРХИЧЕСКИХ ИГРАХ

Исследуются две задачи о рациональном агрегировании информации в

иерархических играх. Рассматриваются непрерывные способы агрегиро-

вания. Рациональность оценивается по двум критериям: максимальному

гарантированному выигрышу одного из игроков и размерности простран-

ства агрегатов.

Ключевые слова: иерархические игры, максимальный гарантированный

результат, теория информации, размерность.

DOI: 10.31857/S0005231021020094

1. Введение

Опишем в нескольких словах одно из направлений развития теории игр.

В 30-х гг. XX в. Г. фон Штакельберг начал рассматривать игры с фиксиро-

ванным порядком шагов (см. [1], первое издание вышло в 1934 г.). Он рас-

сматривал лишь игры без обратной связи: игроки, принимающие решения

раньше, не имели никакой информации о выборах, которые будут делать иг-

роки, принимающие решения позже.

На рубеже 60-х и 70-х гг. XX в. стали исследоваться аналогичные модели

с обратной связью: некоторые игроки выбирали свои решения как функции

от выборов своих партнеров. Такие модели стали исследовать практически

одновременно и независимо в теории иерархических игр [2], теории активных

систем [3], теории контрактов [4] и т.д. Это позволило существенно расши-

рить класс процессов принятия решений, описываемых теоретико-игровыми

моделями. В первых моделях такого рода рассматривались лишь крайние

случаи: либо предполагалось, что один игрок имеет полную информацию о

выборе своего партнера, либо считалось, что такой информации у него нет

вовсе.

Промежуточные случаи стали изучаться следующим поколением исследо-

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

мацию о выборах друг друга, но в агрегированном виде [5]. Это направление

развивалось параллельно в теории иерархических игр и теории активных

систем (дальнейшие ссылки - в [6] и [7] соответственно). По-видимому, за

149

рубежом такие задачи отдельно не изучались, хотя, возможно, и возникали

где-то в неявном виде.

Следующий шаг в данном направлении - рассмотрение моделей, в которых

некоторые из игроков могут сами выбирать содержание используемой инфор-

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

традиционных моделей легко доказывается принцип: чем большей информа-

цией обладает игрок, тем лучше для него [8]. Поэтому ответ на вопрос о вы-

боре “оптимального” способа обмена информацией становится тривиальным

и потому неинтересным. Но при этом никак не учитывается, что использова-

ние больших объемов информации требует затрат времени, сил, денег и т.д.

Для учета этого обстоятельства необходима мера объема информации.

К сожалению, на сегодняшний день (да, вероятно, и вообще) такой универ-

сальной меры нет. Можно предложить несколько вариантов. Наиболее инте-

ресным¹ представляется вариант, рассмотренный в [9]. В этом варианте счи-

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

сообщений в битах предлагается использовать. Этот подход представляется

разумным, пока объемы информации относительно невелики.

При больших объемах информации возникает проблема. В другом контек-

сте она отмечалась уже в [10]. Применительно к задачам принятия решений ее

можно сформулировать так. Допустим, лицо, принимающее решения, готово

обработать один терабайт информации. Тогда ситуация практически никак

не изменится, если увеличить этот объем на триста килобайт или уменьшить

на двести мегабайт. Таким образом, при таких объемах информации обычные

числа не слишком приспособлены для их измерения. Эта проблема заслужи-

вает отдельного обсуждения, но оно выходит за рамки данной статьи.

В физике часто подобные проблемы решаются следующим образом: боль-

шое конечное множество заменяется континуумом, и для описания его “мас-

сивности” используется какой-то обобщенный показатель. Можно использо-

вать, например, размерность этого континуума. Это, собственно, и сделано

далее. Точные формулировки содержатся в разделе 2.

Подобная задача была впервые поставлена А.Ф. Кононенко [6, 11]. Правда,

в этих публикациях рассматриваемый континуум считался вложенным в ев-

клидово пространство и в качестве “меры информации” использовалась раз-

мерность этого евклидова пространства. Это дополнительное ограничение не

очень хорошо отражает суть дела и затрудняет решение задачи. Кроме того,

в цитированных публикациях для решения задачи используются локальные

дифференциально-геометрические методы. Как будет видно из дальнейшего,

рассматриваемая задача имеет существенно глобальный характер². Поэто-

¹ Ссылки на публикации, в которых рассматриваются другие варианты, можно найти

в [9]. К сожалению, в большинстве случаев приходится сталкиваться с какими-то патоло-

гиями: либо решение задачи “вырождается” и плохо интерпретируется в содержательных

терминах, либо в типичном случае это решение оказывается неустойчивым по отношению

к малым изменениям параметров модели и т.п. Модель, рассмотренная в [9], будто бы,

свободна от этих недостатков. Кроме того, на ее основе удалось построить модели, учиты-

вающие, например, возможность ошибок при передаче информации. Все эти результаты

опубликованы в журнале “Автоматика и телемеханика” и сборнике “Управление большими

системами” и легко могут быть найдены по фамилии автора данной статьи.

² См. замечание 6 далее.

150

му локальными методами удается получить решение лишь для очень узкого

класса игр.

Для случая антагонистических игр рассмотренная в данной статье задача

была решена в [12]. В принципе, общий случай сводится к антагонистическо-

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

ские конструкции. Техника, впервые примененная в [9], позволяет исследо-

вать общий случай так же просто, как и антагонистический.

2. Постановка задачи

Будем рассматривать игру двух лиц в нормальной форме Γ = 〈U, V, g, h〉,

где U и V - компактные топологические пространства, а g и h - непрерыв-

ные функции из U × V в множество действительных чисел R. Элементы мно-

жеств U и V интерпретируются как управления первого и второго игроков.

Их интересы описываются стремлением к максимизации значений функций

выигрыша g и h соответственно. Выбор управления из множества U или V

считается элементарной операцией.

Замечание 1. Здесь компактность понимается в смысле [13, 14] как воз-

можность выбрать из каждого открытого покрытия конечное подпокрытие.

В [15] для этого понятия используется термин бикомпактность, а компакт-

ность понимается несколько иначе. К сожалению, терминологические рас-

хождения имеются и в других случаях. Везде далее используется термино-

логия из [13, 14].

Введем обозначение. Далее Φ (X, Y ) обозначает класс всех функций из

множества X в множество Y .

Пусть заданы множество W и отображение P : V → W . Наряду с иг-

рой Γ будем рассматривать игру Γ_P = 〈U_P , V_P , g_P , h_P 〉, заданную следующи-

ми условиями:

V_P = V , U_P = Φ (W,U),

g_P (u_P ,v_P ) = g(u_P (P(v_P )),v_P ), h_P (u_P ,v_P ) = h(u_P (P(v_P )),v_P ).

Содержательно множество W интерпретируется как множество сообще-

ний, которые второй игрок может передать первому, а функция P - как спо-

соб агрегирования информации о сделанном вторым игроком выборе.

Замечание 2. В дальнейшем систематически будет рассматриваться па-

ра игр Γ и Γ_P . Удобно термин “управление” использовать в отношении исход-

ной игры Γ, а термин “стратегия” относить к ее информационному расшире-

нию Γ_P . При этом стратегия будет пониматься как способ выбора управлений

в зависимости от получаемой информации, что соответствует традиции, вос-

ходящей к фон Нейману.

Если отображение P постоянно, то игра Γ_P в естественном смысле изо-

морфна игре Γ. Особое место занимает случай, когда W = V , а отображение

P - тождественное. Соответствующую игру по традиции будем обозначать

через Γ₂. Н.С. Кукушкин показал, что при любом способе обмена информа-

цией первый игрок гарантированно получает выигрыш, который не превосхо-

дит максимального гарантированного результата в игре Γ₂. Таким образом,

151

этот результат - это идеал, которого хотелось бы достичь, по возможности, с

наименьшими объемами передаваемой информации. Именно такая постанов-

ка вопроса исторически была первой (см., например, [6, 11]). В частности, по

этой причине во многих работах речь идет об “агрегировании информации”.

В данной статье используется несколько иной подход: акцент сделан на полу-

чении “достаточно хорошего” (но не обязательно максимального) результата

при приемлемом объеме передаваемой информации.

Будем считать, что игрок номер один обладает правом первого хода, т.е.

он первым выбирает свою стратегию и сообщает ее партнеру. В таком случае

нетрудно оценить множество рациональных выборов второго игрока. В са-

мом деле, если он действительно стремится к максимизации значения функ-

ции h_P , то естественно предположить, что он выберет свою стратегию из

множества BR (u_P ), определенного одним из условий³:

{

}

• BR(u_P) = v ∈ V : h(u_P(P(v)),v) = maxh(uP (P (w)), w)

, если верхняя

w∈V

грань sup h(u_P (P (v)), v) достигается;

^v∈V {

}

• BR(u_P) = v ∈ V : h(u_P(P(v)),v) ≥ sup h(u_P(P(w)),w) - κ в против-

w∈V

ном случае (здесь κ - наперед заданное положительное число).

Следовательно, выбрав стратегию u_P , при разумном поведении партнера пер-

вый игрок может с гарантией рассчитывать на получение выигрыша

inf

g(u_P (P (v)), v),

v∈BR(u_P )

а его максимальный гарантированный результат составит

R_κ(Γ_P ) = sup

inf

g(u_P (P (v)), v).

u_P ∈Φ(W,U)

v∈BR(u_P )

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

зультат первого игрока в исходной игре Γ:

R_κ(Γ) = sup

inf g(u, v),

u∈U

v∈BR(u)

где

{

}

BR(u) = v ∈ V : h(u,v) = maxh(u,w)

w∈V

Непосредственно проверяется, что игра Γ_P является квазиинформацион-

ным расширением игры Γ. Некоторые простые следствия этого факта будут

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

W и P : V → W справедливы неравенства Rκ (Γ) ≤ Rκ (Γ_P) ≤ Rκ (Γ₂). Кроме

³ Поскольку по определению V = VP , здесь и далее вместо vP и VP будем писать v и V

соответственно. Это сокращает формулы и не должно вызвать недопонимания.

152

того, при “увеличении объема доступной информации” максимальный гаран-

тированный результат первого игрока не убывает. Определение квазиинфор-

мационного расширения и доказательства этих простых фактов можно найти

в [8].

Если считать, что интересы управляемой системы отождествляются с ин-

тересами первого игрока (Центра), то для оценки качества управления систе-

мой довольно естественно использовать величину R_κ (Γ_P ). Попробуем опре-

делить меру сложности управления системой. Для этого придется несколько

уменьшить класс рассматриваемых игр Γ_P . В контексте изложенного в раз-

деле 1 достаточно естественным выглядит следующее п р е д п о л о ж е н и е.

Будем считать, что пространство W наделено топологией, а отобра-

жение P непрерывно.

В таком случае достаточно разумно использовать в качестве меры сложно-

сти процесса управления размерность пространства W⁴. Но здесь требуется

несколько уточнений.

Очевидно, множество W всегда можно снабдить тривиальной топологией,

объявив открытыми пустое множество, само множество W и только их. То-

гда всякое отображение P : V → W будет непрерывным. Соответствующая

задача была, по сути, решена в [16]. Найденное там решение не очень хорошо

интерпретируется. Да и размерность такого топологического пространства

определить непросто⁵. Поэтому нужны дополнительные предположения, ис-

ключающие такого рода тривиальные решения. Из изложенного в данном

абзаце следует, что это должны быть предположения типа отделимости.

В дальнейшем будем считать, что пространство W - нормальное. (Напом-

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

любых двух различных точек x и y найдется открытое множество O, для

которого x ∈ O и y ∈ O, а, во-вторых, для любых непересекающихся замкну-

тых множеств X₁ и X₂ найдутся такие открытые множества O₁ и O₂, что

X₁ ⊂ O₁, X₂ ⊂ O₂ и O₁ ∩ O₂ = ∅.)

Для простоты сделаем еще одно техническое предположение. Будем рас-

сматривать только пространства W, имеющие счетную базу. От этого пред-

положения можно было бы отказаться, но это потребовало бы более тонких

топологических рассуждений, что выходит за рамки данной статьи. Данное

предположение будет использоваться только при доказательстве необходи-

мых условий в разделе 5.

Содержательная интерпретация более общих пространств в контексте за-

дачи об агрегировании информации вызывает определенные затруднения.

Поэтому, не имея в том конкретной нужды, рассматривать их не станем.

⁴ Переходя на неформальный уровень, можно мыслить так. Центр в процессе игры ΓP

получает некоторое “сообщение” о положении точки w ∈ W . Можно предполагать, что ему

сообщаются “координаты” точки w. И чем меньше этих координат, тем лучше. А количество

координат - это уже “размерность”.

⁵ Формальное определение размерности должно отражать определенные содержатель-

ные представления. Придумать определение, удовлетворяющее этому условию для всех

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

условия типа отделимости.

153

Существует несколько альтернативных определений размерности. Для

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

сти не совпадают. Но такие пространства “устроены” весьма сложно, и их

вряд ли можно рассматривать в качестве “разумных” решений в задачах при-

нятия решений. Поэтому выбор такого определения можно делать достаточно

произвольно. В дальнейшем будет удобно пользоваться определением Чеха-

Лебега. Соответствующая размерность пространства X обозначается через

dim X.

Напомним, что согласно этому определению размерностью пространства

называется наименьшее натуральное число m, для которого в любое конеч-

ное открытое покрытие пространства можно вписать покрытие кратности m.

Несложно показать, что размерность куба [0, 1]^m не превосходит m. Слож-

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

dim [0, 1]^m ≥ m. Следовательно, dim [0, 1]^m = m. Кроме того, размерность яв-

ляется топологическим инвариантом пространства. А поскольку m-мерный

симплекс (выпуклая оболочка m + 1 точек общего положения, расположен-

ных в евклидовом пространстве) гомеоморфен m-мерному кубу, его размер-

ность тоже равна m.

Остановимся на одном обстоятельстве. Пусть ϕ : W → W^′ - гомеомор-

физм. Тогда, с одной стороны, так как ϕ - гомеоморфизм, то dim W = dim W^′.

А с другой стороны, так как ϕ - взаимно однозначное отображение, то ра-

зумно считать, что с помощью отображений P и P^′ передается одна и та же

информация, только по-разному закодированная. Этот факт можно рассмат-

ривать как аргумент в пользу использования размерности в качестве меры

сложности информационного обмена⁶. Заметим кстати, что в таком случае

несложно показать, что игры Γ_P и Γ_P ′ изоморфны в том смысле, что каж-

дая из них является квазиинформационным расширением другой. Поэтому

получим равенство R_κ (Γ_P ) = R_κ (Γ_P ′ ).

Если зафиксировать показатель качества управления системой и количе-

ственную меру сложности информационных обменов, то получим двухкрите-

риальную задачу. С одной стороны, хотелось бы, чтобы качество управления

было повыше. А с другой - чтобы сложность информационных обменов была

поменьше. Если эти показатели задавать так, как сделано выше, то эти две

цели “почти противоположны”: с уменьшением сложности качество всегда не

увеличивается, а часто уменьшается. Поэтому возникает вопрос о свертке

этих двух критериев. Здесь возможны разные варианты.

В данной статье будут получены условия для чисел γ и m, при которых для

заданной игры Γ существуют такие нормальное топологическое пространство

W со счетной базой и непрерывная функция P : V → W , что одновременно

R(Γ_P ) > γ и dimW ≤ m.

Замечание 3. При сформулированных условиях образ

P (V ) = {w ∈ W : ∃v ∈ V w = P (v)}

⁶ Разумеется, первое, что приходит в голову в качестве меры “массивности” множества, -

это его мощность. Но такая мера слишком “груба”: и одномерный отрезок и многомерный

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

интерес). Поэтому нужна более “тонкая” мера.

154

множества V при отображении P - компактное, а значит, замкнутое подмно-

жество пространства W . Следовательно, dim P (V ) ≤ dim W (см. [14], с. 567).

Поэтому, не уменьшая общности, можно считать, что отображение P сюръ-

ективно, а множество W компактно.

Займемся решением поставленной задачи.

3. Альтернативное определение максимального гарантированного результата

Удобнее пользоваться другим определением максимального гарантирован-

ного результата.

Определение 1. Число γ называется гарантированным результатом

первого игрока в игре Γ_P , если существуют стратегия u_P ∈ Φ (W,U) и та-

кое число λ, что выполняются условия:

1^◦. Существует стратегия v ∈ V для которой h(u_P (P(v)),v) ≥ λ;

2^◦. Для любой стратегии v ∈V или g(u_P (P(v)),v)>γ, или h(u_P (P(v)),v)<λ.

Точная верхняя грань R(Γ_P ) гарантированных результатов первого игрока

называется его максимальным гарантированным результатом.

Замечание 4. В предыдущих публикациях [17] использовалось анало-

гичное определение, но там вместо строгого неравенства g (u_P (P (v)) , v) > γ

использовалось нестрогое неравенство g (u_P (P (v)) , v) ≥ γ. Несложно видеть,

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

определением со строгим неравенством.

При сделанных в разделе

предположениях справедливо равенство

R_κ (Γ_P ) = R (Γ_P ). В этом разделе будут установлены некоторые факты, необ-

ходимые для его доказательства.

Введем следующее понятие. Назовем стратегию u_P ∈ U_P регулярной, если

верхняя грань

sup h(u_P (P(v)),v)

v∈V

достигается. Пусть UrP - множество всех регулярных стратегий. Наряду с

игрой Γ_P = 〈U_P , V_P , g_P , h_P 〉 можно рассмотреть игру Γ^rP = 〈U^rP , V_P , g_P , h_P 〉

(здесь сужения функций g_P и h_P на множество U^rP обозначены теми же

символами). Для игры Γ^rP можно определить величины R_κ (Γ^rP ) и R (Γ^rP ) ,

практически дословно повторяя определения этих величин для игры Γ_P . Из

включения U^rP ⊂ U_P непосредственно следуют неравенства R_κ (Γ^rP ) ≤ R_κ (Γ_P )

и R(Γ^rP) ≤ R(Γ_P).

Установим следующие вспомогательные факты.

Лемма 1. Имеет место неравенство Rκ (Γ_P) ≤ R(Γ_P).

Лемма 2. Справедливо равенство Rκ (Γ^rP) = R(Γ^rP).

Лемма 3. Выполняется равенство R(Γ^rP) = R(Γ_P).

Доказательства лемм 1-3 приведены в Приложении.

Из этих лемм немедленно следует равенство R_κ (Γ) = R (Γ), которое будет

использовано в дальнейшем.

155

4. Достаточные условия существования агрегата

В этом и следующем разделах будем заниматься вопросом о том, при ка-

ких условиях, связывающих числа γ и m, существуют пространство W и

отображение P : V → W , для которых R (Γ_P ) > γ и dim W ≤ m.

Простейшее из таких условий может быть сформулировано следующим

образом.

Теорема 1. Пусть числа γ и m таковы, что существуют такие управ-

ления u₀, u₁, . . . , u_n из множества U и число λ, что множества

(1)

O_i = {v ∈ V : g (u_i

,v) > γ}, i = 0,1,... ,k,

(2)

O_i = {v ∈ V : h(u_i

,v) < λ} , i = k + 1,... ,n,

покрывают множество V и кратность покрытия O₀,O₁,... ,O_n не превос-

ходит m + 1, а множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ}.

Тогда существуют нормальное пространство W со счетной базой и непре-

рывное отображение P : V → W , для которых R (Γ_P ) > γ и dim W ≤ m.

Доказательство теоремы 1 см. в Приложении.

Можно сформулировать другое достаточное условие.

Теорема 2. Пусть числа γ и m таковы, что существуют такие управ-

ления u₀, u₁, . . . , u_n из множества U и число λ, что множества

O_i = {v ∈ V : g (u_i,v) > γ} ∪ {v ∈ V : h(u_i,v) < λ} , i = 0,1,... ,n,

покрывают множество V и кратность покрытия O₀,O₁,... ,O_n не превос-

ходит m + 1, а множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ}.

Тогда существуют нормальное пространство W со счетной базой и непре-

рывное отображение P : V → W , для которых R (Γ_P ) > γ и dim W ≤ m.

Доказательство теоремы 2 практически не отличается от доказательства

теоремы 1⁷ и поэтому не приводится.

Достаточные условия теорем 1 и 2, вообще говоря, независимы. Понять

причину несложно. Говоря неформально, множества O_i из теоремы 1 “мень-

ше” соответствующих множеств из теоремы 2. Поэтому для того чтобы по-

крыть множество V, таких множеств потребуется больше. А поэтому крат-

ность такого покрытия может оказаться большой. А с другой стороны,

“большим” множествам из теоремы 2 может оказаться “тесно” в простран-

стве V, и по этой причине покрытие будет иметь большую кратность. Все

зависит от конкретной игры. Соответствующие конкретные примеры строят-

ся без труда.

Можно формулировать и другие подобные достаточные условия. Самым

общим из них является следующее.

⁷ Функции ϕi нужно определить условием ϕi (v) = max {g (ui, v) - γ, λ - h (ui, v) , 0} , а

остальное повторяется практически дословно.

156

Теорема 3. Пусть числа γ и m таковы, что существуют такие управ-

ления u₀, u₁, . . . , u_n из множества U и число λ, что множества

O_i = {v ∈ V : g (u_i,v) > γ} ∪ {v ∈ V : h(u_i,v) < λ} , i = 0,1,... ,n,

покрывают множество V , множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ},

и существуют множества Ω₀,Ω₁,... ,Ω_l и непрерывные функции ϕ₀,ϕ₁,

...,ϕ_l :V → R, удовлетворяющие условиям:

• множества Ω₀,Ω₁,... ,Ω_l покрывают V ;

• покрытие Ω₀,Ω₁,... ,Ω_l вписано в покрытие O₀,O₁,... ,O_n;

• кратность покрытия Ω₀, Ω₁, . . . , Ω_l не превосходит m + 1;

• ϕi (v) > 0 при v ∈ Ω_i и ϕ_i (v) = 0 при v ∈ V \Ω_i (i = 0,1,...,l).

Тогда существуют нормальное пространство W со счетной базой и непре-

рывное отображение P : V → W , для которых R (Γ_P ) > γ и dim W ≤ m.

Доказательство теоремы 3 практически не отличается от доказательства

теоремы 1, поэтому приводить его не будем.

Замечание 5. В данной статье не делается предположений относитель-

но выполнения аксиом отделимости в пространстве V . Есть основания счи-

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

ничительными. Поэтому существование функций ϕ_i приходится отдельно

предусматривать в условии теоремы 3. Теоремы 1 и 2 показывают, что такие

функции могут естественно возникать из теоретико-игровых соображений.

Разумеется, условие существования таких функций выполняется автомати-

чески, если пространство V вполне регулярно. Но условие теоремы 3 слабее

этого предположения.

Разумеется, достаточное условие теоремы 3 менее конструктивно, чем до-

статочные условия теорем 1 и 2. Но оно допускает обращение.

5. Необходимое условие существования агрегата

Справедливо следующее утверждение.

Теорема 4. Пусть числа γ и m таковы, что существуют нормальное

пространство W со счетной базой и непрерывное отображение P : V → W,

для которых R (Γ_P ) > γ и dim W ≤ m. Тогда существуют такие управления

u₀,u₁,... ,u_n из множества U и число λ, что множества

O_i = {v ∈ V : g (u_i,v) > γ}, i = 0,1,... ,k,

O_i = {v ∈ V : h(u_i,v) < λ} , i = k + 1,... ,n,

покрывают множество V , множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ},

и существуют множества Ω₀,Ω₁,... ,Ω_l и непрерывные функции ϕ₀,ϕ₁,

...,ϕ_l :V → R, удовлетворяющие условиям:

157

• множества Ω₀,Ω₁,... ,Ω_l покрывают V ;

• покрытие Ω₀,Ω₁,... ,Ω_l вписано в покрытие O₀,O₁,... ,O_n;

• кратность покрытия Ω₀, Ω₁, . . . , Ω_l не превосходит m + 1;

• ϕi (v) > 0 при v ∈ Ω_i и ϕ_i (v) = 0 при v ∈ V \Ω_i (i = 0,1,...,l).

Доказательство теоремы 4 приведено в Приложении.

Замечание 6. Из результатов теорем 3 и 4 видно, что оптимальное ре-

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

игры: количеством множеств в покрытии и их взаимными пересечениями.

Локальные свойства, например гладкость функций выигрыша или размер-

ность касательного пространства к многообразию V , не существенны (даже

если в конкретной модели они определены). Кроме того, понятно, что ско-

рее всего это решение будет устойчиво по отношению к малым изменениям

параметров игры, в том числе и нарушающим эти локальные свойства.

Как и достаточные условия раздела 3, необходимые условия можно запи-

сывать в различной форме. Удобство той или иной записи зависит от кон-

кретной игры.

6. Структура оптимального решения

При постановке задачи были наложены лишь самые общие ограничения на

структуру множества W и отображения P . Если, скажем, найденное множе-

ство W окажется совсем уж экзотическим, то вряд ли такое решение можно

будет считать осмысленным с точки зрения принятия решений. На самом

деле в этой задаче таких неприятностей не предвидится. Кое-что в этом на-

правлении уже сделано: из доказанных теорем следует, что оптимальное мно-

жество W можно искать в классе компактных подмножество конечномерных

евклидовых пространств. Но и среди таких множеств имеются множества,

устроенные весьма сложно, например как ковер Серпинского. Однако можно

пойти и дальше.

Ранее установлено, что можно выбрать отображение так, что образ P (V )

будет содержаться в некотором симплексе. В этом разделе будет показано,

что отображение P можно выбирать так, что каждая грань этого симплекса

либо входит в P (V ) целиком, либо не пересекается с P (V ), т.е. оптимальное

множество W можно искать в классе симплициальных комплексов.

Для простоты и конкретности будем отталкиваться от достаточных усло-

вий из теоремы 1. В других случаях рассуждения аналогичны.

Пусть O₀, O₁, . . . , O_n и Θ - множества, предусмотренные условием теоре-

мы 1. Фиксируем точку v₀ ∈ O₀ ∩ Θ и такое число γ₀, что γ < γ₀ < g(u₀, v₀).

Пусть Z = {v ∈ V : g (u₀, v) ≥ γ₀}. По построению v₀ ∈ Z ⊂ O₀, а в силу непре-

рывности функции g множество Z замкнуто. Для i = 1, . . . , n положим

O^′i = O_i\Z.

Множества O_i′ открыты. Совокупность множеств O₀, O_1′, . . . , O_n′ по-

прежнему покрывает пространство V, и кратность этого покрытия не превос-

ходит m + 1. А кроме того, точка v₀ покрывается лишь одним множеством O₀

(и не принадлежит множествам O_1′, . . . , O_n′).

158

Отображение P определим так же, как в доказательстве теоремы 1, но

с использованием покрытия O₀, O_1′, . . . , O_n′ вместо покрытия O₀, O₁, . . . , O_n:

функции ϕ_i определим условиями:

ϕ₀ (v) = max{g (u₀,v) - γ,0} ,

ϕi (v) = max {min [g (ui, v) - γ, γ0 - g (u0, v)] , 0} , i = 1, . . . , k,

ϕi(v) = max {min [λ - h (ui, v) , γ0 - g (u0, v)] , 0} , i = k + 1, . . . , n,

а все остальное повторим дословно. Получим отображение множества V в

симплекс S. Но в данном случае можно быть уверенными в том, что верши-

на a₀ симплекса S принадлежит P (V ), в частности, P (v₀) = a₀. Дословно по-

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

новому отображению P игре Γ_P можно построить стратегию, гарантирую-

щую первому игроку получение выигрыша γ. Фиксируем построенную таким

образом стратегию u_P .

Будем последовательно упрощать множество W = P (V ), используя сле-

дующую процедуру. Выберем грань S₀ симплекса S, относительная внутрен-

ность которой пересекается с W , но содержит и точку a, не принадлежа-

щую W (если такой грани нет, то все уже доказано). Пусть π - проекция

симплекса S₀ на его границу из точки a, т.е. π (a^′) - это (единственная) точ-

ка пересечения луча aa^′ с границей симплекса S₀. Отображение π оставляет

неподвижными все точки, не принадлежащие внутренности симплекса S₀, в

частности точку a₀, если она является его вершиной. Пусть

{ π(P (v)), если P (v) ∈ W ∩ S

Q (v) =

P (v) , если P (v) ∈ W \S₀.

По построению отображение Q : V → S непрерывно и Q (V ) ⊂ P (V ).

Пусть u_Q - сужение функции u_P с множества P (V ) на множество Q (V ).

Непосредственно проверяется, что стратегия u_Q гарантирует первому игро-

ку в игре Γ_Q получение результата γ (практически дословно проходят соот-

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

P (v₀) = Q (v₀)).

При повторении такой процедуры число граней, которые пересекаются с

множеством P (V ), но не содержатся в нем целиком, будет уменьшаться. А по-

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

искомое множество W и отображение P .

Хорошо известно, что всякий симплициальный комплекс размерности m

может быть вложен в евклидово пространство размерности 2m + 1. Таким

образом, достаточные условия, полученные в разделе 3, одновременно дают

и достаточные условия для задачи, рассмотренной в [11] (об этой постановке

говорилось в разделе 1). Впрочем, в [12] построен пример игры, в которой

“оптимальное” множество W представляет собой три ребра тетраэдра, вы-

ходящие из одной вершины. Такое множество одномерно, но не может быть

вложено в одномерное евклидово пространство. Таким образом, задача из [11]

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

159

Несколько слов об отображении P . При его построении в теореме 1 исполь-

зовались функции выигрыша в игре Γ. Понятно, что если эти функции “слож-

ные”, то сложным будет и отображение P . И это принципиально. С другой

стороны, использованные выше рассуждения показывают, что если функции

g и h “простые”, то среди решений рассматриваемой задачи найдутся такие,

у которых отображение P не намного сложнее. Понятию “сложности” в дан-

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

способами, но это уводит слишком далеко от темы данной статьи. Поэтому

ограничимся сделанными неформальными замечаниями.

7. Вычисления

Полученные необходимое и достаточные условия записаны в немного

нетрадиционной форме. Поэтому имеет смысл обсудить вопрос о том, на-

сколько они конструктивны.

В теории иерархических игр задача считается решенной, если ее удается

свести к вычислению максиминов на “простых” множествах. В рассматривае-

мой задаче эти множества должны фигурировать в описании игры Γ (в иг-

ре Γ_P появляется уже гораздо более сложное функциональное пространство

U_P = Φ (W,U)). Разумеется, так понимаемое решение в общем случае дале-

ко от получения конкретных численных результатов. Но и их полезность во

многих случаях отрицать нельзя. Поэтому будем следовать традиции.

Покажем, как полученные результаты можно переписать в более традици-

онной форме. Для конкретности вновь обратимся к результатам теоремы 1.

Определим функцию

{

1, если x > 0,

ϑ (x) =

0, если x ≤ 0.

Множества O_i, определенные условиями (1) и (2), покрывают простран-

ство V тогда и только тогда, когда

{

}

minmax max

[g (u_i, v) - γ] , max

[λ - h (u_i, v)]

> 0,

v∈V

i=1,...,k

i=k+1,...,n

или, что то же самое,

{

}

minmax max

[ϑ (g (u_i, v) - γ)] , max

[ϑ (λ - h (u_i, v))]

> 0.

v∈V

i=1,...,k

i=k+1,...,n

Аналогично кратность рассматриваемого покрытия не превосходит m + 1,

если

{

}

∑

max

ϑ (g (u_i, v) - γ) +

ϑ (λ - h (u_i, v))

≤ m + 1,

v∈V

i=0

i=k+1

или

{

}

∑

min m + 2 - ϑ (g (u_i, v) - γ) -

ϑ (λ - h (u_i, v))

> 0.

v∈V

i=0

i=k+1

160

Наконец, множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ}

тогда и только тогда, когда

maxmin {ϑ (g (u0, v) - γ) , 1 - ϑ (λ - h (u0, v))} > 0.

v∈V

Все три условия выполняются в том и только том случае, когда

{

}

min minmax max

[ϑ (g (u_i, v) - γ)] , max

[ϑ (λ - h (u_i, v))]

v∈V

i=1,...,k

i=k+1,...,n

{

}

∑

min m + 2 - ϑ (g (u_i, v) - γ) -

ϑ(λ - h(u_i,v))

v∈V

i=0

i=k+1

}

maxmin {ϑ (g (u0, v) - γ) , 1 - ϑ (λ - h (u0, v))}

> 0.

v∈V

А поскольку числа k и n и управления u_i можно выбирать, достаточное

условие из теоремы 1 записывается в виде

{

maxmax

max

min minmax max

[ϑ (g (u_i, v) - γ)] ,

k≥0

n≥k

(u₀,u₁,...,un)∈Uⁿ⁺¹

v∈V

i=1,...,k

}

max

[ϑ (λ - h (u_i, v))]

i=k+1,...,n

{

}

∑

min m + 2 - ϑ (g (u_i, v) - γ) -

ϑ (λ - h (u_i, v))

v∈V

i=0

i=k+1

}

maxmin {ϑ (g (u0, v) - γ) , 1 - ϑ (λ - h (u0, v))}

> 0.

v∈V

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

теоремы 2 и другие похожие утверждения. Теоремы 3 и 4, разумеется, менее

конструктивны. Понятно, что их нельзя сделать конструктивными, не имея

конструктивного способа описания топологии на пространстве V . Если такой

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

использованным в этом разделе, применимы. Соответствующие конструкции

сложнее, поэтому приводить их не станем.

8. Заключение

Итак, в данной статье приведена сбалансированная постановка топологи-

ческой задачи синтеза рациональных способов агрегирования информации.

161

Предложен метод ее решения. И постановка, и метод решения оказались

достаточно простыми. Кроме того, было показано, что среди оптимальных

решений задачи непременно найдутся способы агрегирования информации,

вполне разумные с содержательной точки зрения. Это дает основание гово-

рить о целесообразности продолжения изучения подобных моделей. Такие

исследования представляются особенно актуальными в связи с появлением

технологий работы с “большими данными”. Остановимся на некоторых воз-

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

В теоремах 1 и 2 свойства топологии на множестве V практически не ис-

пользуются. В теореме 3 эти свойства используются уже существенно. В [12]

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

зования свойств топологии, заданной на множестве V, нельзя. В этой связи

возникает следующий вопрос. Кроме заданной внешним образом топологии

на множестве V, можно определить на нем внутреннюю топологию - тополо-

гию, базу которой образуют прообразы открытых множеств действительной

прямой R при отображениях g и h (при всех фиксированных u). Интересно

более детально разобраться, каким образом соотношение между внутренней

и внешней топологиями влияет на характер оптимальных способов агрегиро-

вания информации и сложность их построения.

В контексте моделирования процессов обмена информацией проще интер-

претировать не топологическую размерность Чеха-Лебега, а какие-то вари-

анты фрактальных размерностей, скажем, размерность Минковского. Речь

идет о следующем.

Можно мыслить размерность линейного пространства или гладкого много-

образия как количество координат, достаточное для определения положения

отдельной точки. Эти представления как-то формализуются определениями

топологической размерности, в частности размерности Чеха-Лебега. И ровно

такие идеи были заложены, например, в публикациях [6, 11]. Но есть и неко-

торые возражения: координата это действительное число, которое задается

бесконечной десятичной дробью. Но чтобы задать такую дробь, уже нужен

“бесконечный объем” информации. Не исключено, что в каких-то случаях

соответствующие конструкции будут неадекватно описывать реальность.

Возможен иной взгляд на вещи, в известном смысле идущий из теории ин-

формации. Будем рассматривать количество сообщений, достаточное, чтобы

с заданной точностью задать положение любой точки множества. Разуме-

ется, это количество существенно зависит от заданной точности. А вот ско-

рость роста этого количества при увеличении точности вполне характеризует

размерность множества⁸. Таким образом, приходим к понятию фрактальной

размерности. Но в этом случае нужна количественная мера близости точек,

т.е. топология должна быть заменена, например, метрикой.

Поэтому рассмотрение постановки задачи с заменой размерности Чеха-

Лебега фрактальной размерностью вполне оправдано. Видимо, решающий

шаг в решении соответствующей задачи сделан в данной статье. Действи-

⁸ Чтобы с точностью ε задать положение точки на единичном отрезке, потребуется

порядка 1/ε сообщений, а чтобы с той же точностью задать положение точки единичного

трехмерного куба, нужно уже около 1/ε³ сообщений.

162

тельно, в общем случае фрактальная размерность не является целым числом,

но для “хороших” множеств оказывается целой и совпадает с топологической

размерностью. Более того, если для какого-то “экзотического” множества (на-

пример, канторова совершенного множества) эти размерности не совпадают,

то фрактальная размерность больше. Поэтому полученные в данной статье

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

и обосновать этот ответ.

В данной статье удалось обойтись самыми простыми техническими сред-

ствами. Было бы интересно понять, что может дать современная топологи-

ческая техника для исследования подобных моделей.

ПРИЛОЖЕНИЕ

Доказательство леммы 1. Пусть γ - произвольное число, строго

меньшее R_κ (Γ_P ). Тогда найдется стратегия u_P , для которой

γ < inf g (u_P (P (v)),v).

v∈BR(u_P )

Фиксируем любую такую стратегию и положим λ = maxh(uP (P (v)),v), если

v∈V

выбранная стратегия регулярна, и λ = sup h (u_P (P (v)) , v) - κ в противном

v∈V

случае.

При таком выборе γ, u_P и λ первый пункт определения 1 выполняется

(достаточно взять произвольное v из непустого множества BR (u_P )). В силу

условия γ < inf g (u_P (P (v)) , v) для v ∈ BR (u_P ) справедливо неравен-

v∈BR(u_P )

ство γ < g (u_P (P (v)) , v), а в силу выбора λ для v ∈ BR (u_P ) имеет место

неравенство h (u_P (P (v)) , v) < λ. Следовательно, и второй пункт определе-

ния 1 выполняется.

Таким образом, γ - это гарантированный результат первого игрока в смыс-

ле определения 1. В силу произвольности γ отсюда следует нужное неравен-

ство R_κ (Γ_P ) ≤ R (Γ_P ). Лемма 1 доказана.

Доказательство леммы 2. Неравенство Rκ (Γ^rP) ≤ R(Γ^rP) доказыва-

ется практически так же, как и неравенство из леммы 1. Докажем обратное

неравенство R_κ (Γ^rP ) ≥ R (Γ^rP ).

Пусть γ - произвольный гарантированный результат в смысле опре-

деления

1. Фиксируем стратегию u_P и число λ, существование ко-

торых предусмотрено этим определением. Для стратегии v из перво-

го пункта этого определения λ ≤ h (u_P (P (v)) , v) ≤ maxh (uP (P (v)) , v),

v∈V

т.е. λ ≤ maxh(uP (P (v)),v). Но тогда для любого v ∈ BR(uP ) выпол-

v∈V

няется неравенство h (u_P (P (v)) , v) ≥ λ и в силу второго пункта опре-

деления

имеет место неравенство g (u_P (P (v)) , v) > γ. Следовательно,

inf

g (u_P (P (v)),v) ≥ γ и тем более

v∈BR(u_P )

R_κ (Γ^rP ) = sup

inf

g (u_P (P (v)) , v) ≥ γ.

u_P ∈U^rP

v∈BR(u_P )

163

В силу произвольности γ отсюда следует нужное неравенство R_κ (Γ^rP ) ≥

≥ R(Γ^rP).

Лемма 2 доказана.

Доказательство леммы

3. Достаточно доказать, что R (Γ^rP ) ≥

≥ R(Γ_P). Сделаем это.

Для каждого w ∈ W множество P^-1 (w) = {v ∈ V : P (v) = w} компактно.

Поэтому максимум max h (u, v) достигается при всех u ∈ U и w ∈ W . Обо-

v∈P^-1(w)

значим f (u, w) = max h (u, v).

v∈P^-1(w)

Точечно-множественное отображение P^-1(w) замкнуто, т.е. замкнут его

график

{(w, v) ∈ W × V : w = P (v)} .

Следовательно, при любом фиксированном u ∈ U функция f (u, w) полу-

непрерывна сверху на множестве W , т.е. ее подграфик

Δ(u) = {(w,t) ∈ W × R : t ≤ f (u,w)}

замкнут.

Но тогда замкнуто и пересечение таких множеств

{

}

⋂

Δ₀ = Δ (u) = (w,t) ∈ W × R : t ≤ inf f (u,w)

u∈U

Следовательно, в некоторой точке u^pP (w) достигается минимум min f (u, w)

u∈U

и, кроме того, функция φ (w) = min f (u, w) полунепрерывна сверху на мно-

u∈U

жестве W (так как Δ₀ - ее подграфик).

Таким образом, корректно определена стратегия наказания u^pP и она яв-

ляется регулярной, т.е. достигается максимум

(

)

λ₀ = maxh

u^pP (P (v)) ,v

= maxmin

max h (u, v) .

v∈V

w∈W

u∈U

v∈P^-1(w)

Пусть теперь γ - произвольный гарантированный результат в игре Γ_P в

смысле определения 1. Фиксируем стратегию u_P и число λ, существование

которых предусмотрено этим определением.

Поскольку по построению

(

)

(

)

λ₀ = min

maxh

u_P′ (P (v)),v

= maxh

u^pP (P (v)),v

u_P′∈U_P

v∈V

(

)

найдется управление v, для которого h (u_P (P (v)) , v) ≥ h

u^pP (P (v)),v

≥λ₀.

Поэтому, не ограничивая общности, можно считать, что λ ≥ λ₀. В самом деле,

второй пункт определения 1 выполнить тем легче, чем больше λ; а первый

пункт при λ = λ₀ выполняется в силу только что установленного неравенства.

164

В силу выбора u_P и λ существует v, для которого h (u_P (P (v)) , v) ≥ λ.

Если для всех v выполняется условие h (u_P (P (v)) , v) ≤ λ, то стратегия u_P

является регулярной: максимум maxh(uP (P (v)),v) достигается и равен λ.

v∈V

В таком случае лемма 3 доказана.

В противном случае существует точка v₀, в которой h (u_P (P (v₀)) , v₀) > λ.

Положим w₀ = P (v₀) и рассмотрим стратегию u^rP , определенную условием

{ uP (w0) , если w = w0,

u^rP (w) =

u^pP (w) , в противном случае.

Стратегия u^rP является регулярной. Действительно, выберем v₁, достав-

ляющее максимум max h (P (w₀) , v). Тогда для v ∈ P^-1 (w₀) имеем

v∈P^-1(w₀)

h(u^rP (P (v)) ,v) = h(u_P (P (v)) ,v) ≤ h(u_P (P (v₁)),v₁) = h(u^rP (P (v₁)) ,v₁) .

А для v ∈ P^-1 (w₀) получим

(

)

h(u^rP (P (v)) ,v) = h

u^pP (P (v)),v

≤λ₀ <

< h(u_P (P (v₀)),v₀) ≤ h(u_P (P (v₁)),v₁) = h(u^rP (P (v₁)),v₁).

Таким образом, верхняя грань sup h (u^rP (P (v)) , v) достигается, например, в

v∈V

точке v₁.

Покажем, что для стратегии u^rP и числа λ₁ = h (u^rP (P (v₁)) , v₁) выпол-

няются оба пункта определения 1. По определению числа λ₁ выполняется

первый пункт и, кроме того, λ₁ ≥ λ и λ₁ > λ₀.

Если v ∈ P^-1 (w₀) и h (u^rP (P (v)) , v) = h (u^rP (P (v₁)) , v₁), то

h(u^rP (P (v)),v) = h(u_P (P (v)),v) ≥ λ

и в силу второго пункта определения 1 (для стратегии u_P и числа λ) по-

лучим g (u^rP (P (v)) , v) = g (u_P (P (v)) , v) > γ и в этом случае второй пункт

определения 1 выполнен.

Если v ∈ P^-1(w₀), но h(u^rP (P (v)), v) = h(u^rP (P (v₁)), v₁), то по определению

числа λ₁ и управления v₁ имеем h(u^rP (P (v)), v) < h(u^rP (P (v₁)), v₁) = λ₁ и сно-

ва второй пункт определения 1 выполнен.

(

)

Наконец, если v ∈ P^-1 (w₀), то h (u^rP (P (v)) , v) = h

u^pP (P (v)),v

≤λ₀ <λ

и опять второй пункт определения 1 выполнен.

Таким образом, стратегия u^rP позволяет первому игроку гарантированно

получить выигрыш γ. В силу произвольности γ отсюда следует неравенство

R(Γ^rP ) ≥ R (Γ_P ).

Лемма 3 доказана полностью.

Доказательство теоремы 1. Определим функции

ϕi (v) = max {g (ui, v) - γ, 0} , i = 0, 1, . . . , k,

ϕi(v) = max {λ - h (ui, v) , 0} , i = k + 1, . . . , n,

∑

φ(v) =

ϕi (v) .

i=1

165

Очевидно, эти функции непрерывны и неотрицательны, а поскольку мно-

жества O₀, O₁, . . . , O_n покрывают пространство V , функция φ (v) строго по-

ложительна в любой точке v.

Выберем в n-мерном евклидовом пространстве n-мерный симплекс S.

Пусть a₀, a₁, . . . , a_n - его вершины. Рассмотрим отображение P : V → S, опре-

деленное условием

∑

ϕi(v)

P (v) =

a_i.

φ(v)

i=0

Отображение P является непрерывным.

Пусть I ⊂{0, 1, . . . , n}. Если для любого j ∈ I выполняется условие v ∈ O_j , то

точка P (v) принадлежит грани симплекса S с множеством вершин {a_i, i ∈ I}.

Так как по условию кратность покрытия O₀, O₁, . . . , O_n не превосходит m + 1,

образ P (v) любой точки v принадлежит грани симплекса S, которая имеет

не более m + 1 вершин и, следовательно, размерность, не превосходящую m.

Пусть W - образ множества V при отображении P . Множество W ком-

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

симплекса S. Следовательно, размерность множества W не превосходит m.

Евклидово пространство нормально и имеет счетную базу. Эти свойства на-

следует и его подпространство W .

Таким образом, определена некоторая игра Γ_P . Построим стратегию u_P

в этой игре следующим образом. Пусть w ∈ W и S₀ - наименьшая по вклю-

чению грань симплекса S, содержащая w (разумеется, если размерность S₀

больше нуля, то w принадлежит внутренности S₀). Пусть {a_i, i ∈ I} - множе-

ство вершин этой грани. Выберем наименьшее i ∈ I и положим u_P (w) = u_i.

Покажем, что выполняются оба пункта определения 1.

По построению отображения P для любого v ∈ O₀ наименьшая грань, со-

держащая точку P (v), имеет a₀ своей вершиной. Следовательно, по определе-

нию стратегии u_P выполняется равенство u_P (P (v)) = u₀. А поскольку O₀ ∩

∩Θ = ∅, для некоторой точки v ∈ O₀ имеем h(u_P (P (v)),v) = h(u₀,v) ≥ λ.

Таким образом, первый пункт определения 1 выполнен.

Пусть теперь v - произвольная точка множества V , а I - множество всех

индексов i, для которых выполняется условие v ∈ O_i. Поскольку множества

O₀,O₁,... ,O_n покрывают V , множество I не пусто. Тогда по построению

отображения P множество вершин наименьшей грани симплекса S, содержа-

щей точку P (v), есть в точности множество {a_i, i ∈ I}. Тогда по определению

функции u_P для некоторого i ∈ I выполняется равенство u_P (P (v)) = u_i. Ес-

ли i ≤ k, то g (u_P (P (v)) , v) = g (u_i, v) > γ (так как v ∈ O_i). А в противном

случае h (u_P (P (v)) , v) = h (u_i, v) < λ. Следовательно, и второй пункт опре-

деления 1 выполнен.

Итак, по определению γ - гарантированный результат в игре Γ_P . Теорема 1

доказана.

Доказательство теоремы 4. В силу неравенства R (ΓP ) > γ чис-

ло γ является гарантированным результатом в игре Γ_P . Фиксируем стра-

тегию u_P и число λ, существование которых постулируется в определе-

166

нии 1. Выберем управление v0, для которого справедливо неравенство

h (u_P (P (v₀)) , v₀) ≥ λ (такое существует в силу первого пункта определе-

ния 1). Положим u₀ = u_P (P (v₀)) и

O₀ (u) = {v ∈ V : g (u₀,v) > γ} .

Множество O₀ не пусто, поскольку в силу второго пункта определения 1

g (u_P (P (v₀)) ,v₀) = g (u₀,v₀) > γ, т.е. v₀ ∈ O₀. Кроме того, по определению

множество O₀ пересекается с множеством

Θ = {v ∈ V : h(u₀,v) ≥ λ}.

Для u ∈ U определим множество

O^′ (u) = {v ∈ V : g (u,v) > γ} ∪ {v ∈ V : h(u,v) < λ} .

Множество O^′ (u) открыто. Поэтому его дополнение Y (u) = V \O^′ (u) за-

мкнуто и, следовательно, компактно. Тогда компактно множество Y^′ (u) =

= P (Y (u)) ⊂ W. Значит, множество Y ′ (u) замкнуто, а его дополнение

O^′′ (u) = W\Y^′ (u) - открытое множество, возможно пустое.

Но если u = u_P (P (v)) для некоторого v ∈ V , то в силу второго пункта

определения 1 выполняется включение P (v) ∈ O^′′ (u_P (P (v))), т.е. соответ-

ствующее множество O^′′ (u) не пусто.

Как отмечалось выше, можно считать, что функция P отображает множе-

ство V на все множество W . В таком случае семейство открытых множеств

O^′′ (u_P (P (v))) , v ∈ V , покрывает компактное пространство W. Значит, из

этого семейства можно выбрать конечное покрытие пространства W . Обо-

значим множества этого покрытия через O_1′′, . . . , O_n′′, а соответствующие им

управления - через u₁, . . . , u_n. Пусть

O_i = {v ∈ V : g (u_i,v) > γ} ∪ {v ∈ V : h(u_i,v) < λ} , i = 1,... ,n.

По построению множества O₀, O₁, . . . , O_n (и даже множества O₁, . . . , O_n)

покрывают V . А кроме того, для любого множества Ω^′ ⊂ O_i′′ его полный

прообраз P^-1 (Ω^′) принадлежит O_i.

Но по условию пространство W имеет размерность m. Значит, в покрытие

O_1′′,... ,O_n′′ можно вписать покрытие Ω_0′′,Ω_1′′,... ,Ω_l′′, кратность которого

не превосходит m + 1. Тогда множества Ω₀ = P^-1 (Ω_0′′), Ω₁ = P^-1 (Ω_1′′) ,

...,Ω_l = P-1 (Ω_l′′) образуют покрытие множества V , вписанное в покрытие

O₀,O₁,... ,O_n и имеющее кратность, не превосходящую m + 1.

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

Поэтому для каждого i можно определить функцию ψ_i : W → R так, что

ψ_i (w) > 0 при w ∈ Ω_i′′ и ψ_i (w) = 0 в противном случае (см. [14, с. 82]). Тогда

для функций ψ_i ◦ P имеем ϕ_i (v) > 0 при v ∈ O_i и ϕ_i (v) = 0 для остальных v.

Теорема 4 доказана.

167

СПИСОК ЛИТЕРАТУРЫ

Von Stackelberg H. Market Structure and Equilibrium. Berlin, Heidelberg: Springer-

Verlag, 2011.

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

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

Bolton P., Dewatripont M. Contract Theory. Cambridge: The MIT Press, 2004.

Алиев В.С., Цветков А.В. Игра двух лиц с фиксированной последовательно-

стью ходов при агрегированной информации // Планирование, оценка деятель-

ности и стимулирование в активных системах. М.: ИПУ, 1985. С. 35-42.

Алиев В.С. Точное агрегирование информации в многошаговых играх двух лиц

с фиксированной последовательностью ходов при агрегированной информации

о выборе партнера // Управление большими системами. Вып. 24. М.: ИПУ РАН,

2009. С. 5-17.

Новиков Д.А., Цветков А.В. Агрегирование информации в моделях стимулиро-

вания // АиТ. 2001. № 4. С. 120-127.

Novikov D.A., Tsvetkov A.V. Aggregation of Information in Incentive Models //

Autom. Remote Control. 2001. V. 62. No. 4. P. 617-623.

Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: МГУ, 1984.

Горелов М.А. Максимальный гарантированный результат при ограниченном

объеме передаваемой информации // АиТ. 2011. № 3. С. 124-144.

Gorelov M.A. Maximal Guaranteed Result for Limited Volume of Transmitted In-

formation // Autom. Remote Control. 2011. V. 72. No. 3. P. 580-599.

10.

Рашевский П.К. О догмате натурального ряда // Успехи математических наук,

1973. Т. 28. Вып. 4 (172). С. 243-246.

11.

Алиев В.С., Кононенко А.Ф. Точное агрегирование в теоретико-игровых моде-

лях. М.: ВЦ РАН, 1990.

12.

Горелов М.А. Непрерывные информационные агрегаты в антагонистических иг-

рах // Динамика неоднородных систем. М.: Книжный дом “ЛИБРОКОМ”, 2008.

С. 41-57.

13.

Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального

анализа. М.: Наука, 1981.

14.

Энгелькинг Р. Общая топология. М.: Мир, 1986.

15.

Александров П.С., Пасынков Б.А. Введение в теорию размерности. М.: Наука,

1973.

16.

Горелов М.А. Теоретико-множественная постановка задачи синтеза рациональ-

ных процедур обмена информацией в иерархической игре двух лиц // Журн.

вычисл. матем. и матем. физ. 2003. Т. 43. № 3. С. 376-387.

17.

Горелов М.А. Максимальный гарантированный результат в иерархических иг-

рах // Управление большими системами. Вып. 67. М.: ИПУ РАН, 2017. С. 4-31.

Статья представлена к публикации членом редколлегии Ф.Т. Алескеровым.

Поступила в редакцию 05.05.2020

После доработки 24.08.2020

Принята к публикации 10.09.2020

168