Стратегические лексикографические игры тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВШНЧЯ УНИВЕРСИТЕТ

На правах рукописи

ЕЕЛТАДЗЕ Гурам Николаевич

СТРАТЕГИЧЕСКИЕ ЛЕКСШГРАМЧЕСКИЕ ИГРЫ 01.01.09 - Математическая кибернетика

Автореферат

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

CUncr-nWfPFyPT - 1992

Работа выполнена в Кутаисском политехническом институте им. 11. И. Цусхелитэили.

Научный консультант - доктор физико-математических наук, проф. Н.Н. ВОРОБЬЕВ

Официальные оппоненты: доктор физико-математических наук проф. ВЖ ДЕМЬЯНОВ доктор физико-математических наук

проф. в. и. еиовошЛ

доктор физико-математических наук проф. В.В. РОЗЕН

Ведущая организация - Институт кибернетики АН Украины

Защита состоится уЛЯ,/]'1992 г. в час.

на заседании Специализированного совета ДР 063.57.99 по эациге диссертаций на соискание учёной степени доктора физико-матема-тнческих наук при Санкт-Петербургском государственном университета по адресу: 199004, Санкт-Петербург, 10 линия, д. 33, оуд.Ш.

С диссертацией мокло ознакомиться в библиотеке им. А.Ц. Горького СПбГУ (Университетская наб., дом 7/9).

Автореферат разослан " / ¿НК^Ц^К 1992 г.

Ученый секретарь Специализированного

совета, канд. физ.-мат. наук В.Ф. ГОРЬКОВОй

ОИ^Я ХАРАКТ¿!Р. 1СТ;Ш РАБОТЫ

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

Дза направления таких: обобщений представляются интересными и перспектар>ны::и. " -

Одно из них связано с отказос от численной оценки сравниваемых объектов, но о сохранением "линейности" их упорядочения, т. е. такого упорядочения, при котором :тз двух различных объектов один долкзн бкть предпочтительнее другого. На этом пути воз-шкант упорядочения, называемые "неархимедовшсГ.

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

Пси резекии многокритериальных: задач иногда требуется учитывать важность отдельных критериев. В некоторых таких задачах из частных критериев удаётся выделять более ватане и ме;;яе ваяние критерии (т. е. упорядочить критерии по важности). При атом лриниг/дется, что малого приращения более ванных критериев целесообразно добиваться за счёт любых потерь по менее важным критериям.

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

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

Лексикографические задачи оптимизации впервые рассматривала' З.Б. Подиновским. Многочисленные задачи такого рода, примеры моделей, приводящих к лексикографическим задачам, а также методологические и вычислительные вопросы решения многокритериальных задач исследованы авторами 3.3. Подиновским, В.М. Гаврилович,

- 2 -

В.Д. Ногиным, В.В. Калашниковым, В. Н. Нефедовым.

Известно, что большое число лексикографических задач неустойчиво. Вопросы устойчивости решений лексикографических задач оптимизации изучаются М.Г. Клепниковой. Устойчивость и устойчивые метода решения лексикографических и других многокритериальных задач оптимизации изучались Д.А. Молодцовым.

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

Общим вопроса« теории игр с неархимедовыми полезностями посвящены работы йишберна, Скала. Теория неархимедовых полезно-стей явилось предметом самостоятельных исследований ряда авторов. 'k:.v, занимался Коттингер. Ванные результаты в этом направлении получены Е.Б. Яновской, в которых исследуются общие вопроси существования решений игр неархиыедовыми полезностями в смысле некоторых принципов оптимальности. К этому же кругу вопросов относится и монография З.Й. Зилкаса "Оптимальность в играх и решениях". Близких вопросов касаются докторская диссертация В.Ü. Роэена.

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

B.ß. Подиновский впервые рассматривает лексикографическую антагонистическую игру как систему ,И ^ , где А и

В - соответственно множества стратегий первого и второго игроков, И - (Н*, ..., Ит) ■ А * ö — /R т - вектор-функция выигрыша первого игрока. Ситуация равновесия в лексикографической антагонистической игре определяется аналогично скалярному случаю. Приводит пример лексикографической матричной игры, в кото-

- з -

роН нет ситуаций равновесия в смешанных стратегиях.'

В.В. Подиновский предложил весьма полезный приём анализа лексикографических' матричных игр в тех случаях, когда множество воз:шжшх значений векторов И ¡А, В) конечны. Оказывается, что существуют такие т вещестзенных чисел С/,..., Сщ , что исходная лексикографическая игра оказывается в известном смысле зк-

т .

