Об одной аксиоматизации обобщенного расширения Оуэна

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 83 ББК 22. 18
ОБ ОДНОЙ АКСИОМАТИЗАЦИИ ОБОБЩЕННОГО РАСШИРЕНИЯ ОУЭНА 1 2
Васильев В. А. 3 ,
(Учреждение Российской академии наук Институт математики им. С. Л. Соболева СО РАН, Новосибирск)
Предлагается новый подход к построению обобщенного расширения Оуэна, базирующийся на идеях неаддитивного интегрирования. Большое внимание уделяется вопросам аксиоматической характеризации этого обобщенного расширения как для дискретных, так и для неатомических игр. Основные результаты работы показывают, что для широких классов кооперативных игр исчерпывающее описание рассматриваемого расширения может быть получено с использованием известной аксиоматизации Аумана-Шепли, разработанной для характеризации мультипликативного продолжения неатомических игр на «идеальные» коалиции.
Ключевые слова: регулярная полиномиальная игра, обобщенное расширение Оуэна, неатомическая кооперативная игра, мультипликативное продолжение Аумана-Шепли.
Введение
В статье дается описание нового подхода к построению обобщенного расширения Оуэна для некоторых классов так называе-
1 Работа поддержана грантами РФФИ№ 07−06−363, РГНФ № 0906−337 и грантом Президента Р Ф №НШ 4113. 2008.6.
2 Текст приводится в соответствии с изданием «Математическая теория игр и ее приложения. — 2009. — Т. 1. № 2″.
3 Валерий Александрович Васильев, доктор физико-математических наук, профессор, (vasilev@math. nsc. ru).
мых регулярных полиномиальных кооперативных игр. Этот подход основан на использовании неаддитивного интегрирования, объединяющего и конкретизирующего идеи-интегрируемости, предложенные в [2, 5, 6]. Помимо построения и анализа ряда конструкций продолжения, связанных с неаддитивным интегрированием, большое внимание уделяется различным аспектам аксиоматизации свойств отображения, сопоставляющего играм их обобщенные расширения Оуэна. В частности, один из главных результатов работы показывает, что в качестве искомой аксиоматизации для некоторых классов неатомических кооперативных игр можно использовать аксиоматизацию Аумана-Шепли [1], предназначенную для описания мультипликативного продолжения неатомических игр, необходимого для бесконечномерного обобщения известной интегральной формулы Оуэна [1, 4]. Как одно из важных следствий указанного результата получена явная формула для мультипликативного продолжения Аумана-Шепли, представляющая интерес как для численного отыскания вектора Шепли неатомических кооперативных игр, так и для теоретического анализа полярных форм этих игр [5, 6]. Что касается дискретных кооперативных игр, то для этого класса найдена аксиоматизация классического расширения Оуэна, отличающаяся от аксиоматизации Аумана-Шепли лишь ослабленным вариантом аксиомы мультипликативности (необходимо подчеркнуть, что эта аксиома не выполняется в полном объеме ни для дискретных, ни для смешанных игр). Именно, в отличие от неатомического случая, расширение Оуэна произведения двух дискретных игр равно произведению расширений сомножителей только при условии дизъ-юнктности минимальных носителей этих игр.
Полученные результаты могут найти применение в анализе так называемых полярных форм неатомических кооперативных игр и их использовании для представления вектора Шепли (подробности, касающиеся полярных форм, см. в [5, 6]).
1. Регулярные полиномиальные игры
Ниже дается описание основного класса игр, используемого в главных конструкциях работы (и, прежде всего, в явном определении мультипликативного продолжения Аумана-Шепли).
Пусть, й) — произвольный непустой метрический компакт с метрикой й. Обозначим через В борелевскую ст-алгебру этого компакта и рассмотрим совокупность V фунций множества v: В ^ И, удовлетворяющих требоанию -и (0) = 0. Согласно теоретико-игровой терминологии [1] тройку Г = (^, В^) с V из
V называют кооперативной игрой (с побочными платежами), элементы множества Q — игроками, а подмножества е С Q, принадлежащие алгебре В — коалициями игроков. Напомним, что значение v (e) интерпретируется как максимальный гарантированный доход коалиции е. В дальнейшем, как это принято в теоретикоигровой литературе, кооперативными играми будем называть и сами функции V.
Детальное описание интересующего нас класса полиномиальных кооперативных игр требует введения некоторых вспомогательных понятий и обозначений (большинство из них, включая используемые понятия теории векторных решеток, можно найти в [5, 6]- там же указан ряд полезных ссылок на литературу по смежной тематике). Пусть е — произвольный элемент алгебры В. Обозначим через Н (е) совокупность конечных В-измеримых разбиений е и положим Н = иеевН (е). Далее, для каждого разбиения П = |ег}геп € Н, состоящего из Ш элементов (|П| = т), и для функции V € V через v (n) = v ({ei}ieп) обозначим полиномиальную т-разность, определяемую формулой
(1) ^П) := ^(-1)|п|-М ^
шСП
где, как обычно, символ |ш| обозначает число элементов конечного множества ш. Полиномиальная вариация |Н|0 функции v € V
7
определяется формулой
М|о := яир{^ ^(п^)| П = {е. }геп € Н^)}
шС П
где пш := {е. }геш, а v (nш) определена согласно формуле (1). Говорят, что функция v € V имеет ограниченную полиномиальную
вариацию, если |Н|о & lt- то. Положим V := ^ € V |^||о & lt- то} и определим конус положительных элементов векторного пространства V, наделяющий его структурой векторной решетки. Напомним [2, 5, 6], что игра v € V называется вполне положительной, если v (n) ^ 0 для любого разбиения п = {ег}™ из € Н. В качестве вышеупомянутого конуса положительных элементов в дальнейшем рассматривается выпуклый конус вполне положительных игр. Обозначим этот конус через Р+. Ясно, что все элементы конуса V+ имеют ограниченную полиномиальную вариацию. Кроме того, как показано в [5], частичный порядок и v и — v € К+, индуцируемый V+ (вместе с нормой полиномиальной вариации || ¦ ||о), наделяет V структурой банахова векторного кольца. Более подробно [5]: V является банаховой и дедекиндово полной векторной решеткой, с согласованными структурами упорядоченного и нормированного пространства (монотонная порядковая сходимость влечет монотонную сходимость по норме).
Следуя стандартным обозначениям теории векторных решеток, для каждой игры v € V введем в рассмотрение положительную (у+), отрицательную ^-) и полную (^|) вариацию этой игры, полагая v+ := v V 0, v- := (-и) V 0 и ^| := (-и) V v, соответственно (здесь через и V ад = 8ир{и, ад} и и Л ад = т?{и, ад} обозначаются точная верхняя и нижняя грани двухэлементного множества {и, v} в полуупорядоченном векторном пространстве (V, ^о)). Обозначим через ^ совокупность всех непустых замкнутых подмножеств метрического компакта Q. Укажем типичный класс игр, фигурирующих в дальнейших рассмотрениях.
8
Определение 1. Игра v € V называется регулярной, если
Ш
II
ее полная вариация ^| удовлетворяет условию: М ({ег}т) =
8Ир{Н ({/г}™) /. С е., /г €, г = 1,…, т} для любого
разбиения п = {ег}™ € Н.
Совокупность регулярных игр обозначим через ^ ^(В).
Определение 2. Игра v € ^ называется регулярной полиномиальной игрой порядка и, если все ее полиномиальные разности порядка и + 1 обращаются в 0: v ({eг}n+1) = 0 для каждого разбиения {ег}П+1 € Н.
Обозначим через пространство всех регулярных полиномиальных игр порядка и и положим rpV = и^=1^га. Будем говорить, что игра v является регулярной полиномиальной игрой, если v принадлежит.
2. Неаддитивное интегрирование и обобщенное расширение Оуэна
Для описания интегрирования по полиномиальной неаддитивной функции множества из зафиксируем некоторое натуральное число и ^ 1 и функцию v € г^. Первое, что потребуется для характеризации искомого интегрирования — построить продолжение v на и-тую симметрическую степень Валгебры В. С этой целью нам понадобится определение и-той симметрической степени е[п] коалиции е € В, задаваемое формулой:
еИ = {т С е |т| ^ и}, где, как и ранее, через |т| обозначается число элементов конечного множества т.
Определение 3. Симметрической степенью порядка и алгебры В называется наименьшая алгебра подмножеств множества Q^"'-], содержащая семейство симметрических степеней
{еМ е € В} всех элементов алгебры В.
На основании описания строения алгебры В[М, предложенного в [5], установлено, что существует единственная аддитивная функция множества Л^: В^ И, удовлетворяющая условию: ь (е[М) = v (e) для каждого е € В. Более того, учитывая регулярность v и компактность метрического пространства, й), с помощью стандартной аргументации можно доказать, что имеется единственное счетно-аддитивное продолжение ^ функции Ль на наименьшую ст-алгебру стВ, содержащую алгебру В^ (другими словами, аддитивная функция Ль: ВМ ^ И допускает единственное счетно-аддитивное продолжение: стВ[М ^ И на ст-алгебру стВ, порожденную алгеброй В). Интересно отметить, что ст-алгебра стВимеет достаточно простое описание в традиционных терминах теории меры.
Предложение 1. Алгебра стВ[М совпадает с борелевской ст-
алгеброй метрического пространства ^[га], й^), где есть сужение стандартной метрики Хаусдорфа на Q["'-^: й[М (т, т'-): =
ш1п {е т С т'-, т'- С те}, где те, т'- - е-окрестности т, т'- в пространстве, й).
Пусть теперь / - произвольный элемент векторного пространства I^, В) ограниченных и В-измеримых функций, определенных на Q. Введем полиномиальное продолжение /|™] функ/ на Qw, определяемое формулой
ции г на
4"'-(т): =П/(г), т € „М.
Нетрудно проверить, что полиномиальное продолжение каждой функции / € I^, В) является стВ-измеримой ограниченной функцией, определенной на множестве Q[ra^ (другими словами, для каждой функции / € I^, В) ее полиномиальное продолжение /|™] принадлежит пространству I (Q[n],
стВН) ограниченных
стВ М -измеримых функций, определенных на Q[n1. Следовательно, для любой функции / € I^, В) ее продолжение /|™] является-интегрируемой функцией. Но это означает, в частности, что для каждого v € функционал Р“: I^, В) ^ И, задаваемый формулой
(2) РV (/): =У /П1^, / € I^, В),
определен корректно.
Используя введенные обозначения и конструкции, сформулируем одно из главных понятий статьи.
Определение 4. Для каждого v €п функционал Р^, определяемый формулой (2), называется обобщенным расширением Оуэна кооперативной игры v.
Нетрудно проверить, что в случае конечного множества Q введенное понятие обобщенного расширения Оуэна совпадает с классическим определением полилинейного продолжения кооперативной игры, предложенным Оуэном в [4]. Что касается бесконечного случая, то здесь мы отметим лишь некоторые характерные свойства обобщенного расширения Оуэна, показывающие, что и в случае бесконечного числа игроков выполняются аналоги ряда ключевых соотношений, типичных для конечных кооперативных игр. Для формулировки соответствующего результата потребуются некоторые дополнительные определения.
Определение 5. Будем говорить, что функция v € является однородной порядка и, если она дизъюнктна с пространствомга-1 (т. е. выполняется соотношение: ^| Л |и| = 0 для всех и € ^п-1). Совокупность однородных порядка и регулярных полиномиальных функций обозначим через ^(п) (V0 =
V (0) := {0}).
Предложение 2. Для всех и ^ 1 пространства ^(п) являются полосами пространства гК
Отметим сразу же, что согласно Предложению 2, для каждой функции v € rpV и для каждого натурального т ^ 1 существует проекция V (m) на ^(т), определяемая формулой
(3) v (m) := sup {u Є rV (m) v+0 u}-sup {u Є rV (m) v0 u}.
Переходя к описанию некоторых важных для дальнейшего свойств обобщенного расширения Оуэна, напомним, что ниже через хе обозначается индикаторная функция множества e G B, через р (n)
— совокупность однородных порядка n непрерывных полиномиальных функционалов на I (Q, B) (с обычной нормой
||/||те := sup { |f (t)| t G Q} на пространстве I (Q, B)), а через
P+ - совокупность непрерывных полиномиальных функционалов l на I (Q, B), удовлетворяющих неравенствам:
? (-l)"-Ml (? /і) & gt- О
шС{1,…, то} іЄш
для любых m ^ 1 и / G I (Q, B), i = 1,…, m.
Теорема 1. Для любой игры v G обобщенное расширение Оуэна Pv является непрерывным полиномиальным функционалом порядка n на нормированном пространстве (I (Q, B), || ¦ ||S). При этом выполняются следующие соотношения:
(P. 1) Pv (xe) = v (e) для любой коалиции e G B-
(P. 2) Pv G P+, если v G rV+ := П V±
(рз) Pv G P (n), если v G
ГУ (П) —
(P. 4) |Pv (/)| ^ Em=1 II/||S ¦ ||V (m)||o для любой функции / G I (Q, B)
(здесь V (m) — однородные компоненты игры v, определяемые формулой (3)).
3. Аксиоматизация расширения Оуэна: неатомический случай
Напомним сначала аксиоматизацию мультипликативного продолжения для неатомических кооперативных игр, предложенную в [1] в связи с необходимостью обобщения известной интегральной формулы Оуэна на случай бесконечного множества игроков. Для простоты ограничимся случаем пространства ртЖА, представляющего из себя замыкание в рассматривавшейся выше норме полиномиальной вариации || ¦ ||0 линейной оболочки всевозможных степеней, к ^ 1, неатомических мер. Как и в [1], будем рассматривать случай, когда Q = [0,1], а В — борелевская ст-алгебра единичного интервала [0,1]. Продолжение & lt-р Аумана-Шепли игры V на пространство I^, В) определяется неявным образом с помощью указания свойств оператора ^& gt-, сопоставляющего каждой игре V € риЖА ее расширение & lt-^^): I^, В) ^ И (с класса индикаторных функций на векторное пространство всех ограниченных В-измеримых функций на Q):
^адЛ) & lt-^)(%е) = v (e), V € риЖА, е € В-
(Оад. 2) ^& gt-(ои + в^) = а^& gt-^) + в^(^), а, в € И, v, w € р^А-
(Оад. 3) ¦ ад) = ^& gt-^) ¦ ^& gt-(ад), и, ад € pvNA-
(Оад. 4) & lt-^)(/) = / /^, / € I (Q, В), V € г1.
В заключение этого пункта сформулируем один из главных результатов работы — аксиоматическое описание обобщенного расширения Оуэна Ру на пространстве pvNA.
Теорема 2. Отображение & lt-р: pvNA ^ Р удовлетворяет условиям (Оад. 1) — (Оад. 4) тогда и только тогда, когда выполняются соотношения
& lt-^^) = Ру, V € риЖА.
4. Аксиоматизация расширения Оуэна: конечные игры
В заключение остановимся на особенностях аксиоматизации расширения Оуэна для случая, когда компакт Q конечен (и, тем самым, все определенные на нем регулярные кооперативные игры заведомо дискретные, атомические). Итак, пусть ^| = п для некоторого натурального п. Не уменьшая общности, будем считать, что Q = {1,…, п}, а алгебра В представляет из себя семейство 2^ - совокупность всех непустых подмножеств множества Q (элементы алгебры 2^, как это принято в теории конечных кооперативных игр, будем обозначать большими латинскими буквами: ?, Т,…). Рассмотрим произвольную кооперативную игру п лиц V: В ^ И и напомним [1], что ее (классическим) полилинейным расширением Оуэна называется отображение РП: I™ ^ И, определенное на единичном кубе I™ := №ъ …, ?п) € И+|^ ^ 1, г € Q} формулой
(4)
РУЖ^…^ := ^ v (T) ^ ^ ^ (1-(*1,… ,*п) €п.
Т еВ геТ ^едт
В дальнейшем для удобства анализа вместо Р» будем рассматривать отображение Р": Ип ^ И, определяемое уже на всем пространстве Ип по формуле, задаваемой правой частью соотношения (4). Собирая в этой формуле коэффициенты при мономах Пгет, получаем следующее представление для отображения Р":
РЛ^Ъ …, ^п) = ^ Vт ^г, (^1,.. ,?") € Ип,
Тев гет
где vт — так называемые дивиденды Харшаньи [3] игры V, определяемые как коэффициенты разложения V =тев vтит функции V по стандартному базису {ит}тев векторного пространства 14
V" = грУ (В). Напомним, что игра ит определяется соотношениями: ит (5) = 1, когда Т С 5, и ит (5) = 0 в остальных случаях. Отметим еще, что в рассматриваемом дискретном случае пространство V™ состоит из всех функций V: В м И, удовлетворяющих единственному условию v (0) = 0.
Как показывает элементарная проверка, отображение V м Р", V € V", удовлетворяет всем требованиям Оад.1 — О-ш. 4, за исключением условия О-ш.3. Оказывается, что в рассматриваемом конечномерном случае мультипликативность отображения
V м РП гарантируется лишь при дизъюнктности так называемых минимальных носителей сомножителей. Напомним, что коалиция К С Q называется носителем игры V, если выполняются соотношения:
(5) v (T П К) = v (T) для каждой коалиции Т € В.
Совокупность всех носителей игры V будем обозначать через 5ирр V. Непосредственно из соотношения (5) вытекает, что 5ирр V = 0, и при этом общая часть Qv = Р|Де5ирр у К всех элементов семейства 5ирр V также принадлежит этому семейству. Тем самым, Qv является наименьшим (относительно вложения) элементом семейства 5ирр V, чем и объясняется вводимая терминология: множество Qv будем называть наименьшим носителем игры V. Отметим, что в ряде случаев удобнее более конструктивное задание наименьшего носителя Qv, определяемое формулой
Qv = {г € Q| существует Т € Вг такое, что vт = 0},
где, как обычно, Вг := {Т € В |г € Т}.
Используя обозначения, максимально приближенных к стандартным, сформулируем аналоги условий (0'^1)-(0'^4) для случая игр с конечным (фиксированным) числом участников (далее V™ := гУ (Q) — совокупность всех кооперативных игр п лиц с побочными платежами на алгебре В, %т — индикаторная функция множества Т С Q, а Рп — пространство полиномов, заданных на п-мерном арифметическом пространстве Ип):
^^. 1) ^(^(хт) = v (T), V € V™, Т € В-
(Ow". 2) ^& gt-«(av+ew) = a^& gt-„(v) + e^"(w), а, в e R, v, w e
V" —
(Ow“. 3) ^& gt-„(v ¦ w) = ^& gt-(v)“ ¦n (w), если Qu П Qw = 0-
(Ow». 4)n (v)(ti,.., tn) = EieQ v (i)ti, (ti,…, t") e
Rn, v e Vi.
Выше, как обычно, v (i) := v ({i}), a V" - подпространство аддитивных (несущественных) игр из пространства V".
В приведенных обозначениях аналог теоремы 4.1 формулируется следующим образом.
Теорема 3. Отображение ^ Pn удовлетворяет
условиям Own. 1-Own.4 тогда и только тогда, когда оно определяется формулой:
& lt-^n (v) = P" для каждой игры v e. Литература
1. АУМАН Р., ШЕПЛИ Л. Значения для неатомических игр.
— М.: Мир, 1977.
2. ВАСИЛЬЕВ В. А. Общая характеристика полиномиальных функций множества // Оптимизация. — 1974. — № 14. -С. 103−123.
3. HARSANYI J. A. A bargaining model for cooperative n-person games // Contributions to the Theory of Games IV (eds. A. W. Tucker, and R. D. Luce). — 1959. — C. 325−355.
4. OWEN G. Multilinear extensions of games // Journal of Management Sciences. — 1972. — V. 18., № 5. — P. 64−79.
5. VASIL’EV V.A. The Shapley functional and the polar form of homogeneous polynomial games // Siberian Advances in Mathematics. — 1998. — V. 8. — № 4. — P. 109−150.
6. VASIL’EV V.A. Polar forms, p-values, and the core // Approximation, Optimisation and Mathematical Economics (ed. M, Lassonde). Heidelberg-New York: Physica-Verlag. -2001. — P. 357−368.
7. VASIL’EV V.A. Cores and generalized NM-solutions for some classes of cooperative games // Russian Contributions to Game Theory and Equilibrium Theory (eds. T. Driessen, G. van der Laan, V. Vasil’ev, and E. Yanovskaya), Berlin-Heidelberg-New York: Springer-Verlag. — 2006. — P. 91−150.
AN AXIOMATIZATION OF GENERALIZED OWEN EXTENSION
Valeri Vasil’ev, Sobolev Institute of Mathematics, Siberian Branch of RAS, Novosibirsk, Doctor of Science, professor (vasilev@math. nsc. ru).
Abstract: To introduce a generalized Owen extension we propose a new approach based on the nonadditive integration. Besides, we pay strong attention to the axiomatization problem for the extension introduced. One of the main results of the paper demonstrates that the axiomatization in question can be chosen similar to that elaborated by R. J. Aumann and L. S. Shapley for the multiplicative extension of nonatomic cooperative games.
Keywords: regular polynomial game, generalized Owen extension, nonatomic cooperative game, Aumann-Shapley multiplicative extension.

ПоказатьСвернуть
Заполнить форму текущей работой