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

РГ Б ОД 1 О ФЕВ 1998

На правах рукописи УДК 519.833, 519.9

НАБАТОВА ДАРИЯ СЕРГЕЕВНА

ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ КОНЕЧНОЙ ИГРЫ ТРЕХ ЛИЦ В ИНФОРМАЦИОННОМ РАСШИРЕНИИ

05.13.01 - управление в технических системах

АВТОРЕФЕРАТ

на соискание ученой степени кандидата физико-математических

наук

Москва 1997

Работа выполнена в Московском государственном авиационном институте (техническом университете)

Научный руководитель: кандидат технических наук,

доцент И.И.Топчеева

Официальные оппоненты: доктор физико-математических наук,

профессор С. Л. Зенкевич

кандидат физико-математических наук, доцент Н. В. Никитин

Ведущая организация: Институт системного анализа РАН

Защита состоится "_"_199_г.

в_часов на заседании диссертационного совета 05.13.01

в Московском государственном авиационном институте (техническом университете).

С диссертацией можно ознакомится в библиотеке МАИ Отзыв на автореферат в 1 экз. просим направлять по адресу института: 125871, Москва, А-80, ГСП, Волоколамское шоссе, 4. Автореферат разослан "_"_199_г.

Ученый секретарь диссертационного совета доктор физико-математических наук, доцент

Ю.Г. Марков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность работы определяется:

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

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

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

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

Методы исследования: теория игр, системный анализ, информационная теория иерархических систем, численные методы, теория графов, математическое программирование.

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

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

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

Диссертационная работа выполнена на кафедре "Математическая кибернетика" МАИ.

Апробация работы. О содержании работы было доложено на

• Всероссийской научно-технической конференции "Проблемы совершенствования робототехнических и интеллектуальных систем ЛА" г. Москва, МАИ, 28-30 мая 1996 г.

• Международном научно-техническом семинаре "Современные технологии в задачах управления и обработки информации" г. Алушта, 12-16 сентября 1996г.

Публикации. По теме работы опубликовано 7 печатных работ. Структура и объем работы. Работа состоит из введения, 5 глав, заключения, списка использованных источников. Основной текст содержит 139 страниц, 4 таблицы и 3 рисунка. Список литературы включает 81 наименование.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

предоставлением игроками информации о действиях друг друга и расположением игроков по разным уровням иерархии, в зависимости от объема получаемой информации. Большой вклад в развитие этой теории, которая получила название теории иерархических систем, принадлежит Моисееву H.H. и Гермейеру Ю.Б. В их работах была сформулирована идея о том, что при описании конфликта необходимо учитывать различную степень информированности игроков о действиях друг друга. Игры, в которых такая информация присутствует и игроки обязаны принимать решение с ее учетом, расширяя для себя таким образом множество своих стратегий, получили название информационных расширений. Применение информационных расширений позволяет в некоторых случаях расположить игроков в иерархические структуры и для различных уровней рассматривать метаигры с меньшим числом участников, чем исходная. Дальнейшее развитие эти идеи получили в работах Ховарда, Васина, Гурвица, Кукушкина.

Данная работа посвящена исследованию конечной игры трех лиц

Г = </,{*,},.,,{ЯДО)},., )

где X j - множество стратегий для /-того игрока;

Hi(o) -платежные функции, определяющие выигрыш каждого

игрока;

а еЛХ, •

формат игры {ш 1, т 2, пг з}.

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

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

Первая глава диссертационной работы посвящена исследованию вычислительного алгоритма решения биматричной игры.

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

Г = (Х,¥,А,В,(т,п) >.

В п. 1.2 показано, что задача определения ситуации равновесия (х°,у°)по Нэшу сводится к определению параметра

а и пары (х',у') - векторов, удовлетворяющих следующим соотношениям:

х* = .,*'), у =(у'1,у'2,...,у'п),

х- > О, 1 < / < т, у] > 0, 1 < у < п а^-а,- а у > О, 1 < / < т, 1 < у < п, Ц = а - Ьу >0, 1 < / < т, 1 < у < л ,

Л Л!

1</<т; ^¿/.х;1 <у<«,

у=1 /=1

п т т п

?,Уг(Еь'в-х;-1) = о 2>; -(IX ■ ^ -1) = о,

у = 1 / = 1 / = 1 у=1

• •

= , 1 < / < т\ 1<у <Л.

IX 2>;

/=1 у=1

Идея алгоритма Лемке-Хоусона состоит в направленном переборе пар векторов (х,у) , определяемых п+т-1 равенствами до достижения точки, в которой выполняются (т+п) условий. В п. 1.3 изложены основные шаги алгоритма по определению ). Итерационная процедура симплекс-преобразования идет отдельно по множеству X и множеству У. Составляются таблицы: из столбцов матрицы А и векторов базиса Я" таблица А', из строк матрицы В и векторов базиса Ят- таблица В'. Определяется (х<0),У0))- начальная точка. По отличным от нуля элементам начальной точки определяются те векторы а1 и Ь]) которые будут введены в базис, вычисляются новые симплекс-таблицы А* и В'. Каждый шаг алгоритма определяет множество векторов:

xjk> = + Xipi, l<i<m,

=yf-v+lijqJ, l<j<n

где А. и |-i определяются следующим образом:

п _

вычислим 4 I = X! ай ~уТ> ' = 1>т, из всех отрицательных У=1

элементов таблицы А' ау < 0, qjr < 0 найдем

1 «« i'J

из всех положительных элементов clsJ > 0, qJ' > О

. maxi -У^Х-Х" найдем maxj--— > ~q*'\~ '

