Экономические науки/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.