Аксиоматический метод в теории кооперативных игр тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

/

^ российская академия наук

центральный экономико-математическии институт

На правах рукописи

ПЕЧЕРСКИЙ Сергей Львович

аксиоматический метод в теории кооперативных игр

Специальность 01.01.09 - Математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1998 год

Диссертация выполнена в Санкт-Петербургском экономико-математическом институте Российской Академии Наук

Официальные оппоненты: - доктор физико-математических

наук, профессор Л.А.Петросян

доктор физико-математических, наук, профессор В.В.Розен

доктор физико-математических наук, В.И.Данилов

Ведущая организация - Вычислительный центр РАН

Защита состоится « /¿С и,'/?/У1998 г. в ч/^» часов на заседании Специализированного совета Д.002.27.02 в Центральном экономико-математическом институте РАН по адресу: 117418, г. Москва, Нахимовский пр. 47, ЦЭМИ РАН.

С диссертацией можно ознакомиться в библиотеке ЦЭМИ РАН.

/

Автореферат разослан « М.. » 1998 г.

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

В.А.Скоков

Общая характеристика работы

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

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

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

Как инструмент экономического анализа теория игр: 1) дает ясный и точный язык исследования различных экономических ситуаций; 2) предоставляет возможность подвергать интуитивные представления проверке на логическую согласованность; 3) помогает проследить путь от "наблюдений" до основополагающих предположений и обнаружить, какие из предположений действительно лежат в основе частных выводов.

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

Однако это деление ни в коем случае не следует рассматривать как взаимоисключающее: кооперативный и бескоалиционный подходы - это два взгляда на одну и ту же проблему. Бескоалиционная теория стратегически ориентирована. Она изучает то, что, как мы ожидаем, будут делать игроки в игре. Кооперативная теория, с другой стороны, изучает исходы, которые мы ожидаем. При кооперативном подходе мы смотрим непосредственно на пространство исходов, а не на способ, каким они были достигнуты. Бескоалиционная теория - это своего рода микротеория, включающая детальное описание того, что происходит. В кооперативной теории нас интересуют возможные (допустимые) исходы: принимается во внимание все, что игроки могут получить, даже если у них нет соответствующих побудительных мотивов. И в этом смысле кооперативную теорию можно трактовать как макротеорию.

Формально, в достаточно общей форме, кооперативная игра описывается с помощью задания множества участников (игроков), множества тех исходов (альтернатив), которые они способны обеспечить, вступая в различные коалиции, которые могут быть образованы участниками игры, и множества отношений предпочтений игроков на множестве исходов (альтернатив). Под решением кооперативной игры понимается некоторый исход, или некоторое множество исходов, доступных для игроков.

Основы классической кооперативной теории были заложены Дж.фон Нейманом и О.Моргенштерном, а затем развивались в различных направлениях многими авторами, работы которых сыграли решающую роль в становлении теории кооперативных игр. Теория кооперативных игр связана с именами Р.Аумана, Л.Биллера, Т.Ишииши, Э.Калаи, Р.Майерсона, Э.Мас-Колелла, М.Машлера, Э.Мулена, Дж.Нэша, Ж.-П.Обена, Г.Оуэна, Б.Пелега, ХПетерса, И.Розенмюллера, Э.Рота, Х.Скарфа, В.Томсона, С.Харта, Дж.Харшаньи, Л.Шепли, Д.Шмайдлера, М.Шубика. Значительный вклад в развитие теории кооперативных игр внесли О.Н.Бондарева, В.АВасильев, Э.И.Вилкас, В.Б.Вилков, Н.Н.Воробьев, В.И.Данилов, Г.Н.Дюбин, Т.Е.Кулаковская, И.С.Меньшиков, О.Р.Меньшикова, В.В.Морозов, Н.И.Наумова, Л.АЛетросян, А.И.Соболев, А.И.Сотсков, С.В.Чистяков, Е.Б.Яновская и другие.

Развитие теории игр как математической дисциплины шло параллельно с расширением сфер ее приложений: развитие математического аппарата открывало возможности новых приложений, в свою очередь стремление к более адекватному отражению и пониманию экономических реалий приводило к необходимости развития теории игр. Многочисленность экономических приложений кооперативных игр во многом связана с недостаточностью использования лишь рыночных механизмов для принятия общественно значимых решений. (Простейшим примером здесь может служить производство публичных благ). Чтобы компенсировать недостатки рыночных механизмов,

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

Аксиоматический метод занимает центральное место в теории кооперативных игр. Причем именно в последние несколько лет наблюдается стремительное разрастание "поля приложений" аксиоматического метода, существенно расширяется многообразие классов новых моделей, для которых он оказывается мощным инструментом исследований. Суть аксиоматического метода можно кратко описать следующим образом: выбирается набор свойств (аксиом), которым должно удовлетворять решение в данном классе кооперативных игр (или, скажем, в данном классе рассматриваемых задач принятия решения), а затем выделяется то решение или решения, которые удовлетворяют этим свойствам. Если такого решения не существует, то какие-то аксиомы отбрасываются, и вопрос существования решается для меньшего набора аксиом.

Если же мы уже имеем некоторое нормативное решение, которое по каким-либо соображениям, мы считаем удачным, то его аксиоматическое обоснование сводится к отысканию такого набора разумных свойств, которые определяют это нормативное решение. Проблемы теоретического обоснования нормативных положений впервые были подробно изучены А.Сеном.

Спектр экономических приложений теории кооперативных игр в настоящее время огромен и постоянно расширяется. Классические результаты о совпадении равновесия, ядра и значения в больших экономиках, о связи ядра экономики обмена с с-ядром соответствующей игры рынка давно уже занимают существенное место в экономической теории. К важнейшим приложениям относятся задачи распределения затрат, задачи, связанные с проблемами банкротства и налогообложения, распределения прибыли, ценообразования, экономические модели справедливого распределения, теория фирмы, производство публичных благ и многое другое. (Кроме того, скажем, теоретико-игровой подход к изучению формирования коалиций - это уже своего рода традиция в социальных и политических науках).

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

Цель работы. Основная цель работы состоит в построении, в рамках аксиоматического метода, единого подхода к исследованию решений кооперативных игр, опирающегося на использование свойств линейности, суперлинейности и их модификаций. Это исследование включает: разработку новых систем аксиом для

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

Научная новизна и практическая значимость работы. Основные результаты и их новизна состоят в следующем.

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

2. В рамках аксиоматического метода построен единый подход к определению решений кооперативных игр, основанный на использовании свойств линейности, суперлинейности и их модификаций.

3. Исследовано семейство аксиоматик, определяющих нелинейные многозначные аналоги значения Шелли. Доказаны теоремы существования и единственности соответствующих решений. Исследованы вопросы существования селекторов введенных многозначных решений. Полученное семейство решений содержит в качестве специальных частных случаев значение Шепли .(без априорного предположения об однозначности решения), с-ядро, сс -ядро. "Предельный" вариант рассмотренной системы аксиом определяет пред-^-ядро, селектором которого является пред-/7-ядро. Определены и исследованы "антирешения" кооперативных игр, ориентированные на приложения к задачам распределения затрат.

4. Исследованы новые системы аксиом, определяющие с-ядро как суперлинейное решение для классических кооперативных игр и для нечетких кооперативных игр. Изучены различные модификации этих систем аксиом. Доказаны теоремы существования и единственности соответствующих решений. Введено понятие квазиядра и изучены его свойства.

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

ядро, а во втором - нечеткое антиядро. В гладком случае многозначное решение превращается в однозначное и совпадает с модифицированным значением Шепли.

6. Исследован аксиоматический подход к определению функции эксцесса в играх без побочных платежей (НТП-играх). Доказано существование и единственность (с точностью до аффинного преобразования) соответствующего "квазилинейного" эксцесса, названного калибровочным эксцессом. Исследованы свойства ¿-ядра, пред-£-ядра, п-ядра, и пред- п-ядра, соответствующих данному эксцессу. Для игр без побочных платежей построена геометрическая процедура определения п-ядра (пред-и-ядра), основанная на использовании свойств введенного эксцесса и модифицирующая для случая НТП-игр известное геометрическое построение Машлера-Пелега-Шепли для классических кооперативных игр. Введен и исследован "опорный эксцесс" для игр без побочных платежей, а также соответствующие этому эксцессу решения. Определено и исследовано Л-трансферабельное пред-и-ядро и я-ядро для игр без побочных платежей.

7. Введен новый класс многошаговых суперлииейных НТП-игр. Для таких игр определено решение и исследованы свойства этого решения, основанного на свойстве динамической Парето оптимальности, восходящем к моделям экономической динамики.

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

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

Апробация работы. Основные результаты данной работы докладывались на различных семинарах Института социально экономических проблем АН СССР, Санкт-Петербургского экономико-математического института РАН, Центрального экономико-математического института РАН, Санкт-Петербургского государственного университета, Института математики и кибернетики АН Литовской ССР, на всесоюзных конференциях и семинарах (Ереван - 1982, Цахкадзор - 1983, Кутаиси - 1990), совместном советско-польском семинаре (Варшава - 1987), на международной конференции "Теория игр и экономика" (Санкт-Петербург - 1996), на III, IV, VII и VIII международных конференциях по теории игр в Университете штата Нью-Йорк (Стони Брук - 1992, 1993, 1996, 1997).

Публикации. По теме диссертации опубликовано 18 работ, в том числе монография.

Структура и объем работы. Диссертация состоит из введения, шести глав и списка литературы (общий объем - 259 страниц).

Содержание работы.

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

Первый параграф первой главы посвящен анализу роли теории игр в современной экономической теории, сопоставлению двух составляющих теории игр - теории бескоалиционных игр и теории кооперативных игр, обсуждению аксиоматического метода как основного метода исследования кооперативных игр и обсуждению того места теории кооперативных игр, которое она занимает в современном экономическом моделировании. В этом же параграфе приведен ряд моделей, формализуемых с помощью кооперативных игр. В § 1.2 приведены необходимые определения из теории кооперативных игр, В § 1.3 главы I обсуждается роль свойств линейности, суперлинейности и их модификаций в теории кооперативных игр, определяются цели исследования, раскрывается научная новизна работы и формулируются основные результаты. В § 1.4 приводится краткое изложение содержания диссертации (по параграфам).

