Супераддитивность рациональной характеристической функции ТП-кооперативной игровой модели
Акимова Арина Николаевна,
Мельников Валерий Викторович,
соискатели Санкт-Петербургского государственного университета.
- Построение ТП-кооперативной игровой модели и свойство супераддитивности
Приведем теоретическое описание ТП-кооперативной игры. Пусть
— множество игроков. Любое непустое
подмножество 
называется коалицией игроков. Каждой
коалиции S ставится в соответствие число V(S), представляющее
собой гарантированный выигрыш (или затраты) коалиции S. Полученная
функция множеств V(S), с естественным
условием 
называется характеристической функцией
игры, а пара (N,V) — кооперативной игрой с трансферабельной полезностью
(или ТП-кооперативной игрой, или ТП-игрой). Для определенности далее значение V(S)
будет интерпретироваться как затраты коалиции S.
В прикладных задачах теории ТП-кооперативных игр при построении функции V(S) применяется подход, который можно разбить на два этапа.
1.
Для
каждого игрока i определяется функция затрат как функция нескольких
переменных 
, где 
–
стратегия i–го игрока.
2. Характеристическая функция V(S) игры строится как
, (1)
т.е. это минимальное значение затрат, которое может гарантировать себе коалиция S, не координируя свои действия с другими игроками. Заметим, что при этом считается, что игроки, не входящие в коалицию S, стараются максимизировать затраты этой коалиции, т.е. действуют наихудшим для S образом [3], (см. также [1, 4]).
Приведем определение супераддитивности для характеристической функции затрат.
Определение 1. Характеристическая функция затрат V(S)
называется супераддитивной, если для всех коалиций S, T таких, что 
выполняется соотношение
. (2)
Свойство супераддитивности интерпретируется как потенциальная возможность объединения игроков в большую коалицию N, так как N может гарантировать наименьшие суммарные затраты своим членам по сравнению с суммарными затратами любого разбиения этой коалиции на более мелкие группы.
Доказано, что характеристическая функция (1) является супераддитивной [3].
2. Условие супераддитивности рациональной харатеристической функции частного вида
Предположение о возможности использования игроками из коалиции (N\S) стратегий, максимизирующих затраты коалиции S, может натолкнуться на возражение о неразумности таких действий, поскольку они могут повлечь за собой ущерб собственным интересам игроков из (N\S).
Для устранения этого противоречия можно использовать другой подход, который учитывает рациональность действия игроков, даже если они не являются членами коалиции S.
Обозначим через 
стратегию игрока j в
том случае, если он не вступает в коалицию с другими игроками, а действует,
исходя из собственных интересов. Будем называть такую стратегию рациональной.
Заметим, что определить, какие именно стратегии игрока j рациональны,
можно только в условиях конкретной модели.
Определение 2. Характеристическую функцию
, (3)
где — рациональная
стратегия игрока j, будем называть рациональной.
Для того чтобы в ТП-игре (N,V) с данной характеристической функцией была возможна кооперация всех игроков, необходимо установить условия, при которых функция (3) является супераддитивной.
Так как рациональность стратегий игроков, не входящих в коалицию S, зависит от игровой модели, то установить является ли рациональная характеристическая функция (3) в общем виде супераддитивной не представляется возможным. Но можно выделить класс ТП-игр с рациональной характеристической функцией специального вида, для которой нетрудно получить достаточные условия супераддитивности. Отметим, что известны модели с подобной характеристической функцией. [2]
Рассмотрим класс ТП-игр, в котором рациональную характеристическую функцию можно представить в виде суммы
, (4)
где функция 
зависит только от действий
игроков 
, а функция 
зависит
только от действий игроков j, не входящих в коалицию S.
Пусть 
— стратегия игрока , минимизирующая затраты коалиции S:
. (5)
Тогда характеристическую функцию (4) можно записать как
. (6)
Для характеристической функции в форме (6), условие супераддитивности (2) можно переписать в виде:
(7)
где 
для , 
для 
и 
для 
определяются следующим образом:
(8)
3. Достаточные условия супераддитивности рациональной характеристической функции частного вида
Из (7) и (8) непосредственно вытекают следующие достаточные условия супераддитивности характеристической функции (6).
Утверждение 1. Для того чтобы характеристическая
функция (6) удовлетворяла условию супераддитивности (7), достаточно, чтобы для
любых 
выполнялись условия: 
для всех , 
для всех и 
для всех .
Замечание 1. Условие в утверждении
1 эквивалентно условию супераддитивности для функции G: 
для всех.
Утверждение 2 (сильное условие супераддитивности). Для
того чтобы характеристическая функция (6) удовлетворяла условию
супераддитивности (7), достаточно, чтобы для любых
(9)
Замечание 2. В формуле (9) условия 
и 
являются
условиями убывания функции F при расширении коалиции игроков.
Утверждение 3 (слабое условие супераддитивности). Пусть
существует подмножество игроков 
(и/или 
) такое, что для каждого 
(и/или 
) выполняется
(и/или 
), а
для 
(и/или 
)
выполняется 
(и/или 
).
Тогда условие супераддитивности (7) имеет место, если 
,
и 
для
любых .
Замечание 3. В утверждении 3 знак можно интерпретировать следующим образом:
- если для выполняется 
(), то
игрок i положительно (отрицательно) влияет на слияние коалиций S
и T и создание коалиции 
;
- если для выполняется 
, то игрок i является безразличным
к слиянию коалиций S и T (игрок-»болван»).
Замечание 4. Численное значение можно интерпретировать как заинтересованность
игрока i в слиянии коалиций S и T и формировании коалиции .
Замечания 3 и 4 дают возможность для выделения игроков, в наибольшей степени влияющих на образование коалиций (заинтересованных в кооперации) и игроков противодействующих интеграции. Если предположить, что коалиция будет приглашать в свои ряды игроков, которые привнесут наибольший вклад в это объединение, то можно выстроить цепочку последовательных вхождений игроков в коалицию и формирование максимальной коалиции.
Литература
1. Васин А.А., Морозов В.В. – «Введение в теорию игр с приложениями в экономике». – М.: 2003.
2. Melnikov V.V., – «A model of collective safety system in ecology». Preprints of the eleventh IFAC International workshop «Control applications of optimization». – St.Petersburg. 2000.
3. Нейман Дж. фон, Моргенштерн О. – «Теория игр и экономическое поведение» (перев. с англ. под ред. и с доб. Н.Н.Воробьева). – М.: «Наука», 1970.
4. Петросян Л.А., Зенкевич Н.А., Семина Е.А. – «Теория игр». – М. 1998.
Поступила в редакцию 08.01.2015 г.