Бивалентной скалярной игре (А, В, Ж С^ И У . Этот приём

как- отмечает и сам автор, удаётся распространить и на конечные лексикографические бескоалиционные игры с произвольным конечна.! числом игроков.

П. ¿кшбэрн изучил лексикографические матричные игры и определил ситуацию равновесия в смешанных стратегиях. Он привёл примеры таких игр, в которых: нет ситуаций равновесия в смешанных стратегиях; порока игрок не имеет максиминной, в второй - минимаксной стратегии; один' игрок икозт оптимальную стратегии, а другой нет; первый игрок имеет максиминцую стратегию, второй игрок - минимаксною стратегию, но ситуации равновесия нет.

Как видно из приведённого исторического очерка работ, пос-вяцённых лексикографическим играм, условия существования ситуаций равновесия в коночных лексикографических бескоалиционных играх специально не изучались. Только а работв 13.В. Подиновского рассматривается возможность сведения конечной лексикографической бескоалиционной игры к скалярной бескоалиционно», игре и установления существования в полученной игре ситуаций равнозесия в чистьк стратегиях.

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

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

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

классических понятий устойчивости и введение новых понятий ус-тойчивост/. лексикографических бескоалиционных игр, получение условий равновесности в лексикографических стохастических и дифференциальных играх.

Научная новизна. Основным объектом исследования работы являются игры .с лексикографическими упорядоченными вкигрьаами игроков в пространствах О?171 и .

Е работе построена систематическая теория стратегических лексикографических к аффинных игр. На основе развитого автором математического аппарата исследуются аналитические свойства аффинных игр. Заводятся необходимые и достаточные условия существования ситуаций равновесия в скеаашых стратегиях в коночных лексикографических бескоалиционные играх конечной к бесконечной глубины. В таких: играх описываются множества ситуаций равновесия в смешанных стратегиях. Для лексикографической бескоалиционной игры Г= (Г*, ••Г"1) глубины П7 вводятся понятия кат-рично-сиеяанных стратегий игроков, т. е. таких смешанных стратегий, в которых к&'кдой компоненте игры Г^ соответствуют свои вероятностные распределения на мисюгстзе чистых стратегий игроков, ¿водятся понятия устойчивой лексикографической бескоалиционной игры, ситуации слабого нестрогого равновесия и её устойчивости в чистых стратегиях и доказываются необходимые и достаточные условия слабой нестрогой устойчивости игры Г . Вводятся понятия % -устойчивости ситуации равновесия и ¿ -устойчивости лексикографической бескоалиционной игры в смешанных стратегиях. Исследованы вопросы суцествованкя и нахождения сед-ловых точек в лексикографических и аффинных матричных играх. Определяется матричная игра с функциональными выигрышам и сед-ловая точка в ней. Вопросы существования седковых точек в такой игре сводятся к существованию седловых точек в лексикографической матричной игре бесконечной глубины. Изучаются многоаагозые лексикографические игры: стохастические, дифференциальные игры и выводятся условия существования решений в этих играх. Для лексикографической антагонистической дифференциальной игры с полной информацией введены аппроксимирующие стратегии игроков в дискретных многошаговых играх, вспомогательных основной непрерывной игре.

Обзля методика исследований. Методика исследований лекси-

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

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

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

диссертационная работа езяоана с госбадкетными темами кафедры выстой математики Кутаисского политехнического института и зоила в отчеты: "Резекиэ некоторых классов лексикографических антагонистических игр на квадрате", гос. регистрацкй 7S0I6770, инвентарный ÎP В 343139. "Анализ множества решений лексикографической би;.:атричной игры", гос. регистрация 0L 84.0003743, инвентарный ¡} 02.85.0074350. "Построение теории лексикографических игр", if гос. регистрация ûï.86.0079740 (I этап - "Устойчивость лексикографических: бескоалиционных игр", инвентарный ;.'> 02.87.0022783; 1Î атап - "Осноаы теории лексикографических игр", инвентарный » 02.91.0033124).

Личный вклад автора. Зсе основные результаты диссертации получены лично автором. Результаты совместной работы с О.А. Малафеевым содержится ч § 3. Введение понятия ситуаций слабого нестрогого равновесия л её устойчивости в лексикографически)' бескоалиционных играя*, а гакл® доказательства соответствующих теорем прияздаекиг1 автору.

Апробация pa'Joi-'i. Сснозные результаты диссертации докладывались на I симпозиуме по теории игр (Ленинград, 1978), на 3 симпозиуме по теории игр (Ленинград, 1285), на конференциях мате-

- б -

матиков высших учебных заведений Груз.ССР (Кутаиси, 1979, Тела-ви, 1933), на 4 Всесоюзном семинаре по исследованию операций и системному анализу (Батуми, 1983), на 5 межреспубликанском семинаре по исследованию операций и системному анализу (Кутаиси, 1935), на школа-симпозиуме по теории игр (Кутаиси, 1990), на международной яколе - "динамические многокритериальные задачи при неопределённости" (Ксбулети, 1991),.на семинарах: отдела вычислительных методов исследования операций £Ш АН Грузик, отдела исследования операций ЛЭ1&1 АН СССР, Института Систем Управлений А г! Грузии.

Публикации. Основные результаты диссертации опубликованы в работах [1-163 .

Структура и объём работы. Диссертация состоит из введения, четырёх глав, списка использованной литературы. Объём диссертации - 259 страниц машинописи.

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

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

Глава I. СИТУАЦИЯ РАВНОВЕСИЯ

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

§ I. Равновесие в общих лексикографических играх

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

графических игр •

1.1. Рассмотрим семейство пар

где - произвольное множество, а - нестрогое бинар-

ное отношение порядка на , т, е. . По

нестрогому отношении строится отнолэние эквивалентности

, а гакке отношение строгого порядка Рк=

Определение. Лексикографической суммой семейства множеств с- отношениями

называется пата.

(5, П =

= ии($к,Як) , где 5 = , а . При этом

... чМЛм'л.

Ко отношению РЬ на 5 естественным образом определяются отношения эквивалентности I -Я П Кь и строгого порядка

1.2. Рассмотрим множество игроков ■ ■ ■> п} , семейство множеств с отношениями {($ ~> ^¿^А еУ > (к-4, ■■■, гп) ,

са

где 1*4 - отношение порядка на множестве •-> , выражаю-дее предпочтения игрока ¿€ У ; конечное семейство множеств чистых стратегий I ^^¿^у и функция реализации

£ £ .7

Множества 5' (к= \ . ., /п) называются при этом исходами игры..

Пусть для паздого £=/.•■., гг. заданы бескоалиционные игры с одними и течи к« ;лно'кест2ами чистых стратегий игроков

Додустж, что в данной игре Д*.-/,...,/?У отнояежя частичного порядка. Тогда она является бескоалиционной игрой с упорядоченными исходами в смысле В.8. Розена.

1.3. Для каткого ¿£ У рассмотрим м-тества 5 уперядо--

ченное огноазнием Я¿ : (5, ' и^ [в^ К^) и функция

- а -

реализации (I ■' i? *• S . Полот«« для любого J€

Ufx) =(1Т1М, Un(x)).

Определение. Лексикографической сукыоЗ игр Г*(к- <,..., П>) будем называть игру

rL=<y,miey,s, mie,> и>-

Эту лексикографическую cy;.aiy игр ш будем называть обцей лексикографической бескоалиционной игрой и обозначать через Ри={Г<,Гт) . Число т будем называть глубиной игры Г^ , а множество S - множеством исходов игры Г^ . Везде мы будем считать, что множество S конечно.

3 игре Г^ множество S состоит из гг> -векторов, k -ке компоненты которых являются исходами игры Гк (k-i, ■ ■ ■, т) , а на S задано лексикографическое отнопе-ние. порядка ^ для каждого . Поэтому, естественно

считать, что обцая лексикографическая бескоалиционная игра Г^ является лексикографическим обобщением бескоалиционных игр с упорядоченными исходами.

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

Определение. 3 игре

гь

ситуация X ь с называется (равновесной) ситуацией равновесия, если ни один игрок Le У не ¡/.оке? путём одностороннего отклонения от этой ситуации получить строго более предпочтительный исход по своему отношению» предпочтения /?£ , чем^исход в ситуации X* ;

Множество всех ситуаций равновесия игры ^ будем обозначать чсГрзз Ц (Г ).

Ьсли все отношения

линейны (т. е. в S нет пар несравнимых элементов по отношению }, то понятие равновесной ситуации совпадает с понятием равновесия по Нэшу:

U(х*)>1 U(x*nxi) , Vie3, Vxi е \ .

В ситуации равновесия ни один из игроков не имеет оснований

для одностороннего отклонения от этой, ситуации путём изменения своеИ стратегии, в этом окисле ситуация равновесия обладает устойчивостью.

Рассмотрим игру и для каэвдого игро-

ка б С У рассмотрим зависящие от ситуации Я Е множества стратегий:

&еи"-1=с)}, кч,..., ю.

Рассмотрим зависящие от ситуации ОС игры с упорядоченными исходами

(ЪЩеу,^ Шеу.-и*^ —г».

Если несравктке элементы ¿г ^ 2по отношению считать эквивалентными (положим ¿2 ), то справедлива сле-дуюцая теорема, в которой доказывается, что множество § (п1>) в чистых стратегиях поддается описания через множества ситуаций

_ п1 ГТП

равновесия игр /,...,/.

Теорема 1.1. Следующие утзеряяенкя равносильны:

Ц=4, • . ., т > ¿еУ ; 3) х*е%(Гк(х«)) , т.

1.4. Обозначим через С множество всех ограниченных,

строго изотопных отображений кз (5, Р^) в , снабжённое

отношением ^ .

Задание семейства отображений Л" г У > !'Ле Д: —'¡Я™,

определяет лексккографпческув иг,чу Ы ■ о векторными функциями выиграв 11 = //£ ИТ) :

Игра Гц называется линейкам доуиорядочением игры Г ■ Игру будем называть также лексикографической бескоалицион-

ной игрой глубины т и для неё положим -Г-[Г, . ..) Гт) . .

»

- 10 -

Теорема 1.2. СС*€ ^{Г14) тогда и только тогда, когда для некоторого семейства отображений А£ у , где имеет место X £

§ 2. Смешанные расширения аффинно-лексккографических игр

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

2.1. Рассмотри.", конечную лексикографическую бескоалиционную игру

г=<2, (Ъ}.ву , Ш£еу> ,

где. п} - множество игроков,

множеств о чистых стратегий игрока ¡-£ У , И'с-(Н™),

п) - функции выигрыпа игроков принимают значения в вещественном векторном пространстве лексикографически

упорядоченном отношением ^ (или },

Игра Г единственным образом представляется в виде Г= = (Г1, ...,гт) , где

конечные бескоалиционные игры с числовыми выигрышами.

Определение. Ситуация Х*£ в игре Г называется приемлемой для игрока I Е У ., если для любой его стратегии ■Х-1 е имеет место (X*) ^ Н1 (Я *" X;) .

Ситуация ОС* , приемлемая для каждого из игроков в игре Г , называется ситуацией равновесия в ней. йншш словами, ситуация X* называется ситуацией равновесия в игре Г , если

Н^пф ЪСх'их^) , V¿SУ> .

Смешанны:« расширением игры

назовем

лексикографическую бескоалиционную игру

ГЧП.^П-О, т.еУ, Щеа>,

- II -

s которой каждая из компонент

Гк*<Э, Юи*>> * = <.....-

является смешанный расширением соответствующей бескоалиционной игры Г^ , а. значениями функции зыигрыша каздсго из игроков L S У Б ситуации Xs будет математическое оясидание

HL (х) = (и[(х),

Ситуации равновесия в смешанном расширении лексикографической игры Г мы будем называть ситуациями равновесия самой игры Г в смешанных стратегиях. Множество.ситуаций равновесия в смешанном расширении игры Г обозначается через ^(Г) . Мтак, ситуация Х*бЗ£-П 3i; называется ситуацией равновесия в игР Le-У L ре / , если

. НиСхЧШЪСхЩ), Vis3, VXitXi

и буде»! писать

Легко показать, что тогда и только тогда, ког-

2.2. Рассмотрим бескоалиционную игру

в которой Функции выигрыш игроков имеют вид:

Я = 0,1, ..., m-{,.

3 ситуациях

xeV к ХеХ

мы итш соответственно полиномиальную матрицу к математическое ожидание

см,Ш я cîrx) ■ *■**>

С (Х\ = С[(Х)+С-(Х)-*фх)• г *, i(t,R4<) k --о, 1, ..., т-1 ; • ;. су, teco.a .

В этом случае игру f 'iijA*/) можно представить как сумму

Аффинные формы (аффиннкз игры) степени k fk-0,1,..., m-i) игры Г- (Г*, ..., Г"У определяются как скалярные бескоалици-

Г ?

- - . . >■■■}' со степенями переменной 'Й' Г^7 = зб ^ в качестве коэффициентов. Причём играл: с меньшими номерами компонент приписывается 1 большие веса и когда Ь—0, то такая комбинация сходится к Г :

По этому определению, функции выиграла игрока се У в таких играх будут равны

Нш,» - »1 , <ь--°>,

Итак, аффинная игра степени А имеет вид:

После упрощения, соотношения (2.1) приобретает вид: В соответствии с этим, из (2.2) полупим:

Лемма 2.1. функции выигрыша Н^ и > 1 е ^ >

(11=0, {, т-1) однозначно определяют друг друга.

В силу этой леммы вместо С^ ^ и мы будем

употреблять соответственно обозначения Нщ.^^^ и

2.3. Определение. Будем называть ситуацию 3£ ситуацией равновесия в аффинной игре ^к-и) (к-0,1, ..., т-1)} если существует такое положительное число ^£(0,13 , что для всех t£ [0, £„J выполняются неравенства

~ мь.пч) ' . (2-4)

При выполнении (2.4) будем писать ■

- 13 - _

Для того, чтобы было Xia)) , необходимо и достаточно, чтобы для любого игрока '¿ и любой ого чистой стратегии 3C¿6 1f¿ выполнялось неравенство

Если для некоторого ts(0,4) ^ существует общая ситуация равновесия для всех аффинных игр fj, ■ tfft т) , то игра Г имеет эту же ситуации равновесия, т. е. имеет место . • включение m.i

¿bü Wí^'W■

В следующей теореме доказывается, что (Г) можно описать с помощью аффинной игры íff¡ т) степени т-1 . Для этой игры поло®™ í}ii гп) - F}¿) ■

