Многошаговые игры с полной информацией и переменным коалиционным разбиением тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Мамкина, Светлана Игоревна

• Мамкина, Светлана Игоревна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Мамкина, Светлана Игоревна

Введение.

Глава 1. Динамическая игра с переменным коалиционным разбиением.и

§ 1.1. Определение динамической игры с переменным коалиционным разбиением.и

§ 1.2. Алгоритм построения решения.

§ 1.3. Построение характеристических функций вспомогательных кооперативных игр.

§ 1.4. Пример.

Глава 2. Структура множества всех ситуаций абсолютного равновесия по Нэшу в играх с полной информацией.

§ 2.1. Абсолютные равновесия в стратегиях поведения.

§ 2.2. Описание всего класса абсолютных равновесий.

§ 2.3. Индифферентное равновесие в позиционных играх с полной информацией.

Глава 3. Построение единственного решения в игре с переменным коалиционным разбиением на основе индифферентного равновесия.

§3.1. Модифицированная игра с переменным коалиционным разбиением.

§ 3.2. Основные функциональные уравнения для построения единственного решения с использованием индифферентного равновесия.бо

Глава 4. Стратегическая устойчивость решений в играх с переменным коалиционным разбиением.

§ 4.1. Распространение решения на все позиции оптимального

ПуЧКа.

§ 4.2. Позиционная состоятельность решений и регуляризация.

§ 4.3. Индивидуальная секвенциальная рациональность решений.

§ 4.4. Квазипоследовательное равновесие и коррелированное квазипоследовательное равновесие в играх с переменным

I коалиционным разбиением.

Введение диссертации (часть автореферата) на тему «Многошаговые игры с полной информацией и переменным коалиционным разбиением»

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

В кооперативных моделях изначально предполагается, что игроки объединяются в большую коалицию, включающую всех игроков, с целью максимизации общего выигрыша. При этом различаются два типа задач: задачи с трансферабельной и нетрансферабельной полезностью. В первом случае речь идет о векторной оптимизации выигрыша, во втором максимизируется сумма выигрышей игроков. Основными принципами оптимальности в кооперативных моделях являются: С-ядро, вектор Шелл и, ЫМ-решение, вектор Банзафа, ядрышко и др. Указанные принципы оптимальности относятся к так называемым «нормативным» принципам. Однако в практических задачах трудно предположить возможность объединения участников конфликта (игроков) в одну большую коалицию с одной стороны, и также является не достаточно реальным предположение о том, что никакая кооперация между игроками невозможна. Поэтому наиболее актуальной является задача, в которой допускается объединение игроков в коалиции, образующих некоторое разбиение всего множества игроков.

Впервые исследованием таких задач занимался Оуэн в 1977 году ([33-34]). Он обобщил понятие вектора Шепли для игр с коалиционными разбиениями, введя так называемый вектор Оуэна-Шепли. При вычислении этого вектора предполагалось, что элементы коалиционного разбиения - коалиции, действуя как игроки, могут объединяться в большую коалицию. И для нахождения выигрышей коалиций использовался вектор Шепли. Далее, внутри каждой коалиции допускалась возможность объединения игроков в подкоалиции, и для нахождения коалиционного дележа использовался вектор Шепли. Таким образом, сперва вектор Шепли применялся на уровне коалиций, принадлежащих коалиционной структуре, для определения выигрышей этих коалиций, а затем вектор Шепли применялся для дележа коалиционного выигрыша. Таким образом, можно утверждать, что коалиционный вектор Оуэна, получался путем двух кратной композиции векторов Шепли.

В 1988 году Ван дер Бринк и Ван дер Лан [42] определили нормализованный вектор Банзафа, который распределяет максимальный суммарный выигрыш игроков пропорционально вектору Банзафа. Этот же подход использовался Ван дер Бринком и Ван дер Ланом в 2005 году году для нахождения решения игры с коалиционным разбиением.