Вторая глава посвящена исследованию нелинейных многозначных аналогов значения Шепли. В первом параграфе вводятся основные определения и формулируется основная система аксиом.

Классической кооперативной игрой или кооперативной игрой с побочными

платежами называется пара Г= (I, у), состоящая щ конечного множества I = {1,2.....п } и

вещественной функции V: 2 1 —> И, определенной на множестве всех подмножеств множества 1 . Элементы множества I называются игроками, подмножества Б с I -коалициями, а сама функция v - характеристической функцией игры Г. Число \(8), м(0) = О интерпретируется как тот максимальный суммарный выигрыш игроков из который они могут обеспечить себе, действуя совместно. При этом отыскание оптимальных действий игроков из Д, которые обеспечивают им это выигрыш, лежит вне данной модели. Здесь предполагается, что полезности игроков обладают свойством трансферабельности, то есть измеряются по одной шкале и могут передаваться от одного игрока другому без потерь и без ограничений (побочные платежи). В таком случае игрокам из каждой коалиции важно максимизировать суммарный выигрыш, гак как в дальнейшем они могут распределять его между собой произвольным образом.

Пусть И' обозначает I/ I -мерное эвклидово пространство, координаты которого заиндексированы элементами из множества I. Часто бывает удобно рассматривать вектор хеК как игру, определенную формулой х(Б) = £,езХ, для всех 5 сг/.

Далее = { хеП" : х, = 0 для /¿5 }, 5сг/.

Если С - некоторый класс кооперативных игр (вообще говоря, не обязательно с побочными платежами), то под решением на С мы понимаем отображение Т7 (однозначное,

или, быть может, многозначное), которое ставит в соответствие каждой игре гей некоторый вектор или непустое множество Р(у) в пространстве И', которое называется решением или значением (в случае однозначности) игры v. Разумеется, отображение F должно обладать некоторыми определенными свойствами, чтобы "иметь право" называться решением. Компонента^ вектора Г(\>) (в случае однозначности решения) или компонентам х, вектора хеР(\>) можно давать различные интерпретации. Так например, можно считать, что есть априорная оценка игроком / выгодности для него игры V . Можно считать .Р/у) в некотором смысле средним выигрышем игрока в игре. Можно также интерпретировать Р/у) как "справедливую" долю игрока / в игре V . Выбирая ту или иную интерпретацию и формализуя интуитивные представления о тех свойствах, которыми должно обладать решение, то есть вводя те или иные аксиомы, можно получать различные отображения . Аксиоматическим подходом к исследованию решений классических кооперативных игр посвящены работы М.Машлера, Э.Мулена, Г.Оуэна, Б.Пелега, А.И.Соболева, С.Харга, Л.Шепли, Е.Б.Яновской и других.

Еудем через Г обозначать множество игроков в игре V .

Определение 2.1. Решение - это многозначное отображение К' \>—>Р(\~) сИ! такое, что Множество Р(с) называется решением игры V.

Далее пусть V ну' - две произвольные игры с множествами игроков Г и Г соответственно. Отображение т: Г ->Т называется изоморфизмом игр V и у' , если (1) х-взаимно однозначное отображение; (2) V'(гБ) - для любой Лг/' . В этом случае игры V и V' называются изоморфными.

Если х: Г —>■ Г - изоморфизм игр V и V', то г*:Я' - > К'" обозначает отображение, определенное формулой х*х-{хл).для любого х е Я1 .

Определим для любой вещественно-значной функции р и любой кооперативной игры V игру (¡¡V следующим образом: (<р»)(1) = (<р\>)(0) = 0, (<р\>)(8) = <р(у(8)), £ 0.

Определение 2.2. р-суммой и © V игр и и V называется множество игр м/ таких,

<р

что

>1 (I) = 9 и = + фУ)

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

А1 (анонимность). Если х сГ(V) и г-изоморфизм игр V и V", то т*х ер(V').

А2 (симметричность). Если V® =/(! ¿1) и \'(1) = 0 , то О е .

АЗ (болвана). Пусть игры v и у' таковы, что I" = I, Г = I иг0, /„ 01, и и(8) = = Т>(3 и и) , V . Тогда xi =0 для любого хе¥(\') и Рг^,/•"()•)=.Р(и) ,

где Ргд, А означает проекцию множества А на ~в!.

А4 (эффективность). Если xerF(v) , то х(Т) = v(I) . AS (ковариантность). Пусть а е и две игры v и v' таковы, что

v' = v + а . Тогда F(v') - F(v) + а. A6(tp) (tp-замкнутость множества нулевых игр). Если О е F(u) , О eF(v) и w ей® v , то О eFfw) .

Аксиома Аб(<р) зависит от функции <р, и мы получаем целое семейство систем аксиом, причем каждая система, возможно, определяет некоторое свое решение F.

Во втором параграфе исследованы некоторые свойства решения, удовлетворяющего приведенной системе аксиом. В частности доказана

Теорема 2.1. Если функция р линейна и отображение F удовлетворяет аксиомам AI • Аб(<р), то F однозначно для любой игры v и совпадает со значением Шепли, то есть F = Ф, где Ф- значение Шепли, определяемое формулой

SjiS

где s = 15| - число игроков в коалиции S.

Таким образом, доказано, что в случае линейности функции <р решение, удовлетворяющее рассматриваемой системе аксиом, существует и совпадает со значением Шепли без априорного предположения об однозначности решения.

Важное для доказательства теоремы существования и единственности решения свойство доказано в теореме 2.2. Определим для любой игры v числа q,(v) следующим образом

«00= 5>-l)l(B-s-l)!p(v(S)), (1)

где <r = I ¿1, к = |Г|.

Теорема 2.2. Предположим, что <р - такая непрерывная, неубывающая функция,

что

т = inf <p(t)<<p (0) < sup <р (t) ~ Ы,

IEB

(причем числа - т и М могут равняться + оо ). Если F удовлетворяет аксиомам А1 -А6(р) и О е F(v), то

Ф) = Ф) (2)

для любых ij el.

