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

ыо^ы 7377

САНКТ-ПЕТЕРБУРГСКИЙ ГО СУ ДАР СТВЕННЬШ УНИВЕРСИТЕТ

На нравах рукописи /р^

ЛЕЖНИНА Елена Александровна

АКСИОМАТИЗАЦИЯ НЕКОТОРЫХ РЕШЕНИЙ КООПЕРАТИВНЫХ ИГР

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

1 б ДЕН 2010

Санкт-Петербург 2010

004617377

Работа выполнена на факультете прикладной математики -процессов управления Санкт-Петербургского государственного университета

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

профессор Яновская Елена Борисовна

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

профессор Розен Виктор Владимирович

кандидат физико-математических наук, Губар Елена Алексеевна

Ведущая организация: Московский государственный университет

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

Защита состоится «ß» аЖл 2010 года в /^часов на заседании диссертационного совета Д^212.232.59 по защитам диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, В.О., Средний пр., 41/43, ауд. 511.

С диссертацией можно ознакомиться в библиотеке имени A.M. Горького Санет-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., дом 7/9.

Автореферат разослан " /У " Н. ¿7. 2010 года

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

профессор #> В. Д. Ногин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Такой подход к формированию решений кооперативных игр называется аксиоматическим.

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

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

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

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

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

Наименьшее ядро, которое занимает «промежуточное положение» между с-ядром и «-ядром, не является согласованным, его аксиоматизации не было получено до последнего времени.

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

Свойство подтверждения до настоящего времени применялось только для другой характеризации пред «-ядра, в которой оно заменило свойство согласованности и одноточечности ([1], [2]). В диссертации получена аксиоматизация нескольких решений кооперативных игр с использованием свойства подтверждения.

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

Целью диссертационной работы является исследование свойств решений кооперативных игр, полученных с применением классического и взвешенного эксцессов и аксиоматизация этих решений. Все наиболее известные и популярные решения кооперативных игр: с-ядро, пред «-ядро, значение Шепли имеют аксиоматические характеризации. Они являются решениями указанных оптимизационных задач приближения. Однако достаточно известное решение - наименьшее с-ядро, введенное Шепли и Шубиком в 1966 году, являющееся промежуточным между с-ядром и пред

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

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

Структура работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающего 63 наименования. Объем работы состаатяет 84 страницы машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Кооперативной игрой с трансферабелъными полезностями называется пара Г = (7,v), состоящая из конечного множества I = {1,2,...,«} и вещественной функции v, определенной на множестве всех подмножеств множества 1, v(0)=O. Элементы множества 1 называются игроками, подмножества Sel - коалициями, функция v - характеристической функцией игры Г. Значения характеристической функции определяют силу коалиций.

Пусть задана произвольная игра (N,v). Исходом кооперативной игры является вектор из множества

X(N,v) = {хе R^x, < v(A0},

teJV

координаты которого обозначают выигрыши игроков.

Решением кооперативной игры (N, v) называется некоторое подмножество a(N,v) cz X(N,v). Если \a(N,v)\ = 1 для всех (N,v) некоторого класса игр G, то такое решение называется одноточечным значением.

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

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

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

Существуют два эквивалентных способа определения наименьшего

ядра.

Определение 1. Наименьшее ядро LC(N,v) - это пересечение всех непустых £-ядер игры (N,v), где £-ядро для произвольного вещественного е определяется следующим образом:

Cc(N,v)={xeR!\x(I) = v(I),x(S) > v(S)-e для всех S /}.

Определение 2. Рассмотрим задачу минимизации max(v(S) — x(S)) -> min .

S N,V)

Наименьшим с-ядром LC(N,v) называется решение этой задачи. Оно существует всегда и достигается на векторах с-ядра, если оно непусто.

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

которым принадлежат рассматриваемые игры. Пусть G - класс всех игр с произвольным универсальным множеством игроков N, таким что (N,v)e G, если yVcN.

Далее в главе приводятся определения свойств согласованности и подтверждения.

Согласованность. Решение <7 называется согласованным на произвольном классе G'cG, если для всех (Лг,у)е G', SczN, S * 0. хе (M,v), то

(S,v*)e G' и xs 6 <7(5-,vj).