В столбец с А, вводится тот элемент из (к',Х"), который отличен от 0. Если они оба равны 0, то вводится 0. Из таблицы А* можно определить п новых точек, принадлежащих множеству Y.

т _

Аналогично для таблицы В'-.Ц j = 'х/0)> J = l>n, из

/-1

всех отрицательных элементов таблицы .5* ß й < 0, р'г < 0 найдем

ГП1Щ-

(л * -1). *i0)

-\ = * ,

ß* Р"

из всех положительных элементов ß is > 0, р" > 0 найдем

Г (ч,-1). .,

maT~tT' "Гц •

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

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

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

Вторая глава посвящена теоретическим аспектам решения игр с тремя участниками в информационном расширении.

В п. 2.1 сформулировано определение конечной игры трех

лиц: Г = ( /,{Х,}/е/,{ЯДа)}/е/ )

Введено понятие тензоров платежей А, В, С и смешанного расширения, приводится доказательство теоремы существования

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

В п. 2.2 доказана теорема о связи между решением задачи определения ситуации равновесия по Нэшу и задачей нелинейного программирования:

Теорема 2.2.2. Для того, чтобы тройка С*0,у0,г0) являлась ситуацией равновесия конечной игры трех лиц, необходимо и достаточно, чтобы для некоторых неотрицательных чисел р, м>

набор х°, у0, р, 1, IV представлял собой решение следующей задачи нелинейного программирования: Максимизировать

т п I

'У} •гк-[ат+Ьцк+ст)-р-д-\9

, = 1 у=1*=1

при ограничениях

п I т

У=1 к=1 /=1

т I п

X Л**?» yJ>0, 1<]<п,

/=1 к=1

т п I

/=1 ]=\ к*1

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

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

игроков, рассмотрена двухуровневая схема информированности по системе ведущий-ведомые.

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

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

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

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

Г' = .{Х(гД Y(zJ, Hf, Н*, H*} -

игра с тем же множеством игроков, что и Г, платежные функции которой определяются с учетом информации о стратегии ведущего игрока гк. Для конечной игры трех лиц выражение для функций платежей имеют вид: А = \\аик\\^->Ак = ||я,||; В = Ц^Ц—В* = ||б,||

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

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

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

В предложенном варианте информационного расширения ситуация в игре определяется тройкой {х(т.к),у{тк),гк), у(т.к) еГ, где х{хк) еХ, у{ък) еУ - вектора из смешанного расширения игры Г' и ¿к - стратегия, выбранная ведущим игроком.

Определение: Тройка (х'(2'к), у'(21), г\) называется ситуацией равновесия по Нэшу информационного расширения конечной игры трех лиц, если для нее выполняются следующие соотношения:

Н^х'^), у{гк), гк) > Н^х, у'(гк), г\) для Ух еХ

Н*(х(гк), у(гк), гк) > Щ(х(гк), у, г\) дляУуе7

у\гк), ък) > Щ(х(хк), у\г[), гк) для V^ = 1.

Теорема. Множество ситуаций равновесия по Нэшу информационного расширения конечно.

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

В п. 2.5 приводится описание шагов алгоритма по определению ситуации равновесия по Нэшу информационного расширения конечной игры трех лиц.

Третья глава посвящена прикладным задачам.

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

критерия оптимальности используется условие минимального загрязнения окружающей среды.

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

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

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

В пятой главе приведено описание программного обеспечения для реализации на ЭВМ предлагаемого алгоритма решения биматричной игры и игры трех лиц.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

При выполнении работы были получены следующие основные результаты:

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

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

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

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

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

5. Представлен и внедрен в учебный процесс компьютерный практикум по курсам "Теория игр и исследование операций", "Оптимизация дискретных моделей в механике и макроэкономике", читаемых на факультете "Прикладная математика и физика" МАИ.

6. Создано программное обеспечение, реализующее алгоритм.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ ^

1. Гришин В.И., Шайкина Д.С. Использование биматричных игр для определения оптимального управления. -В сб.:Марковские случайные процессы и их применение. -Саратов, издательство Саратовского государственного университета, 1987.

2. Набатова Д.С. Вычислительный алгоритм определения ситуации конечной игры трех лиц в информационном расширении. -М.: МАИ, 1996. -Деп. в ВИНИТИ. В96 № 1494.

3. Набатова Д.С. Математическая модель принятия решения робототехнической системой в условиях неопределенности и конфликта. - В сб.: Труды Всероссийской научно-технической конференции: Проблемы совершенствования

робототехнических и интеллектуальных систем ЛА. -М.: МАИ, 1996.

4. Набатова Д. С. Определение ситуации равновесия по Нэшу как решение задачи нелинейного программирования. -М.: МАИ, 1995. 12стр. -Деп. в ВИНИТИ. В95 № 1367.

5. Набатова Д.С. Формирование вектора оптимального управления для систем, функционирующих в условиях конфликта, с помощью вычислительных алгоритмов теории игр. -В сб.: Труды международного научно-технического семинара: Современные технологии в задачах управления и обработки информации. - Алушта, 1996.

6. Набатова Д.С. Решение задачи оптимального распределения ресурсов с известными оценками эффективности для систем, функционирующих в условиях конфликта. -М.: МАИ, 1996. 9стр. -Деп. в ВИНИТИ. В96 № 1495.

7. Топчеева И.И., Шаыкина Д.С. Диалоговая система принятия решений в робототехнических системах на основе теории игр. -В сб.: Анализ и синтез нелинейных систем управления. -М.: Энергоатомиздат , 1990.