Эта теорема справедлива и для невозрастающией функции (р. Кроме того, из (2) следует, что если О е F(v) и функция (р удовлетворяет условиям теоремы 2.2, то Ф (<pv)= О.

В § 2.3 определено решение, удовлетворяющее предложенной системе аксиом. Пусть v - игра, а хе R7. Предположим, что lF : R R - собственная выпуклая функция (то есть для всех х выполнено неравенство Ч*(х) > - х> и хотя бы для одного х выполнено неравенство Ч/(х) < + сс) и рассмотрим функционал

Qrfcv) ^Z(s-l)!(n-s-l)!4'(v(S)-x(S)) , где сумма берется по всем S *1, 0.

Ilycib.Y*Ay - множество пред-дележей в игре v, то есть Х*(\>) = { хе li': x(I) = v(I) }. Определим отображение F9 следующим образом

Fv(v) = Argmiti { Q^x.v) : х е X*(v) }.

Это отображение обладает целым рядом хороших свойств. В частности, множество Fv(v) непусто и выпукло. Если Ч'не является аффинной, то множество F*(v) компактно. Кроме того, справедливо следующее предложение.

Предложение 2.7. Если функция У непрерывно дифференцируема, то отображение Fr удовлетворяет аксиоме <46(4*'), где У - производная функции Ч/.

Достаточно неожиданным, на первый взгляд, может показаться результат теоремы 2.3. Обозначим через epi '!' надграфик функции 'V, то есть epi Ч'r { (t,y) е R2: у £ 4'(t) }.

Теорема 2.3. Отображение F* удовлетворяет аксиоме A3 тогда и только тогда, когда точка (0, Ч/(0)) является крайней точкой надграфика epi ^функции Ч'.

В четвертом параграфе главы II доказано существование и единственность решения, удовлетворяющего рассматриваемой системе аксиом.

Теорема 2.4. Пусть (р - непрерывная неубывающая функция, для которой точка О является точкой роста, то есть в любой окрестности 0 существует такая точка t, что q>(t) * <р(0). Пусть Ч' - некоторая ее первообразная, то есть 4J' = <р. Тогда отображение F'' удовлетворяет аксиомам А1 - A6(q>). Если, кроме того, функция ip удовлетворяет неравенству (1), то Fr является единственным решением, удовлетворяющим этой системе аксиом.

Важный специальный случай дает следующий пример. Пусть seR и (О, i < s, [t-e, t>s.

Рассмотрим отображение Fr, где Ч'' = <р.

Легко видеть, что если г-ядро Cs (v) ифы v непусто, то F*(v) = Сс (v) = { xeX*(v): vfS) - x(S) <e }. Нетрудно также показать, что если v(I) достаточно мало по сравнению с остальными v(S) , то Fv(v) состоит из единственной точки, которая совпадает со значением Шепли.

F^ удовлетворяет предложенной системе аксиом только если е <0. Более того, если е < 0 , то fv - единственное решение, удовлетворяющее этой системе аксиом.

Если ¥(1) = Г , то соответствующее решение - это значение Шепли. В пятом параграфе рассматривается вопрос о существовании селекторов решений. Ответ на вопрос о существовании селекторов рассмотренных выше решений, безусловно, зависит от того, какие требования, кроме обязательного условия f(v) е F(v) , мы наложим на однозначное отображение / . В силу теоремы 2.4, - единственное решение, удовлетворяющее аксиомам AI - A6(q>), поэтому селекторов, удовлетворяющих аксиомам A J -А6(ф), не существует. Поэтому мы несколько модифицируем аксиому А6((р).

Аб '(ср). Существует такая операция Ф на множестве кооперативных игр, что

u@v ей® v и f(u) = f(v) =0 => f(u Ф\) = О.

<р

Иными словами, мы как бы рассматриваем еще и селектор <р-суммы (поскольку <р-сумма, по определению - это некоторое множество игр). Кроме того, так как отображение /однозначно, то аксиомы AI - AS можно упростить. Например, в этом случае А2 следует из А1 и А4.

Теорема 2.5. Пусть <р - непрерывная неубывающая функция на R, для которой точка 0 является точкой роста. Тогда отображение F*, где - <р, допускает селектор, удовлетворяющий аксиомам А1 - А6'(<р).

Соответствующий селектор может быть получен следующим образом: для строго выпуклой функции в на R и положим

/(v) = argmin{0s(x,v):x eF*(v)}-Шестой параграф второй главы посвящен аксиоматическому определению прсд-А-ядра. Рассматриваемая система аксиом представляет собой некоторую модификацию системы аксиом^ 1 - А6(<р), определившей нелинейные многозначные аналога значения Шепли. Аксиомы А2 пА6(<р) заменяются следующими аксиомами.

А2*. Если v(SU)=v(Suj) для любой коалиции S такой, что i.jeS и xeF(v), то

x i xj .

Аб*. Если О е F(v), О eF(v) и \v(S) = max { u(S), v(S) } , то О eF(w) . Далее вводится еще одна аксиома.

А7. Пусть а е R,v'(I) = v(l) и V(S) = v(S) + а для S W, 0. Тогда Ffv') = F(v) . Пред-£-ядром кооперативной игры v называется множество

K*(v) - {re- R;: max (v(S)-x(S)) = max (v(S)-x(S)), i, jel;x(I) =v(I)}.

S:i£S,j3S SjsS.isS

Пред-£>ядро всегда непусто.

Доказано, что отображение К* , ставящее в соответствие каждой кооперативной игре v множество K*(v) , удовлетворяет аксиомам AI, А2* A3 - A3, Аб*, А7. Кроме того, справедлива следующая теорема.

Теорема 2.6. Пусть F удовлетворяет аксиомам АI, А2*, A3 - AS, Аб*, А7 . Тогда F(v) cK*(v) :

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

Пусть Х - произвольное непустое замкнутое множество в R7. Для любого хеХи любой кооперативной игры v определим вектор 9fxJ следующим образом

0(х) = (e(S,,x), e(S2,x),..., е($г„,х)),

где e(S, х) = v(S) - x(S) - стандартный эксгрсс (или функция эксцесса) косагщии Sex классической кооперативной игры v. Величина e(S,x) шггерпретируегся как мера неудовлетворенности коалиции распределением выигрышей, которое предписывается вектором 1". При этом различные эксцессы всех коалиций расположены в убывающем (невозрастающем) порядке. Компоненты вектора в(х) определены и непрерывны. Будем говорить, что в(х) лексикографически меньше чем 0(у), и обозначать это как 6(х) </ет в(у), если существует такое натуральное число q, что в/х)= й.(у) для любого k < q и 9q(x)< 9q(y) .

А-ядром игры v относительно множества X (и данного семейства эксцессов e(S,.J, Saf ), которое мы будем обозначать через N(X,v), называется множество тех векторов из множества X , для которых соответствующие вектора 9 минимальны относительно определенного лексикографического порядка, то есть

N(X,v) = {хеХ: в(х) <!а Щу) для всехуеХ}.

Далее для игры с побочными платежами v будем обозначать через X*(v) множество пред-дележей, то есть

X*(v) = {xeü! :x(IJ = v(I)).

Множество дележей будет обозначаться через X(v), то есть

X(v) = {xeR7 :x(I) = v(I), x,>v(i) для любого iel}.

Если X = X(v), то N(X,v) \= N(v) называется п-ядром игры v. Если X=X*(v) , то N(X,v) := PN(v) sU*(v) называется пред-п-ядром игры v.

Далее в этом параграфе обсуждается интерпретация пред-к-ядра и пред-п-ядра как справедливых схем распределения.

В последнем параграфе главы II рассматриваются простые аналоги иред-А-ядра и пред-л-ядра, которые называются, соответственно, анти-пред-А:-ядром и анти-пред-я-ядром, и естественная область применения которых - задачи распределения затрат. Соответствующая аксиоматика без труда получается из предыдущих результатов за счет замены операции взятия максимума операцией взятия минимума.

Таким образом, полученные в главе II результаты позволяют в рамках единого подхода получить целое семейство нелинейных многозначных решений кооперативных игр, содержащее в качестве специальных частных случаев значение Шепли, г-ядро, пред-£-ядро и пред-и-ядро, а также их модификации.

Третья глава диссертации посвящена изучению с-ядра в классических и нечетких кооперативных играх. С-ядро в классических кооперативных играх, сбалансированность, нечеткие коалиции, нечеткие кооперативные игры и другие связанные с этой проблематикой вопросы исследовались в работах О.Н.Бондаревой, В.А.Васильева, Р.Вебера, В.И.Данилова, Ж.-П.Обена, Б.Пелега, А.И.Сотскова, Л.Шепли и других.

В первом параграфе этой главы подробно обсуждается понятие нечетких коалиций, нечетких кооперативных игр, сбалансированности и канонического представления стандартной (классической) кооперативной игры.

Пусть I — {!,...,п } - конечное множество игроков. Каждую коалицию 5 можно отождествить с ее характеристическим вектором ^ е {1,0}", тоесть

[0,

Мы определяем нечеткую коалицию и нечеткие кооперативные игры, следуя Ж.-П.Обену. Нечеткая коалиция (то есть нечеткое подмножество (в смысле Л.Заде множества I) • это вектор ге[0,1]п. Число г, рассматривается как "степень участия" игрока г в т.

Определение 3.1. Нечеткая кооперативная игра - это положительно однородная функция V: [0,/]° К, которая ставит в соответствие каждой нечеткой коалиции г ее выигрыш У(т).

Как и в стандартном случае, функция Г называется характеристической функцией. Положительная однородность функции V означает, что У(0) = 0 (ср. у(0у=О в случае стандартных кооперативных игр) и У(Лт) = ХУ(т) для Я Последнее предположение позволяет продолжить характеристическую функцию V с единичного куба [0,1]п на , полагая

для 7*0.

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

сильно. Обычно один и тот же индивид может участвовать в нескольких коалициях, организациях, принимать участие в различной деятельности, причем каждая такая коалиция "защищает" его интересы. Однако, если индивид i является участником одновременно двух коалиций, скажем, Si и & , то он не может быть полиостью представлен ho отдельности, ни коалицией Si ни коалицией 5?, поскольку каждая из этих коалиций считает его своим членом. Иными словами, участник не обязан полностью включаться в одну коалицию, а может делить свою активность (и соответственно, получать вознаграждение в виде каких-то результатов деятельности коалиций) между несколькими различными коалициями. С этими соображениями, в частности, связано рассмотрение канонического представления.

Если v - классическая кооперативная игра, то каноническим представлением игры v называется нечеткая кооперативная игра v*: [0,7]" -^R", определяемая формулой

v*(T) - мир { X MSV(S): ps>0, X Mses = r}. s s

Функция v* суперлинейна, и ее супердифференциал ¿fo*(e) в точке е = (1, 1, ... , 1) совпадает с нечетким с-ядром игры v* где нечеткое с-ядро нечеткой игры V- это множество C(V)={xeR! : х]+...+х„ = V(e), xt^V(t) для всех теВ1*}.

Хорошо известно, что С-ядро C(v) (стандартной) кооперативной игры v непусто тогда и только тогда, когда v сбалансирована, то есть v(I) = v*(e). В этом случае C(v) = C(v*).

Пусть v - стандартная игра. Множество A(v) = {xbR7 •: x(S) > v(S), VSc=I) известно как приемлемое множество (множество приемлемых векторов).

Для нечеткой кооперативной игры V приемлемое множество A(V) - это а(v) = { xcfr': xt>v(t), v г е[0,1]" }, при этом нижняя опорная функция р множества A(V) , определяемая равенством

pA(Jr) = inf { (х, т) : xeA(v) } , совпадает с функцией v*. Более тогоРа,у/т) = рлку(т), а следовательно, A(v) = A(v*).

В § 3.2 рассматривается аксиоматика с-ядра и нечеткого с-ядра. Пусть /"множество всех нечетких суперлинейных игр, и пусть я - произвольная перестановка множества I =

{1.....п }. Она индуцирует линейное преобразование л* :R" —» R" по формуле (л*х), = х„,

для любого xeR". Для любой игры V обозначим через лV игру, определенную равенством

Решение на Г ■ это такое многозначное отображение О, которое ставит в соответствие каждой игре УеГ непустое множество Q(V)c R* векторов выигрышей игроков. Введем следующие аксиомы.

А'1 (приемлемость). ()(У) сА(У) для любой игры УеГ.

А '2 (достижимость). Для любого хеО(У) найдется такая нечеткая коалиция г е [0,1]\ г^о, что хт = у(т).

А'З (симметричность). Для любой перестановки ,т множества игроков /

х е 0(1-9 => ж*хе <2(яУ).

А'4 (аддитивность). Для любых двух игр V,УеГ, 0(17+У) = <2(и) + 0(У)-

Нетрудно проверить, что если О удовлетворяет аксиомам А'1 - А'4, то 0(17) Парето оптимально для любой игры УеГ, то есть X; + ... + х„ = У(е) для любого х е 0(У). Справедлива следующая теорема.

Теорема 3.1. 1) Отображение С , ставящее в соответствие каждой нечеткой суперлинейной игре УеГ ее с-ядро С(У), удовлетворяет аксиомам А'1 -А '4.

2) Если О - решение на Г, удовлетворяющее аксиомам А'1 - А'4 , то 0(У) сС(У) для любой игры УеГ, то есть С - максимальное решение, удовлетворяющее системе аксиому!7 - А'4.

3) Существует селектор (] отображения С, удовлетворяющий аксиомам А 7 -А '4.

Указанный селектор q может быть построен следующим образом: (¡(17) = $(С(\0),

где л~(К) обозначает точку Штейнера выпуклого компактного множества К, причем С(У) рассматривается как (п-1)-ъл£рное выпуклое компактное множество. Для произвольного выпуклого компактного множества точка Штейнера множества К определяется по формуле

где X - Лебегова мера на единичной сфере У'1 сК", а,„ - объем единичного шара в Я1", а а - переменный вектор на сфере и р(К,.) - опорная функция множества К.

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

Теорема 3.3. С-ядро является единственным решением на Г, удовлетворяющим аксиомам А 7 -А'З.

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

А '4'(супераддитивность). £>(и+У) => 0(У) + 0(У).

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

А'5. Пусть и,Уе Г, U(e) = У(е) и W(z) = min (U(z), У(т)). Тогда Q(Wj id Q(U) uO(\r).

Теорема 3.4. С-ядро является единственным решением на множестве О всех сбалансированных игр, удовлетворяющим аксиомам приемлемости, достижимости, симметричности, супераддитивности и "тт-аксиоме".

В этом же параграфе рассмотрены различные "вариации" введенных аксиом.

В § 3:3. вводится понятие квазиядра и рассматриваются некоторые его свойства. Хорошо известно, что произвольная классическая кооперативная игра может быть стандартным образом (с использованием простейших игр) представлена в виде разности двух выпуклых кооперативных игр ( то есть таких игр v, что для любых коалиций £ и Т, выполняется неравенство у(БОГ) - > v(S) + у/77). С-ядро любой выпуклой игры

всегда непусто, а потому можно рассмотреть "разность" двух с-ядер соответствующих выпуклых игр, причем под разностью двух множеств понимается разность, введенная В.Ф. Демьяновым.

Разность двух выпуклых компактных множеств в смысле Демьянова определяется следующим образом. Пусть С/ и V - выпуклые компактные множества, а Г - некоторое множество полной меры, в точках которого существуют градиенты Урс{а) и Vр^а) . Рассмотрим множество разностей { Ург/а) - \р,{а) : аеТ } и обозначим его выпуклую замкнутую оболочку через ШУ. Таким образом, по определению

ШУ=со { Чр,/а) -Ур,{а) : аеТ} . Данное определение корректно, то есть ШУ не зависит от выбора множества Т.

Пусть т = у' - V. - стандартное представление V в виде разности двух выпуклых игр.

Определение 3.4. Квазиядром Сд(и) произвольной классической кооперативной игры V называется множество С/\) = ± С(у_).

Из определения следует, что С0(у) - непустое компактное выпуклое множество и £ х, = \'(1) для каждого хе Саб')- Более того, квазиядро определено корректно, то есть С/у) не зависит от представления v в виде разности двух выпуклых функций, то есть если v = v*- v. = = - V. , то С/у) = С(10 Л С(У) = С(у*) 1 С(у.). Если V - выпуклая игра, то С/г) = С(у).

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

В последнем параграфе этой главы рассмотрены приложения антирешений к классической задаче распределения затрат.

В четвертой главе исследуются квазидифференцируемые кооперативные игры и их линейные решения. В § 4.1 рассматривается еще одна интерпретация нечетких кооперативных игр в контексте задач распределения затрат, которая подчеркивает необходимость исследования общих классов кооперативных игр. Далее приводятся

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

Пространство выпуклых компактных множеств определяется следующим образом. Пусть П - класс всех выпуклых компактных множеств в К1. Рассмотрим отношение эквивалентности ~, определенное на ОхП следующим образом:

(А,, В,) ~ (А2, Дг) о А,-В2 = А3-В, . Класс эквивалентности, содержащий пару множеств (А, В) обозначается через [А, В]. Линейное пространство (2 выпуклых компактных множеств представляет собой фактор пространство /2хО~, в котором алгебраические операции вводятся следующим образом: [А,, В,] + [А2, В2\ = [А,+А2,В1 + В2] и '[ЯА,ЛВ], л>0,

Я[Л'В] = \1ЯВ,АА], Л<0.

Квазидифференцируемые функции были введены В.Ф.Демьяновым и А.М.Рубиновым. Пусть функция / : S -> R определена на открытом множестве S er R". Функция / называется квазидифференцируемой в точке х £ S , если она дифференцируема в х в каждом направлении g е R" и существуют компактные выпуклые множества df(x) с: R", df{x)czR" такие, что

max(v,g)+ min {w,g) Vg eR".

8g »&№)

Пара выпуклых компактов [ U, V ] , участвующих в определении, определяется не единственным образом. Класс эквивалентных пар Df(x) = \dJ(x),Sf (х)] называется тазидиффгреицшиом функции / в точке х . Множества df (х) и д/(х) называются субдифференциачом и супердиффереициалом функции / в х , соответственно. Каждую пар, принадлежащая этому классу эквивалентности также называется квазидифференциалом.

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

В § 4.2 рассматриваются линейные решения квазидифференцируемых игр. Игра называется квазидифференцируемой, если ее характеристическая функция положительно однородна и квазидифференцируема (в е).

Определение 4.6. Квазирешением игры v называется квазидифференциал D'v(e) характеристической функции v в точке е, обладающий свойством Парето оптимальности: ecmiD"vfe)=[Sv(e),ffv(e)],xeSv(e) и yeßv(e),тоZi(x,+yJ=v(e) .

Существование такого квазидифференциала гарантируется теоремой 4.1. Квазиришение определяется не однозначно, так как квазидифференциал определяется с точностью до отношения эквивалентности (поэтому мы используем термин

"квазирешение"). Квазирешение обладает рядом свойств, оправдывающих введенное определение. А именно:

1. Если характеристическая функция V непрерывно дифференцируема в и, то

= [ О ] , (или [О , 1Л>(е) ] ), где \Л'(е) - градиент V в е , и квазирешение

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

2. Если V вогнута (суперлинейна), то В"у(е) = [0,д\'(е)], где д\'(е) -супердифференциал вогнутой функции v, и квазирешение 0"у(г) можно отождествить с е-ядром игры.

3. Квазирешение линейно по V.

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

Для локально липшицевых игр Ж.-П.Обен определил множество решений как субдифференциал Кларка характеристической функции в е. В этом же параграфе рассмотрено соотношение между квазирешением и субдифференциалом Кларка для игр, являющихся одновременно локально липшицевыми и квазидифференцируемыми. В частности, если характеристическая функция обладает некоторым достаточно необременительным свойством, то 8с{(х) §/{х) -I- (-*?/(*)), причем стоящая в правой части этого включения разность представляет собой аналог квазиядра, рассмотренного в предыдущей главе.

Далее определяется однозначное линейное решение, называемое .«-решением.

Определение 4.8; ^/-решением квазидифференцируемой игры V называется вектор определяемый следующим образом Я(г) = ¡¡(£ у(е)) + ¡(¿>у(е)), где $(К) - точка Штейнера выпуклого компакта К.

Это определение корректно, то есть не зависит от пары, определяющей конкретный квазидифференциал V (такая пара может быть даже не Парето оптимальна).

Л-решение обладает свойствами линейности, симметричности, удовлетворяет аксиоме болвана (теоремы 4.3 - 4.4), а потому рассматривался как аналог значения Шепли.

В § 4.3 полученные для квазидифференцируемых игр результаты обобщаются на случай г-квазидифференцируемых функций, которые определяются следующим образом. Пусть е > 0. Функция / называется е-квазидифференцируемой в точке т, если она дифференцируема в ней по любому направлению g и существуют такие выпуклые компакты с7,/(г),«?, /(т), что

Пара DJ(т) = [<?./(г),де/(г)] называется е-квазидифференциалом функции/в точке -с.

Пятая глава посвящена исследованию кооперативных игр без побочных платежей. В первых трех параграфах этой главы рассматривается аксиоматический подход к определению функции эксцесса в играх без побочных платежей. Если с определением понятия доминирования в играх без побочных платежей, а значит и с определением связанных с ним понятий решений, таких, скажем, как с-ядро и решение по Нейману-Моргенштерну, проблем не возникает, то совсем иначе обстоит дело с определением таких понятий как и-ядро, Л-ядро и т.д., которые опираются на понятие эксцесса. Проблема здесь состоит в том, что нет такого же естественного, как в случае игр с побочными платежами, определения самого понятия эксцесса. Исследования, рассматривающие распространение »-ядра и к-ядра на игры без побочных платежей все еще редки, а основной вопрос касается того, каков же должен быть аналог функции эксцесса. Этой проблеме был посвящен целый ряд работ В.Б.Вилкова, Э.Калаи, Л.Биллера, М.Накаямы, О.Н.Бондаревой, Е.Б.Яновской и др. Однако эти попытки до сих пор не выкристаллизовались в единую теорию.

Э.Калаи определил семейство эксцессов для игр без побочных платежей. Точнее, он сформулировал те свойства, которыми должна обладать функция, "претендующая на роль" эксцесса. С помощью такого эксцесса можно определить ¿-ядро, ¿-ядро, л-ядро, ... игры без побочных платежей. Эти эксцессы обладают рядом естественных свойств, однако ничего нельзя сказать относительно единственности такого эксцесса, поскольку список желательных свойств очень невелик, что делает возможным брать в качестве эксцесса достаточно произвольные функции, не только не обладающие хорошими свойствами, с точки зрения соответствующих им решений, но даже не всегда обладающих какой бы то ни было естественной интерпретацией, как это происходит, скажем, в случае эксцесса, определяемого расстоянием от точки до границы множества (взятого со знаком "+" для точки, лежащей внутри множества, и со знаком "-" для точки - вне множества). Предлагаемый подход делает существенный шаг по направлению к решению этих вопросов.

Идея, используемая для определения эксцесса, в каком-то смысле близка идее, лежащей в основе определения функции ожидаемой полезности по Нейману-Моргенштерну. А именно, для каждой коалиции 51 вводится отношение предпочтения на множестве всех пар, состоящих из игрового подмножества и вектора полезностей (выигрышей) игроков, причем это отношение предпочтения полно, транзитивно и непрерывно, а потому предегавимо непрерывной функцией ценности. Такое представление, конечно же, не единственно, поэтому вводится дополнительное свойство, названное свойством квазилинейности, которое связано с некоторой естественной операцией на множестве всех игровых подмножеств. Квазилинейность определяет

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

В первом параграфе этой главы вводятся основные определения и пространство игр без побочных платежей, для которых определяется эксцесс. Кооперативной игрой без побочных платежей (НТП-игрой) называется пара (¡У), где / { 1, 2,..., п } - множество игроков, а V- многозначное отображение, которое ставит в соответствие каждой коалиции

1 множество У@), обладающее следующими свойствами:

(1)ГД)с-^= {кИ'.-г, = 0 для

(2) УСЯ) - непустое, замкнутое, исчерпывающее множество в И5.

Определим теперь рассматриваемое пространство НТП-игр СО±. НТП-игра Уе Сй* , если (а) Для любого уеУ(8) найдется такой г е = { хе И5: x/> 0 для ¡еБ }, что у <

2 и = У(Б) п компактно; (Ь) О = (0, 0,...,0) является внутренней точкой множества У*(5)=У(3) +■

Очевидно, что множество является нормальным множеством, то есть, если

хеУ+(3) и О <у <х (в И5 ) , то усУ,($) . Множества У($) с: называются игровыми подмножествами, если выполнены условия (1) и (2). Пространство, состоящее из всех игровых подмножеств в , удовлетворяющих свойствам (а) и (Ь), будем обозначать СС5,.

Функция Е$: СО^хЯ1 —> И называется функцией эксцесса (1ши просто эксцессом) для коалиции £, если она удовлетворяет следующим свойствам.

(A) Если х, у еИ! и х, = у, для каждого г е £, то для любой игры V ЕЦ(Г.х) = Ец(1г,у)

(B) Если г.д'еЫ' таковы, что х, < у, для любого ; е £, то для любой игры V Ец(У,х)>Е3(У,у)

(C) Для любой игры У, если

хесУ(5) = { геЩ) : несущеетвуегуеЩ}такого, что у,> г,-, УгеЯ},

