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

• Лежнина, Елена Александровна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Лежнина, Елена Александровна

Введение

Глава 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/С(ЛГ, г>).

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Лежнина, Елена Александровна, 2010 год

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