Теорема 2.2. Для игры Г- (Г1, ..., Гт) имеет место

%{ñ=Ull ^(f}t)). (2.5)

ГеМ teCo,г] \J

Эту теорему мы будем далее упоминать, как теорему о виде множества ситуаций равновесия игры Г . _

После того, как оказываются известными вид множества ^(Г) и вид выражения функции выигрыша H¿fi) (2.3) в игре Га) , а также дано определение (2.4), легко проверить елрг чедливость равенства (2,5).

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

Лексикографическая игра может быть представлена в виде (степенного) полжома, коэффициентами которого являются скалярные игры (аналог разложения в строку или ряд Тейлора-Маклорена). Наоборот» для семейства аффинных игр при определённых условиях существует лексикографическая бескоалиционная игра, с тем же самым множеством ситуаций равновесие, что и у данного семейства.

§ 3. Представления функции выигрыша в аффинных играх рядами

В данном параграфе функция выигрыша L -го игрока в африн-ной игре представляется в ее разложении по формуле Тейлора.

Рассматривается лексикографическая бескоалиционная игра бесконечной глубины Г(ос) и соответствующая аффинная игра оо) •

(Еункция выигрыша в игре Qt,oo) представляется в виде ряда Макло-рена и доказываются необходимые и достаточные.условия существования ситуации равновесия в игре l~0i,oо) .