то х) О

(О) Е$(У, х) непрерывно но х и V.

Далее 1Я(У) обозначает множество индивидуально рациональных векторов полезностей в игре У, СЩУ) - множество (слабо) Парето оптимальных точек игры Г;

Дтя любого вещественного е, с-ядро игры ^определяется следующим образом

Cedr) = {xeGR(V) ^IR09 : VS*I, Es(V, x)<e).

В § 5.2. вводится отношение предпочтения на пространстве CG'', х Rs, , а затем определяется калибровочный эксцесс для игр без побочных платежей как функция ценности, представляющая это отношение предпочтения. Мы ограничиваемся рассмотрением векторов полезностей только из Rs+, поскольку все множества V е CGS+ , по определению, нормально порождены, а значит для любого xgV+ найдется такой zeV¥, что х <z, а значит для любого эксцесса Es и любой игры V должно выполняться (и действительно выполняется), как следствие свойств (В) и (D), неравенство E/lr, xj>Es (V, z). Поэтому для любых "разумных" решений следует рассматривать лишь х е Rs* .

Рассмотрим произвольную коалицию S 0 и определим <j следующим образом: для любой пары игр V, V' е С(}\ и любых векторов х, уе Rs будем говорить, что пара (V, х) не хуже, чем пара (V, у), и обозначать это через (V, х) <s (V, у), тогда и только тогда, когда