где - редуцированная игра на множество игроков S. Впервые

определение редуцированной игры было дано Дэвисом и Машлером. Если игрок / е N покидает игру с выигрышем х,, то в редуцированной игре с

множеством игроков N\{i} коалиция S<zN\{i} может использовать свои

*

возможности как и в исходной игре и получить v(S). С другой стороны считается, что уходящий игрок оставляет колиции свои возможности. Для определения редуцированной игры рассматриваются два значения: v(S) и v^uf/})-*,.. Дэвис и Машлер предложили считать максимум из этих чисел max(v(5),v(Su{»})-значением характеристической функции редуцированной игры для коалиции S. Далее это определение обобщается на случай, когда игру покидает коалиция S:

да=тах{у(Ги0-х(0)}.

QcN\S

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

Свойство подтверждения. Решение <т на множестве G обладает свойством подтверждения, если для любой игры (A',v) е G из xea(N,v), (N\Sys)e G и ymse cr(N\S,vXs) следует (xs,yms)e cr(N,v), где (N\S,vXs) - редуцированная игра на множество N\S относительно векторах.

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

Первый результат данной работы следующий:

Лемма 1.1. Наименьшее с-ядро и промежуточные решения ст2,<73,... обладают свойством подтверждения.

Для наименьшего с-ядра этот результат был получен в [5].

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

Для аксиоматической характеризации названных решений применяются еще следующие свойства решений.

Инвариантность относительно сдвига. Решение а инвариантно относительно сдвига, если для любого числа а и для любой игры (W,v)

&(N,va) = cr(iV,v),

где

f v(N), если S = N,

(ve)(S)= \Л ох,

[^(6) + а, для остальных Л с N

Симметрия. Если для игроков i,jeN выполняется v(S и{/}) = v^S' и {_/'}) для всех S с /V, i,jgS, то xi = x¡ для любого хе cr(N,v).

Анонимность. Пусть (iV,v)eG, ?r:N—>N - произвольная перестановка игроков. Через n(N,v) обозначим игру k(N,v) = (N,in),vrq ttv(S) =v(7iS). Решение ^называется анонимным, если o(N,nv) = xa(N,v) для любой игры (N,v) е G и для любой перестановки л.

Макс-инвариантность. Решение а называется макс-инвариантным, если для любых игр (iV,v),(jV,w), таких что v(N) = w(N) из хв a(N,v)na(N,w) следует хе cr(iV,max{v,w}), где max{v,w}(5') = max{v(5'),'H'(S')} для всех S с N.

Ковариантность относительно сдвига. Для произвольной игры (/V,v) е G и любого вектора Ъ<а R" обозначим через vb следующую характеристическую функцию на множестве игроков N:

v4(S) = v(S) + 2>.

Тогда из (N,vb) е G следует cr(N,vb) = a(N,v) + b.

Основная теорема:

Теорема 2.1. Наименьшее с-ядро является максимальным по включению решением для класса С с универсальным бесконечным множеством игроков N уд овле творяющим аксиомам непутоты, ограниченности, ковариантности относительно сдвига, независимости от сдвига, подтверждения и макс-инвариантности.

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

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

Лемма 2.1. Если решение <7 для класса всех игр двух лиц удовлетворяет аксиомам непустоты, ограниченности, ковариантности и инвариантности относительно сдвига, то <7 является стандартным решением.

Лемма 2.2. Если решение а удовлетворяет свойству подтверждения на классе игр С, то его замыкание также обладает свойством подтверждения.

Игра в называется симметричной, если выигрыши игроков

зависят от количества игроков в игре, вектор выигрышей имеет вид

Лемма 2.3. Если решение с на классе игр С удовлетворяет свойству подтверждения, замкнуто и стандартно для игр двух лиц, то для симметричной игры (ЫУ)

(у*(Ы)1п,...У(Щ1п)еа(ЫУ).

Обозначим ¡и(х,у) = тах(\'(8) -х($)), =агйтах(у(5).

Лемма 2.4. Пусть решение (7 на классе игр О удовлетворяет аксиомам непустоты, ограниченности, ковариантности, инвариантности относительно сдвига, и макс-инвариантности. Если х е сг(Л',у), то х е сг(Л/Т,\>'), где V - произвольная характериатическая функция, удовлетворяющая условиям:

у'(Б)=у(Б) для {5 с JV:v(S)-д;(5) = max(v(S')-л;(S,))},

Я'г V

с < V' (З1) - х(Х) = Ъ < //(х,V) для остальных коалиций,

где с - второй по величине эксцесс:

с= тах (у(Г)-х(Г)).

ГсЛГ,

Лемма 2.5. Пусть решение <7 на классе игр С удовлетворяет

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

Пусть для хе о(К,у) компоненты вектора эксцессов - х^) принимают только два значения:

Тогда для любой игры (/V, е С и ее вектора выигрышей у из равенств

следует уе (Т(М,и>).

Лемма 2.6. Если решение о для класса всех игр трех лиц С3 удовлетворяет аксиомам непустоты, ограниченности, ковариантности, свойству подтверждения, независимости от сдвига и макс-инвариантности, то а(Мс ¿С(Л,г3у).

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

Пред к-ядром РК назыается максимальное по включению решение, удовлетвряющее свойствам симметрии, ковариантности и согласованности.

Обозначим через согласованное расширение <7, решения а и решение &, которое является максимальным согласованным подрешением решения РК п сг,.

Лемма 2.7. Решение 9 одноточечно, т. е. является значением на классе игр С, где <т, — согласованное расширение решения <7, <3 -максимальное согласованное подрешением решения.

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

v(S)-x(S) =

а, для З'е^^у), Ь < а, для остальных 6'.

с, для Б е (у, у>) = (х, у), й < с, для остальных Б,

ev(v(S),x(S)) = w(S)(v(S) -x(S)), w(S) > 0, применялись для определения взвешенных пред п -ядер [3].

Для анонимных решений, учитывающих значения эксцессов, функция эксцесса может зависеть только от числа игроков в коалиции. Одной из таких функций является «per capita» (нормированный) эксцесс

\S\

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

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

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

Пусть задано конечное множество N. Набор его подмножеств S называется сбалансированным, если существуют такие положительные числа Zs, для всех S е S, что для всех i е N

S)i

Набор S называется слабо сбалансированными, если числа Л3 неотрицательны.

Теорема 3.1. Пусть (N,v)g G - произвольная игра. Для того чтобы у = PN"(N,v) необходимо и достаточно, чтобы наборы

B"a(v,y) = с jV|

были сбалансированы для всех чисел а.

Эта теорема является аналогом известной теоремы Колберга [4] для эксцессов v(S) - x(S).

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

Характеристическая функция редуцированной игры определяется из формулы

УХ$(Т)-Х(Т) ^

\Т\

шах —и ^ .если Т Ф Б,

т „ (31)

'ф 1 если!-Ь.

Предложение. Нормированное пред п-ядро согласовано в классе С при определении редуцированной игры формулой (3.1).

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

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

Рассмотрим задачу минимизации (по векторам выигрышей) максимального (по коалициям) нормированного эксцесса:

шах-—--> ш ■

5 | Л | теЛ-(ЛГ.у)

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

ад с N: = =

Используя известный результат [5], доказанный для наименьшего ядра ЬС(Ъ1,у), доказывается следующая теорема:

Теорема 3.3. Для того чтобы необходимо и

достаточно, чтобы набор S" (х) был слабо сбалансирова.

Следствие. Нормированное пред п-ядро содержится в нормированном наименьшем с-ядре.

Основным результатом третьей главы является следующая теорема, обобщающая результат теоремы 2.1.

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

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

Основные результаты, выносимые на защиту

Па защиту выносятся аксиоматические характеризации наименьшего с-ядра, нормированного наименьшего ядра и нормированного пред /¡-ядра.

Наименьшее с-ядро определяется как максимальное по включению решение для класса С с универсальным бесконечным тожеством игроков N удовлетворяющим аксиомам иепутоты, ограниченности, ковариантности относительно сдвига, независимости от сдвига, подтверждения и макс-инвариантности.

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

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

Литература

1. Orshan G., Sudholter P. Reconfirming the Prenucleolus // Math. Oper. Res. 2003. Vol. 28. P. 283-293.

2. Соболев А.И. Характеризация принципов оптимальности в кооперативных шрах посредством функциональных уравнений.

Математические методы в Социальных науках, б, Вильнюс, Институт математики и кибернетики АНЛит ССР, 1975. с.51-94.

3. Derks J., Heller Н. (1999). Weighted nucleoli // Int. J.Game Theory. Vol. 28. P. 1-18.

4. Kohlberg E. On the nucleolus of a characteristic function game. // SLAM J. Appl. Math. 1993.Vol. 20. P. 62-66.

5. Thompson W. Consistent allocation rules. Economics Department, University of Rochester. 2003. 202 p.

6. Печерский С.JI., Яновская Е.Б. Кооперативные игры: аксиоматический подход. СПб: Европейскиу ун-т в СПб, 2004.

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

8. Schmeidler D. The nucleolus of a characteristic function game // SIAM J. Appl. Math. 1969. Vol.17. P. 1163-1170.

9. Yanovskaya E. Consistency for proportional solutions // Logic, Games and Social Theory. Extended Abstract of the Intern. Conf. St. Petersburg. 2001. P. 249-253.

10. Orshan G. The prenucleolus and the reduced game property: Equal treatment replaces anonymity // Int. J. Game Theory. 1993. Vol. 22. P.241-248.

Апробация работы

• International Congress of Mathematicians, Game Theory and Applications Sattelite Conference, August 14-17, 2002, Quingdao, China.

• Международная конференция «Логика, теория игр и социальный выбор», 21-24 июня 2001 года, факультет прикладной математики - процессов управления, С.-Петербургский государственный университет, Институт экономики и математики РАН, Санкт-Петербург, Россия.

• Second Tvvente Workshop 19-21 June, 2002 on Cooperative Game Theory join with Dutch-Russian Symposium, Faculty of Mathematical Sciences, University of Twente at Enschcde, The Netherlands.

• International Conference «Game Theory and Management», 28-29 июня 2007 г., Санкт-Петербург, Россия.

• XXXVII международная научная конференции «Процессы управления и устойчивость», 11-13 апреля 2006, факультет прикладной математики - процессов управления, Санкт-петербургский государственный университет, Санкт-Петербург.

Публикации. По результатам выполненных исследований опубликовано 4 печатные работы.

] Lezhnina Е. and Yanovskaya Е. The axiomatisation of Least Соте and connected Solutions // Proceedings Volume ISM 2002 GTA, Quingdao: Quingdao University, P.R.China. 2002. P. 405-407.

2. Лежнина E.A. Нормированное наименьшее с-ядро в кооперативных играх // Процессы управления и устойчивость: Труды 37-й международной научной конференции аспирантов и студентов / Под ред. А.В. Платонова, Н.В. Смирнова. - СПб.:Изд-во С.-Петерб. Ун-та, 2006. С. 578-585.

3. Е. Lezhnina. An Axiomatization of the Normalized Solutions // Game Theory and Management. Collected abstracts of papers presented on the International Conference Game Theory and Management / Editors Leon A. Petrosjan, Nikolay A. Zenkevich - SPb.: Graduate School of Management SpbU, 2007. P. 77-78.

4. Лежнина E.A. Свойство подтверждения и аксиоматизация наименьшего ядра//Вестник СПбГУ. Сер. 10. 2010, вып.1. С. 50-64.

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать15.11.10 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л.1. Тираж 100 экз., Заказ № 1141/с 198504, СПб, Ст. Петергоф, ул. Ульяновская, д. 3, тел. 929-43-00.

Введение

Глава 1. Решения кооперативных игр с фиксированным множеством игроков, с-ядро.

1.1. Основные свойства решений для классов игр с фиксированным множеством игроков.

1.2. с-ядро.

1.3. Наименьшее с-ядро, пред п-ядро и промежуточные решения.

Глава 2. Аксиоматическая характеризация наименьшего с-ядра.

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

3.1. Определения.

3.2. Нормированное пред п-ядро.

3.3. Нормированное наименьшее с-ядро.

3.4. Аксиоматическая характеризация нормированного наименьшего с-ядра.

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

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

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

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

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

Научная новизна. Большинство известных аксиоматизаций используют свойство согласованности решений. Свойство согласованности говорит о том, что если часть игроков уходит из игры с выигрышами, предписываемыми им выбранным правилом (решением), то оставшиеся игроки в оставшейся (редуцированной) игре должны делить выигрыш по тому же правилу. Существуют разные подходы к тому, как изменяется характеристическая функция после ухода игроков.Эти подходы дают разные определения редуцированных игр и разные свойства согласованности. Наименьшее ядро, которое занимает «промежуточное положение» между с-ядром и п-ядром, не является согласованным, его аксиоматизации не было получено до последнего времени. Однако, существует еще одно свойство, связанное по смыслу с согласованностью. Им является свойство подтверждения. Предположим, часть игроков решила покинуть игру. Оставшиеся игроки в усеченной игре делят выигрыш в соответствии с тем же решением. Тогда вектор выигрышей, составленный из вектора выигрышей ушедшей коалиции и усеченного соответствующим образом вектора исходной игры будет тоже принадлежать решению исходной игры. Свойство подтверждения до настоящего времени применялось только для одной из характеризаций пред п-ядра [5, 6]. В диссертации получена аксиоматизация нескольких решений кооперативных игр с использованием свойства подтверждения.

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

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

Наименьшее с-ядро характеризуется как максимальное по включению решение для класса игр 0 с универсальным бесконечным множеством игроков Л7", удовлетворяющее аксиомам непустоты, ограниченности, ковариантности относительно сдвига, независимости от сдвига, подтверждения и макс-инвариантности.

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

Нормированное n-ядро является единственным значением, удовлетворяющим аксиомам ковариантности, анонимности и согласованности при определении редуцированной игры формулой (3.3).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и конгрессах:

1. Международная конференция «Логика, теория игр и социальный выбор», 21-24 июня 2001 года, факультет прикладной математики - процессов управления, Санкт-Петербургский Государственный Университет, Институт Экономики и Математики РАН, Санкт-Петербург, Россия.

2. International Congress of Mathematicians, Game Theory and Applications Sattelite Conference, August 14-17, 2002, Quingdao, China.

3. Second Twente Workshop 19-21 June, 2002 on Cooperative Game Theory join with Dutch-Russian Symposium, Faculty of Mathematical Sciences, University of Twente at Enschede, The Netherlands.

4. XXXVII международная научная конференции «Процессы управления и устойчивость», 11-13 апреля 2006, факультет прикладной математики - процессов управления, Санкт-петербургский государственный университет, Санкт-Петербург.

5. International Conference «Game Theory and Management», 28-29 июня 2007 г., Санкт-Петербург, Россия.

Публикации. Материалы диссертации опубликованы в 4 печатных работах, из них 1 статья в рецензируемом журнале [53], 1 статья в сборнике трудов конференции [52] и 2 тезиса докладов [24, 25].

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающего 63 наименований. Объем работы составляет 83 страницы текста.

Заключение

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

Применяя лексикографическую минимизацию векторов эксцессов (по векторам выигрышей), получаем различные решения: на первом шаге - наименьшее ядро 1/С(ЛГ, г>).

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

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

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

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

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

1. Aumann R. J., Mashler M. The bargainingse for cooperative games // 1.: M.L. Dresher, L.S. Shapley, A.W. Tacker, eds. Advances in game theory. (Annals of Mathematical Studies, vol. 52). Princeton. N.J.: Princeton Univ. Press. 1964. P.443-476.

2. Billera L.J. A note on a kernel and the core for games without side payments // Techn. Rep. 152, Dept. of Operat. Research. Cornell University. Ithaca, New York. 1972.

3. Billera L.J., McLean R.P. Games in support function form: an approach to the kernel of NTU games // In: N.Meggido, ed., Essays in game theory in honor of Mochael Maschler. NY: Springer. 1994. P. 39-49.

4. Billera L.J. Some theorems on the core of an N-person game without side payments // SIAM J. Appl. Math. Vol. 18. 1970. P.567-579.

5. Bondareva, O.N. The Nucleolus of a Game without Side Payment. 1989. Working Paper No 176, Institute of Mathematical Economics, Bielefeld University, Germany.

6. Castaing, C., Valadier M. Convex Analysis And Measurable Multifunctios. 1977. Lecture Notes in Mathemetics, 580, Berlin-Heidelberg-NY.: Springer-Verlag.

7. Davis M.,Maschler M. The kernel of a cooperative game. Naval Ras. Logist. Quart., 12, 1965, 223-259.

8. Derks J., Haller H. Weighted nucleoli// International Journal of Game Theory. 1999.-28.- N2.- C.173-188.

9. Dragan I. New mathematical properties of the least square value. Technical Report 308, Departament of Mathematics, University of Texas, U.S.A. 1996.

10. Driessen T.S.H. A survey of consistency properties in cooperative game theory // SIAM Review, 1991, 33, 43-49.

11. Dubey P., Neyman A, and R.J. Weber. Value theory without afficiency // Mathemetics of Operation Research, 1981, 6, 122-128.

12. Dutta B. The egalitarian solution and the reduced game properties in convex games // Int. J. Game Theory. Vol.19. 1990. P. 153-159.

13. Feldman B. The proportional value of a cooperative game. Mimeo. Seudder Kemper Investments, Chicago. 1999.

14. Fiagle, U., Kern, W. and W. Hochstatter. The Nucleón of Cooperative Games and an Algorithm for Matching Games // Mathematical Programming, 1998, 83, 195-211.

15. Greenberg J. Cores of convex games without side payments // Math. Oper. Res. Vol. 10. 1985. P. 523-525.

16. Harsanyi J.C. A bargaining model for the cooperative n-person game // In: A.W. Tucker, R.D. Luce eds., Contributions to the theory of games, 4 (Annals of Math. Studies. Vol. 40). Princeton: Princeton Unov. Press. 1959. P. 325-355.

17. Hart S., Mas-Colell A. Potential, value, and consistency // Econometrica. Vol. 64. N 2. 1989. P. 357-380.

18. Kalai E. Excess functions, nucleolus, kernel and -core of non-sidepayments cooperative games. Technical Report. N 12, Department of Statistics, Tel-Aviv University. 1973.

19. Kalai E. Excess functions for cooperative games without payments // SIAM J. Appl. Math. Vol. 29. N 1. 1975. P. 60-71.

20. Kalai E., Samet D. Weigted Shapley value: Essays in honor of Lloyd S. Shapley. Cambrige: Cambrige University Press. 1988. P. 83-100.

21. Keiding H.(1986). An Axiomatisation of the Core of a Cooperative Game // Economics Letters. 20. 111-115. 1986.

22. Kohlberg E. On the nucleolus of a characteristic function game// SIAM Joutnal of Applied Mathematics. 1993 20 - C.62-66.

23. Kohlberg E. The nucleolus as a solution of a minimization problem // SIAM J. Appl. Math. Vol. 23. 1972. P. 34-39.

24. Lezhnina E. and Yanovskaya E. The axiomatisation of Least Core and connected Solutions //Proceedings Volume ISM 2002 GTA, Quingdao: Quingdao University, P.R.China. 2002. P. 405-407.

25. Maschler M., Peleg B., Shapley L. Geometric properties of the kernel, nucleolus and related solution concepts // Math. Oper. Res. Vol. 4. 1979. P. 303-338.

26. Maschler M., Potters J.A.M., Tijs S. The general nucleolus and the reduced game property // Peleg B. (1985). An axiomatisation of the core, Vol. 21. 1992. P. 85-106.

27. Moulin H. Axioms of cooperative decision making. Econometric Society Monographs 15, Canbrige University Press. 1988.

28. Myerson R. Game theory. Anaysis of conflict. Harvard Univ. Press. 1991.

29. Orshan G. The prenucleolus and the reduced game property: Equal treatment replaces anonymity.// International Journal of Game Theory. 1993.-22.-C.241-248.

30. Orshan G., Sudholter P. Reconfirming the prenucleolus// Mathenatics of Operations Research. 28(2):283-293. 2003.

31. Maschler M., Owen G. The consistent Shapley value for games without side payments // In: R. Selten , ed., Rational interaction. New York: Springer. 1991. P. 5-12.

32. Peleg B. An axiomatisation of the core // In: R.J. Aumann, S. Hart, eds., Handbook of game theory with aconomic applications. Vol. 1. Amsterdam: Elsevier. 1992. P. 398-412.

33. Peleg B. An axiomatisation of the core of cooperative games without side-payments // J. Math. Econ. Vol. 14. 1985. P. 203-214.

34. Peleg B. An Axiomatization of the Core of Market Games, Mathematics of Operations Research, 1989, 14, 448-456.

35. Peleg B. On the Reduced Game Property and its Converse. Internat. J. Game Theory, 1986, 15, 187-200. A Correction (1987) Internat. J. Game Theory, 16.

36. Peleg B., Sudholter P. Introduction to the theory of cooperative games. Boston, Dordreht, London: Kluwer Acad. Publ. 2003.

37. Potters J.,Tijs S. The nucleolus of matrix games and other nucleoli// Mathematics of Operations Research. 1992.-17 C. 164-174.

38. Rosenmuller J. The theory of games and markets. 2nd ed. Amsterdam: North-Holland Publ. Co. 1981.

39. Schmeidler D. The nucleolus of a characteristic function game. SIAM J. Appl. Math., 1969, 17, N6, 1163-1170.

40. Shapley L.S. On balanced sets and cores // Naval Res. Logist. Quart. Vol. 14. 1969. P. 453-460.

41. Shapley L.S., Shubik M. Quasi-Cores in a Monetary Economy with Nonconvex Preferencec. Econometrica, 1966, 34, 805-827.

42. Sudholter P. Independence for characterizing axioms of the prenucleolus // Working paper 220, Institute of Mathematical Economics, University of Bielefeld. 1993.

43. Tadenuma K. Reduced games, consistency, and the core // Int. J. Game Theory. Vol. 20. 1992. P. 325-334.

44. Thompson W. Consistent allocation rules. Economics Department, University of Rochester. 2003. 202 p.

45. Yanovskaya E. Consistency for proportional solutions // Logic, Games, and Social Theory. Extended Abstracts of the Intern. Conf. St.Petersburg. 2001. P. 249-253.

46. Yanovskaya E. Strongly consistent solutions to balanced games // International Game Theory Review, 1, 63-85. 1998.

47. Бондарева О.Н. Некоторые применения методов линейного программирования к теории кооперативных игр // Проблемы кибернетики. Вып. 10, М.: Физматгиз. 1963. С.119-140.

48. Вилков В.Б. N-ядро в кооперативных играх без побочных платежей //Ж. вычисл. мат. и мат. физ. Т. 14. 1974. Вып. 5. С. 1327-1331.

49. Воробьев. H.H. Коалиционные игры // Теория вероятн. и ее прим. Т. 12. 1967. Вып. 2. С. 289-306.

50. Воробьев H.H. Теория игр для экономистов-кибернетиков М.: Наука. 1985.

51. Лежнина ЕА. Свойство подтверждения и аксиоматизация наименьшего ядра // Вестник СПбГУ. Сер.10. 2010, вып.1, стр. 50-64.

52. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир. 1985.

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

54. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

55. Печерский СЛ. О значении Шепли для игр без побочных платежей: аксиоматический подход // Экономико-математические исследования: математические модели и информационные технологии. СПб.: Наука. 1978. С.65-82.

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

57. Печерский С.Л., Яновская Е.Б. Трансферабельные значения для игр с нетрансферабельными полезностями // Экономические исследования: теория и приложения. СПб.: Европейский университет с

58. Печерский С.Л., Яновская Е.Б.Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европ. уп.-та в С.-Петербурге. 2004.

59. Розенмюллер И. Кооперативные игры и рынки. М.: Мир. 1974.

60. Соболев А.И. Характеризация принципов оптимальности в кооперативных играх посредством функциональных уравнений // Мат. методы в социальных науках. Вып. 6. Вильнюс: Ин-т математики и кибернетики АН Лит. ССР. 1975. С.94-151.

61. Яновская Е.Б. Аксиоматическая характеризация редуцированных игр // Вопросы механики и процессов управления. Сер. Управление в социально-экономических системах. СПб.: С.-Петербургский Гос. Университет, вып. 20. 2002.1. СПб. 2000. С. 310-349