3.1. В силу (2.3) функция выигрыша игрока 1£Э ■ в аффинной игре имеет вид

ншг^фнгнп^', ,

£=/,..., л; teiO.a .

Для ситуации Х^ЭЕ в силу (3.1) писем

н.у (x)=HUx)+^k (H--M*")(x)-tk-', (з.2)

tfU 1 к-2

что является многочленом от t степени т-4 . k -к> производную функции по t обозначим, как обычно через

Н^^ (X) (в точке t-О ш рассматриваем правую производную). По формуле Тейлора для (3.2) имеем

H.jx) = 21 Щр- tk . ¡■it) k!

Следующая теорема устанавливает достаточные условия непустоты множеств и %(Ц±)) '

Теорема 3.1. Для всех t 6 СО, 1J имеют места включения

__ ГГ7 , _

%(гк-гк-%%(гш)£П(П,

Л — fc

или что го же самое, что

где %(Гк)=%(Н*).

3.2. Рассмотрим две аффинные бескоалиционные игры следующего вида

Определение. Будем говорить, что аффинная бескоалиционная игра Гс^функцией выигрышей Hid) ^стратегически; эквивалентна игре P(t) с функцией выигрышей , еслл существуют такие не зависящие от Х[ функции ^ = fy (X, t)>0, = (Х,±), ¿еС/ , что на некотором положительном интервале t£ СО, tc~] :

Hi(i) ~ % HiftJ * Vi •

- 15

В этом случае пиае.м Гщ ~ .

Обозначим через ГШ пространство аффинных игр с непустыми множествами равновесных ситуаций, т. е. если Г^ £ Г(^)> то Фф для некоторого ta>0 -

Теорека 3.2. Отношение ~ является отноаением эквивалентности на_пространстве ГЦ) . Если ГШ и [({) — , То %(Гш) = <в(Гш) .

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

Теорема 3.4. ¡¡меет место следующее соотношение

где ¡¡у есть аффинная бескоалиционная^ игра с функциями выигрыш, определяемыми следующим образом: И^щ - ^¿с-ц + •

3.3. ¿Зпздено понятие лексикографической бескоалиционной игры бесконечной глубины.

Рассмотрим систему:

(3.3)

где H¿ , ■.. j , ...)=■ H¿i coa) - бесконеч: -мерный вектор Ькигрылей игрока is,, . | пУ .

Будем считать, что на. множестве ситуаций ^= ¿Jy эек-тооы И• Сж) f ос е if) упорядочены лексикографически. Тогда

1,(сх>)

систему (3.3) будем называть лексикографической бескоалиционной игрой бесконечной счётной глубины и обозначать через

- (Г1, ..., Г™...), Смешанны!.! расширением этой игры будет

¡7a,¡ ■ ■ ■ , Г , ■■ ■) ■ Ks#~Cafñ i

Как и в случае игр конечной глубины, Л с If^j тогда и только тогда, когда

H;':q<*)¿H./X*llx¿)i V¿sy> Vcc.e^ .

i,(oo) L,(<x>¡

Аналогично лексикографической игра Р глубины т , построим для игры Г(оо) аффиннуи игру

(t> ' ksZ

Будем считать, что этот степенной ряд для каядой конкретной рассматриваемой лексикографической игры [}«>; имеет положительный радиус сходимости.

В соответствии с (3-4) функция выигрыаа £ -го игрока э игре F}i,oo) определяется через функции выигрыша исходной игры,

Положим для функций на множестве всех ситуаций тождественно

Так что

Hift.oa) ~ Н'¿Ci.m) +Ri(t,m) .

Определение. Ситуация X* является ситуацией равновесия в аффинной игре Га, оо) (обозначаем X*G ££ (ff-t,<»;) ), если существует такое t0 $ (О,!"} , что на сегменте t&C0,iaJ имеет место .

HV/K'J >H.jxyxi), Viey, VXLeXL .

L(t,oo) L(i, 00}

Совершенно аналогично доказательству теоремы 2.2 для игры

Г глубиной Л7 , получается доказательство следующей теоремы о ввде множества % (/¡^) с помощью аффинной игры <*>) . Тсоце;ла 3.5. Для игры F}ooj ..., ...) имеет ыссто

%(ГЫ) = и п .

' ХФ,<) t£[0,rj * Допустим, что для Х^ЗС существует конечные производные всех порядков функции Н^ (X) по i в точке t=0 и lim R.JX) =О

. Тогда в силу равенства

л» -*>со пу

H.JX} = ± (H?-H*-4)(X)ik-<, Hl(X)

H.JX) представляется в виде ряда Маклорена

(■(¿.СО) festf к!

Предположим, что при каждом Х£ & и при всех t е £0, teJ

- 17 -

Теорема З.б. В условиях (3.5) для того, чтобы X*G%(fït)<M)), необходимо и достаточно, чтобы при любом t на положительном сегменте [О, taJ выполнялись неравенства

£т H.JX*)> ест HfrjX*tfXi) ,VUJ, VK.

