автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Позиционные игровые задачи при неопределенности

Введение.

1. Позиционная задача векторной оптимизации при неопределенности

1. Позиционная игра при неопределенности.

2. Конечный многошаговый процесс принятия решения при неопределенности.

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

4. Принцип пессимизма-оптимизма в многошаговой многокритериальной задаче.

2. Позиционная бескоалиционная играг < с при неопределенности ; у

5. Равновесие Нэша-Слейтера и Нэша-Парето.

6. Свойства равновесия Нэша-Парето.

7. Равновесие Нэша-Гурвица.

8. Теоретико-игровые модели эколого-экономических задач.

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

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

Первые результаты для позиционных игр с полной информацией представлены Э.Цермело [65]. Основные понятия теории конечных позиционных игр были введены Дж. фон Нейманом и О.Моргенштерном [81] в связи с задачами экономики. Конечно-графовая формализация и концепция информационных множеств предложены в работе Бержа [2]. В статье Г.Куна [28] завершено построение модели позиционной игры N лиц и получены важные результаты. Так как позиционная игра допускает представление в нормальной форме [22, 29], то большое значение для конечных позиционных игр имеют результаты Дж.Нэша [40, 80] о существовании равновесия. В большинстве учебной литературы по теории игр имеются разделы, посвященные конечным позиционным играм [22, 29, 30, 41, 42, 47]. Важные результаты по теории позиционных игр содержатся также в следующих работах отечественных и зарубежных авторов [12, 13, 14, 44, 49, 69, 71]. В настоящее время теория игр активно развивается в связи с запросами экономики. Имеется большое число работ, где рассматриваются модели экономических явлений в форме конечной позиционной игры. Результаты этих исследований обобщены в работах [70,71,72,73,76,77,79].

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

Причины появления неопределенных факторов в процессах принятия решения могут быть различными [18, 19, 82]. В формальном отношении можно выделить [19] два "вида неопределенностей":

- вероятностно-определенные условия, когда помимо однозначных исходных данных имеются случайные величины с точно известными вероятностными характеристиками;

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

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

В теории принятия решений помимо наличия различного вида неопределенностей необходимо учитывать также наличие нескольких критериев, оценивающих качество функционирования системы. В связи с этим особое значение приобретает развивающееся в последнее время направление теории принятия решений, которое получило название "многокритериальные задачи при неопределенности" [19, 20, 21, 37, 38].

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

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

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

Объектом исследования является теория позиционных игр, теория бескоалиционных игр при неопределенности и теория многокритериальных задач.

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

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

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

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

- распространить принципы оптимальности из теории многокритериальных задач и бескоалиционных игр при неопределенности на многоуровневые модели;

- уточнить предложенные концепции решения путем введения абсолютных равновесий;

- установить существование таких равновесий в чистых стратегиях в играх с полной информацией и в смешанных стратегиях в играх с полной памятью;

- выявить свойства рассмотренных принципов оптимальности.

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

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

Формализованы понятия равновесия Нэша-Слейтера, Нэша-Парето и Нэша-Гурвица в позиционных бескоалиционных играх при неопределенности. Доказано их существование и изучены свойства для игр N лиц.

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

Все основные результаты работы являются новыми.

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

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

1. Бардин А.Е., Смирнова J1.B. Принцип Гурвица для многокритериальной задачи при неопределенности // Сложные управляемые системы: Межвуз. сб. научн. тр. - М.: РосЗИТЛП, 1996. - С.34-37.

2. Берж К. Общая теория игр нескольких лиц. М.: Физматгиз, 1961. -128с.

3. Бесконечные антагонистические игры: Сб. научн.тр. М.: Физ.-мат.лит., 1963. - 503с.

4. Борисович Ю.Г., Гельман Б.Д., Мышкис А.Д., Обуховский В.В. Введение в теорию многозначных отображений. Воронеж: Воронежский гос. ун-т., 1986. - 104с.

5. Бравая Г.Ю., Кузютин Д.В., Петренко Н.В. Устойчивое оптимальное поведение в некоторых классах позиционных игр // Сложные управляемые системы: Межвуз. сб. научн. тр. М.: РосЗИТЛП, 1996. -С.84 -89.

6. Вайсман К.С., Жуковский В.И. Особенности антагонистических игр с векторной функцией выигрыша // Многокритериальные системы при неопределенности и их приложения: Сб. научн. тр. Челябинск: Уфимский гос. ун-т, 1988. - С.22-28.

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

8. Воробьев H.H. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984. - 496с.

9. Воробьев H.H. Современное состояние теории игр // Теория игр.: Сб. докл. I Всесоюзной конф. по теории игр. Ереван: АН Армянской ССР, 1973. - С.5-57.Ю.Воробьев H.H. Теория игр для экономистов-кибернетиков. М.: Наука, 1985. - 272с.

10. Гермейер Ю.Б. Введение в исследование операций. М.: Наука, 1971. - 284с.

11. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976. - 328с.