Исследование статических коалиционных игр может быть найдено также в работах [ 1, 2, 20, 27, 30]. Здесь в качестве принципов оптимальности дано определение у/ устойчивой конфигурации. В 1960 г. H.H. Воробьев (см. [6 ]) ввел более общее понятие (р устойчивости, которое в 1967 г. он распространил на смешанные расширения коалиционных игр (см. [7 ]) Имеются и другие принципы оптимальности, для классических коалиционных игр: «класс разумных исходов», «замкнутый исход» и др.

В работе [ 21 ] сделана попытка распространения принципов кооперативной теории на игры с заданной коалиционной структурой.

Подробное обсуждение указанных вопросов можно найти в книгах Э. Вилкаса [3,4 ].

Однако указанные подходы (в частности, предложенный Ван дер Бринком и Ван дер Ланом, также как и подход Оуэна) предполагают возможность объединения элементов коалиционного разбиения в большую коалицию. Но это предположение не может быть во всех случаях приемлемо, поскольку сам факт возникновения коалиционного разбиения и происходит от того, что полная кооперация игроков невозможна. Поэтому более естественным является подход, при котором игра первого уровня между элементами коалиционного разбиения происходит как стратегическая игра, то есть полная кооперация коалиций как игроков не предполагается. В этом случае для этой игры в качестве принципа оптимальности может быть использовано равновесие по Нэшу [31]. А уже на втором этапе выигрыши, полученные в равновесии по Нэшу игроками коалициями, могут распределяться согласно принципам оптимальности кооперативной игры.

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

Справедливости ради следует отметить, что в работе Харшаньи и Зельтена [18 ] предложен метод трассирования для нахождения единственного равновесия по Нэшу в одновременной игре, который, хотя бы в теоретическом плане, позволяет снять проблему единственности в одновременной (статической) игре. Но указанный метод достаточно громоздок и едва ли может быть применен для игр с большим количеством участников.

По-другому обстоит дело в динамических играх с полной информацией. В игре с полной информацией всегда существует абсолютное равновесие по Нэшу в чистых стратегиях ([14,15]). И в данной диссертации нам удалось выделить единственное «индифферентное» равновесие по Нэшу в таких играх. Именно основываясь на этом, мы предложили другой принцип оптимальности для игр с переменным коалиционным разбиением и полной информацией, а именно: для игроков коалиций в качестве принципа оптимальности мы рассматриваем «индифферентное» равновесие по Нэшу, а внутри коалиции осуществляем дележ в соответствии с вектором Шепли. Получившийся в результате такой двухэтапной процедуры вектор выигрышей мы называем pms вектором.

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

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

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

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

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

Практическая ценность. Работа носит теоретическую направленность. Полученные результаты представляют теоретический и практический интерес. Основная практическая ценность определяется многочисленными применениями коалиционных игр для моделирования работы парламентов и других 8 общественных организаций, в которых возможно объединение участников в различные партии (коалиции) ([19, 23, 24, 25, 26, 28, 32, 43, 47]). Принципы оптимальности, предложенные в работе, использовались при исследовании более сложных многошаговых игр с изменяющейся коалиционной структурой.

Основные положения, выносимые на защиту.

1. Построение многошаговой игры с переменным коалиционным разбиением, и построение принципов оптимальности для многошаговой игры с переменным коалиционным разбиением.

2. Построение класса всех абсолютных равновесий по Нэшу в многошаговых играх с полной информацией. Выделение единственного абсолютного равновесия, определенного в работе как индифферентное равновесие.

3. Выделение единственно решения для многошаговой игры с переменным коалиционным разбиением.

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

5. Формулировка и доказательство теорем о реализуемости предложенных принципов оптимальности в некотором квазипоследовательном коррилированном равновесии в игре с переменным коалиционным разбиением.

Апробация работы. Результаты работы докладывались на 11-ом международном симпозиуме по динамическим играм и приложениям ISDG2004 (Аризона, США), на 1-ом семинаре Китайского отделения международного общества динамических игр (WCC2004) (Qingdao, Qingdao University, Китай), 4-й Московской международной конференции по "Исследованию операций" (ORM2004), на XXXV научной конференции "Процессы управления и устойчивость" (Санкт-Петербург), на семинаре центра теории игр при факультете ПМ-ПУ СПбГУ. Основные результаты опубликованы в работах [8], [10], [28-31].

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав (13 параграфов), списка используемой литературы. Общий объем диссертации - 104 страницы. Список используемой литературы включает 47 наименований. Работа содержит 3 рисунка.

Список литературы диссертационного исследования кандидат физико-математических наук Мамкина, Светлана Игоревна, 2005 год

1. Ауман Р., Дряз A. Coopérative Games with Coalition Structure. 1.t J. Gametheory, 1974, V.4, P.217-237.

2. Ауман P., Машлер M. The Bargaining set for coopérative games . Advanced in game theory. Ann. Math. Studies. V.52. Princeton: Princeton Univ. Press, 1964, P. 443-476.

3. Вилкас Э.Й. Оптимальность в играх и решениях. М.: Наука, 1990.

4. Вилкас Э.Й. Понятие оптимальности в теории игр. Современные направления теории игр. Вильнюс: Минтис, 1976.

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

6. Воробьев Н.Н. Устойчивые ситуации в коалиционных играх . Докл. АН СССР, 1960, Т131 №2, С.493-495.

7. Клейменов А.Ф. К кооперативной теории бескоалиционных позиционных дифференциальных игр . Докл. АН СССР, 1990, Т32 №1, С.32-35.

8. Красовский Н.Н., Субботин А.И, Позиционные дифференциальные игры. М., 1974.

9. Кун Г. У. Позиционные игры и проблемы информации. В сборнике Позиционные игры под ред. Н.Н. Воробьева, И.Н. Врублевская. М.: "Наука", 1967 г., С.13-40.

10. Льюс, Райфа. Игры и решения. М: ИЛ, 1961.

11. Мамкина С.И., Петросян Л.А. Структура множества ситуаций абсолютного равновесия по Нэшу в играх с полной информацией. Труды XXXV научной конференции "Процессы управления и устойчивость", 2004, С. 639-647.

12. Понтрягин Л.С., Болтянский В.Г., Гаикрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М., 1961.

13. Петросян Л.А., Аешин Д.А. Значение динамических игр с частичной кооперацией. Труды института математики и механики. Том 6, №1,2, Екатеринбург, 2000, С. 160-172.

14. Петросян Л.А., Зенкевич H.A., Семина Е.А. Теория игр. М: Высш. шк., 1998.

15. Петросян Л.А., Кузютин Д.В. Игры в развернутой форме: Оптимальность и устойчивость. СПб: Изд. СпбГУ, 2000.

16. Петросян Л.А., Мамкина С.И. Игры с переменным коалиционным разбиением. Вестник СПбГУ, 2004, Сер 1, Вып. 3, С.60-69.

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

18. Харшаньи Д., Зельтен Р. Общая теория выбора равновесия в играх. СПб: Эконом, шк., 2001.

19. Bettina Klaus. Coalitional Strategy-Proofness in Economies with Single-Dipped Preferences and the Assignment of an Indivisible Object. J. Games and Economics behavior. 2001, Vol. 34, 64-82.101

20. Davis M., Maschler M. Existence of Stable Payoff Configuration for Cooperative Games. Essays in Mathematical Economics in Honor of O. Morgenstern, M. Shubik ed, 1967, Princeton, P. 39-52,

21. Dragan I., Poters J., Tijs S. Superadditivity for Solutions on Coalitional Games. Libertas Mathematica 9, 1989, 101-110.

22. Fudenberg D., Tirole J. Game Theory. Mass: MIT Press, 1991.

23. Fukuda. E., Muto., Dynamic Coalition Formation in the Apex Game. Preprint version, 2004

24. Jinpeg Ma. Job Matching and Coalition Formation with Utility or Disutility of Co-Workers. J. Games and Economics behavior. 2001, Vol. 34, 83-104.

25. M. Josune Albizuri, Jose M. Zarzuelo. On Coalitional Semivalues. J. Games and Economic Behaviour, 2004, Vol. 49 №2, p. 237-245.

26. Juan Vidal-Puga and Gustavo Bergantinos. An Implementation of the Owen Value. J. Games and Economics behavior. Aug 2003, Vol. 44, №2.

27. Hart S., M. Kurz. Stable Coalitional Structures. Coalitions and Collective Action, Ed. by M.J. Holler. Wurzburg, 1984, p. 236-258.

28. Katsunori Ano, Susumu Seko, Takashi Suzuki. Nonsymmetric Indices of Power and their Applications to the House of Councilors in Japan.

29. Kuhn H.W. Extensive Games and Problem Information. Ann. Math Studies. 1953. Vol. 28, p.193-216.

30. Luce R.D. A Definition of stability for n-person games. Ann. Math, 1954, V.59, P. 357-366.

31. Nash J. Equilibrium Points in n-person Games. Nat. Acad. Sei. U.S. 36, p. 48-49.

32. Ono R., Muto. S. Party Power in the House of Councilors in Japan: An Application of the Nonsymmetric Shapley-Owen Index. J. Operations research Society of Japan, 40, p. 21-33.

33. Owen G. Game Theory. Third edition, Academic Press, 1995.

34. Owen G., Political Games. Naval Research Logistics Quarterly, 18 (1989), p. 345-355.

35. Ray D., Vohra R., A Theory of Endogenous Coalition Structure. J. Games and Economics behavior. 1999, Vol. 26, p. 286-336.

36. L.A. Petrosjan, S.I. Mamkina. Dynamic Games with Coalitional Structure. J. of Quigdao University, 2004, Vol.17, p. 38-47.

37. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Coalitional Games. Proceeding of the 4th Moscow International Conference on Operations Research (ORM2004), 2004, p. 173-175

38. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Games with Perfect Information and Changing Coalitional Structure. Poceedings of the 11th International Symposium on Dynamic Games and Applications, Tucson Arizona, 2004, Vol. 2, p. 1-15.

39. L.A. Petrosjan, S.I. Mamkina. Value for the Games with Changing Coalitional Structure. Games Theory and Applications, 2005, Vol. 10, p.141-152.

40. Shapley L.S. A Value for n-person games. In Contributions to the Theory of Games II (Eds. H. Kuhn and A.W. Tucker). Ann. Math. Stud. 28, Princeton University Press. Princeton, NJ.

41. Van Damme E.E.C. A Relation between Perfect Equilibria in Extensive form Games and Proper Equilibria in Normal Forms Games. Intern. J. Game Theory. 1984. Vol. 13, p.1-13.

42. R. Van den Brink, G. van der Laan. Axiomatization of the Normalized Banzhaf Value and the Shapley Value. Social Choice and Welfare, 15. Springer-Verlag, 1998.

43. Vazquez-Brage M., Van den Nouweland A., Garcia-Jurado I. Owen's Coalitional Values Aircraft Landing Fees . Math. Soc. Sci.34, 1997, p. 273-286.

44. Vohra R., A Theory of Endogenous Coalition Structure. J. Games and Economics behavior. 1999, Vol. 26, p. 286-336.

45. Winter E. A Value for Cooperative Games with Levels Structure of Cooperation. Int. J. Game Theory, 1992, 18, p. 27-240.

46. Winter E. The Consideration and Potential for Values of Games with Coalition Structure. J. Games and Economics Behavior. 1992, Vol. 4, p. 132-144.

47. Wojciech Olszewski. Coalition Strategy-Proof Mechanism for Provision of Excusable Public Goods. J. Games and Economics Behavior. Jan 2004, Vol. 46, №1.