§ 4. Равновесие в невырожденных аффинно-лексикографических играх

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

Теорема 4.1. m -Невырожденная лексикографическая бимаг-ричная игра имеет непустое множество ситуаций равновесия, число которых нечётно.

Следуем отметить, что результаты этого параграфа можно распространить на произвольные конечные лексикографические бескоалиционные игры.

§ 5, Достаточные условия невырожденности биматричнкх игр

Определение m -невыровденности игры состоит из двух пунктов. Первый пункт совпадает с условием невырожденности скалярной игры Г1 в игре Г ~ (Г1, ..., Гт) . Анализ теоремы 4.1 показывает, что второй пункт не может бить ослаблен, если придерживаться известной схемы доказательства. Однако, формулировка условия tn -невыровденности игры является для практических целей неудобной, поэтому представле? интерес получения условия, гарантирующего ТП -невыровденность игры Г и сводящегося к несложным вычислениям.

В данном параграфе устанавливается достаточные условия m -невырожденности лексикографических бшатричных игр.

■§ 6. '..'атрично-смеааннне расширения лексикографических игр

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

№ -мерное вероятностное распределение, т. е. когда каждой компоненте игры Г^ соответствуют свои вероятностные распределения на множестве чистых стратегий игроков. Кроме того, на мнояе-

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

6.1. Дяя нашл целей нам необходимо ввести операции лексикографического произведения О т -векторов с упорядоченными компонентами в = (й° •.., а™'1) и ■ ■ ■, & т"/) следу-гщим образом:

к=о ¿=0 ' '

Установлены некоторые существенные для дальнейшего свойства лексикографические произведения О {леша 5.1).

6.2. Пусть (Л,Л) измеримое пространство, где .52 множество в пространстве

. Рассмотрим отображение ^'■Л —" 1Ят , которое является счётно-аддитивным. 3 качестве единицы мы возьмём £ = £г) ...)£гл"{) , где £ -бесконечно малое гипердействительное число.

Рассмотрим конечную лексикографическую бескоалиционную игру глубины т

где для кавдого игрока мы будем полагать

Катрично-смешанная стратегия игрока £ в У в игре Г задаётся в виде матрицы

зН -

4

L Je=t

¿xffxp = £fe, k-.i, g:f 4 t-1 ' 1

Множество матрично-смешанных: стратегий игрока LG. У в игре Г обозначим через , а множество ситуаций - через

= П 5Г • • Матрично- смешанное расширение игры Г

обозначим через

Ситуация в игре является X = {Xf, ...,Хп

MX.

Пусть 37= (Х{ t ..., Хп) с *в ситуация а чистых стратегиях. Тогда в ситуации ОС выигрыш £ -го игрока в игра /■£ равен

Hl(XhHilXU...JX„)='^ Н;(Х)оХ(ЗС) =

xeV

где р = «„ + + ... +«п . ^

Определение. Будем говорить, что ситуация JC £ IE является ситуацией равновесия в игре Лг , если

H^in-jXHXi), Viej, VXL е ^ .

В игре ^ возможен' такой ае переход к матрично-смешан-нкм стратегиям, как к смешанным стратегиям (теорема 6.1).

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

Вопрос существования ситуации равновесия для игры fz остаётся открытым. Показано (см. § 17), что даже в случае лексикографической матричной игры ситуации равновесия (т. е. седло-вая точка) в матрично-смешанных стратегиях может и не существовать.

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

- 20 -

Глава 2. СИТУАЦИИ £ -РАВНОВЕСИЯ И УСТОЙЧИВОСТЬ ' ЛЕШИОГРАШЧШШХ ИГР

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

§ 7. £ -Равновесия

В этом параграфе для конечной лексикографической бескоалиционной игры Г-(У, у > глубины т , в отличие от скалярного случая вводится сходное понятие ситуации лексикографического £ -равновесия в смешанных стратегиях.

Положим (е) = (е-1,..,, £т) , где £'>О, £т>0 .

Определение. Ситуация Х£€Х-,Пу%1 в игре Г называется ситуацией лексикографического £ -равновесия, если имеет

ме"° ъгх^н^х'и*)-®

для всех и Х-^Х-, .

Теорема 7.2. Ь любой конечной л&ксикографической бескоалиционной игре Г всегда существует ситуация лексикографического £ -равновесия в-смешанных стратегиях.

Доказательство этого результата оснозано на ток факте, что для любого фиксированного £>0 на множестве всех ситуации игры иогно построить непрерывный фу!ЖЦионал, обладающий некоторым специальным свойством, 3 качестве £ возьмём Е=гпсл

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

§ 3. Устойчивость ситуации равновесия ь чистых стратегиях

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

6.1. Рассмотрим кноаество 2Г лексикографических бескоалиционных игр данного формата (Р4, ..Рп)

пн)=<у, ,

где (Xi, ) - компактное метрическое пространство стратегий игрока ¿еЗ , a Hi=(Hft ..., Н™) непрерывная векторзнач-ная функция выигрыша игрока L .

На (.шоясестве Г* определим расстояние Р следующим образом:

J>(r{H), Г(Н)) = тих 1ШСХ)-НГх)Ц , х=п хс ,

ЗГ СХ t й 3

IIH(x)-H(x)ll*rnax lHk(x)-H?(x)j .

Положим такке для r.zc'ff-X, J>L(xit х[) .

Г i LgJ _____________ метрическое подпространство пространства 2Г , состоящее из игр с непустым множеством ситуаций равновесия ^ /А/у) , где - множество всех ситуаций равновесия в игре Г(Н) .

Рассмотрим многозначьое отображение ч ■'

Г — X , действующее по правилу %(Г(Н)) =%(Н) . Оказывается, что в отличие от скалярных функций выкгрьгла игроков, это отображение не является полунепрерывным сверху. Кроме того, отметим, что -может не быть компактным. Эти обстоятельства являются причинами ряда сложностей, возникающих при использовании понятия лексикографической оптимальности и равновесия применительно к классам лексикографических бескоалиционных игр. Поэтому приходится ввести понятия ситуаций слабого нестрогого лексикографического равновесия. _

Обозначим через G<j> замыкание графика отображе-

ния • С (У) , где С(Х) - семейство всех непустых подмножеств пространства X „ Пусть К(Х) ' - метрическое пространство всех компактных подмножеств пространства X , снабжённое хаусдорфовой метрикой.