12. З.Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М.: Радио и связь, 1982. - 144с.

13. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр. М.: Наука, 1981.-334с.

14. Житомирский Г.И., Матвеев В.А. Максимин и седловая точка по Слейтеру // Многокритериальные системы при неопределенности и их приложения: Сб. научн. тр. Челябинск: Уфимский гос.ун-т, 1988. -С.29-33.

15. Жуковский В.И. Введение в дифференциальные игры при неопределенности. М.: Международный НИИ проблем управления, 1997. -446с.

16. Жуковский В.И., Чикрий A.A. Линейно-квадратичные дифференциальные игры. Киев: Наукова Думка, 1994. - 320с.

17. Жуковский В.И., Молоствов B.C. Многокритериальная оптимизация систем в условиях неполной информации. М.: Международный НИИ проблем управления, 1990. - 112с.

18. Жуковский В.И., Молоствов B.C. Многокритериальное принятие решений в условиях неопределенности. М.: Международный НИИ проблем управления, 1988. - 131с.

19. Жуковский В.И., Салуквадзе М.Е. Многокритериальные задачи управления в условиях неопределенности. Тбилиси: Мецниереба, 1991.- 128с.

20. Жуковский В.И., Салуквадзе М.Е. Оптимизация гарантий в многокритериальных задачах управления. Тбилиси: Мецниереба, 1996. -475с.

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

22. Кирута А .Я., Рубинов A.M., Яновская Е.Б. Оптимальный выбор распределений в сложных социально-экономических задачах. JL: Наука, 1980. - 166с.

23. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1972. - 543с.

24. Кузютин Д.В., Бравая Г.Ю. К определению сильной динамической устойчивости в позиционных играх // Сложные управляемые системы: Межвуз. сб. научн. тр. М.: РосЗИТЛП, 1996. С. 104-107.

25. Кузютин Д.В. Устойчивость решений в позиционных играх. СПб, 1995. - 40с.

26. Кругман П.Р., Обстфельд М. Международная экономика. Теория и политика: Пер. с англ. М.: ЮНИТИ, 1997. - 799с.

27. Кун Г.У. Позиционная игра и проблема информации // Позиционные игры. М.: Наука, 1967. С. 13-40.

28. Льюис Р.Д., Райфа X. Игры и решения. М.: ИЛ, 1961. -642с.

29. Мак-Кинси Дж. Введение в теорию игр. М.: Физматгиз, 1960. - 418 с.

30. Матвеев В.А., Фахретдинова В.А. Двухуровневая задача в условиях неопределенности // Моделирование и исследование устойчивости систем: Тезисы докл. Киев, 1997. С.81.

31. Матвеев В.А. Многокритериальная позиционная задача для параболической системы: Автореф.дисс. . канд.физ.-матем.наук. Екатеринбург, УрГУ, 1992. 16с.

32. Матвеев В.А. Общая бескоалиционная игра // Сложные динамические системы: Сб.научн.тр.- Псков: Псковский пед.ин-т., 1994. -С.46-51.

33. Матвеев В.А. Равновесие угроз и контругроз в общей бескоалиционной игре // Математика, экономика, компьютер и инвестиции: Тез.докл. II Межд.конф. Пущино, 1994. - С.21.

34. Матвеев В.А. Существование £-седловой точки по Парето в дифференциальной игре с параболической системой // Многокритериальные системы при неопределеннсти и их приложение: Сб.научнтр. Челябинск: Уфимский гос.ун-т., 1988. -С. 17-21.

35. Матричные игры: Сб.научн.тр. М.: Физ-мат.лит., 1961. - 280с.

36. Многокритериальные динамические задачи при неопределенности // Международный сб. работ. Орехово-Зуево: ОЗПИ, 1991. - 152с.

37. Многокритериальные системы при неопределенности и их приложения // Сб. научн. тр. Челябинск: Челябинский гос.ун-т. 1988. - 146с.

38. Мулен Э. Теория игр с примерами из математической экономики. -М.: Мир, 1985. 198с.

39. Нэш Дж. Бескоалиционные игры // Матричные игры. М.: Физ.-мат. лит, 1961. -С.205-221.

40. Оуэн Г. Теория игр. М.: Мир, 1971. - 232с.

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

42. Петросян Л.А., Захаров В.В. Введение в математическую экологию. -Л.: 1986.

43. Петросян Л.А., Ширяев В.Д. Иерархические игры. Саранск: Мордовский ун-т, 1986. - 92с.

44. Петросян Л.А. Многошаговые многокритериальные игры с полной информацией // Теория игр и ее приложения: Сб.научн.тр. -Кемерово: КемГУ, 1989. С.66-74.

45. Петросян JI.A., Малафеев O.A. Ситуация равновесия в антагонистической дифференциальной игре с векторной функцией выигрыша // Многокритериальные системы при неопределенности и их приложения: Сб. научн. тр. Челябинск: Уфимский гос. ун-т, 1988. - С.7-16.

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

47. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 254с.

48. Позиционные игры: Сб.научн.тр. -М.: Наука, 1967. 522с.

49. Принятие решений в игровых задачах / Специальное приложение к журналу "Вестник ПВУ". Серия "Математика и информатика". Вып. 1. Псков: ПВУ, 1997. - 177с.

50. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

51. Сложные динамические системы: Межвузовский сб.научн.тр. -Псков: ПГПИ, 1994. 190с.

52. Сложные управляемые системы // Межвузовский сб. научн. тр. М.: РосЗИТЛП, 1996. - 179с.

53. Смирнова Л.В. Принцип Гурвица в сложных управляемых системах. Дисс. канд. физ.-мат.н, М., 1997. - 98с.

54. Теория игр // Сб. докл. первой Всесоюзной конференции по теории игр. Ереван: АН Армянской ССР, 1973. - 368с.

55. Теория игр и ее приложения // Сб.научн.тр. Кемерово: КемГУ, 1989. - 134с.

56. Управление сложными системами // Межвузовский сб.научн.тр.- М.: РосЗИТЛП, 1999. 77с.

57. Успехи теории игр // Труды второй Всесоюзной конференции по теории игр. Вильнюс: Изд-во "Минтис", 1973. - 332с.

58. Фахретдинова В.А. Двухуровневая игра двух лиц // Информатика -исследования и инновации. Вып.2: Межвузовский сб.научн.тр. -СПб.: Изд-во ЛГОУ, 1999. С.65-66.

59. Фахретдинова В.А. Многошаговая многокритериальная задача при неопределенности // Управление сложными системами: Межвузовский сб.научн.тр. М.: РосЗИТЛП, 1999. - С.75-77.

60. Фахретдинова В.А. Модель внедрения технологий в условиях конкуренции // Проблемы моделирования в естествознании: Тезисы докл. -Волжский, 1997. С.5.

61. Фахретдинова В.А. Одна эколого-экономическая задача // Проблемы физико-математического образования в педагогических ВУЗах России на современном этапе: Материалы Всероссийской научно-практической конференции. 4.2. Магнитогорск, 1999. - С.91-92.

62. Фахретдинова В.А. Существование равновесия Нэша-Парето в конечных многошаговых играх в условиях неопределенности // Прикладная математика, информатика, электроника: Межвуз. сб. научн. тр. СПб.: РГПУ им. А.И.Герцена. 1997. - С. 123-129.

63. Цермело Э. О применении теории множеств к теории шахматной игры // Матричные игры. М.: Физ.-мат. лит., 1961. - С. 167-172.

64. Яновская Е.Б. Бесконечные антагонистические игры // Теория вероятностей. Математическая статистика. Математическая кибернетика. Т.10. -М., 1972. -С.75-106.

65. Яновская Е.Б. Антагонистические игры // Проблемы кибернетики. Вып.34. М.: Наука, 1978. - С.221-246.

66. Basar T. Olsder Dynamic Noncooperative Game Theory. London: Academic Press, 1982.

67. Van Damme E. Refinements of the Nash Equilibrium Concept Berlin, Heidenlberg: Springer - Verlag, 1983. - 15 lp.

68. Van Damm E. Stability and Perfection of Nash Equilibria Berlin, Heidenlberg: Springer - Verlag, 1987.

69. Fudenberg D., Tirole J. Game Theory. Cambridge, MA : The MIT Press, 1993. - 579p.

70. Gibbons R. Game Theory for Applied Economists Princeton, NJ.: Princeton Univ. Press, 1992. - 267p.

71. Harsanyi J.C., Selten R. A General Theory of Equilibrium Selection in Games Cambridge, MA: The MIT Press, 1988.

72. Hurwicz L. Optimality Criteria for Decision Making under Ignorance, Cowles Commission Discussion Paper, Statistics, 1951. 370p.

73. Hurwicz L. Programming in Linear Space // Arrow K.J., Hurwicz L., Uzava H."Studies in Linear and Non-Linear Programming." California: Stanford Univ. Press, 1958. P.38 - 102.

74. Heffernan S., Sinelair P. Modern International Economics Oxford, UK: Basil Blachwell Inc., 1990. - 399p.

75. Kohlberg E., Merten J.F. On the Strategic Stability of Equilibria // Econometrica, V.54, P. 1003-10037.

76. Kuhn H. Extensive Games and the Problem of Information / Annals of Mathematics studies, №28. Princeton Univ. Press, 1953.

77. Mc Millan J. Game Theory in International Economics // Fundamental of Pure and Applied Economics. Vol.1 Char: Harwood Academic Pbl., 1986.-338p.

78. Nash J. Non-cooperative games // Annals of Mathematics. V.54, 1951. -P.286-295.145

79. Von Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton Univ. Press, 1944.

80. Zhukovskii V.l., Salukvadze M.E. The Vector-Valued Maximin. Boston. San Diego, New-York, London : Academic Press, 1994. 404p.