518 Г 38 УДК 519.95 Игры с непротивоположными интересами. Гермейер Ю. Б., Главная редакция физико-матема- тической литературы издательства «Наука», 1976. Книга содержит результаты исследований, про- водившихся в последние годы по играм с непротиво- положными интересами, занимающим важное место в теории принятия решения. Значительное место уде- ляется принципам принятия рационального решения, вопросам субъективности и информированности при принятии решения, принципу гарантированного ре- зультата в иеантагонистических играх и т. п. Изу- чаются проблемы, связанные с передачей информации, с порядком ходов, характерным для иерархических систем и соответствующим расширением понятий стра- тегии анализируется влияние совместных ограниче- ний. Излагаются основные результаты для игр двух лиц с фиксированной последовательностью ходов и учетом разной степени информированности. На основе принципа гарантированного результата обсуждаются некоторые специальные игры п лиц. Библ. 87 20204—142 Главная редакция 053(02)-76 66-76 фжзико-математмческой литературы мзцательства «Натка», 1978 ОГЛАВЛЕНИЕ Предисловие редактора серии ............... 7 Предисловие автора .................. 9 Глава I. Общее описание модели с несовпадающими интересами ...... ............ 13 § 1. Характерные примеры игр с непротивоположными интересами .................. 13 § 2- Общее описание обстановки бескоалиционной игры с учетом взаимной информированности об инте- ресах ..................... 23 § 3. Ситуации, стратегии и взаимная информирован- ность игроков о «ходах» ............ 32 § 4. О задаче рационального выбора стратегий ... 38 § 5. Обмен информацией и расширение понятия стра- тегии .................... 45 § 6. Формализованное описание компромиссов и коа- лиций ..................... 50 Глава II. Некоторые принципы выбора рациональных стратегий ........ ............ 61 § 7. Оптимизация и осреднение ........... 61 § 8. Максимин ................... 65 § 9. Абсолютно оптимальные стратегии и стратегии наказания ................... 73 § 10. Принцип наилучшего гарантированного резуль- тата при обмене информацией в играх с фикси- рованным порядком принятия решений ...... 83 § 11. Ситуации равновесия ............. 93 § 12. Преимущества и недостатки коалиций ..... 107 § 13. Устойчивость коалиционных решений в повторяю- щихся играх ... .............. 130 Глава III. Принцип гарантированного результата в иг- рах двух лиц . . ................ 151 § 14. Игры качества ... ............. 151 § 15. Игры с запрещенными ситуациями ....... 165 § 16. Игры с фиксированной последовательностью хо- дов без запрещений .............. 176 § 17. Неточная информация об интересах второго игро- ка при точной информации о его выборе . . . 192 § 18. Отсутствие у первого игрока информации о ходе вгрогв .................... 204 § 19. Корректность задачи о максимальном гараптиро- ванном Р^У^тате и аппроксимация игр Ч Л). Другие случаи информированности. Метаигры '. ' '• § Л. Игры со вспомогательными критериями эффектив- ности .... ...... § 22. Динамика в играх двух лиц. .....''''" '• § 23. Замечания ....... ••••... ^ Глава IV. Некоторые игровые модели для многих лиц . ; § 24. К теории игр трех лиц ........ § 25. Ситуации равновесия и устойчивые совместные и01?0111" в сверяющихся играх ..... ; § Л. Побочные платежи как средство управления" в иерархических системах ......... '- Литература ............ у Предметный указатель •••....... • • • • ^ 1. Дж. фон Нейман, О.Моргенштерн, Теория игр и экономическое поведение, М., «Наука», 1970. 2. Дж. Н э ш, Бескоалиционные игры, сб. «Матричные игры», М., Физматгмз, 1961, 205—221. 3. Г. У. К у н, Позиционные игры и проблема информации, сб. «Позиционные игры», М., «Наука», 1967, 13—40. 4. Н. Н. Воробьев, Современное состояние теории игр, Труды I Всесоюзной конференции по теории игр (Ереван, 1968), Изд. АН Армянской ССР, Ереван, 1973, 5—57. 5. Г. Оуэн, Теория игр, М., «Наука», 1971. 6. Ю. Б. Гермейер, Введение в теорию исследования опе- раций, М., «Наука», 1971. 7. Д. А. Молодцов, Модель Гросса в случае непротивопо- ложных интересов, ЖВМ и МФ 12, 2, 1972, 309—320. 8. В. А. Горелик, Принцип гарантированного результата в неантагонистических играх двух лиц с обменом информацией, сб. «Исследование операций», вып. 2, М., Изд. ВЦ АН СССР, 1971, 102—118. 9. В. А. Горелик, Игры с близкими интересами, ЖВМ и МФ 11, 5, 1971, 1166—1179. 10. Ю. Б. Г е р м е и е р, Н.Н.Моисеев, О некоторых за- дачах теории иерархических систем управления, сб. «Проблемы прикладной математики и механики», М., «Наука», 1971, 30—43. 11. Ю. Б. Гермейер, Игровые концепции в исследовании си- стем, Изв. АН СССР, Техническая кибернетика, 2, 1970, 25—33. 12. В. А. Л е ф е в р, Конфликтующие структуры, М., «Высшая школа», 1967. 13. X о в а р д (N. Howard), Theory of meta-games, сб. «General systems», 11, 1966, 187—200. 14. Ю. Б. Гермейер, Тезисы о принятии решений в играх с непротивоположными интересами, Известия высших учебных заведений, Радиофизика 15, 7, 1972, 972—981. 15. Ю. Б. Г е р м е йе р, Об играх двух лиц с фиксированной по- следовательностью ходов, ДАН 198, 5, 1971, 1001—1004. 16. Н. С. Кукушкин, Роль взаимной информированности сторон в играх двух лиц с непротивоположными интересами, ЖВМ и МФ 12, 4, 1972, 1029—1034. 17. А. Ф. К о н о н е н к о, Роль информации о функции цели противника в играх двух лиц с фиксированной последователь- ностью ходов ЖВМ и МФ 13, 2, 1973, 311—317. 18. Дж. Д а н с к и н, Теория максимина и ее приложение к зада- чам распределения вооружений, М., «Сов. радио», 1970. :i22 ЛИТЕРАТУРА 19. В. Ф. Демьянов, В. Н. М а л о з е м о в, Введение в минимакс, М., «Наука», 1972. 20. Ю. Б. Гермейер, Приближенное сведение с помощью штрафных функций задачи определения максимина к задаче определения максимума, ЖВМ и МФ 9, 3, 1969, 730—731. 21. В. В. Федоров, О методе штрафных функций в задаче определения максимина, ЖВМ и МФ 12, 2, 1972, 321—333. 22. В.В.Федоров, К задаче поиска последовательного мак- симина, ЖВМ и МФ 12, 4, 1972, 897—908. 23. Ю. Б. Г е р м е и е р, И. А. К р ы л о в. Поиск максиминов методом «невязок», ЖВМ и МФ 12, 4, 1972, 871—881. 24. X. Н и к а и д о и К. И с о д а, Заметки о бескоалиционных выпуклых играх, сб. «Бесконечные антагонистические игры», М., Физматгиз, 1963, 449—458. 25. 26. А. С. Белоцерковский, Принцип максимальной ус- тойчивости, Труды I Всесоюзной конференции по теории игр (Ереван, 1968). Изд. АН Армянской ССР, Ереван, 1973, 70—73. Н. Н. Моисеев, Элементы теории оптимальных систем, М., «Наука», 1975. 27. 28. А. Г. Сухарев, Наилучшие стратегии последовательного поиска экстремума, ЖВМ и МФ 12, 1, 1972, 35—50. С. А. П и я в с к и и, Алгоритм отыскания абсолютного ми- нимума функций, Теория оптимальных решений, семинар ИК АН УССР, вып. 2, 1967, 18—24. 29. Ю. Г. Евтушенко, Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке), ЖВМ и МФ 11, 6, 1971, 1390—1403. 30. Р. Г. С т р о н г и н, Об одном алгоритме глобальной миними- зации, Известия высших учебных заведений. Радиофизика 13 4, 1970, 539-545. 31. В. В. М о р о з о в, Об одном способе образования коалиций, ЖВМ и МФ 11, 3, 1971, 611-622. 32. Д ж и л л и с (G. Gillies), Solution to general nonzero-sum ga- mes, сб. «Contributions to the theory of games» IV, Ann. Math. Studies, 40, Princeton Univ. Press, 1959, 47—86. 33. О. II. Бондарева, Некоторые применения методов ли- нейного программирования к теории кооперативных игр. Про- блемы кибернетики 10, 1963, 119—139. 34. Л у к а с (W. F. Lucas), A game with no solution, Bull. Amer. Math. Soc. 74, 2, 1968, 237—239. 35. А у м а н, М а ш л е р (R. J. Aumann, M. Maschler), The bar- gaining set for cooperative games, сб. «Advances in game theory», Ann. Math. Studies 52, Princeton Univ. Press, 1964, 443—476. 36. В. В. Морозов, Об одном подходе к кооперативным иг- рам, ЖВМ и МФ 13, 3, 1973, 781—787. 38. 37. С. А. Орловский, Матричные игры с запрещенными ситуациями, ЖФМ и МФ 11, 3, 1971, 623—631. С. А. Орловский, Бесконечные игры двух , лиц с запре- щенными ситуациями, ЖВМ и МФ 13, 3, 1973, 775—781. 39. А. Ф. К о н о н е н к о, Н. С. К у к у ш к и н. Смешанные стратегии в играх с фиксированной последовательностью ходов, ДАН 209, 6, 1973, 1274—1277. ЛИТЕРАТУРА 323 40. Ф. И.Ерешко, А.Ф.Кононенко, Решение игры с правом первого хода при неточной информации о цели парт- нера, ЖВМ и МФ 13, 1, 1973, 217—221. 41. Н. С. Кукушкин, Об одной игре с неполной информаци- ей, ЖВМ и МФ 13, 1, 1973, 210—216. 42. И. А. В а т е л ь, Н. С. К у к у ш к и н, Оптимальное по- ведение игрока, обладающего правом первого хода, при неточном знании интересов партнера, ЖВМ и МФ 13, 2, 1973, 303—310. 43. Е. С. Л е в и т и н, Б. Т. П о л я к, Методы минимизации при наличии ограничений, ЖВМ и МФ 6, 5, 1966, 787—823. 44. В. А. Горелик, Приближенное нахождение максимина с ограничениями, связывающими переменные, ЖВМ и МФ 12, 2, 1972, 510-517. 45. Ю. Б. Гермейер, А. Ф. К о н о н е и к о, Игры со вспо- могательными критериями эффективности, Изв. АН СССР, Техническая кибернетика, 1, 1973, 3—10. 46. И. А. В а т е л ь, Ф. И. Е р е ш к о, Математика конфликта и сотрудничества, М., «Знание», 1973. 47. Ю. Б. Г е р м е и о р, Слабоустойчивые совместные решения в повторяющихся играх, ДАН 216, 3, 1974, 481—484. 48. Б. И. Б у т р и м, Модифицированное решение задачи торга, ЖВМ и МФ 16, 2, 1976, 340—350. 49. Р. Л ь ю с, X. Р а и ф а, Игры и решения, М., ИЛ, 1961. 50. Ю. М.Ермольев, О методе обобщенных стохастических градиентов и стохастических квазифейеровских последователь- ностях, Кибернетика, Киев, 2, 1969, 73—83. 51. В. В. Федоров, Необходимые условия оптимальности в игре с передачей информации, ЖВМ и МФ 15, 2, 1975, 505—508. 52. Ю. Б. Г е р м е и е р, Ф. И. Е р е ш к о, Побочные платежи в играх с фиксированной последовательностью ходов, ЖВМ и МФ 14, 6, 1974, 1437-1450. 53. В. 3.Б е л е н ь к и и, В. А. Волконский, С. А. И в а н к о в и др., Итеративные методы в теории игр и про- граммировании, М., «Наука», 1974. 54. Ю. Б. Гермейер, И. А. В а т е л ь, Игры с иерархиче- ским вектором интересов, Изв. АН СССР, Техническая кибер- нетика, 3, 1974, 54—69. 55. Ю. Б. Гермейер, Игровые принципы в исследовании систем, сб. «Методы управления большими системами», Иркутск, Изд. СЭИ, 1970. 56. Э. И. Вилка с, Теоретико-игровые принципы оптимально- сти, Диссертация, Институт физики и математики АН Литов- ской ССР, Вильнюс, 1972. 57. М. Ш у б и к, Гейминг и теория игр, сб. «Математика сегодня», М., «Знание», 1974. 58. Д. А. Молодцов, Один класс игр с запрещенными ситуа- циями, Тезисы III Всесоюзной конференции по теории игр, Одесса, 1974. 59. И. А. В а т е л ь, О математических моделях стимулирования в экономике, сб. «Планирование и управление экономическими целенаправленными системами», Новосибирск, «Наука», 1974, 52-63. 324 ЛИТЕРАТУРА 60. В. И. П р о к о п е н к о, Об одной игре с инертным партне- ром, ЖВМ и МФ 15, 3, 1975, 795-799. 61. Р. А. В е д е р н и к о в, А. Ф. К о н о н е н к о, О при- нятии решений в двухуровневой иерархической системе управ- ления при неполной информации о нижнем уровне, Изв. АН СССР, Техническая кибернетика, 2, 1976, 13—22. 62. Д. А. Молодцов, Один класс игр с непротивоположными интересами, ЖВМ и МФ 15, 3, 1975, 789—795. 63. В. А. Горелик, В. В. Федоров, Метод внешней точки в задаче определения краткого максимина с ограничениями, ЖВМ и МФ 15, 3, 1975, 599-607. 64. А. Ф. К о н о н е н к о, Теория игр и иерархические структу- ры, сб. «Планирование и управление экономическими целена- правленными системами», Новосибирск, «Наука», 1974, 63—72. 65. Д. А. М о л о д ц о в, В. В. Ф е д о р о в, Аппроксимация игр двух лиц с передачей информации, ЖВМ и МФ 13, 6, 1973, 1469—1484. 66. В. В. Федоров, Методы поиска максимина, Изд. Москов- ского университета, 1975. 67. Д. А. Молодцов, Методы решения одного класса игр с не- противоположными интересами, Диссертация, Московский университет, 1974. 68. Н. С. Кукушкин, Точки равновесия в метаиграх, ЖФМ и МФ 14, 2, 1974, 312-320. 69. Т. Н. Д а н и л ь ч е н к о, К. К. М о с е в и ч, Многошаго- вые игры двух лиц с фиксированной последовательностью ходов, ЖВМ и МФ 14, 4, 1974, 1047—1052, 70. Т. Н. Д а н и л ь ч е Е к о, К. К. М о с е в и ч, Многошаго- вая игра двух лиц при «осторожном» втором игроке и последо- вательной передаче информации, ЖВМ и МФ 14, 5, 1974, 1323-1327. 71. Я. 3. Ц ы п к и н, Адаптация и обучение в автоматических системах, М., «Наука», 1968. 72. И. С. Меньшиков, Игра трех лиц с фиксированной по- следовательностью ходов, ЖВМ и МФ 15, 5, 1975, 1148—1156. 73. Н. М. Новикова, Игры 2-х и 3-х лиц со связанными огра- ничениями при фиксированном порядке ходов, ЖВМ и МФ 16, 2, 1976, 326—339. 74. Ю. Б. Г е р м е и е р, М. С. Ш т и л ь м а н, Некооператив- ные повторяющиеся игры с произвольным дисконтированием, ДАН 211, 1, 1975, 22—25. 75. А. Ф. К о н о н е н к о, Теоретико-игровой анализ двухуровне- вой иерархической системы управления, ЖВМ и МФ 14, 5, 1974, 1161-1170. 76. Е. Г. Г о л ь ш т е и н, Теория двойственности в математи-- ческом программировании и ее приложения, М., «Наука», 1971. 77. М. С. Ц е т л и н, Исследования по теории автоматов и моде- лированию биологических систем, М., Физматгиз, 1969, 78. С. А. Орловский, Игры п лиц с неполными связями, ЖВМ и МФ 12, 4, 1972, 1022—1029. 79. Ю. Б. Г е р м е и е р, Игры с непротивоположными интере- сами, Изд. Московского университета, 1972. ЛИТЕРАТУРА 325 80. О. Н. Б о н д а р е в а, О теоретико-игровых моделях в эко- номике, Изд. Ленинградского университета, 1974. 81. Ю. Б. Г е р м е и е р, К теории игр трех лиц, ЖВМ и МФ 13, 6, 1973, 1459-1468. 82. Л. В. Агапова, Об устойчивости решений в повторяю- щихся кооперативных играх, ЖВМ и МФ 16, 1, 1976, 48—60. 83. И. С. Меньшиков, Игра п лиц с фиксированной после- довательностью ходов, ЖВМ и МФ 16, 3, 1976, 634—639. 84. В. А. Г о р е л и к, В. В. Ф е д о р о в, Метод внутренней точки в задаче определения кратного максимина с ограниче- ниями, ЖВМ и МФ 15, 4, 1975, 883-894. 85. И. А. В а т е л ь, Я. Н. Д р а н е в, Об одном классе по- вторяющихся игр с неполной информацией в двухуровневой экономической системе, Труды международной конференции «Моделирование экономических процессов» (Ереван, 1974), М., Изд. ВЦ АН СССР, 1975, 224—238. 86. Я. Н. Д р а н е в, Выявление интересов партнера в повторя- ющейся игре с линейными критериями, Изв. АН СССР, Тех- ническая кибернетика, 4, 1976, 37—45. 87. И. А. В а т е л ь, Ф. И. Е р е ш к о, А. Ф. Коно.ненко, Игры с фиксированной последовательностью ходов и иерархи- ческие системы управления в экономике, сб. «Методы оптими- зации и их приложения», Иркутск, Изд. СЭИ, 1974, 85—99. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Абсолютно оптимальная стратегия 41, 73 — — — частичная 81 Антагонизм 13, 108 Арбитраж 57, 122 Арбитражная схема Нэша 43, 57 «Безразличие» природы 14, 67 Бесконечное повторение игры 291 Благожелательность партнера 208, 312 Блеф 46 — корректный 48, 88, 172, 242, 245, 313, 318 — некорректный 48, 87, 214 Введение новых критериев эффектив- ности 42 Вектор дележей 53, 56, 123 — Парето' 43, 111, 141 — Шепли 43 Вероятность «жизнеспособности» ко- алиции 63 Весовые коэффициенты свертки 55 Взаимная информированность 43 Выявление неизвестных интересов 267 Гросса задача обобщенная 16, 73, 212 Двухвтапная задача стохастической оптимизации 64 Диктат в коалиции 122 Дилемма заключенного 78, 90, 105 Динамика в играх двух лиц 249 — в получении информации 32, 42 Дисконтирующая последователь- ность 290 — — экспоненциально убывающая 296 » щ Замыкание! игры 26, 35, 151 Запаздывание в наказании 150 — в получении информации 258 Зона нечувствительности коалиции Игра антагонистическая 29, 144 — — с запрещенными ситуациями — Г, 231 — Г, 231 — Г, 232 — идеальная 209, 234, 258 — качества 151 — несущественная 123, 127 — повторяющаяся 27, 116, 130, 259 — с близкими интересами 23, 22S Игра с вспомогательными критериями эффективности 240 — с запрещенными ситуациями 15, 25, 165 — с полной информацией 35 — с природой 13 — существенная 123, 127 — с фиксированным порядком ходов 83, 157, 176 — типа «соревнование» 18, 73, 90, 204 — циклическая 31 Игровая обстановка 23 Иерархические системы 19, 79 87 104, 205, 245, 307 Изоляционизм 42, 153 Информация с ошибкой 33 Исследователь операции 24 Коалиция 43, 50 — лексикографическая 58 — фон Неймана 57, 275 — частичная 58, 110 Коллективизм 42 Компромисс 43 Конкуренты на рынке 17 Конфигурация 126 Корректность задачи о максималь- ном гарантированном результате 224, 229 Коэффициент дисконтирования 131 Критерий качества 121, 151 Максимальная устойчивость коали- ционного решения 136, 304 Максимин 65 — со связанными переменными 91 Метаигры 35, 105, 236 Метод невязок 70 — сеток 229 — штрафных функций 217 Минимакс 67 Минимаксимин 67 Множество Парето 111 —^ситуаций, в которых оказывается игра после выбора первого игро- ка 83 — «физических» ограничений 24 32 38, 82, 86, 110 Накавывающие повторения 132, 142 Нарушение согласованного решения 128, 131, 147 Неединственность ситуации ра>и*- весия 104, 240 Независимость интересов 13 Нерешительность игрока 22. 26. 187 ПРВДМЕТНЫЙ УКАЗАТЕЛЬ 327 Неточная информация об интересах партнеров 29, 192, 222, 247, 313 Нечувствительность игрока по кри- терию 28, 30, 177 НМ-решение 126 Область возможных компромиссов 108 Обмен информацией 43, 50, 168 — — добровольный 45, 161 Общая цель коалиции 54 • Объединение ресурсов 50, 58, 110 Объективное описание игры 23, 24 Однотипные (или сравнимые) кри- терии эффективности 27, 57 Операция 9 Оперирующая сторона 9, 24 Оптимальный выбор 38 Оптимизация векторная 11 Осреднение критерия 36, 51, 62, 65 Осторожность игрока 184, 200, 243, 259 » Отказ от выплаты побочных плате- жей 129, 299 Отношение доминирования 124 Параметрическая оптимизация 65 Первый ход 20, 79 Переговорное множество ill Передача информации 48, 83, 231 — — об интересах 241 — — о стратегии 86, 89, 170 Побочные платежи 28, 37, 51, 61, 307 — — априорные 129 — — коалиции как целого 51 — — неограниченные 28, 53, 127 Порядок ходов 34, 85 Право первого хода 83, 95, 145 Принцип гарантированного резуль- тата 17, 43, 84 Природные неопределенности 24, 26, 103 Прогнозирование результата 39, 64 Противоположность интересов 13 Психологические процессы отраже- ния 35 Распределение ресурсов 120, 235 Рациональный выбор 38 Регуляризация задачи вычисления максимина 225 Регулярная совокупность множеств стратегий 97 Решение 126 — в конфигурациях 127 Сведение максимальной задачи к оп- тимизационной 69, 219 Свертка критериев 55 Сепаратные действия 128 Ситуация (исход) 32, 34 — равновесия 44, 155, 290 — — в метаиграх 238, 286 — — в смешанных стратегиях 103 — — наилучшая 106 — — нестрогая 93 — — строгая 93 — — тривиальная 291, 296 Совпадение интересов 13, 98 Согласованное (коллективное) реше- ние коалиции 130 — — — — «нежесткое» 147, 149 — — — — слабо устойчивое 140 — — — — L-устойчивое 292, 298 — — — — ^'-устойчивое 292 Сообщество с согласованным векто- ром интересов 23, 58, 76, 106 Стратегии 32 — наибольшего поощрения 82 — наказания 81 — — частичные 82 — смешанные 35, 51, 72, 174, 180, 190 — — совместные 51 — частные 36, 114 Субъективное описание игры 23, 29, 31, 87, 152 Супераддитивная функция 123 Торг в коалиции 56, 121 Условия существования коалиции 62 Устойчивость 43 — коллективных решений 130 Фиктивные игроки 22, 26, 36, 85, 102 Характеристическая функция 53, 122 Штраф за нарушение ограничений 15, 22 24 Ядро 124, 129 е-абсолютно оптимальная стратегия 74, 100 е-ситуапия равновесия 93