Определение. Ситуацией слабого нестрогого равновесия игры Г (И) назовём значение (точку) образа многозначного отображения Т' —^ К(Х) , график которого ест1« G<q

Лемиа 8.2. Пространство игр Г(Н) о непустым множеством слабых нестрогих лексикографических ситуаций равнозескя полно.

- 22 -

Определение. Ситуация ЭС .слабого нестрогого равнозесия в игре Г(Н) называется устойчивой, если для всякого числа Е>0 найдётся такое число >0 , что как только для всякой игры Г'Н) £ Г' выполняется неравенство

найдётся такая ситуация х'£ ^(Н) , для которой £(Х, Х')<£. Игру Г(Н) назовём слабо нестрого лексикографически устойчивой, если все её слабые нестрогие лексикографические ситуации равновесия устойчивы. ^

Лемма 0.3. Лексикографическая бескоалиционная игра Г(Н) является слабо нестрого лексикографически устойчивой тогда и только тогда, когда_ Г(Н) есть точка непрерывности многозначного отображения £?

Теорема 3.1. Множество слабо устойчивых лексикографических бескоалиционных игр пространства ¡Г всюду плотно в !Г' .

Теорема 5.2. Если игра Г(Н) обладает единственной ситуацией слабого равновесия ЭС , то она является устойчивой ситуацией слабого равновесия, а игра Г(Н) - устойчивой.

§ 9. Устойчивость ситуации равнозесия в смешанных стратегиях

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

Выделим множество 2Г' тех лексикографических бескоалицион- • ных игр пространства <Г всех конечных лексикографических игр глубины П> , в которых существуют ситуации равновесия в смешанных стратегиях.

В силу теоремы 2.2, для всякой игры Г(Н) в 1С найдётся такси интервал [0, 1 гдэ t^>0 г и такое семейство аффинных бескоалиционных игр , параметризованное числами t £ [0, t¡?] , множества ситуаций равновесия а которых одно и то ке, и совпадает с множеством ситуации равновесия лексикографической игры

Г(Н)*<3, {ЦеУ> ■

Определение. Игра Г(Н)£Т' называется устойчивой относительно подпространства <Г' , если все её ситуации равновесия устойчивы относительно У' - Ситуация равновесия Х*£ 32 игры Г(Н) называется устойчивой ситуацией равновесия относительно пространства ¡Г' , если для любого О найдётся такое число '£>0 , что как только Г(Н')бЯ" и ]>(Г(Н), Г(Н'))<& . так существует такая ситуация равновесия £ в игре Г(Н') ,

что р(х* х')<е.

Это естественное понятие устойчивости лексикографической бескоалиционной игры не является, однако, удобным при исследовании устойчивости. В связи с этим мы введём новое понятие Ь -устойчивости ситуации равновесия и £ -устойчивости лексикографической игры Г (И) .

В пространстве У неделим множество тех лексикографических бескоалиционных игр ¡¿*(И) , которые соответствуют скалярным бескоалиционным играм с фиксированным параметром £* >0 . Это подпространстзо обозначим через .

Таклм образом, мы установили ззакмно-однозначное соответствие кекщг подпространствами лексикографических бескоалиционных игр и множествами аффинных бескоалиционных игр соответствующих параметру ^ , которое обозначим через

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

Определение. Будем говорить, что ситуация равновесия X игры является ¿"^-устойчивой относительно подпрост-

ранства , если ока является устойчивой ситуацией равновесия в скалярной бескоалиционной игре

¿4 ПН)) относительно

подпространства •

^ Фиксируем такое число I >0 , для которого пространства Ф (Э . Очевидно, что для всякой игры € множество

ситуации равновесия в смешанных стратегиях, совпадающее с множеством ситуации равновесия в скалярной игре £, (Г± (Н)) компактно.

Раса.отрик замыкание графика компакгнозкачногс многозначного отображения ставящего кгре Г±(Н)£ ¿X' в соответствие множество её ситуаций равновесия в смешанных^стратегиях. Распространение этого отображения обозначим через ^ ^ —

где 3£=Л Щ в игре flfH).

С € ^

Лемма 9.2. Игра (И) £ ^ устойчива в том и только в row случае, когда она является точкой непрерывности отображения ff £ .

Теоое:.-а 9.1. множество t -устойчивых игр пространства всюду плотно в Г* . _

Теорема 9.2. Если множество (^t (Н)) шеет единственную точку X , то X - устойчивая ситуация равновесия, а игра Ц. (И) -устойчивая.

Для аффинной бескоалиционной игры . определяется отображение Нэиа и доказывается следующая лемма.

Лемма 9.5. Если ре 3£ устойчивая неподвижная точка отображения Наша J/fa »то р - устойчивая ситуация равновесия аффинной игры Г/^.

'Уеорема 9.3. Если в игре fjy (H(t\) множество ситуации равновесия конечно, то хотя бы одна из них явля-

ется устойчивой.

§ 10. Устойчивость Парето-оптимальных и равновесных ситуаций

3 этом параграфе введено распространение понятия Парето-оп-тимальной ситуации для лексикографической бескоалиционной игра (а также для лексикографической бескоалиционной позиционной игры), компромиссного множества для задачи (X, И) на лексикографический случай и исследуются вопросу их устойчивости в слабом смысле.

§ II. Конечность и нечётность множества ситуаций равновесия ^ Для кавдой игры Г(Н}£ Т' рассмотри..! максимальное из_чисел tg , определённых з параграфе S и обозначим его через' t^ . Назовём if* характеристическим числом игры Г(Н) .

Зафиксируем некотсое t*>0 и рассмотрим те лексикографические бескоалиционные игры Г(Н) , для которых t*< t" . множество обозначим через К* .

