ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ В ПОВТОРЯЮЩЕЙСЯ БИМАТРИЧНОЙ ИГРЕ С КОНЕЧНОЙ ПАМЯТЬЮ И В ПОВЕДЕНЧЕСКОЙ МОДЕЛИ ФИРМЫ
|
Актуальность работы. Во многих технических, экономических и социальных процессах возникают задачи принятия решения, в которых важное место занимают игровые постановки. Основы теории статических игр были разработаны в 30 - 50-х гг. в трудах Дж. фон Неймана и О. Моргенштерна, Дж. Нэша, X. Штакельберга и других исследователей.
В конце 50-х - начале 60-х гг. в работах Р. Айзекса были сформулированы первые задачи антагонистических динамических игр и были предложены методы их решения. В дальнейшем эти задачи исследовались многими отечественными и зарубежными учеными. Фундаментальный вклад в построение теории антагонистических дифференциальных игр принадлежит научным школам академиков Н. Н. Красовского и Л. С. Понтрягина. Этому направлению посвящены исследования Р. Айзекса4, Н. Н. Красовского, А. Н. Красовского, А. В. Кряжимского, А. Б. Куржанского, Ю. С. Осипова, Л. А. Петросяна, Л. С. Понтрягина, А. И. Субботина, А. Г. Ченцова и других авторов.
Большое внимание исследователей уделяется математическим моделям, формализуемым в рамках теории неантагонистических позиционных дифференциальных игр. Такие модели возникают при описании динамических задач управления механическими, экономическими, биологическими системами, когда управление осуществляется разными участниками. При этом интересы участников не являются полностью противоположными, каждый из них оптимизирует собственный показатель качества и имеет свой собственный ресурс управления. В этом случае задача состоит в выработке управления, приемлемого для всех сторон, участвующих в игре. Основополагающие результаты в этом направлении были получены в работах Ю. Б. Гермейера, А. Ф. Кононенко, Л. А. Петросяна, Э. Мулена, В. И. Жуковского, А. Ф. Клейменова и других исследователей.
Одна из основных проблем в неантагонистической игре состоит в выборе понятия решения, соответствующего содержанию задачи. В соответствии с различными принципами оптимальности выделяются равновесные но Нэшу решения, решения по Штакельбергу, кооперативное решение по Парето.
Важным частным случаем неантагонистических динамических игр являются повторяющиеся биматричные игры.
Среди них отметим бесконечно повторяющуюся игру, на каждом шаге которой разыгрывается известная биматричная игра «дилемма заключенного», предложенная А.У. Таккером. Активность, с которой изучается эта игра в последние годы, объясняется большим количеством ее интерпретаций с точки зрения социологии, психологии, биологии, экономики, философии, что отмечено в работах многих исследователей. Основной вопрос, возникающий при анализе этой игры, следующий: какие условия необходимо создать игрокам, чтобы они проявили стремление к сотрудничеству22.
Наиболее известным экспериментом, в ходе которого эмулировалось бесконечное повторение игры, стали два компьютерных турнира, описанных в монографии Р. Аксельрода22. Участниками турнира являлись программы, реализующие некоторые решающие правила в повторяющейся игре. Эффект бесконечного повторения достигался за счет того, что была задана вероятность продолжения игры, одна и та же для каждого шага. Турнир проводился по круговой схеме: каждая программа играла с каждой и, кроме того, со своей копией. В процессе принятия решения на программу не накладывалось никаких ограничений за исключением того, что ей не был известен алгоритм, по которому принимал решение партнер. Многие программы при выборе решения на текущем шаге использовали информацию о нескольких предыдущих шагах игры (например, так действовала стратегия Tit For Tat, ставшая победителем обоих турниров).
Вторым наиболее распространенным подходом к решению «дилеммы заключенного» является подход, основанный па рассмотрении динамического процесса как эволюционной игры24-28.
Их идея заключается в том, что организуется партия повторяющихся игр, состоящая из довольно большого количества итераций, в некотором сообществе игроков - представителей различных популяций. Игроки одной популяции используют одну и ту же стратегию. Перед началом игры все игроки хорошо «перемешиваются», так что ни один из них не знает, с каким партнером он ведет игру. Более того, в некоторых экспериментах допускается, чтобы в ходе партии пары игроков разбивались и смешивались несколько раз.-
По окончании партии подсчитываются накопленные выигрыши каждого игрока и на основе этих данных вычисляются рейтинги каждой популяции. Количество игроков каждой популяции, допущенных к игре в следующей партии, берется пропорциональным ее рейтингу.
Следует также отметить подход к решению повторяющихся биматричных игр, заключающийся в смене типов поведения*“, и игроков на протяжении повторяющейся игры.
Доказано30,31, что выбор типа поведения по определенному алгоритму при некоторых условиях приводит к тому, что частота кооперации игроков в бесконечно повторяющейся игре стремится к единице. При этом существуют ситуации, в которых игроки должны проявлять альтруизм или агрессию по отношению к партнеру.
Данная работа примыкает по своей тематике к области упомянутых выше исследований.
Цель работы.
В первой главе диссертации изучается повторяющаяся биматричная игра типа «дилемма заключенного» с конечной памятью игроков в иерархической постановке. Целью исследования является разработка и обоснование алгоритма построения оптимальных стратегий лидера и ведомого.
Во второй главе изучается одна многокритериальная модель фирмы. Целью исследования является построение оптимального управления, приводящего систему на паретовское множество.
Методы исследования. В диссертации используются понятия и методы классической теории игр, теории графов, линейной алгебры, математического анализа, теории оптимального управления, теории дифференциальных уравнений.
Научная новизна. Основные результаты диссертации:
1. Разработан алгоритм построения оптимальных стратегий лидера и ведомого в бесконечно повторяющейся биматричной игре типа «дилемма заключенного» с конечной памятью игроков.
20Клейменов А. Ф. О решениях в неантагонистической позиционной дифференциальной игре// ПММ Т.61. Вып.5. 1997. С. 739-746.
30Kleimenov A. F., Kryazhimskii А. V. Normal behavior, altruism and aggression in cooperative game dynamics// IIASA Interim Report IR-98-076, 1998.
31 Kleimenov A. F., Volegova E. I. Problems of control by dynamics for repeated bimatrix 2x2 games with switching of local criteria for players// Nonsmooth and discontinuous problems of control and optimization, Pergamon Press, 1999.
2. Построены оптимальные стратегии игроков в играх с одно- и двухшаговой памятью; для построения оптимальных стратегий в игре с двухшаговой памятью на основе указанного алгоритма разработана программа.
3. Доказано, что стратегия TIT FOR TAT оптимальна для лидера в игре с одношаговой памятью при произвольных параметрах игры, а также определены значения параметров, при которых эта стратегия является оптимальной в игре с двухшаговой памятью.
4. В одной многокритериальной модели фирмы указан алгоритм построения множества точек, оптимальных по Парето, при раз-личных значениях параметров системы.
5. Доказано существование таких начальных состояний рассматриваемой модели, для которых использование нормальных типов поведения недостаточно для достижения паретовского множества.
6. В нескольких частных случаях построено оптимальное управление системой, приводящее ее на паретовское множество с минимальным временем использования типов поведения, не являющихся нормальными. Разработанные методы допускают компьютерную реализацию.
Результаты диссертационной работы являются новыми.
Теоретическая и практическая ценность. Результаты, полученные в первой главе диссертации, дополняют теорию повторяющихся биматричных игр и теорию эволюционных игр. Алгоритмы и методы, предложенные в ней, являются конструктивными и создают теоретическую основу для разработки численных методов.
Во второй главе диссертации получены результаты, применимые в рамках теории оптимального управления экономическими процессами.
Апробация работы. Основные результаты диссертации обсуждались и докладывались
- на международной конференции 11-th IFAC International Work-shop «Control Applications of Optimization» (Санкт-Петербург, 2000 г.),
- на Воронежской весенней математической школе «Современные методы в теории краевых задач» (Воронеж, 1999 г.),
- на Всероссийской конференции «Общие проблемы управления и их приложения к математической экономике» (Тамбов, 2000 г-),
- на 30-ой молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 1999 г.),
- на научных семинарах Санкт-Петербургского государственного университета, кафедры теоретической механики Уральского государственного университета и отдела динамических систем Института математики и механики УрО РАН.
Структура и объем диссертации. Диссертация состоит из введения, двух глав и списка литературы. Объем диссертации 144 страниц. Библиография 61 наименование.
Публикации. Основные результаты диссертации опубликованы в 7 работах.
В конце 50-х - начале 60-х гг. в работах Р. Айзекса были сформулированы первые задачи антагонистических динамических игр и были предложены методы их решения. В дальнейшем эти задачи исследовались многими отечественными и зарубежными учеными. Фундаментальный вклад в построение теории антагонистических дифференциальных игр принадлежит научным школам академиков Н. Н. Красовского и Л. С. Понтрягина. Этому направлению посвящены исследования Р. Айзекса4, Н. Н. Красовского, А. Н. Красовского, А. В. Кряжимского, А. Б. Куржанского, Ю. С. Осипова, Л. А. Петросяна, Л. С. Понтрягина, А. И. Субботина, А. Г. Ченцова и других авторов.
Большое внимание исследователей уделяется математическим моделям, формализуемым в рамках теории неантагонистических позиционных дифференциальных игр. Такие модели возникают при описании динамических задач управления механическими, экономическими, биологическими системами, когда управление осуществляется разными участниками. При этом интересы участников не являются полностью противоположными, каждый из них оптимизирует собственный показатель качества и имеет свой собственный ресурс управления. В этом случае задача состоит в выработке управления, приемлемого для всех сторон, участвующих в игре. Основополагающие результаты в этом направлении были получены в работах Ю. Б. Гермейера, А. Ф. Кононенко, Л. А. Петросяна, Э. Мулена, В. И. Жуковского, А. Ф. Клейменова и других исследователей.
Одна из основных проблем в неантагонистической игре состоит в выборе понятия решения, соответствующего содержанию задачи. В соответствии с различными принципами оптимальности выделяются равновесные но Нэшу решения, решения по Штакельбергу, кооперативное решение по Парето.
Важным частным случаем неантагонистических динамических игр являются повторяющиеся биматричные игры.
Среди них отметим бесконечно повторяющуюся игру, на каждом шаге которой разыгрывается известная биматричная игра «дилемма заключенного», предложенная А.У. Таккером. Активность, с которой изучается эта игра в последние годы, объясняется большим количеством ее интерпретаций с точки зрения социологии, психологии, биологии, экономики, философии, что отмечено в работах многих исследователей. Основной вопрос, возникающий при анализе этой игры, следующий: какие условия необходимо создать игрокам, чтобы они проявили стремление к сотрудничеству22.
Наиболее известным экспериментом, в ходе которого эмулировалось бесконечное повторение игры, стали два компьютерных турнира, описанных в монографии Р. Аксельрода22. Участниками турнира являлись программы, реализующие некоторые решающие правила в повторяющейся игре. Эффект бесконечного повторения достигался за счет того, что была задана вероятность продолжения игры, одна и та же для каждого шага. Турнир проводился по круговой схеме: каждая программа играла с каждой и, кроме того, со своей копией. В процессе принятия решения на программу не накладывалось никаких ограничений за исключением того, что ей не был известен алгоритм, по которому принимал решение партнер. Многие программы при выборе решения на текущем шаге использовали информацию о нескольких предыдущих шагах игры (например, так действовала стратегия Tit For Tat, ставшая победителем обоих турниров).
Вторым наиболее распространенным подходом к решению «дилеммы заключенного» является подход, основанный па рассмотрении динамического процесса как эволюционной игры24-28.
Их идея заключается в том, что организуется партия повторяющихся игр, состоящая из довольно большого количества итераций, в некотором сообществе игроков - представителей различных популяций. Игроки одной популяции используют одну и ту же стратегию. Перед началом игры все игроки хорошо «перемешиваются», так что ни один из них не знает, с каким партнером он ведет игру. Более того, в некоторых экспериментах допускается, чтобы в ходе партии пары игроков разбивались и смешивались несколько раз.-
По окончании партии подсчитываются накопленные выигрыши каждого игрока и на основе этих данных вычисляются рейтинги каждой популяции. Количество игроков каждой популяции, допущенных к игре в следующей партии, берется пропорциональным ее рейтингу.
Следует также отметить подход к решению повторяющихся биматричных игр, заключающийся в смене типов поведения*“, и игроков на протяжении повторяющейся игры.
Доказано30,31, что выбор типа поведения по определенному алгоритму при некоторых условиях приводит к тому, что частота кооперации игроков в бесконечно повторяющейся игре стремится к единице. При этом существуют ситуации, в которых игроки должны проявлять альтруизм или агрессию по отношению к партнеру.
Данная работа примыкает по своей тематике к области упомянутых выше исследований.
Цель работы.
В первой главе диссертации изучается повторяющаяся биматричная игра типа «дилемма заключенного» с конечной памятью игроков в иерархической постановке. Целью исследования является разработка и обоснование алгоритма построения оптимальных стратегий лидера и ведомого.
Во второй главе изучается одна многокритериальная модель фирмы. Целью исследования является построение оптимального управления, приводящего систему на паретовское множество.
Методы исследования. В диссертации используются понятия и методы классической теории игр, теории графов, линейной алгебры, математического анализа, теории оптимального управления, теории дифференциальных уравнений.
Научная новизна. Основные результаты диссертации:
1. Разработан алгоритм построения оптимальных стратегий лидера и ведомого в бесконечно повторяющейся биматричной игре типа «дилемма заключенного» с конечной памятью игроков.
20Клейменов А. Ф. О решениях в неантагонистической позиционной дифференциальной игре// ПММ Т.61. Вып.5. 1997. С. 739-746.
30Kleimenov A. F., Kryazhimskii А. V. Normal behavior, altruism and aggression in cooperative game dynamics// IIASA Interim Report IR-98-076, 1998.
31 Kleimenov A. F., Volegova E. I. Problems of control by dynamics for repeated bimatrix 2x2 games with switching of local criteria for players// Nonsmooth and discontinuous problems of control and optimization, Pergamon Press, 1999.
2. Построены оптимальные стратегии игроков в играх с одно- и двухшаговой памятью; для построения оптимальных стратегий в игре с двухшаговой памятью на основе указанного алгоритма разработана программа.
3. Доказано, что стратегия TIT FOR TAT оптимальна для лидера в игре с одношаговой памятью при произвольных параметрах игры, а также определены значения параметров, при которых эта стратегия является оптимальной в игре с двухшаговой памятью.
4. В одной многокритериальной модели фирмы указан алгоритм построения множества точек, оптимальных по Парето, при раз-личных значениях параметров системы.
5. Доказано существование таких начальных состояний рассматриваемой модели, для которых использование нормальных типов поведения недостаточно для достижения паретовского множества.
6. В нескольких частных случаях построено оптимальное управление системой, приводящее ее на паретовское множество с минимальным временем использования типов поведения, не являющихся нормальными. Разработанные методы допускают компьютерную реализацию.
Результаты диссертационной работы являются новыми.
Теоретическая и практическая ценность. Результаты, полученные в первой главе диссертации, дополняют теорию повторяющихся биматричных игр и теорию эволюционных игр. Алгоритмы и методы, предложенные в ней, являются конструктивными и создают теоретическую основу для разработки численных методов.
Во второй главе диссертации получены результаты, применимые в рамках теории оптимального управления экономическими процессами.
Апробация работы. Основные результаты диссертации обсуждались и докладывались
- на международной конференции 11-th IFAC International Work-shop «Control Applications of Optimization» (Санкт-Петербург, 2000 г.),
- на Воронежской весенней математической школе «Современные методы в теории краевых задач» (Воронеж, 1999 г.),
- на Всероссийской конференции «Общие проблемы управления и их приложения к математической экономике» (Тамбов, 2000 г-),
- на 30-ой молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 1999 г.),
- на научных семинарах Санкт-Петербургского государственного университета, кафедры теоретической механики Уральского государственного университета и отдела динамических систем Института математики и механики УрО РАН.
Структура и объем диссертации. Диссертация состоит из введения, двух глав и списка литературы. Объем диссертации 144 страниц. Библиография 61 наименование.
Публикации. Основные результаты диссертации опубликованы в 7 работах.