Экономические науки/8. Математические методы в экономике
К.ф.-м.н.
Зинченко А.Б., Гречко А.С., к.т.н. Мермельштейн Г.Г.
Южный
федеральный университет. Россия
Кооперативные ТП игры с одноэлементным С-ядром
Кооперативная игра с трансферабельной
полезностью (ТП игра) , где
- множество
агентов,
- функция множества, возникает
в ситуациях, участники которых, объединяясь, получают дополнительную прибыль. Это
наиболее популярная и простая кооперативная модель. При фиксированном
игра
отождествляется с
. Далее предполагается, что
,
,
. Через
обозначено множество таких
игр. Для практического использования ТП игры нужно определить функцию
, выбрать принцип формирования
коалиций и концепцию решения. В экономических задачах, как правило,
наиболее выгодно объединение всех игроков. Анализ соответствующей игры
начинается с проверки непустоты ее
-ядра (core)
,
где ,
. Несмотря на существование
игр с парадоксальными
-ядрами [1], это основная концепция устойчивости коалиции
. При любом дележе
ни одна из коалиций
не может
гарантировать своим агентам суммарный выигрыш, превышающий
. Если
и участников игры устраивает принцип «справедливости», реализованный
-ядром, то возникает еще одна проблема - выбор единственного
вектора индивидуальных выигрышей
. Задача не
тривиальная, т.к.
-ядро может быть относительно большим.
Считается «идеальным», когда , поэтому
актуальна проблема явного описания классов игр с одноэлементным
-ядром и соответствующих дележей
. Для некоторых
практически важных игр эта задача решается
просто. Например, в игре большого босса (big boss game) [2] с игроком 1 в качестве босса
-ядро не пусто и ограничено парами параллельных гиперплоскостей
,
где - вклад игрока
в коалицию
. Следовательно, в игре большого босса
тогда и только тогда, когда
,
.
Из вложения
-ядра игры
во множество дележей
и множество
двойственных дележей
, следует, что
,
, для всех
. Если
, то условие
,
, достаточно, но не необходимо для существования единственного
дележа
.
Для описания всех игр 3-4 лиц с одноэлементным -ядром и некоторых классов таких игр с
участниками, мы будем
использовать понятие сбалансированного множества. Пусть
- многогранник, заданный
системой
и
- множество его крайних
точек. Набор
коалиций
будем называть минимальным
сбалансированным множеством (м.с.м.), если существует такая точка
, что
,
, и
,
. Вектор
, где
, назовем весом
. В литературе имеются
другие (эквивалентные) определения. Обозначим:
- семейство всех м.с.м.
,
- подмножество таких
, что
. Известно [3]-[4],
что
тогда и только тогда, когда игра
сбалансирована, т.е.
,
. (1)
Если , то
тогда и
только тогда, когда, существует
, для которого (1) выполняется как равенство [4]. Рассмотрим множества
,
,
где ,
. Они принадлежат
[5] и попарно не
пересекаются. Определив
и используя (1), мы
получаем следующую теорему.
Теорема 1. Если ,
,
,
,
и
удовлетворяет хотя бы
одному из равенств
(2)
то -ядро игры состоит из единственного дележа.
Заметим, что при вторая часть условия
(2) выделяет известный класс несущественных игр, в которых
-ядро совпадает с множеством дележей
, где
. Дележ
называют «точкой разлада»
(каждый игрок получает выигрыш, который может обеспечить себе без кооперации с
другими агентами). Первая часть условия (2) при
определяет класс игр,
в которых
-ядро совпадает с множеством двойственных дележей
, где
. В
выигрыш каждого игрока равен его вкладу в коалицию
.
Так как и
резко возрастают при
увеличении
, семейства
и
разбивают на классы
эквивалентности
и
, каждый из которых содержит м.с.м., отличающиеся
перестановкой игроков. Представители
всех классов эквивалентности семейств
и
опубликованы во многих работах. Известно, что
состоит из двух одноэлементных
классов
,
.
Семейство состоит их пяти классов
,
,
,
,
а представителем
пятого класса является м.с.м. . Несущественные игры не имеют
практического значения, поэтому в следующей теореме они исключены.
Теорема 2. Существенная сбалансированная игра (
) имеет одноэлементное
-ядро тогда и только тогда, когда она удовлетворяет условию
(хотя бы
одному из условий
,
(3)
или условию,
получающемуся из (3) перестановкой игроков).
Представители классов эквивалентности семейства найдены, но к соответствующим
публикациям нет свободного доступа. В связи с этим, были проведены вычисления для
и
при
. Существует несколько методов нахождения крайних точек многогранника.
Наиболее известны: метод двойного описания [6] и модифицированный метод
перебора базисных решений [7]. Соответствующие программы [8-9] доступны в
Интернете, используют общий формат входных и выходных данных. Каждый из методов
имеет свои преимущества и недостатки. Например, метод двойного описания требует
большого объема оперативной памяти. Эксперимент показал, что уже для
использовать соответствующую
программу [8] невозможно. Программа [9] лишена этого недостатка (каждая найденная
крайняя точка пишется в выходной файл и не хранится в памяти), что позволяет решать
задачи большой размерности или, по крайней мере, находить часть вершин многогранника.
Эксперимент проводился на машине с процессором Intel Core i5, 8 ГБайт оперативной памяти, OC Mac OS X 10.7.4 с использованием одного ядра и потока команд
процессора. Была написана программа (язык С++), которая: генерирует
входной файл для многогранника , обращается к [8] или [9], преобразует выходной файл с крайними
точками
в файл минимальных
сбалансированных множеств и их весов, разбивает
на классы, выдает
количество классов, их мощности, а также представителей классов эквивалентности.
Аналогичная программа создана для получения сведений о семействе
м.с.м. максимальной
размерности. В таблице 1, содержащей некоторые сведения об эксперименте, используются
обозначения:
- время поиска всех
элементов
,
(
) – время поиска представителей классов эквивалентности
семейств
(
),
(
) - количество классов в
(
). Было также получено, что
. Нахождение всех элементов
потребовало 9 дней 10
ч. 37 мин. 50 сек.
Таблица 1
Результаты
вычислительного эксперимента
|
3 |
4 |
5 |
6 |
|
5 |
41 |
1291 |
200213 |
|
0 сек |
0 сек |
1 сек |
12 мин. 5 сек. |
|
3 |
9 |
44 |
447 |
|
0 сек |
0 сек |
5 сек |
38 мин. 22 сек. |
|
2 |
28 |
976 |
15934 |
|
2 |
5 |
28 |
375 |
|
0 |
0 |
5 сек |
5 мин 1 сек |
Результаты проведенного эксперимента позволяют записать необходимые и
достаточные условия одноэлементности -ядра сбалансированных игр пяти и шести лиц, но желательно
иметь их в компактном виде. Например, для
условие (2) включает
равенства, соответствующие м.с.м. из 6 классов эквивалентности семейства
. Получены также формулы, «охватывающие» дополнительные 22
класса этого семейства.
Литература:
1. Zinchenko A.B. On polytope of (0-1)-normal big boss games: redundancy and extreme points //
Contributions to game theory and management. Collected papers of the Fifth International
Conference «Game Theory and Management». SPb: Graduate School of Management.
SPbU. 2012. V. 5. P. 386-397.
2.
Muto S., Nakayama M., Potters J., Tijs S. On big boss games // The
Economic Studies Quarterly. 1988. № 39. P. 303-321.
3. Shapley L. S. On
balanced sets and cores // Naval Research Logistics Quarterly. 1967. V. 14. P.
453-460.
4.
Бондарева О.Н. Некоторые
применения методов линейного программирования к теории кооперативных игр // Проблемы
кибернетики. 1963. Вып. 10. М.: Физматгиз. С. 119-140.
5.
Зинченко А.Б., Тенищев
И.Е. Сбалансированные множества коалиций классической кооперативной игры //
Известия вузов. Северо-Кавказский регион. Естественные науки. 2008. № 2. С. 8-12.
6.
Fukuda K., Prodon A. Double description method revisited // Lecture
Notes in Computer Science. V. 1120. Springer-Verlag, 1996. P. 91-111.
7.
Avis D. lrs: A Revised Implementation of the Reverse Search Vertex
Enumeration Algorithm // Polytopes – Combinatorics and Computation. DMV Seminar
Band 29, Birkhauser-Verlag, 2000. P. 177-198.
8. Cdd
Home Page: http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html.
9. Lrs Home Page: http://cgm.cs.mcgill.ca/~avis/C/lrs.html.