Основной целью данного параграфа является доказательство следующей теоремы. ■ , (

Теорема II. I. Существует такое семейство подмножеств '(¿*С<Г запараметрмзованнсе точками t*>0 (так, что для t^t* ¿|4с для каждого из которых имеет место следующее представление

¡к-

Здесь (к-^.-.^Т) - множества регулярности, внутри

кшздого из которых игра име^т конечное нечетное

число ситуаций равновесия, гладко зависящих от игры. -

сингулярное множество. Множества Щ'/1 пределяюгся полиномиальным соотношениями - неравенствами (так что является полуалгебраическими).

Глава 3. СВДЛОВШ ТОЧКИ 'Л МЕТОДЫ Ж ПОСТРОЕНИЯ

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

§ 12. Аффинные матричные игры

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

Определение. В аффинной матричной игре с матрицей

выигрьмей ситуация называется седловоР точ-

кой в чистых стратегиях, если выполняются неравенства

ац. ш < а^с ш ^ ац щ , Ус , V/.

на некотором положительном интервале , ^€(0,42 .

Теорема 12.1. Для того, чтобы в аффинной матричной игре Г(1] (или в лексикографической матричной игре Г ) существовала седловая точка в чистых стратегиях, необходимо у достаточно, чтобы на некотором положительном интервале t€[0,tв] выполнялось равенство

- 26 -

max min üL1{i) = min max Qr.(t) . L j * J. L *

Определение. В аффинной матричной игре с матрицей выигры-ией H(i) ситуация (X* Y*)5 Xх У в смеианнкх стратегиях называется седловой точкой (или решением), если существует такое t0 е (0, -/J , что для всех t£ [0, ts]

XH{i) Y*riX*Hfi]У*т<X%JVT, УХеЗЕ, VYeV .

В отом случае пиаем (X*, Y*)_e % (Qtl) ■

Ке;.ду множествами ' и соотношение задаёт-

ся равенством (2.Ь).

функции выигрыша в аффинной матричной игре представляются в виде рядов по параметру t^CO, Yj . Изучен вопрос дифференцирования значения аффинной игры.

§ 13. Матричные игры с функциональными ваигрыза.ж

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

13.1. Рассмотрим рхд, -матричную игру [у^)-If с матрицей выигрьией F , олементами которой являются функции ■

14,. ..,/>;

V

и имеющих непрерывные производив® всех порядков на некотором положительном интервале [О, t3JC [О, ■fj . Положим

Как к в аффинной матричной игре, введём .для игры if следующее определение.

Определение. В матричной игре ff с матрицей внигрцией Fft) ситуация (X*, Y~*) в смешанных стратегиях называется седловой точной (или решением), если существует такое ,

что для всех Ь€[0, t(¡J

ХГШУ*\У*гйугтУт, УХ, VУ (13.1)

и будем писать . (X* У*) е .

Введём ещё одну модификацию понятия седловой точки игры . Для этого рассмотрим последовав тьность положительных чисел ал из [0, Ье] С [О, У7 , сходящиеся к нулю - 61т tn-0.

Определение. 3 игре Гр с матрицей выигрышей Р ситуация У*,/ в смешанных стратегиях называется седловой точкой на {Ьп} > если Для всех ? {'¿п} . начиная с некоторого п , выполняются неравенства (13.1). Прь этом положим

Легко показать, что % (Гр (О,±о))с Гр {^пУ) ■

Теорема 13.2. Если существует такая последовательность {±п } С [0, ¿о 7 сходящаяся к кулю, что все скалярные игры ...) стратегически эквивалентны, то

13.2. Разложим каздуи из матрицы Р в ряд Макло-

рена в точке

и рассмотрим матричную игру с матрицей выигрышей

ПИ = {fij.fi)} .

Пусть = Г/*» ■■. ,Гт, ...) лексикографическая -

матричная игра бесконечной глубины с матрицей вкчгрысей

Если сходятся все ряды ^к функциям М для всех I и на некотором положительном интервале ¿о] , т. е. если РМ-Р(Ь), t£ [0,£о] , то между матрица;.:',! РЛУ и // существует взаимно-однозначное соответствие. Теорема 13.4. Имеет место включение

Д (ом) , где {-^-Ц .

- 28 -

§ 14. Применен*/е математического поограмкрования

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

§ 15. Алгоритмы нахождения седловых точзк в

лексикографических и айриккыг матричных играх .Для нахонления оптимальных стратегий игроков в лексикографических и аффинных матричных играх можно применять традиционные методы для классических матричных игр: метод, основанный на теореме ¡!1епли-С:юу, метод Брауна-Робинеон! а такие для случая матриц малых размероз графоаналитический метод. Все оти методы описываются.в данном параграфе. Для иллюстрации приводятся также примеры.

§ 15. Седловне точки в лексикографических бесконечных играх Здесь определяется лексикографическая антагонисгачэскач иг-'ра на компа..ге, а для неё - седловая точка з чистых стратегиях и значение. Описывается ;масс таких игр, в которых существуют седловые точки. .

§ Р. .'.¡атрично-скешаннке стратегии в лексикографических

матричных играх В данном параграфе рассматривается матрично-сиеаанное рас-шрение лексикографической матричной игры Г=(Г{ ■ ■ -;Гт) глубины ГЛ , как частный случай матриччо-смешсшого расширения лексикографической бескоалиционной игры, введённой с § 6. Рассмотренный здесь призер лексикографической матричной игры показывает, что седловая точка в таком смепаннок расширении может и не существовать (в этой игре не существует также седловая точка в'смешанных стратегиях).

Глава 4. ШОГСКАГОШЕ ШС;Н0ГРА^Н2СЮЕ ИГШ

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

§ 18. Аффинные стохастические игоы В атом параграфе определяется лексикографическая антагони-

стическая стохастическая игра. Показывается, что условия существования решений в лексикографических стохастических играх сводятся к существованию решений стохастических аффинных игр.

Лексикографическая стохастическая игра глубины ffl есть набор» состоящий из Р лексикографические игровых олекентоз, или позиций Г}, - (Гр^Г^ ) (k = j,. . ., р) . :{акдкй лексикографический игрозой элемент опксквае' гя некоторой Р/> у ^ -матрицей, элементы которой имеют вид

=(a*'J,..ak,m) + 51 о.кеп

'■■■>piJ. ' LJ. J 'l, Ч >

где р ^

Стратегии игроков здесь определяются как и в скалярном случае.

Пусть fi) - аффинная игра позиций . Аффинную форму вектора В™) » будем обозначать через

Теорема IB.I. Пусть р

(6l.JmW, ../л,

тогда р c-f Ч-

B(i)--a(i)+?r^re,«) . iia.i)

Допустим, что существуют решения игр Чг,^) на интерзале t s Г"; ^ J (k ~ 1, ■ ■ ■, р) . Заменим в (I3.I) компонентой

значения V^li} t te [О, i^l и положим

Trk(t)*Vae(bktn) , (13.2)

где 5kit) есть -матрица l$fj,(t)} , элементы которой

определяются равенствами

Рассмотрим кроме того, /^х^ -матрицу = {^¿^} ,

■ ■ ■ г Р , составленную из вероятностей разыгрывания игровых элементов. Множество решений игры Г с матрицей выигрышей А обозначим через Г(А)) ,

Теорема 16.2. Если существует решение игры на инте-

рвале [О, , то имеет место включение

$(ПАт))П

на интервале

Теорема Ш.З. Если для всех и t€[0,t*]

то существует ровно одна вектор-функция

на [О, ±о] £ [0, t *] , удовлетворяющая соотношениям

(10.2) и (18.3).

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

§ 19. О существовании садловой точки в дифференциальных играх

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

Пусть динамика игрока I определяется векторным дифференциальным уравнением СС =/(X, и) , а динамика игрока 2 - векторным дифференциальным уравнением у, V) , в этих уравнениях и(-) и суть управляющие функции игроков соответственно I и Предполагается4 что функции 4 н §■ удовлетворяют условиям, гарантирующим существование и единственность решения, соответствующего любой паре допустимых управлеа.Л игроков. Игра начинается в момент времени ^=0 и процесс игры продолжается некоторое предписанное заранее время "Ь = Т< , после чего игрок I получает от игрока 2 лексикографический вектор-выигрыш Н(х>у)=(Н*(х,у), Н^х, у)) , где ХГ-) , соответственно траектории игроков I и 2. Игрок I стремится лексикографически максимизировать, а игрок 2 - лексикографически минимизировать И(х,у) ,

Наиболее просто поддаётся описанию случай игры с полной

информацией, в которой игрокам в кагедий момент в^змени t при выборе Uft) и V~ii) известны фазовые состояния ОС ft) , y(t) , Иногда требуется ещё знание одним .из игроков или обоими в каждый текущий момент t значения.управления противника. В этом случае противник дискриминирован, а сама .чгра называется игрой с дискриминацией противника. При таком определении полной информации усматривается аналогия с многоша^свыми (позиционными) играми с полной информацией. •

