Методы решения кооперативных игр и их применение тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

§ I. Классические кооперативные игры. Понятие оптимальных решений».

§ 2. Непрерывные отображения систем множеств, непрерывные отношения, их ядра и решения (гл.1 ).

§ 3, Приближенные методы нахождения ядра (гл.П)

§ Приближенные методы е кооперативных играх. Ациклические игры (гл.Ш),.

§ 3. Покрытия и их применение в кооперативных играх (гл,1У)

§ 6. Обобщение понятия покрытий. Услоеия существования решений. Решение игры четырех лиц» Пространства игр (гл.У).

ГЛАВА I. НЕПРЕРЫВНЫЕ ОТНОШЕНИЯ В ТОПОЛОГИЧЕСКИХ ПРОСТРАНСТВАХ, ИХ ЯДРА И РЕШЕНИЯ НЕЙМАНА-МЭРГЕНПГГЕРНА

§ I. Отношения. Ядро и решение Неймана-Моргенштерна

§ 2. Топологии подмножеств.

§ 3. Непрерывные отношения в топологических пространствах и их свойства.

§ 4. Связь непрерывности отношений с непрерывностью некоторых отображений.

§ 5. Устойчивость ядер и решений непрерывных отношений.

ГЛАВА П. СХОДИМОСТЬ ПРОСТРАНСТВ С ОТНОШЕНИЯМИ. ПРИМЕНЕНИЕ К БЕСКОАЛИЦИОННЫМ ИГРАМ И ЗАДАЧАМ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

§ I. Сходимость пространств с отношением.

§ 2, Сходимость и устойчивость ядер и решений.

§ 3. Сходимость бескоалиционных игр

§ 4, Устойчивость ситуаций равновесия в играх с непрерывными функциями выигрышей.

§ 5# НеКоторые классы игр с разрьтннми функциями выигрышей, шлющие ситуации равновесия

§ б. Общие многокритериальные задачи.

СЕертки критериев.

§ 7. Сходимость многокритериальных задач.

ГЛАВА Ш. ОБЩИЕ КООПЕРАТИВНЫЕ ИГРЫ

§ I. Общие кооперативные игры, отношение доминирования.

§ 2. Сходимость кооперативных игр. Условия непустоты

§ 3. -решения кооперативных игр и их сходимость, ♦ •

§ 4. Существование решений для некоторых классов игр, . •

§ 5. Ациклические игры.

§ б. Доказательство теоремы 3.5.

DIABA ГУ. МЕТОД ПОКРЫТИЙ В РАЗЛИЧНЫХ ТЕОРЕТИКО-ИГРОВЫХ ЗАДАЧАХ

§ I. Шкрытия. Условия непустоты ядра для классических кооперативных игр.

§ 2. Применение покрытий к теории -устойчивости