для любого Х>0 такого, чтохе?У имеет место уе),II".

Это отношение предпочтения корректно определено, в силу определения пространства CG* . Каждое множество VeCGs+ звездно, то есть замкнуто, содержит начало координат в качестве своей внутренней (в R3) точки и

хеУ=>{Хх:Ле[0, J]}cV.

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

(V, х) ~s 0У) <=> { для любого ju>0, /uxeV о fjyel"} и

(V, х) <s (V., у) а> существует такой X >0, что х gkV, но у eXV.

Предложение 5.2. Отношение предпочтения <j полно, транзитивно и непрерывно.

Следствие 5.1. Существует непрерывная функция ценности us на CGS* х R5 + , представляющая Ss , то есть (V, х) <s (\п, у) <=> us(V, х) <s iis(V', у) • Более того, она удовлетворяет условиям (А), (В) и (D)

Функция ценности us(.), представляющая <j , не единственна. Однако, введение дополнительного условия на функцию ценности, позволяет существенно ограничить множество функций ценности, представляющих данное отношение предпочтения. Определим операцию © в пространстве CGS+ следующим образом. Пусть V, V - два произвольных игровых подмножества в CG6-.. Рассмотрим две пары (V, х) и (I", х), х & О. Тогда существует единственная пара чисел Д р>0 , таких что Л - р =1 и (XV, х) ~ (pV,

^.Операция Ф должна обладать следующим свойством: для любых V и V, для каждого х е 1Г.

(ЮГ, х) ~ (XV, х) ~ (цГ, х)

Теорема 5.1. Существует единственная операция ©, обладающая указанным свойством. При этом

ГФГ= у (вГп(1-а)П .

=<0.1]

Множество У(ВУ известно как инверсная сумма звездных множеств V и V'. Множество СО* можно рассматривать как полулинейное пространство относительно операции "сложения" Ф и произведения * множества V на положительное число к> О, определенное формулой л*У = (1/к)1г (к*У= для Я =0).

Определение 5.1. Функция ценности г/5 называется квазилинейной, если и* (к* V® к'* V, х) = ки^, х) + к'щ(Г, х)

для любых к, к' >0, таких, что к =I .

Теорема 5.2. Предположим, что непрерывная функция ценности м? квазилинейна. Тогда непрерывная функция ценности и'э является другой квазилинейной функцией, представляющей то же отношение предпочтение , тогда и только тогда, когда существуют такие числа Ь > 0 и а, что и^О - Ьи$ (■) + а.

Таким образом, квазилинейность определяет фзтгецию ценности, представляющую введенное отношение порядка, однозначно с точностью до положительного аффинного преобразования. Такая функция определяется с помощью калибровочной функции.

Предложение 5.3. Пусть у (V, . ) - калибровочная функция (функционал Минковского) множества V, то есть у(V, х) = тГ {/>(): хеХУ}. Тогда функция ценности щ(У, х) = - у(У, х) представляет и квазилинейна.

Таким образом, справедлива следующая теорема.

Теорема 5.3. Существует непрерывная квазилинейная функция ценности и;, определенная на СО, х^ , представляющая <•, а потому, обладающая свойствами (А), (В) и (Б). Более того, непрерывная функция ценности г;?, представляющая <3 (а потому удовлетворяющая (А), (В) и (Б)) квазилинейна тогда и только тогда, когда Кч(К х) = аз -хг) для некоторых чисел и с,ц . Кроме того она удовлетворяет свойству (С) тогда и только тогда, когда а3 = то есть х) = ря - Ь5 для некоторого

Ъ3>0.

Определение 5.2. Функция ценности us = bs - bs y(V(S), у?) , представляющая <s, называется калибровочным эксцессом и обозначается через gs. Семейство {gs}s калибровочных эксцессов называется согласованным, если bs = Ъ > 0 для всех Sc 1. Согласованное семейство эксцессов называется стандартным семейством, если Ъ = 1, а соответствующий эксцесс - стандартным калибровочным эксцессом.

Стандартный эксцесс gsßr,x) можно интерпретировать как степень неэффективности вектора х относительно V(S) . В частности, степень неэффективности вектора х отрицательна, если х - не достижим, то есть х g V(S) , и положительна, если х достижим и неэффективен, то есть х е int V(S) (в R5). Наконец, степень неэффективности равна нулю, если х - эффективный вектор в V(S), то есть х е cV(S) .

§ 5.3. посвящен исследованию свойств калибровочного эксцесса, а также свойств соответствующих этому эксцессу решений. В частности, если игра FeCG+ соответствует игре с побочными платежами v (здесь речь идет о "соответствии", ввиду того, что игры из множества CG+ являются нормально (и компактно) порожденными), то эксцесс совпадает со взвешенным стандартным эксцессом (v(S) - x(S))/v(S).

Для этого эксцесса, поскольку он является эксцессом в смысле Калаи справедливы все стандартные результаты о соответствующих решениях. Кроме того, справедливо

Предложение 5.5. Пусть V, V е CG+ - такие игры без побочных платежей, что V(I) - V'(I) и Г(Б) = aV(S), VS и некоторого а >0 . Тогда xePN(V) <^хеРЫ(У), где PN(V) -пред-н-ядро игры V.

Важнейшим свойством калибровочного эксцесса является возможность геометрической характеризации соответствующих ему и-ядра и пред-и-ядра. Соответствующая харакгеризация представляет собой модификацию на случай НТП-игр геометрической характеризации (пред)-л-ядра классической кооперативной игры, предложенной М.Машлером, Б.Пелегом и Л.Шепли. Разумеется, соответствующая процедура значительно более громоздка, а (пред-)гс-ядро, вообще говоря, состоит из конечного числа точек. Если рассматриваемая игра соответствует "гиперплоскостной" НТП-игре, то (пред-)л-ядро одноточечно.

В § 5.4 рассматривается "двойственный" (к "калибровочному") подход к играм без побочных платежей, основанный на использовании опорных функций, определяется Я-трансферабельное пред-л-ядро, а также рассматривается так называемый опорный эксцесс.

х-трансферабельное пред-й-ядро (н-ядро) определяется аналогично Я-трансферабельному значению Шепли следующим образом. Пусть V - игра без побочных платежей. Подвергнем полезности игроков изменению масштабов измерения, а именно, умножим полезность каждого игрока iel на неотрицательный множитель Я, . Я-

трансферабелыюе пред-и-ядро (л-ядро) игры V- это такой вектор F(V), что существуют такие множители ЯД iel, для которых:

(a) F(V) eV(I) -

(b) вектор FftJxÄ* = (Fi(V)Xi*, ..., F„(J)À„*) максимизирует суммарную полезность коалиции 1 в игреке побочными платежами с ¡смененными масштабами полезностей;

(c) вектор F(V)yA* есть пред-л-ядро (и-ядро) соответствующей игры с побочными платежами.

Теорема 5.6. Если игра без побочных платежей v такова, что dorn v(S, .) = R- для любой коалиции S, где dorn v(S, .) - эффективное множество опорной функции v(S, .), множества V(S), то существует Д-трансферабелыюе пред-и-ядро. Если dorn v(I, .) crR'^ , то существует Л-трансферабельное и-ядро игры v.

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

Шестая глава посвящена исследованию многошаговых суперлинейных кооперативных игр без побочных платежей. Различные аспекты динамических кооперативных игр исследовали Л.Л.Петросян, Н.Н.Данилов, С.В.Чистяков, Е.Розенталь, И.Гильбоа и другие. Мы рассматриваем так называемые обобщенные кооперативные игры как многозначные отображения в R" , и интерпретируя их специальным образом, используем аппарат суперлинейных многозначных отображений.

Точнее, под обобщенной игрой без побочных платежей (НТП-игрой) мы понимаем многозначное отображение V: R"_ R".

"Степень участия" т, игрока i в обобщенной коалиции т е R"+ мы интерпретируем как "вклад" этого игрока в игру. Такая интерпретация позволяет рассматривать произвольный вектор х e V(r) как обобщенную коалицию, а это даст возможность

определить многошаговую игру как последовательность отображений V, V2, V3.....

Предлагаемый подход позволяет, во-первых, дать удобную интерпретацию нечетких коалиций, во-вторых, позволяет определить многошаговую НТП-игру, а в-третьих, дает возможность определить решение для таких игр. Далее, с одной стороны, этот подход определяет решение именно как решение многошаговой игры, основанный только на "динамической Парето оптимальности". С другой стороны, такой подход позволяет рассматривать и решение статической НТП-игры.

Для любых х с R" и г е R" положим т • х = (ti*i , ... , Tr^cJ. Обобщенной НТП-игрюй называется многозначное отображение V: R"+ -» R" такое, что

(a) Множество У(т) сгИг = т • Я" выпукло, ограничено сверху и исчерпывающе, то есть У(т) = У(т) - г.;

(b) Отображение V замкнуто;

(С) Отображение F положительно однородно, то есть У(Хх)=ХУ(т), 1>0. (Это определение формально восходит к Ж.-П.Обену).

Предлагаемая интерпретация нечетких коалиций состоит в следующем. Предположим, что каждый игрок обладает некоторым ресурсом (это может быть продукт, деньги, фактор производства (скажем, труд) и т.д.). Представим себе, что игрок вкладывает этот ресурс (полностью или частично) в игру или некоторый процесс. Представим себе теперь далее, что каждый игрок описывается своей функцией полезности, заданной "на его ресурсе". Скажем, если речь идет о ситуации, когда ресурс игрока - это деньги, то его функция полезности - это функция полезности на множестве денежных сумм (или функция полезности Бернулли). Функция полезности "более тонко" описывает ситуацию. Поэтому, когда игрок 1 вносит, скажем, свой денежный вклад г, , то тем самым он как бы вносит полезность г, = и,((¡). В этом смысле можно говорить о том, что игрок / вносит свою полезность. При всей своей спорности и нестандартности именно такая интерпретация, как представляется, дает возможность по-новому взглянуть на игры без побочных платежей.

Если интерпретировать вектор т именно таким образом, то множество У(г) представляет собой множество векторов полезностей, которые могут быть получены, если игрок 1,1 = 1,... ,п внес (вложил, "инвестировал") в игру г, единиц своей полезности.

Далее рассмотрим поведение игроков в моменты времени т 0, 1.....

Предположим, что масштабы полезностей игроков не меняются со временем. (Вообще говоря, можно считать также, например, что они изменяются синхронно с одним и тем же коэффициентом дисконтирования). Для нас будет также удобно предположить, что единицей измерения своей полезности каждый игрок считает всю имеющуюся у него полезность в момент времени т = 0 (или максимальную полезность, которую он готов внести в момент т = 0). То есть г, < I , а е с - вектор "полного участия", вектор максимальных вкладов, которые могут сделать игроки в момент т = 0 . (Вектор с рассматривается только для удобства и может бьггь заменен любым строго положительным вектором в И". ).

Безусловно, возможна и более стандартная - "технологическая" интерпретация, когда вектор т трактуется не как набор полезностей, а как набор ресурсов, имеющихся, скажем, у отраслей. При этом выбор точки из У(т) можно рассматривать как параметры отраслей на следующем этапе, и мы получаем таким образом, некоторую траекторию

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

Пространство R" мы рассматриваем как пространство полезностей. Если тс[ 0, 1 ]" - стандартная нечеткая коалиция, то вектор т • е определяет некоторый вектор вкладов, который соответствует ситуации, когда каждый игрок i вносит в игру г, -ую часть своей полезности. Если же мы имеем вектор вкладов (t¡, ... , т„ ) е [ 0, 1 ] " , то в силу формального равенства r¡ = (т • е), мы можем говорить о нечеткой коалиции т . Это позволяет говорить нам о векторе т е R". (даже если г ¡r [ О, I ] " ) не только как о векторе вкладов, но и как об обобщенной коалиции.

Коалицию Sel мы отождествляем с ее характеристическим вектором es и говорим, что коалиция S действительно сформировалась, если каждый игрок i е S вложил всю имеющуюся у него (в момент m = 0 ) полезность. Если // е R+ , то мы будем называть /jes (обычной) коалицией S с уровнем реализуемости р .

В § 6.2. рассматривается каноническое представление НТП-игры, которое, формально обобщая каноническое представление классической кооперативной игры, рассмотренное в § 3.1, связано с совершенно другими соображениями. Если V -стандартная НТП-игра, то предположим, что действует следующее правило: могут образовываться только обычные коалиции с различными уровнями реализуемости, и игроки могут распределять свои вклады произвольно (в соответствии с уровнями реализуемости коалиций, включающим этих игроков) и вносить их в эти коалиции.

Это правило определяет суперлинейную обобщенную игру

у (г)-- и y>.sw')-

~£f,ses*t s

fs*"

Стандартная НТП-игра V вполне сбалансирована, если V(es) = V(S) VScI, и сбалансирована, если V(e) = V(l) . Если игра F представляет собой арбрпражную схему с нулевой точкой status quo, то есть V(S) ={xeRs:r¡ ¿q, для каждого i eS } для любой S ¿I, и q<£ int V(I), то

K(r) = (min т,)г(/).

В § б.З вводится определение многошаговых НТП-игр, определяется решение таких игр и вводится понятие устойчивых коалиций. Пусть V - обобщенная игра. Игроки

участвуют в игре, делая свои вклады т,, i = 1.....п. Множество достижимых векторов

полезностей определяется множеством У (г) . Каждый вектор х еУ(г) может быть снова вектором вкладов. Поэтому множество достижимых векторов полезностей на следующим шаге есть

уК(х) = К(Г(г)) = Кг(г).

КГ(Т)

Тогда, если игроки продолжают игру, и на каждом шаге вносят все свои выигрыши (в терминах полезностей), которые они получили из начального вектора вкладов т, то на шаге т они могут получить произвольный вектор хеУ"{ г) , где V" - т-ая степень отображения У . (Мы можем предположить, что игроки вносят лишь некоторую фиксированную часть своих выигрышей, что лишь изменит отображение V ). Последовательность V" ,т = 1, 2, ... определяетмпогошагикую обобщеннуюН'Ш-игру.

Если V - такая обобщенная игра, что У(т) = [ У(т)]т - , то она (и степени Т-*") полностью определяется нормальным множеством [ У(т) ]+ . Более того, эффективные точки множеств У(т) однозначно определяются эффективными точками множеств (У*Р(т) . Поэтому отображение Г+, удовлетворяющее всем условиям определения НТП-игры, за исключением исчерпываемости (которое заменяется условием нормальности), рассматривается как обобщенная игра.

Обозначим через К, множество всех обобщенных игр п игроков, обладающих свойством У(г) пп & 0, (т > О) . Представим себе, что игроки играют по некоторым правилам в игру, но не знают, когда эта игра закончится. Принцип, которым руководствуются игроки, состоит в следующим: в любой момент, когда бы ни закончилась игра, вектор полезностей, получаемых игроками, должен быть эффективным. Иными словами, мы хотим, чтобы каждому г решение ставило в соответствие такой вектор (или множество векторов) из У(т), который гарантировал бы игрокам получение эффективного (Парето оптимального) вектора выигрышей в любой момент окончания игры, каким бы он ни был.

Итак, пусть IV - нормальный компакт, ¡У сг , Б с: I , а я0УУ обозначает множество (слабо) Парето оптимальных (эффективных) точек множества W10 есть тсЖ = { г е IV : не существует у £ IV: у > х (в ^ ) } .Для отображения V е Г„ , т > О и натурального числа те рассмотрим множество

Включение в е^,,(т,У) имеет место тогда и только тогда, когда

(1) точка 9 может быть получена из г на первом шаге;

(2) из точки 9 можно попасть в эффективную точку множества Vя(т) за т - 1 шаг (то есть эффективная граница множества У(т) достижима за т -1 шаг).

Иными словами, если игра продолжается т шагов, то игроки выбирают на первом шаге такую точку в, что .из нее, на шаге т , может быть достигнута эффективная точка множества У"(т) .

Определение 6.2. Решение на Т„ есть отображение, определяемое равенством

Важнейшим средством исследования этого решения является теория суперлинейных отображений и эффективных функционалов, первоначально рассматривавшихся как аппарат для исследования моделей экономической динамики. В этом контексте ее развитие связано, в частности, с именами В.3.Беленького, В.Л.Макарова и А.М.РубиноваЛ

Множество C(t,V) непусто, компактно для любых Fn г, и £ (t,V) er тх0У(т).

Таким образом, решение ставит в соответствие каждому вектору г > О и каждой суперлинейной игре такие вектора 6 е У(т] , которые гарантируют игрокам возможность получения в момент окончания игры, каким бы он ни был, эффективного вектора выигрышей.

Определение 6.3. Обобщенная коалиция г > О называется устойчивой в обобщенной суперлинейной игре V, если существует такое число а > 0 , что атеС,(х,У) .

Смысл этого определения в следующем. Предположим, что данная первоначально коалиция выбрала х е У(т) и вкладывает все свои выигрыши вновь. Тогда, вообще говоря, может образоваться эта коалиция х. Однако, если коалиция г устойчива, то игрокам нет смысла менять что-либо и переключаться на х (кроме, быть может, уровня реализуемости коалиции т).

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

1. фУ)с£(T,V).

2. Если ¿¡(т,У) одноточечно, то £(t,V2) = £(t,V) .

3. Если коалиция г устойчива в исходной игре V, то есть axeQx, V) , то эта коалиция устойчива и в первой итерации V2, а именно, сс г ^ V2) .

4. Решение £,(х, V) положительно однородно, то есть V) = ХС,(х,У), Л> 0.

5. Если коалиция г устойчива, то «""'г е((а"т,У) , m = 0,1, ... . Таким образом, коалиция ~х является устойчивой на каждом шаге, при этом изменяется лишь "уровень реализуемости" коалиции.

В § 6.4 приведены некоторые свойства решения и устойчивых коалиций. При исследовании решения и устойчивых коалиций полезно использовать отображение V* , сопряженное к суперлинейному нормальному отображению V. По определению, V*(g) = {/¿О :(f,T)>(g,e), т^О.ве V(r) } .

Тройка (а, % 1) , где а - положительное число, г, 1 е R" , называется состоянием равновесия суперлинейного нормального отображения V, если

ах е V(t), al е V*(l), (I, г) > 0; число а называется темпом роста, а элементы х и / - равновесным вектором и равновесными ценами, соответственно.

Пусть V - суперлинейная игра. Пусть Vs обозначает сужение отображение V на грань Rs+ конуса R"+ . Vs называется под-игрой игры V.

Предложение 6.4. Обобщенная коалиция ? устойчива тогда и только тогда, когда вектор т является равновесным вектором в игре V или некоторой ее под-игре.

Суперлинейный функционал (то есть вогнутый, положительно однородный, непрерывный) у : II"т Я. называется эффективным для суперлинейного отображения V, если при некотором а> 0 для всех т>0 выполняется соотношение щ(т) = шах \qf9j : б? е } . Справедливы следующие утверждения.

Предложение 6.6. Пусть ц - эффективный функционал суперлинейной игры V, а вектор г >0 таков, что ц(т) > 0 Тогда

веГ(г)

Теорема 6.1. Пусть обобщенная игра Г имеет вид У(т) = ц(г) IV , где д -суперлинейный функционал, а Ж нормальный выпуклый компакт с непустой внутренностью. Тогда для любого т>0 С(т, V) = с](т)1/.

(Здесь (7 - множество точек максимума функционала q на IV, "нормированных" условием равенства 1 калибровочной функции).

В этом же параграфе рассмотрено несколько примеров. В частности, показано, что "мультилинейное Оуэновское" расширение арбитражной схемы приводит к арбитражному решению Нэша или несимметричному аналогу этого решения, введенного Калаи.

Последний параграф главы VI посвящен рассмотрению канонического представления игр вполне сбалансированных НТП-игр. Приведен вид сопряженного отображения к каноническому представлению НТП-игры. Установлены необходимые и достаточные условия устойчивости стандартной коалиции в каноническом представлении (теорема 6.2).

В частности доказано, что если игра \\ определена следующим образом. ^-{геН^гГ? е)<у(3)}, где V - (положительная) характеристическая функция игры с побочными платежами, то, коалиция $ устойчива тогда и только тогда, когда для

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

По теме диссертации опубликованы следующие работы:

1. О значении Шепли для игр без побочных платежей, Математические методы в социальных науках, 10, Вильнюс: ИМК АН Лит. ССР, 1978,43 - 62.

2. О нелинейных аналогах значения Шепли для игр с априорными союзами, Тезисы докладов III Всесоюзной конференции по исследованию операций, Горький, 1978, 349 -350.

3. Об одном арбитражном решении, Математические методы в социальных науках, 12, Вильнюс: ИМК All Лит. ССР, 1978, 88 - 107.

4. Линейкое значение для арбитражных схем, Математические методы в социальных пауках, 15, Вильнюс: ИМК АН Лит. ССР, 1982, 37 - 54.

5. Проблема оптимального распределения в социально-экономических задачах и кооперативные игры, Л.: Наука, 1983, 11.2 п л., соавт. А.И.Соболев, лично автора 5.5 п л.

6. Задачи многокритериальной оптимизации и л-ядро в кооперативных играх без побочных платежей, Тезисы докл. II Всесоюзн. Школы-семинара по оптимизации и ее прилож. к экономике, Ашхабад.

7. Динамическая Парето оптимальность, суперлинейные многозначные отображения и кооперативные игры, Математические методы в социальных науках, 19, Вильнюс: ИМК АН Лит. ССР, 1986, 56 - 71, соавт. А.М.Рубинов.

8. Многозначные решения кооперативных игр: аксиоматический подход, Математические методы в сажальных науках, 19, Вильнюс: ИМК АН Лит. ССР, 1986, 72 - 86, соавт А.И.Соболев.

9. Квазидифференцируемые кооперативные игры, В кн. Некоторые вопросы анализа и моделирования народнохозяйственных процессов, М.: ЦЭМИ АН СССР, 1989, 98-113.

10. Некоторые применения методов негладкого анализа: анализ кооперативных игр. В кн.: В.Ф.Демьянов, А.М.Рубинов Основы негладкого анализа и кеазидчфференц и а?ьног исчисление, М.: Наука, 1990, 382 - 394.

11. О теоретико-игровых методах моделирования в экономике, Препринт, СПб: ЕУСПб, 1.5 п.л.

12. Positively Homogeneous Quasidifferentiable Functions and their Applications in Game Theory, Collaborative Paper, CP-84-26, IIASA, Laxenbuirg, Austria, 1984.

13. Positively Homogeneous Quasidifferentiable Functions and their Applications in Cooperative Game Theory,Math. Programming Study, 29, 1986, 135 - 144.

14. Solution Concept for Generalized Multi-Stage Games Without Side Payments, Journal of Math. Economics, 25, 1993, 403 - 420, соавт. А.М.Рубинов.

15. Set-Valued Nonlinear Analogues of the Shapley Value, International J. of Game Tlteory, 24, 1995, 57 - 78, соавт. А.И.Соболев.

16. Additive and Superadditive Solutions for Bargaining and Cooperative Games, Book of abstracts, Game Theory and Economics: N.N.Vorob'ev Memorial Conference, St.Petersburg, 1996, 52.

17. Note on Two Excess Functions for Cooperative Games Withjout Side Payments, The Seventh Stony Brook International Conference on Game Theory, Book of abstracts, Stony Brook, NY, 1996,68.

18. On Gauge Excess Function for NTU-Games: Axiomatic Approach, The Eighth Stony Brook International Conference on Game Theory, Book of abstracts, Stony Brook, NY, 1997, 70.

4/М-?

/

РОССИЙСКАЯ АКАДЕМИЯ НАУК САНКТ-ПЕТЕРБУРГСКИЙ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

ПЕЧЕРСКИЙ Сергей Львович

АКСИОМАТИЧЕСКИЙ МЕТОД В ТЕОРИИ КООПЕРАТИВНЫХ ИГР

Специальность 01.01.09 - Математическая кибернетика

Диссертация на соискание ученой степени доктора физико-математических наук

Санкт-Петербург - 1998-год

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ....................................................... 4

I. ЭКОНОМИЧЕСКОЕ МОДЕЛИРОВАНИЕ, КООПЕРАТИВНЫЕ ИГРЫ И ИХ РЕШЕНИЯ........................................9

1.1. Аксиоматический метод, кооперативные игры и

экономическое моделирование...................................9

1.2. Основные определения и обозначения........................ 34

1.3. Основные результаты......................................49

1.4. Краткое содержание работы.................................69

II. НЕЛИНЕЙНЫЕ МНОГОЗНАЧНЫЕ АНАЛОГИ

ЗНАЧЕНИЯ ШЕПЛИ........................................75

2.1. Основные определения и аксиомы...........................75

2.2. Некоторые свойства решения................................79

2.3. Отображение Fw и его свойства..............................86

2.4. Существование и единственность решения....................92

2.5. Селекторы решений........................................94

2.6. Пред-/с-ядро..............................................98

2.7. Антирешения.............................................106

III. С-ЯДРО И КВАЗИЯДРО В КЛАССИЧЕСКИХ И

НЕЧЕТКИХ КООПЕРАТИВНЫХ ИГРАХ.........................111

3.1. Нечеткие коалиции, сбалансированность и

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

3.2. Аксиоматика с-ядра и нечеткого с-ядра........................122

3.3. Квазиядро................................................132

3.4. Антиядро и распределение затрат............................139

IV. КВАЗИДИФФЕРЕНЦИРУЕМЫЕ КООПЕРАТИВНЫЕ ИГРЫ..........144

4.1. Положительно однородные функции и квазидифференцируемость . .144

4.2. Квазидифференцируемые кооперативные игры..................150

4.3. ^-квазидифференцируемые кооперативные игры.................159

V. ИГРЫ БЕЗ ПОБОЧНЫХ ПЛАТЕЖЕЙ: ФУНКЦИИ ЭКСЦЕССА

И СООТВЕТСТВУЮЩИЕ РЕШЕНИЯ.............................169

5.1. Предварительные замечания и основные определения............169

5.2. Отношение предпочтения на CGs+xRs и калибровочный эксцесс.....175

5.3. Свойства калибровочного эксцесса и соответствующих решений .... 187

5.4. Игры без побочных платежей в форме опорной функции...........195

5.5. Некоторые модели, формализуемые с помощью НТП-игр...........201

VI. МНОГОШАГОВЫЕ СУПЕРЛИНЕЙНЫЕ ИГРЫ БЕЗ

ПОБОЧНЫХ ПЛАТЕЖЕЙ.......................................213

6.1. Обобщенные игры без побочных платежей.......................213

6.2. Каноническое представление НТП-игры.........................218

6.3. Многошаговые НТП-игры: решение и устойчивые коалиции.........221

6.4. Свойства решения и устойчивых коалиций........................226

6.5. Устойчивые коалиции и каноническое представление НТП-игры......235

ЛИТЕРАТУРА...................................................240

ВВЕДЕНИЕ

В последние десять-пятнадцать лет наблюдается стремительное повышение интереса к теории игр и значительное возрастание ее роли. Это объясняется, в первую очередь, тем, что без нее в настоящее время уже немыслима современная экономическая теория, причем область применения теории игр постоянно расширяется. Теория игр прошла путь от весьма формализованной теории, представлявшей интерес в первую очередь для математиков и ставшей источником целого ряда работ чрезвычайно глубокого математического содержания, до одного из важнейших инструментов анализа огромного многообразия задач, возникающих в экономике, политике, социальных науках и т.д. (не утратив при этом, разумеется, своего математического содержания). Так, видимо, не было бы слишком большим преувеличением сказать, что происходит своего рода "теоретико-игровой поворот" в экономической теории.

Когда чуть более 50 лет назад закладывался фундамент теории игр -классическая монография Дж. фон Неймана и О. Моргенштерна (Иеитапп/Могдег^егп (1944)) - ее перспективы представлялись достаточно оптимистично. Однако долгое время формальная сторона превалировала над неформальными, и в первую очередь экономическими, интерпретациями. Но в настоящее время круг проблем, который охватывается теорией игр чрезвычайно широк, выходит уже далеко за рамки экономики, захватывает все новые и новые области и придает тем самым все больший вес теории игр.

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

(альтернатив), которые они способны обеспечить, вступая, быть может, в различные коалиции, и множества отношений предпочтений игроков на множестве исходов (альтернатив). Под решением кооперативной игры понимается некоторый исход, или, может быть, некоторое множество исходов, доступных для игроков. Скажем, в простейшем случае, классическая кооперативная игра - это набор, состоящий из множества игроков и вещественно-значной функции, ставящей в соответствие каждой возможной коалиции игроков (то есть каждому произвольному подмножеству множества всех игроков) число, интерпретируемое как максимальный возможный суммарный выигрыш (минимальный проигрыш в случае его отрицательности), который коалиция может гарантировать своим членам. Решение такой игры - это некоторый вектор, или множество векторов, описывающих распределение выигрышей игроков.

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

Второй метод - "противоположно направлен", это своего рода обратный аксиоматический метод. Применяя его, обычно исходят из тех решений, которые выбраны на основе каких-то интуитивных соображений или формальных

представлений о схемах, используемых в реальной практике, а лишь затем уже изучают те свойства, которым эти решения удовлетворяют (хотя это уже не является центральным моментом исследований). Здесь, однако, следует особо отметить, что граница, разделяющая эти два метода весьма и весьма расплывчата в том смысле, что очень часто второй метод естественно переходит в первый: исследование свойств выбранного решения приводит к тому, что полученные свойства (или некоторые из них) становятся аксиомами, которые однозначно и определяют то самое решение, с которого процесс начинался. В этом смысле, о втором методе можно тоже достаточно естественно говорить как об аксиоматическом методе, не разделяя строго "прямой" и "обратный" аксиоматический методы.

Именно аксиоматический метод занимает центральное место в работе. Все решения, которые здесь исследуются, группируются вокруг свойств линейности, суперлинейности и их различных модификаций, включающих свойства, связанные не только с операцией сложения кооперативных игр, но и с нелинейными аналогами операции сложения, и их "предельным аналогом" -операцией взятия максимума. Получающийся при этом спектр решений чрезвычайно широк. Причем, с одной стороны, изучаются новые системы аксиом, приводящие как к новым решениям, так и к ряду традиционных, таких, например, как вектор Шепли, с-ядро, с£-ядро, л-ядро, /с-ядро и другие. С другой стороны, рассматриваются новые классы игр, вводятся новые решения и исследуются их свойства.

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

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

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

В главе 2 исследуются нелинейные многозначные аналоги значения (функции, вектора) Шепли для классических кооперативных игр. Здесь же рассматриваются некоторые "анти-решения" кооперативных игр, наиболее естественная область применения которых - задачи распределения затрат. Глава 3 посвящена аксиоматической характеризации с-ядра для классических кооперативных игр и нечетких кооперативных игр как супераддитивного и, соответственно, аддитивного решений, а также вводится понятие квазиядра кооперативной игры. В главе 4 изучается новый класс нечетких кооперативных игр - квазидифференцируемые кооперативные игры, и их линейные решения. Пятая глава посвящена аксиоматическому определению функции эксцесса для игр с нетрансферабельной полезностью и изучению свойств некоторых соответствующих этому эксцессу решений - с-ядра, /?-ядра, /с-ядра. В шестой

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

В диссертации принята автономная нумерация параграфов, формул, теорем, лемм и т.д. Они нумеруются с помощью двойного индекса: первая компонента указывает номер главы, а вторая - номер параграфа, формулы, теоремы или леммы в этой главе. Каждый параграф разбит на пункты, имеющие тройной индекс: первые две цифры - номер параграфа, третья - номер пункта.

I. ЭКОНОМИЧЕСКОЕ МОДЕЛИРОВАНИЕ, КООПЕРАТИВНЫЕ ИГРЫ И ИХ

РЕШЕНИЯ

§ 1.1. Аксиоматический метод, кооперативные игры и экономическое

моделирование

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

1.1.1. В настоящее время основное "поле приложений" теории игр - это, безусловно, экономическая теория. Более того, сейчас она относится к важнейшим составляющим экономической теории. Именно поэтому мы подробно остановимся на той роли теории игр, которую она играет в экономической теории и экономическом моделировании.

Первыми исследованиями игр в экономической литературе, по-видимому, следует считать статьи Курно (Cournot (1838)), Бертрана (Bertrand (1883)) и Эджворта (Edgeworth (1897)), в которых рассматривались проблемы производства и ценообразования в олигополии. Однако они рассматривались лишь как очень специальные модели, не имевшие существенного значения для осмысления массы проблем, стоявших перед экономистами.

В 1944 году вышла в свет основополагающая монография Дж. фон Неймана и О.Моргенштерна "Теория игр и экономическое поведение" (von Neumann/Morgenstern (1944)), которая, по существу, заложила фундамент общей

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

Хотя, как отмечает В.М.Полтерович, блестящие образцы современного стиля теоретизирования в экономике, сложившегося за последние 50 лет, появлялись уже в двадцатых и тридцатых годах нашего столетия (достаточно упомянуть имена Ф.Рэмзи, И.Фишера, А.Вальда, Дж.Хикса, Е.Слуцкого, Л.Канторовича, Дж. фон Неймана) решающий перелом произошел в пятидесятые годы. Ключевую роль в создании нового подхода сыграло возникновение теории игр (Neumann/Morgenstern (1944)), теории социального выбора (Arrow (1951), и разработка математической модели общего равновесия (Arrow/Debreu (1954), McKenzie (1954), Debreu (1959)) (см. Полтерович (1997): с. 10). И действительно, без малейшего преувеличения можно утверждать, что теория игр относится к важнейшим составляющим современной экономической теории, и в настоящее время ее роль в экономической теории трудно переоценить.

За прошедшие с момента появления книги Дж. фон Неймана и О.Моргенштерна немногим более чем полвека теория игр прошла различные этапы своего развития и пережила несколько волн интереса к ней. Примерно 40 лет назад казалось, что теория игр дает чрезвычайно большие обещания экономике, однако эти обещания, увы, оказались во многом лишь обещаниями, хотя нельзя отрицать того, что был получен целый ряд очень глубоких математических результатов, представляющих значительный интерес даже вне экономических приложений. 25 лет назад "теорию игр" можно было найти в предметном указателе некоторых учебников по теории организации промышленности (Industrial Organization) при рассмотрении олигополии по Курно, по Бертрану или по Штакельбергу. Однако за последние 15-20 лет произошел гигантский шаг вперед, и теперь вряд ли можно найти область экономики или дисциплины, связанной с экономикой, такой, скажем, как финансы, маркетинг..., в

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

Среди многочисленных определений того, что есть теория игр и каковы ее задачи, которые можно найти в различных статьях, учебниках и монографиях (см., например, Воробьев (1984, 1985), Аитапп (1989), 01хКЛ\1а1еЬи1Т (1991), Рис1епЬегд/Т1го1е (1992), Муегэоп (1991), Равтизэеп (1989) и многие другие) упомянем лишь четыре. Первые два - это определения теории игр, которые с некоторыми вариациями, по-видимому, наиболее часто встречаются в литературе и достаточно точно характеризуют общую проблематику, охватываемую теорией игр: "Теория игр - это теория рационального поведения людей с несовпадающими интересами" (Аитапп (1989)), и "Теория игр - наука о стратегическом мышлении" (□¡хМЫа1еЬиА: (1991)). Третье подчеркивает математическую природу теории игр: "Теория игр - это теория математических моделей принятия оптимальных решений в условиях конфликтов" (Воробьев, (1984)). Наконец, четвертое определение выделяет роль теории игр именно в экономическом моделировании: "Суть теории игр в том, чтобы помочь экономистам понимать и предсказывать то, что будет происходить в экономическом контексте" (Кгерэ (1990)). В настоящий момент, если говорить об экономическом контексте, речь идет уже не только о применении теоретико-игровых методов к ставшим достаточно традиционными проблемам организации промышленности, но и, по сути дела, ко всему многообразию экономической проблематики. Так например, на микроуровне - это модели процесса торговли (модели торга, модели аукционов). На промежуточном уровне агрегации изучаются теоретико-игровые модели поведения фирм на рынках факторов производства (а не только на рынке готовой продукции, как в олигополии). Теоретико-игровые модели возникают в связи с различными проблемами внутри фирмы. Наконец, на высоком уровне агрегации, с международной экономикой связаны модели конкуренции стран по поводу тарифов и торговой политики, а

макроэкономика включает модели, в которых, в частности, стратегическое взаимодействие рассматривается в контексте монетарной политики. "Аппарат теории равновесия и теории игр послужил основой для создания современных теорий международной торговли, налогообложения, и общественных благ, монетарной экономики, теории производственных организаций" (Полтерович (1997): с. 11).

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

1) Она дает ясный и точный язык исследования различных экономических контекстов.

2) Она дает возможность подвергать