С помощью вспомогательных результатов данного параграфа и с помощью леммы 7,5 об эпиморфизме, доказывается следующая теорема.

Теорема 19.8. В лексикографической дифференциальной игра с полной информацией при любом £ > О существует ситуация лексикографического £ -равновесия ( £ -седлсвая точка).

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

ресурсов

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

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

Теорема 20.1. При любом £>0 в играх Г(-) и ГО) существуют ситуации лексикографического £ -равновесия.

РАБОТЫ, ОПУЫШШАНШЕ ПО ГШ ДИССЕРТАЦИИ

I. Бептадзо Г.Я. Достаточные условия существования ситуации равновесия з лексикографических бескоалиционных играх //Труды молодых учёных и специалистов г. Кутаиси. - Тбилиси, Мецниереба, 1978. - С. 25-31.

2. Белтадзе Г.Н. Лехсикохрзфпческиз бесконечные антагонистические игры с г. -лукло-вогнутыми функциями выигрыша //Тезисы докл. 8 конф. математиков высших уч. зав. ГССР. - Тбилиси, ТГУ, 197Э. - С. 20-21.

3. Белтадзе Г.Н. Множество ситуаций равновесия в лексикографических бескоалиционных играх //Сообщения АН ГССР. - i960.

- том 98, /5 I. - С. 41-44.

4. Белтадзе Г.Н. Смешанное рас-лиренке конечных лексикографических бескоалиционных игр //Сообщения АЛ ГССР. -• 1930. - том 93, ¡Г> 2. - С. 273-276.

5. Еелтадзе Г.Н. Биматричние игры со строго упорядоченными по значимости критериями //Тезисы докл. 4 Всесоюзны? семинар по исследованию операций и системному анализу "Принятие реиений в условиях многокритериальное™ и неопределённости". - Ы. Батуми.

- 1933. - С. 9.

6. Белтадзе Г.Н. Метод Брауна-Робинсон для лексикографических матричных игр //Тезисы докл. 10 конф. математиков высших уч. зав. ГССР. - Тбилиси, ТГУ, 1933. - С. 23.

7. Белтадзе Г.Н. Условия гп -невырожденности в играх двух лиц со строго упорядоченными по важности критериями //Тезисы докл. 5 Межреспубликанский семинар по исследованию операций к системному анализу "Принятие решений при многих критериях".

- а. - IS35. - С. 54.

3. Белтадзе Г.Н. Ситуации равновесия в лексикографических биматричных играх //Сообщения АН ГССР. - 1936. - том 121, № I.

- С. 33-35.

9. Белтадзе Г.Н., Малафеев O.A. Парето-Олтимальные ситуации ь дифференциальных играх со многими участниками (часть 2: Устойчивость ситуаци1" равновесия в лексикографических бескоалиционных играх) //Межвузовский тематический сб. научных трудов. Многошаговые, иерархически^ диадические и бескоалиционные игры.

- Калинин, ¡{ГУ, 1987. - С. 29-32.

10. Белтадзе Г.Н. Анализ аффинных форм лексикографических игр //Сообщения АН ГССР. - 1990. - том 137, № 2. - С. 265-263.

11. Белтадзе Г.Н. Лексикографические матричные игры и математическое программирование //Сообщения АН ГССР. - 19?0. - ч'ом 137, 5 3. - С. 485-483.

12. Белтадзе Г.Н. Ситуации равновесия в аффинных играх

- 33 -

//Сообщения АН ГССР. - 1990. - том 139, № I. - С. 66-68.

13. Белтадзе Г.Н. О суцествозании решения в лексикографических дифференциальных играх с полной информацией //Сообщения АН ГССР. - 1990. - том 140, № 2. - С. 293-295.

14. Белтадзе Г.Н. О решении матричных игр с функциональными выигрышами //Сообщения АН ГССР. - 1991. - том 141, I. - С. 21-24.

15. Велтадзе Г.Н. Диализ бесконечноразмерной лексикографической игры /'/Сообщения АН ГССР. - 1991. - том 141, »2. - С. 241-244.

16. Белтадзе Г.Н. Лексикографические теоретико-игровые задачи динамического распределения ресурсов //Сообщения АН Грузии. - 19Э1, том 142, » I. - С. 41-44.

Белтадзе ГУрам Николаевич Стратегические лексикографические игры