§ 3. Применение метода покрытий к вопросу существования решений (Д-'О -игры

§ 4. Применение покрытий к вычислению М-ядра.

§ 5. Пример выпуклой игры специального вида . 1о

§ 6, Обобщенное IV-ядро и максимальное покрытие. . . . Г

§ 7. Покрытия е играх без побочных платежей

ПЛАВА У. ОБОБЩЕННЫЕ ПОКРЫТИЯ. РЕШЕНИЕ ИГР ЧЕТЫРЕХ ЛИЦ

§ I. Обобщенные покрытия и их сеойствэ. . . Г

§ 2. Необходимые условия совпадения ядра и решения.

§ 3. Необходимые и достаточные условия совпадения ядра и решения в терминах обобщенных покрытий

§ Обобщенные покрытия и решение игры четырех лиц с непустым ядром

§ 5. Доказательство теоремы 5,3.

§ о. Пространства игр. Некоторые гипотезы.

Актуальность теории игр до недавнего времени в основном определялась тем влиянием, которое она оказывала на смежные области науки. Такие понятия теории кооперативных игр как ядро и решение Неймана-Моргенштерна получили широкое распространение в теории графов, математической статистике, теории многокритериальной оптимизации. Ядра графов, £ «базы, полный класс решающих функций являются реализациями этих понятий.

В последнее время появились и важные практические приложения теории кооперативных игр. Так Институтом Системных Исследований в Вене в 1^80 г. была закончена разработка теоретико-игровой модели распределения капиталовложений между 18 муниципалитетами юга Швеции при строительстве трубопровода для снабжения их пресной водой.

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

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

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

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

Новизна работы состоит в первую очередь в разработке новых методов теоретико-игрового анализа и введении новых понятий,таких как сходимость пространств с отношениями и обобщенные покрытия. Эти новые методы и понятия применяются в основном к уже поставленным в теории игр задачам существования ядер и решений. Большинство полученных в работе результатов являются новыми. На защиту выносятся основные результаты глав Ш,1У и У.

Структура работы следующая. Работа состоит из введения и пяти глав, главы состоят из параграфов, нумерация параграфов своя в каждой главе. Почти весь текст работы, кроме введения, разбит на леммы, утверждения или теоремы. Утверждения, обычно приводят к теоремам, но имеют и самостоятельное значение; теоремы, по мнению автора, имеют большую значимость, чем утверждения. Доказательства наиболее трудных теорем 3.5 и 5.3 вынесены в отдельные параграфы. Нумерация определений, лемм, утверждений и теорем двойная, следствия имеют простую нумерацию, отдельную для каждой теоремы, к которой они относятся. Примеры имеют сквозную нумерацию. Те утверждения, которые не принадлежат автору, не имеют нумерации, им сопоставляется либо фамилия автора, либо номер статьи, из которой они взяты. Исключением являотся утверждения § 2 гл.1, которые, хотя и получены автором, не могут считаться новыми, так как в литературе имеются весьма близкие к ним утверждения.

Список литературы содержит 97 названий.

Основные теоретике-игровые понятия, использованные в работе, можно найти в монографиях и обзорах [I5j , [28], [49j , [53j, [б2j, [80], [8Ij •

Некоторые результаты кандидатской диссертации автора, опубликованной в виде статьи [5j входят в § I гл.1У, все остальные результаты работы не входят в кандидатскую диссертацию.

Основные результаты главы I опубликованы в статьях [10] и [16] , главы II - в [IOj, [II], рб] и [18], главы Ш - в [10], [I3J, [14] и [18], главы 1У - в [3], [4], [5], [7] и [20], главы У - в [8j [18] и [19] .

1. Билингсли П. Сходимость вероятностных мер. М.: Наука, 1977, 351 с.

2. Бондарева О.Н. Теория ядра в игре гъ лиц. Вестник ЛГУ, Г96 2, -v 13, е.141-I4 2.

3. Бондарева О.Н. Некоторые теоремы теории (4) -устойчивости в кооперативных играх. ДАН СССР, 1963, т. 193, № 1,с.6Г-бЗ.

4. Бондарева О.Н. Некоторые применения линейного программирования к теории кооперативных игр. Проблемы кибернетики, 1963,А/10,1119-139.

5. Бондарева О.Н, Устойчивость в играх с i -квотой. Литовский мат.сб., 1965,т.1, Л 3,с,391-395.

6. Бондарева О.Н. О единственности решений в (п, -{) -играх. -Кибернетика , 196 9,л/4, c.118-121.

7. Бондарева О.Н. Об одном преобразовании, сохраняющем решение.В сб. Исследование операций и стат.моделирование, 1972,6.1, с.40.Л 2.

8. Бондарева О.Н», Наумова Н.И. О слабом доминировании в теории кооперативных игр. Тезисы докл. и сообщ. П Всес.конф. по теории игр, Вильнюс, 1972,с.Г7.

9. Бондарева О.Н. Ношение и ядро ациклического отношения на компакте. В сб. Успехи теории игр, Вильнюс, 1973,c.127-130.

10. Бондарева О.Н, Новый подход к бескоалиционным играм. В.сб. Исследование операций и стат.моделирование, 1973 Д2,с,53~67.

11. Бондарева О.Н, О теоретико-игровых моделях в экономике. Л.: Изд.ЛГУ, 1974 , 39 с.

12. Бондарева О.Н. Ациклические игры. Вестн. ЛГУ, 1975,л7, с, 15-22.

13. Бондарева О.Н. Конечные приближения для ядер и решений кооперативных игр. Ж.вычислима тем. и матем.физ., 1975,-16, f? 3,с. 624-633.

14. Бондарева О.Н., Вилкое В.Б., Кулаковская Т.Е., Наумова Н.И., Соколина Н.А. Обзор советских работ по теории кооперативных игр. В сб. Исследование операций и стат,моделирование, 1977 , с.81-126.

15. Бондарева О.Н. Развитие теоретико-игровых методов оптимизации в кооперативных играх и их применение к многокр игери>альным задачам. ~ В кн. Современное состояние теории исследования операций, М.: Наука, 1979,с.150-Г72.

16. Бондарева О.Н. Взшение классических кооперативных игр четырех лиц с непустым ядром (общий случай). Вестник ЛГУ, 1979,л119,с. 14-19.

17. Бондарева О.Н. Одна производственная модель и вычисление fV-ядра с помощью покрытий. Кибернетика, 1932,с. 101-104

18. Боренштейн О.Ю. Об одной теореме отделимости с приложением к принципу оптимальности по Нэшу. В сб.: Теоретико-игровые вопросы принятия решений. М., 1973, с.5-5.

19. Боренштейн O.IO. К вопросу о разрешимости бескоалиционных игр Ю, лиц. JLlot-ft. O^jvuzkiaibfo'cbch. il iiativt. j 1975д.б, № 4,с.627-639.

20. Вальд А. Статистические решающие функции. В сб.: Позиционные игры. М., 1967, с.300-522.

21. Васильев В.А. Полиномиальные ядра кооперативных игр.В кн.: Оптимизация, вып.21 (33). Новосибирск, 1973, с.5-28.

22. Вилков В.Б. Кооперативные игры без побочных платежей на многогранниках, В кн. Успехи теории игр. Вильнюс, 1973, с. 131-13 4.

23. Вилков В.Б. Некоторые принципы оптимальности е играх без побочных платежей. Дисс.канд.физ.-мат.наук, -Ленинград, 1974. 113 с.

24. Вилков В.Б., Кулаковская Т.Е. О ядре ретзнии в кооперативных играх без пойочных платежей. - Вестник ЛГУ, 1975, № 13, с. 14-13.

25. Воробьев Н.Н. Теория игр. Лекции для экономистов-кибернетиков. -Л.: Из д. ЛГУ, 1974, Г60 с.

26. Гликсберг HJI. Дальнейшее обобщение теоремы Какутани о неподвижной точке с приложением к ситуациям равновесия в смысле Нэша. В сб. Бесконечные антагонистические игры, - М.: Ф.М., 1963,с,497-503.

27. Карлин С. Математические методы в теории игр, программировании и экономике. М,: Мир, 1964, 333 с.

28. КонурбаеЕа Б.М. Двойственная кооперативная игра, В сб.Оп-тимиз. и моделир. сложных систем, - Алма-Ата, Наука Каз. ССР, 1976 33-40.

29. Кулаковская Т.Е. Достаточные условия совпадения ядра и решения в кооперативной игре. Лит.Мат.сб., 1969,г.9, jj? 2,с,424-425

30. КулакоЕская Т.Е. Необходимые и достаточные условия совпадения ядра и решения в классической кооперативной игре. ДАН СССР, 1971,т:199, с1015-10Г7.

31. Кулаковская Т.Е. Достаточные условия существования ядра-решения е кооперативной игре. В сб.Исследование операций и статистическое моделирование, I972,&I,c.I06-II2,

32. Кулаковская Т.Е. О решении одного класса игр четырех лиц. -В кн. Теория игр. Ереван, 1973,с 216-219,

33. Кулаковская Т.Е. Ядро-решение для игр в форме функции разбиения. В сб.Исс лед.операций и ста т.моделирование, 1974,1.2, с. 67-74.

34. Кулаковская Т.Е. Классические принципы оптимальности для бесконечных кооперативных игр. В кн.: Современные направления теории игр. Вильнюс, 1976, с.94-108.

35. Кулаковская Т.Е. Рёшение одного класса кооперативных игр четырех лиц с непустым ядром. Вестник ЛГУ, 1979, II 19, с,42-47.

36. Куратовский К. Топология т.1- М.: Мир, 1966, 594 е., т.П М,: Мир, 1969, 624 с.

37. Лыос Р.Д., Рзйфа X. Игры и решения. М.: ИЛ, 1961, 642 с.

38. Макаров В.Л., Рубинов A.M. Уатематическая теория экономической динамики и раЕНОЕесия. Мж: Наука, 1973, 335 с.

39. Малафеев О.А. Естественная метрика и ситуации раЕНОЕесия в бескоалиционных играх. Вестник ЛГУ, £973, !§ 19, с. 143-145.

40. Меньшикова О.Р, 0 вычислении обобщенного N -ядра. Ж.вычислит.матем. и матем.физ., 1976, т.16, № 5, с.1121-1135.44. ^ныпикова О.Р. Методы поиска ядер кооперативных игр и их приложения. Дисс. канд.физ.-мат.наук. - Москва, 1977, 129 с.

41. Наумова Н.И. По поводу существования решения для кооперативных игр. В кн. Теория игр, Ереван, 1973, с.253.

42. Наумова Н.И. Ц-И -решение некоторых кооперативных игр четырех лиц с пустым ядром. Вестник ЛГУ, 1979, Л 19, с. 52-60.47. фон Нейман Дж., АЬргенштерн 0. Теория игр и экономическое поведение. М.: Наука, 1970 , 707 с.

43. Никайдо X., Исода К. Заметка о бескоалиционных выпуклых играх. В сб. Бесконечные антагонистические игры, - М»: Ф.М., 1963 А4 49-4 53.

44. Оуэн Г. Теория игр. М.: Мир, Г971, 230 с.

45. Партхасаратхи П., Рагхаван Т. Некоторые Еопросы теории игр двух лиц, М.: Мир, 1974, 295 с.

46. Подиноеский В.В. Методы многокритериальной оптимизации, вып.1 М.: Воен.инж.акад., 1971, 123 с.

47. Прохоров Ю.В. Сходимость случайных процессов и предельные теоремы вероятностей. Теория вероятн. и ее примен. 1956, т.1,в.2, с.Г77-238.

48. Розенмюллер И. Кооперативные игры и рынки. М.: Мир, 1974, 167 с.

49. Соколина Н.А. О ядре-решении кооперативной игры, В сб. Исследование операций и ста т.моделирование. 1972, в.1, с.170-173.

50. Суджуте Д. Неантагонистические игры на единичном квадрате с различными кривыми разрыва ядер игры, Лит.мат.сб., 197 2, т.ХП, Я 3.

51. Суджуте Д. К Еопросу о сходимости ь -раЕноЕесий к равновесиям в неантагонистических играх двух лиц с выбором моментавремени.-Лит.мат.сб., 1976, т.ХУХ, № 3, с.203-2X5.

52. Фань Дзи, 0 системах линейных неравенств .-В сб. Линейные неравенства и смежные вопросы. М., 1959, с. 214-262.

53. Шимялис Ч.П. Одно замечание об N -ядре монотонной игры.-Литоеский мат.сб., 1977, т.ХУЛ, ?§ 3, с.105-109.

54. Шмадич К. О существовании решений в графах.-Вестник ЛГУ, 1976, Ш 7, с.88-92.

55. Яновская Е.Б. О существовании ситуаций равновесия в бескоалиционных играх двух лиц. В сб. Теория игр, Ереван, 1973, с. 354-364.

56. АХо-дшигоГГ P. ,Hcpf Н. ^opoXogio.- Berlin, 1933» 203р.

57. Auoon J. maaio-.i:.tical uotliodc of game and economic theory.-Amsterdam-irca-Yorc --Cazfnrd, I7orth Holland Publishing Co., 1979, 619 p.

58. Auinann R.J., Peleg B. Von Neumaxin-Mox'g ens tern solution to cooperative panes v/ibhout side payments.-Bull.Amer.I;lath.Soc. I960, Ю, p.173-179.

59. Auman R.J. The core of a cooperative game without side payments -Trans.Amer.Liath.Soc. 1961, v.98,IT; , p.339-332.

60. Berge C. Topological spaces.- ITew-Iork: MacnilXcm, 1963,270p„ 55. Bergstrom Т.О. Maximal elements of acidic relation on compact sets.-J.Econ.Theory, 1975, H 10, p.403-^04.

61. Eillera L.J. Souo rceont :?scultfj in n-percon pane theory, — hath. Propr., 1971, И I, p.56-67.

62. Bilhera L.J. A note of a liernel md the corc for panes Y/ithout side pajnentc. -Ithaca, 1972 I2p. ( To clinical Rep./ Cornell Univ.: IT 192 ).

63. Gharries A. ,Kor banen K. On balancod note, с ого с, and linear propra-nainp,-Cahiers Centre etndec roch. operat., 1967, IT 9, F I, p.52-43.

64. Choquet5 Conaurpences,-Ann.Univ.Grenoile, IQ/j-C, IT 23, p. 99-112.73« Gillicc D.E. Solutions to pencral non-uoro-siui pa:.es ,-A'ia. of1.ath. Studies, 1959, II 40, p.47-85.

65. Kainiai Y. Countably additive measures in cores of panes,—J. llatii. Anal, and Appl. , 1969, v. 27, H 2, p.227-240.75» Lucas y/.F. Solutions for four-person panes in partitions function form, J. SIAh, 1965, IT 13, p. 1Ю-128.

66. Lucas W.F. A coxmtre^ample in parae theory ,-Manas. Sci., 1967, v. 15, IT 9, P.766-767.79* Lucas '„7.F. The proof that a game mar/ not have a solution f— Trans. Aner. Hath. Soc., 1969, П 157, p.219-229.

67. Lucas W.F. Some recent devclopuents in n-person paiae theory, SIAi/I Rev. , 1971, v.13, IT 4, p. 49I-525.

68. Lucas 71.F. On overview of the mathematical theory of panes.— f'laaag. Sci., 1972, v. 18, If 5, p.5-15'.- 2у/ 82. i.Iichael K. Topologies on spacos 01 subsets.- Trans. Auer. Math. Soc. , 1951, 71, p.152-18;;.

69. ITorio Okada, Eaauliiro Xoshikawa. Mathematical programing models applied to water re sours planning f-7/ater Supply & Lbmayenent, 1979» N 3, p.209-223.

70. Owen G. IT-person yanes with only 1, n-I and n-porson coalitions.-^ Pi' о с. Ане r. Hath. Soc. , 1968, v. 19, И 6, p. 1298-12б I.

71. Owen G. ihristcnce of equilibrium pair in continuous panes. Int. J. oi Game Theory, 1978, v. у, IT 2/3, p.97-105.

72. Report on the fourth International «Vorksiiop on Garao Theory.-Nov:-York, 1978, 53p« ( Technical Report / Cornell Univ.:EM 78-049 ).

73. Richardson M. On weakly ordered systems,- Bull. Amer. Math. Soc., 1946, N 52, p. II3-II6.

74. Richardson M. Solutions of irreflexive relations Ann. of Math., 1953, v.38, p. 973-390.

75. Scarf H.bi. The core of 11-person yane. — iiiconoiaetrica, 1967, v. 35з h I, У- >9-60.

76. Schmeidler D. On balanced games with infinitely лапу layers .-Jorusalon, 1966, 7 p. С Research program in game theory and iiiath. econ.: RI.I 28 ).

77. Schuaidler D. The nucleolus of a characteristic function {janes.- SIAm ,J. Appl. Hath., 1969, h 17, p. II63-II70.

78. Sen A. Social choice theory; a re-uraiaination. — jiconomet-rica, 1977, v.45, К I, p.

79. Ehapley L.S. On balanced sets and cores. ITaval Res. Loyist. yuart. , 1967, v. 14, F 4, p. 433-460.

80. JSnaplcy L.t. On "balanced games uithoui; side -payments. --Llath. Progr., 1973, H !>• 261-290.

81. Suzuki И., ITaca-co'ia II. 'lie cost i;;nK:nt of the cooperative water recource development: a pane theoretical approach, -hanapciuent Sci., 1976, li 22, p. I00I-I086.

82. Torao TJ. She continuity of a critical point set with applications to cone decision problene. SIAII J. Ap'j?l. hath.,

83. Vrhite E'.I. Kernels of "px-oforoncc; с tract tires.- Econometrica, v. 4S IT I, r>. 91-100.