Математическое моделирование задач поиска методами теории игр тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Гарнаев, Андрей Юрьевич

• Гарнаев, Андрей Юрьевич
• доктор физико-математических наук
• 1997

Оглавление диссертации доктор физико-математических наук Гарнаев, Андрей Юрьевич

СОДЕРЖАНИЕ

Введение

Глава I. Проблемы о защите объекта

1. Игра на плоскости

1.1. Основные результаты

1.2. Обсуждение результатов

1.3. Доказательство теоремы 1.1 и леммы 1.1

2. Игра на прямой

2.1. Случай & + 03 > 2Д

2.2. Случай 0i + 0з < 202

2.3. Обсуждение результатов

2.4. Доказательство лемм 2.1,2.2 и теорем 2.1-2.4

2.5. Обсуждение второй проблемы Айзекса

2.5.1. Случай Tii + газ < 2га3

2.5.2. Случай щ + щ> 2п2

2.6. Игра на отрезке

2.6.1. Случай к = 1

2.6.2. Случай к- 2

3. Проблема о таможне-контрабандисте

4. Трехкатерный вариант проблемы таможня-контрабандист

5. Задача защиты объекта на графе

5.1. Случай к > w

5.2. Случай wn<k<w

5.3. Случай к < wn

6. Задача защиты объекта от быстрого диверсанта

6.1. Диверсант двигается вдоль одной дуги

6.2. Основной результат

2

6.3. Случай простого движения охраны

Глава II. Игры с выбором момента времени

7. Дуэль, момент окончания которой имеет непрерывную функцию распределения

7.1. Единственность равновесия по Нэшу

7.2. Обсуждение результата

7.3. Шумная дуэль

7.4. Бесшумно-шумная дуэль

8. Дуэль, момент окончания которой имеет дискретную функцию распределения

8.1. Случай (I)

8.2. Случай (И)

8.2.1. Подслучай (а)

8.2.2. Подслучай (Ь)

8.3. Шумная дуэль

8.3.1. Случай Ki(p) > Ki{ 1) при г = 1,2

8.3.2. Случай К{{р) < Ki( 1) при г = 1,2

8.3.2. Случаи Ki(p) < Ki( 1) и Kj(p) > Kj( 1)

8.4. Бесшумно-шумная дуэль

8.4.1. Случаи К2{р) > К2{ 1)

8.4.2. Случай К>(р) < #¿(1) при i = 1,2

8.4.3. Случай Ki(p) > üTi(l) и Kj(p) < Kj( 1)

9. Смешанная дуэль с фиксированным моментом окончания

10. Дуэль во время дележа

Глава III. Игры поиска при отсутствии информации

11. Постановка задачи и формулировка основных результатов

11.1. Оценка сверху ожидаемого времени обнаружения

11.2. Оценка снизу ожидаемого времени обнаружения

Заключение

3

Литература

Введение диссертации (часть автореферата) на тему «Математическое моделирование задач поиска методами теории игр»

ВВЕДЕНИЕ

Математическая теория поиска является широко разветвленной, богатой результатами и приложениями областью прикладной математики. Первоначально теория поиска развивалась преимущественно для военных целей, но в последствии выяснилось, что методы этой теории могут с успехом применяться при исследовании многочисленных проблем производства, в вопросах экономики, экологии, медицины, спорта, права, техники и бизнеса. Большой вклад в развитие теории поиска был внесен в работах Альсведе и Вегенера [2], Бека [78,79], Брауна [81], Купмана [102,103], Сартскало [117], Стоуна [120,121] и Хеллмана [60]. Среди поисковых задач особое место занимают:

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

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

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

ских же задачах процесс поиска состоит из последовательности (может быть, бесконечной) шагов поиска и кроме того, сам объект поиска может обладать некоторыми динамическими возможностями. Статические задачи рассматриваются методами классической теории игр [5,6,9,36,37]. Значительный интерес и развитие динамические игры поиска получили после выхода в свет книги Айзекса "Дифференциальные игры" [2]. Отметим, что динамические игры поиска тесно связаны с одним из разделов теории дифференциальных игр, а именно, теорией дифференциальных игр с неполной информацией. Большой вклад в развитие теории игр с неполной информацией был внесен в работах Алперна [6870], Базара и Олсдера [73], Бастона и Востока [74-77], Батухтина [4], Гала [88-94], Захарова [45], Карлина [97], Красовского [17-21], Кряжим-ского [23,24], Куржанского [25,26], Мазалова [29], Малафеева [30], Ме-ликяна [31], Никольского [33], Осипова [35], Петрова [38,39], Петросяна [40-48], Пшеничного [52,53], Ракла [108-110], Сакагучи [111-117], Субботина [58], Томского [48], Черноусько [63], Чикрия [64-67]. Также по играм поиска отметим работы Вошбурна [126], Зеликина [12], Зенкевича [113-115], Луценко [27,28], Скитовича и Чистякова [55] и Субелмана [122]. В настоящее время, в связи с многообразным спектром проблем, моделируемых посредством игр поиска, одной из наиболее актуальных задач является создание и дальнейнее развитие методов решения задач игр поиска, нахождение оптимального поведения участников в моделируемых конфликтных ситуациях. Данная работа посвящена развитию таких методов и подходов. В ней, в частности,

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

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

6

нием и точкой "взрыва".

2. Решена дискретная задача, сформулированная Раклом, о поиске точки при помощи двух отрезков для широкого класса случаев.

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

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

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

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

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

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

Айзеке [96] с целью обоснования необходимости применения смешанных стратегий в дифференциальных играх с запаздыванием информации сформулировал и решил две антагонистические дискретные игры на полуоси. Сформулируем первую из этих задач. Имеются два игрока: стрелок и мишень. Мишень может двигаться со скоростью, не превосходящую з единиц, только по целочисленным точкам полуоси Ох. Стрелок в каждый момент времени производит по выстрелу по любой выбранной им точке полуоси Ох. В точке О находится бункер, достигнув которого мишень оказьюается в безопасности от огня стрелка. Стрелок обладает полной информацией о местоположении мишени с запаздыванием на единицу времени. Целью стрелка является максимизация количества попаданий в мишень до того, как она достигнет бункера. Вторая задача Айзекса формулируется аналогично первой, с тем различием, что в случае попадания стрелком в точку, в которой находится мишень, поражение мишени происходит не достоверно, а с некоторой вероятностью а, где а 6 (0,1). Стрелок стремится максимизировать вероятность поражения мишени до того, как она достигнет бункера. Ли [100,101] предложил обобщение первой задачи Айзекса на случай, когда стрелок в каждый момент времени имеет альтернативу:

вести или не вести огонь. Сакагучи [112] исследовал обобщения второй

8

задачи на случай указанной альтернативы, а Накаи [104] - без указанной альтернативы. Бастон и Восток [74] предложили обобщение игры Айзекса, когда в точке х = 0 располагается барьер, а не бункер, т.е. эта точка не является точкой, которую в целях безопасности хотела бы достичь мишень, а является точкой, через которую мишень не может перейти на отрицательную полуось. В параграфах 1 и 2 данной работы решены обобщения задачи, сформулированной Айзексом, на случай игры на плоскости и произвольного бункера и на случай, когда вероятность поражения мишени зависит от расстояния между местоположением мишени и точкой, в которую попадает выстрел.

Томас и Нисгав [125] сформулировали задачу моделирования патрулирования пролива с целью предотвращения провоза контрабанды в виде антагонистической игры следующим образом. Контрабандист, имеющий катер, должен в течении одной из к ночей совершить попытку провоза контрабанды через пролив. Таможня, имеющая в своем распоряжении т быстроходных катеров, осуществляет патрулирование пролива с целью предотвращения попыток провоза контрабанды. Вероятность захвата контрабандиста зависит от количества катеров, используемых для патрулирования в ночь осуществления попытки провоза контрабанды. Имеются ограничения на количество ночей, в течении которых могут использоваться те или иные катера. Томасу и Нис-гаву [125] удалось решить эту задачу в случае, когда в распоряжени таможни имеется только один катер. Бастон и Восток [77] предложили метод для решения двухкатерной проблемы. В параграфах 2 и 3 предложен подход, отличный от рассмотренного Бастоном и Востоком [77], предоставляющий возможность решить также трехкатерную проблему. Стоит отметить, что по своей структуре игра контрабандист -таможня близка к проблеме инспекции описанной Оуэном [36].

Гал [92] сформулировал в общем виде задачу защиты объекта от не-

9

законного проникновения к нему диверсанта в виде антагонистической игры следующим образом. Имеются два игрока: диверсант и охрана. Игра осуществляется в районе П, в котором имеется защищаемый объект, расположенный в точке А. Диверсант проникает в район О в неизвестный момент времени в известной точке О и, осуществляя простое движение, пытается достичь защищаемый объект. Охрана, не имея информации о текущем местоположении диверсанта, пытается построить систему охраны объекта таким образом, чтобы минимизировать вероятность успешного достижения диверсантом защищаемой зоны. Кроме того, Г ал [92] конкретизировал эту проблему в виде следующей дискретной игры. Игра протекает на целочисленном интервале О = [0,т + 1]. Защищаемая зона располагается в точке х = т + 1, а диверсант проникает в район П через точку х = 0 и, осуществляя простое движение, пытается достичь защищаемую зону. Охрана, осуществляя простое движение, пытается помещать диверсанту. В случае, если в некоторый момент времени местоположения диверсанта и охраны совпадают, вероятность обнаружения диверсанта считается равной 1 - А, где Л -вероятность необнаружения диверсанта. Целью диверсанта является максимизация вероятности достижения защищаемой зоны. Лалли [98] решил проблему, сформулированную Галом, в предположении, что в точке х = 0 находится безопасная зона для диверсанта (т.е. охрана не имеет права производить там поиск). Игра продолжается конечный интервал времени, и оба игрока осуществляют простое движение с единичной скоростью. Аугер [72] обобщил этот результат на случай игры на графе состоящим из п непересекающихся дуг, соединяющих вершины А и О, в которых находятся защищаемая и безопасная зоны соответственно. Кроме того, он предполагал, что диверсант осуществляет простое движение с единичной скоростью, и нет ограничения

на движение охраны (т.е. она может осуществить поиск в любой точ-

10

ке). Алперн [70] получил некоторые предельные результаты для игры Аугера для случая произвольного графа. В главе 1 даны обобщения результатов Аугера и Лаллея на случай произвольной скорости диверсанта и ограничения на число поисковых операций охраны. Кроме того, дан положительный ответ на вопрос, сформулированный Аугером [70], о существовании оптимальной смешанной стратегии охраны состоящей только из V) чистых стратегий, где ъо - общее число так называемых ждать-бежать стратегий диверсанта.

Айзеке [2] сформулировал антагонистическую игру поиска "принцесса и чудовище". Игрок 5 ("чудовище" или ищущий игрок), начиная из фиксированной известной обоим игрокам точки и осуществляя простое движение в районе поиска П с максимальной скоростью, равной единице, пытается обнаружить игрока Я ("принцессу" или прячущегося игрока). Игрок Я сам произвольно выбирает свое первоначальное местоположение в районе поиска О. Игроки не получают никакой информации о текущем местоположении противника. Под временем обнаружения понимается время сближения на расстояние г, где г - радиус обнаружения. Айзеке [2] показал, что для районов поиска с достаточно регулярной границей и неподвижным игроком Я, значение игры приблизительно равно шее(12)/(4г), где тев(П) - мера множества П. Алперн [68] и Зеликин [12] решили задачу »принцесса и чудовище» с шщвиж-ным игроком Я на окружности П в предположении, что оба игрока осуществляют простое движение с единичными скоростями в О, а их первоначальное местоположение выбирается независимо друг от друга в соответствии с равномерным распределением на П. Обнаружение игрока Я происходит в случае, если оба игрока окажутся в один и тот же момент времени в одной и той же точке. Алперн [68] и Зеликин [12] нашли оптимальные стратегии игроков и показали, что значение игры

равно 31-/4, где Ь - длина окружности П. Андерсон и Арамендиа [71]

И

на основе линейного программирования предложили алгоритм построения оптимальных стратегий игроков игры "принцесса и чудовище" на графе в предположении, что игра протекает в течении конечного интервала времени. Гал [91,92] решил задачу "принцесса и чудовище" с подвижным игроком Я на графе специального вида, состоящего из двух вершин, соединенных к непересекающимися дугами единичной длины в предположении, что игрок S не может ждать в вершинах и скорость игрока Я не больше скорости игрока S. Он показал, что значение игры равно 1 /к. Алперн и Асик [69] решили проблему Гала при к = 3 опустив предположение, что игрок S не может ждать в вершинах графа. Гал [91,92] также решил задачу "принцесса и чудовище" при поиске в прямоугольно подобных районах поиска О. Он построил стратегии игроков, позволяющие сделать вывод о том, что значение игры при малых радиусах обнаружения асимптотически эквивалентно mes(ß)/(2r). Лаллей и Робине [99] предложили стратегию игрока S, отличную от предложенной Галом [91,92], дающую ту же самую оценку для значения игры в выпуклом районе поиска в предположении, что игроку Я запрещено движение в малой окрестности границы района поиска. В главе 3 представлено обобщение метода, предложенного Галом, позволяющее получить асимптотику значения игры в случае, когда вектограмма скоростей игрока S отлична от круга.

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

М V »

компании типа книга - почтой намереваются издать свои ежегодные

каталоги. Проблема поиска оптимального момента выпуска каталога

12

является важным вопросом. Компания, которая первая выпустит свой каталог, получает возможность опередить конкурента. С другой стороны, компания, которая ждет дольше, может нажить капитал на недостатках каталога своего конкурента. С аналогичной ситуацией выбора сталкиваются, например, конкурирующие нефтедобывающие компании при принятии решения о продолжительности геологоразведочных работ и моментом времени подписания контракта на добычу нефти. Карлин [97] систематизировал методы предложенные для решения подобных задач, сформулированных в виде антагонистических игр. Сакагучи [113] сформулировал и решил задачу с выбором момента времени с фиксированным моментом окончания в виде неантагонистической игры. Те-раока [124] и Сакагучи [114] исследовали данную неантагонистическую игру в случае, когда момент окончания игры является случайным. Стоит отметить, что в работах [114,113, 124] оптимальные стратегии по Нэшу искались среди довольно ограниченного класса стратегий игроков. Во второй главе предложен оригинальный метод, позволяющий искать равновесия по Нэшу среди всех стратегий игроков. На основе этого нового метода исправлена ошибка, допущенная Тераока [124] при решении игры с выбором момента времени, когда момент окончания игры является случайным с непрерывной функцией распределения. Решена задача, сформулированная Сакагучи [114], об игре с выбором момента времени, когда момент окончания игры является случайным с дискретной функцией распределения. Также диссертантом исследована проблема, когда игрок получает информацию о действиях противника с некоторой вероятностью и решено обобщение задачи, предложенной Хамерсом [86], о дележе с дискаунтным фактором по времени.

Перейдем к краткому изложению содержания диссертации

Глава 1 посвящена исследованию математических игровых моделей

защиты объекта от проникновения к нему противника.

13

В параграфах 1-1.3 рассмотрена следующая антагонистическая игра. Имеются два игрока: охрана и диверсант. Игра протекает в дискретные моменты времени I = 0,1,____Диверсант может двигаться только

по точкам целочисленной решетки Z2 = {(¿,7) : г,з е 2} плоскости Оху. Если в некоторый момент времени диверсант находится в точке (*, У), то через единицу времени диверсант может перейти в одну из следующих точек: (г — 1,.?), (г + 1,.?), (г,3 — 1), (г,3 + 1) или остаться на месте в точке (г,3). Охрана имеет некоторое вооружение с к единицами боеприпасов и в каждый момент времени может производить не более одного выстрела по любой выбранной ей точке целочисленной решетки Ъ2. Пусть В С Я1, В Ф Ъ2 и В Ф 0. В множестве В расположен "бункер", достигнув которого диверсант становится недосягаемым для огня охраны. Если диверсант, находившийся в точке (1,3), через единицу времени перейдет в точку £(¿,7) (или останется на месте в точке (»,.?)), а охрана будет вести огонь по точке £(¿,.7) (или то вероятность

поражения диверсанта будем считать равной щ (или соответственно, где £ = 1,3,4,5. Здесь ае € (0,1),£ € [1,5];1(и) = (г - = = (* + 1,Л4(|,Л = (»,3 ~ = + 1). Охрана обладает полной информацией о местоположениии диверсанта с запаздыванием на единицу времени, т.е. охрана знает, где находился диверсант, но не знает, куда он пошел. Диверсант знает, сколько единиц боеприпасов осталось у охраны, но не знает, по каким позициям она ведет огонь. Выигрыш охраны равен единице (нулю), если диверсант поражен (не поражен) огнем охраны. Найдена рекуррентная формула для определения значения данной игры и найдены оптимальные поведенческие стратегии игроков. В параграфах 2-2.4 рассмотрена следующая антагонистическая игра на прямой. Имеются два игрока: охрана и диверсант. Диверсант может двигаться только по целым точкам 0,1,...

прямой со скоростью, не превосходящей единицу, т.е. если в некото-

14

рый момент времени диверсант находится в точке », то через единицу времени он может перейти в одну из следующих двух точек: г - 1 или % + 1, или остаться на месте в точке г. Охрана, первоначально вооруженная некоторым вооружением с к единицами "осколочных боеприпасов", в каждый момент времени I = 0,1,... может либо производить, либо не производить выстрел. "Осколочный боеприпас", попавший в точку », с вероятностью а\ поражает объект, находящийся в этой точке; с вероятностью «г поражает объект, находящийся в точке г — 1, либо г + 1; с вероятностью а3 поражает объект, находящийся в точке г — 2, либо г + 2; Естественно считать, что 0 < «3 < а2 < «ь В точке О расположен "бункер", достигнув которого диверсант становится недосягаемым для огня охраны. Охрана обладает полной информацией о местоположениии диверсанта с запаздыванием на единицу времени, т.е. охрана знает, где находился диверсант, но не знает, куда он пошел. Диверсант знает, сколько единиц боеприпасов осталось у охраны, но не знает, по каким позициям она ведет огонь. Выигрыш охраны равен единице (нулю), если диверсант поражен (не поражен) огнем охраны. Найдена рекуррентная формула для определения значения данной игры и найдены оптимальные поведенческие стратегии игроков. В параграфах 2.5-2.5.2 обсуждена первая проблема Айзекса для случая игры на отрезке, а в параграфах 2.6 -2.6.2 дано решение проблемы Ракла [110] поиска двумя отрезками одной точки. В параграфе 3 рассмотрена следующая антагонистическая игра. Имеются два игрока: таможня и контрабандист. Таможня в своем распоряжении имеет два катера, и она может использовать » - й катер для патрулирования в течении ночей. В случае, когда таможня патрулирует пролив г - м катером в ту же ночь, когда контрабандист пытается провезти контрабанду, вероятность его захвата равна р». В случае, если в эту ночь таможня

осуществляет патрулирование обоими катерами, вероятность захвата

15

контрабандиста равна р, где р > тах^х,^}« Выигрыш таможни в случае захвата контрабандиста равен 1 и —1 в противном случае. Найдено значение данной игры и определены оптимальные поведенческие стратегии игроков. В параграфах 4-4.1 исследован трехкатерный вариант этой задачи. В параграфах 5-5.3 рассмотрена следующая антагонистическая игра. Имеются два игрока: охрана и диверсант. Игра протекает на графе, состоящем из двух вершин О ж А соединенных п непересекающимися дугами. В вершине О располагается зона безопасности, где диверсант не достижим для поражения охраной. Защищаемый объект располагается в вершине А, куда диверсант намерен пробраться к моменту времени Г. Игра протекает в дискретные моменты времени/ = ОД,...,!1 на т равномерно расположенных отмеченных точках этого графа (на разных дугах может быть расположено разное количество отмеченных точек, т.к. дуги могут иметь разные длины). Не теряя общности, можно предположить, что расстояние между соседними отмеченными точками равно единице. В начальный момент времени t = 0 диверсант находится в зоне безопасности (вершине О) и его задачей является достижение защищаемой зоны (вершины А) не позднее момента времени £ = Т, осуществляя простое движение с единичной скоростью (т.е. в течении одной единицы времени он может перейти в одну из соседних точек вдоль дуг графа, либо остаться на месте). Охрана не имеет больше информации о диверсанте, в частности, она не знает его текущую позицию. Охрана с некоторым видом вооружения и к единицами боеприпасов располагается в течении игры в защищаемой зоне и в каждый момент времени может произвести по выстрелу по любой отмеченной точке. В случае попадания в ту же точку, где находится диверсант, вероятность его поражения равна 1 — Л (т.е. Л - вероятность промаха), а в противном случае 0. Игра оканчивается

в случае поражения диверсанта, либо достижения диверсантом защи-

16

щаемой зоны. В случае достижения диверсантом защищаемой зоны до его поражения выигрыш диверсанта равен 1, и в противном случае, он равен 0, т.е. целью диверсанта является максимизация успешного достижения защищаемого объекта. Найдено значение этой игры и оптимальные стратегии игроков. В параграфах 6-6.3 рассмотрена проблема из параграфа 5 в предположении, что диверсант может двигаться со скоростью не превосходящей щ где и > 1. Найдено значение этой игры и оптимальные стратегии игроков.

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

Параграфы 7-8.4.3 посвящены исследованию следующей двухперсон-ной игры с неопределенным моментом окончания, являющейся обобщением классической дуэли. Имеются два игрока: игрок 1 и игрок 2. Каждый из игроков имеет по ружью с одним патроном, который он может выстрелить в любой момент времени из интервала [0,1] по цели. Ружья предполагаются бесшумными, т.е. каждый из игроков не знает, поразил ли его противник мишень или промахнулся. Точность поражения г - ым игроком мишени характеризуется непрерывной строго возрастающей функцией А; : [0,1] [0,1], называемой функцией точности, так, что если игрок г производит свой выстрел в момент времени ж, то вероятность поражения мишени равна А,-(ж). Игрок, первый поразивший мишень, является победителем, и игра заканчивается. Кроме того, соревнование оканчивается в случайный момент времени Т из [0,1] с данной плотностью распределения Н(х). Каждый из игроков выбирает момент выстрела. В параграфах: 7-7.4 считается, что Я является непрерывной, а в параграфах 8-8.4.3 - что Я является дискретной. В обоих параграфах найдены равновесия по Нэшу у исследуемых игр. В параграфах 7.3, 7.4, 8.3-8.4.3 исследованы шумные и

бесшумно-шумные варианты исследуемых игр со случайным моментом

17

окончания. В параграфе 9 исследуется описанная в параграфе 7 игра с фиксированным моментом окончания в предположении, что игрок может с некоторой вероятностью получить информацию о моменте выстрела своего противника. Найдено равновесие по Нэшу у исследуемой игры. В параграфе 10 исследуется ситуация, когда два игрока делят нормализованный бесконечно делимый ресурс. В момент времени I = 0 игрок г, г = 1,2 имеет право получить а» -ю часть бесконечно делимого ресурса, где а = + «2 < 1. Игроки 1 и 2 должны выбрать моменты времени х и у из интервала [0, оо) соответственно для того, чтобы потребовать свою часть бесконечно делимого ресурса. Если х < у, то игрок 1 получает а^ -ю часть бесконечно делимого ресурса, а игрок 2 оставшуюся (1 — од)^ -ю часть бесконечно делимого ресурса, где б\ и ¿2 - дискаунтные факторы. Если ж > у, то игрок 2 получает ~ю часть бесконечно делимого ресурса, а игрок 1 оставшуюся (1 - агЖ ~ю часть бесконечно делимого ресурса. Если х = у, то каждый из игроков получает зарезервированную за ним часть бесконечно делимого ресурса плюс половину остатка, т.е. игроки 1 и 2 получают (а + а./2)8^ и (а2 + «/2)<5| части бесконечно делимого ресурса соответственно, где £ = 1 - Предполагается, что игрок г получает информацию о выборе игрока э с вероятностью Д-, где € [0,1]. Найдено равновесие по Нэшу и доказана его единственность.

Глава 3 посвящена исследованию математической модели поиска уклоняющегося объекта при полном отсутствии информации о текущем местоположении противника. В параграфах 11-11.2 исследована следующая игра, являющаяся модификацией игры "принцесса и чудовище". Имеются два игрока: Н и 5. Игра протекает в прямоугольном множестве П. Игрок 5 в начальный момент времени располагается в точке О Е О, известной обоим игрокам, и осуществляет движение с векто-

граммой скоростей Р в множестве П, где Р - ромбовидное множество,

18

показанное на рис. 11.1. Игрок Н осуществляет простое движение со скоростью w > 0 в множестве О. Каждый игрок в любой момент времени знает свое местоположение, но не знает местоположение противника. В момент времени, когда расстояние между игроками становится не больше г > 0, имеет место обнаружение игрока Н. Целью игрока Н является максимизация времени, необходимого игроку S для его обнаружения. Построены стратегии игроков, позволяющие определить асимптотику значения игры при малом радиусе обнаружения.

Основные результаты по теме диссертации опубликованы в работах [128-151]. Апробация результатов диссертации прошла на международном конгрессе по компьютерным системам и прикладной математике (Санкт-Петербург, 1993), на международной конференции по теории игр и экономике (Санкт-Петербург, 1996), на семинарах по теории игр Санкт-Петербургского государственного университета, Саутгемтонско-го университета, Лондонского университета и на семинаре кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета. Исследования, проводимые по теме диссертации, были награждены 12 месячной postdoctoral fellowship Лондонского королевского общества и поддержаны грантом N 93-1-51-27 Министерства Науки, Высшей Школы и Технического Образования Российской Федерации.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гарнаев, Андрей Юрьевич

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Обобщен метод, предложенный Лаллеем, что дало возможность диссертанту решить задачу, сформулированную Г алом о за.-щите объекта при отсутствии информации у игроков о текущем местоположении противника в случае, когда ищущий игрок имеет ограничение на число поисковых операций. Дан положительный ответ на вопрос Аугера о существовании оптимальной смешанной стратегии охраны, состоящей только из т чистых стратегий, где IV - общее число так называемых ждать-бежать стратегий диверсанта. Найдены оптимальные стратегии игроков и значение игры.

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

6. Развит подход, позволяющий распространить формализм Га

237

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

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

Список литературы диссертационного исследования доктор физико-математических наук Гарнаев, Андрей Юрьевич, 1997 год

ЛИТЕРАТУРА

1. Абчук В.А., Суздаль В.Г. Поиск объектов. М.: Советское радио, 1977, 334с.

2. Айзеке Р. Дифференциальные игры. М.: Мир, 1967, 480с.

3. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982, 368с.

4. Батухтин В.Г. Об одной игровой задаче наведения с неполной информацией. Прикладная математика и механика, 1980, т.44, вып.4, с.595-601.

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

6. Гермейер Ю.Б. Введение в теорию исследования операций операций. М.: Наука, 1981, 383с.

7. Гусятников П.Б. Об одной проблеме Z-yбегания. Прикладная математика и механика, 1976, т.40, вып.1, с.25-37.

8. Доманский В.К. О некоторых играх, связанных с последовательностью испытаний Вернули. Известия АН СССР, Техническая кибернетика, 1974, т.4, с.35-39.

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

10. Ермолов А.Н. Дифференциальные игры в смешанных стратегиях. Автоматика и телемеханика, 1988, N 6, с.40-51

11. Ермолов А.Н., Кряковский B.C., Маслов Е.Б. Об одной дифференциальной игре в смешанных стратегиях. Автоматика и телемеханика, 1986, N 10, с.32-45.

12. Зеликин М.И. Об одной дифференциальной игре с неполной информацией. Доклады АН СССР, 1972, т.202, N 5, с.998-1000.

13. Зенкевич H.A. Одна оценка для простого поиска на плоскости. Вестник Ленингр. ун-та, серия мат., мех. и астрон., 1981, вып.4, с.112-

14. Зенкевич H.A. Теоретико-игровой поиск на плоскости в одном классе однопараметрических семейств траекторий. В кн.: Динамические управляемые системы. Якутск, Изд-во Якутского гос. ун-та, 1983, с.57-61.

15. Зенкевич Н.А.,Петросян Л.А. Динамические модели поиска в условия конфликта. В кн.: Вопросы механики и прцессов управления. Управление динамическими системами. Вып.7, JL: Изд-во Ленингр. ун-та, 1984, с.97-108.

16. Киселев В.Н., Малафеев O.A. Игровые задачи динамического поиска. В кн.: Теория игр и ее приложения. Кемерово: Изд-во Кемеровского гос. ун-та, 1989, с.108-119.

17. Кра.совский H.H. Об управлении при неполной информации. Прикладная математика и механика, 1976, т.40, вып.2, с.197-206.

18. Красовский H.H. Дифференциальные игры. Апроксимационные и формальные модели. Математический сборник, 1978, т.107, N 4, с.541-571.

19. Красовский H.H., Осипов Ю.С. К теории дифференциальных игр с неполной информацией. Доклады АН СССР, 1974, т.215, N 4, с.780-781.

20. Красовский H.H., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974, 455с.

21. Красовский H.H. Управление динамической системой: задача о минимуме гарантированного результата. М.: Наука, 1985, 518с.

22. Кренкин A.A., Субботин А.И. Игровая задача преследования в условиях неполной информации о преследуемой системе. В кн.: Дифференциальные системы управления. Свердловск, УНЦ АН СССР, 1979, с.21-33.

23. Кряжимский A.B. Альтернатива в линейной игре сближения -

240

уклонения с неполной информацией. Доклады АН СССР, 1976, т.230, N 4, с.773-776.

24. Кряжимский А.В. К теории позиционных дифференциальных игр сближения-уклонения. Доклады АН СССР, 1978, т.239, N 4, с.779-782.

25. Куржанский А.В. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977, 302с.

26. Куржанский А.Б. Об информационных множествах управляемой системы. Доклады АН СССР, 1978, т.240, N 1, с.14-17.

27. Луценко М.М. Об одном подходе к решению игр на единичном квадрате с функцией выигрыша к(х - у). I. Optimization, 1990, vol.21, pp.71-86.

28. Луценко М.М. Об одном подходе к решению игр на единичном квадрате с функцией выигрыша к(х - у). II. Optimization, 1990, vol.21, рр.453-467.

29. Мазалов В.В. Игровые моменты остановки. Новосибирск: Наука, 1987, 188с.

30. Малафеев О.А., Петросян Л.А. Дифференциальные игры поиска. Сведение к динамическим играм с полной информацией. Вестник Ленингр. ун-та, серия мат., мех. и астрон., 1983, вып.2, с.26-30.

31. Меликян А.А., Черноусько Ф.А. Некоторые минимаксные задачи управления с неполной информацией. Прикладная математика и механика, 1971, т.35, вып.6,

32. Мищенко Е.Ф. Задачи преследования и убегания от встречи в теории дифференциальных игр. Известия АН СССР, техническая кибернетика, 1971, т.5, с.3-9.

33. Никольский М.С. Об одной задаче преследования с неполной информацией. Изв. АН СССР, Тех. кибернетика, 1971, N 5, с.10-13.

34. Овсянников Д.А. Математические методы управления пучками.

Л.: Изд-во Ленингр. ун-та, 1980, 228с.

241

35. Осипов Ю.С. Позиционное управление в параболических системах. Прикладная математика и механика, 1977, т. 41, вып. 2,

36. Оуэн Г., Теория игр. М.: Мир, 1971, 230с.

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

38. Петров H.H. Задачи преследования на одномерном остове куба. Дифференциальные уравнения, 1987, т.23, N 5, с.908-911.

39. Петров H.H., Петров Н.Никандр. О дифференциальной игре "казаки-разбойники". Дифференциальные уравнения, 1983, т.19, N 8, с.1366-1374.

40. ПетросянЛ.А. Дифференциальные игры преследования. Л.: Изд-во Ленинг. ун-та, 1977, 244с.

41. Петросян Л.А. Дифференциальные игры с неполной информацией. Доклады АН СССР, 1970, т.195, N 3, с.558-561.

42. Петросян Л.А. Игры преследования с задержкой информации у игрока Р. Известия АН Арм.ССР, 1973, т.8, N 2, с.93-101.

43. Петросян Л.А. Одновременная игра поиска и случайное распределение точек на плоскости. Вестник Ленингр. ун-та, Серия мат., мех. и астрон., 1985, вып.1,

44. ПетросянЛ.А. Матричные игры поиска. В кн.: Динамика систем и управление, Саранск: Изд-во Мордовского гос. ун-та, 1986, с.37-43.

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

46. Петросян Л.А., Зенкевич H.A. Оптимальный поиск в условиях конфликта. Л.: Изд-во Ленингр. ун-та, 1987, 57с.

47. Петросян Л.А., Скитович В.В. Поиск неподвижного объекта на сфере. Вестник Ленингр. ун-та, серия мат., мех. и астрон., 1986, вып.1, с.54-58.

48. Петросян Л.А., Томский Г.В. Дифференциальные игры с непол-

242

ной информацией, Иркутск: Изд-во Иркутского ун-та, 1984, 187с.

49. Понтрягин Л.С. Линейные дифференциальные игрыД. Доклады АН СССР, 1967, т.174, N 6, с. 1278-1281.

50. Понтрягин Л.С. Линейные дифференциальные игры,П. Доклады АН СССР, 1967, т.175, N 4, с. 764-767.

51. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1976, 392с.

52. Пшеничный Б.Н. О линейных дифференциальных играх. Кибернетика, 1968, т.1, с.47-53.

53. Пшеничный Б.Н., Чикрий A.A., Редковский H.H. Дискретная задача поиска. Киев, 1984, 30с. /препринт АН УССР, Ин-т кибернетики/

54. Сатимов Н.Ю. Об одном способе уклонения от встречи в дифференциальной игре. Математический сборник, 1976, т.99, N 3, с.380-393.

55. Скитович В.В., Чистяков C.B. Игровые задачи сближения и поиска. М.: Изд-во МАИ, 1985, 47с.

56. Слобожанин Н.М. Об одной гипотизе Л.А.Петросяна. Вестник Ленингр. ун-та, Серия мат., мех. и астрон., 1981, вып.З,

57. Слобожанин Н.М., Петросян Л.А. Функциональные уравнения для дифференциальных игр с неполной информацией. В кн.: Вопросы механики и процессов управления. Вып.4. Методы математического анализа управляемых процессов. Л.: Изд-во Ленингр. ун-та, 1980, с.183-197.

58. Субботина H.H., Субботин А.И. Игровые задачи при неполной информации. Известия АН СССР, Техническая кибернетика, 1977, N 5, с. 14-23.

59. Суздаль В.Г. Теория игр для флота. М., Наука, 1976, 336с. 60. Хеллман О., Введение в теорию оптимального поиска. М., Наука, 1985, 246с.

61. Ченцов А.Г. Оптимизация в условиях нечетких ограничений. Свердловск, 1986, 54с./препринт, УНЦ АН СССР, Ин-т математики и механики/.

62. Черноусько Ф.Л. Управляемый поиск подвижного объекта. Прикладная математика и механика, 1980, т.44, вып.1, с.3-12.

63. Черноусько Ф.Л., Меликян А.А. Игровые задачи управления и поиска. М., Наука, 1978, 265с.

64. Чикрий А.А. Дифференциальные игры с несколькими преследователями. Труды Центра Банаха. Математическая теория оптимального управления, Варшава, 1985, с.81-107.

65. Чикрий А.А., Грицевский А.Э. Непрерывная задача поиска с дискретным распределением состояния. Доклады АН УССР, сер.А, 1985, N 9, с.70-73.

66. Чикрий А.А., Клименко Е.Ф. Об одной задаче поиска. В кн.: Методы решения экстремальных задач, Киев, йн-т кибернетики АН УССР, 1981, с.34-39.

67. Чикрий А.А., Чикрий Г.Ц. Об информированности в дискретных игровых задачах. Кибернетика, 1979, N 5, с.46-51.

68. Alpern S. The search game with mobile hider on the circle. In.: Differential games and control theory, Dekker, New York, p.181-200.

69. Alpern S., Asic M. Ambush strategies in search games on graphs. SIAM J. Control and Optimization, 1986, Vol. 24, N 1, p. 66-75.

70. Alpern S. Infiltration games on arbitrary graphs. Journal of Mathematical Analisys and Applications, 1992, Vol.163, p.286-288.

71. Anderson E.J., Aramendia M.A. The search game on a network with immobile hider. Networks, 1990, Vol.20, p.817-844.

72. Auger J.M. An infiltration game on k arcs. Naval Research Logistics, 1991, Vol.38, p.511-529.

73. Basar Т., Olsder G.J. Dynamic noncooperative game theory, N.Y.,

244

Academic Press, 1982, 416p.

74. Baston V.J., Bostock F.A. An evasion game with barriers. SI AM Journal of Control and Optimization, 1988, Vol.26, p.1099-1105.

75. Baston V.J., Bostock F.A. Deception games. International Journal of Game Theory, 1988, Vol.17, p.129-134.

76. Baston V.J., Bostock F.A. A simple cover-up game. American Mathematical Monthly, 1990, Vol.28, p.671-677.

77. Baston V.J., Bostock F.A. A generalized inspection game. Naval Research Logistics, 1991, Vol.38, p.171-182.

78. Beck A. On the lineax search problem. Israel J.Math. 1964, Vol.2, p.221-228.

79. Beck A. More on the linear search problem. Israel J.Math. 1965, Vol.3, p.61-70.

80. Brams S.J., Kilgour D.M., Davis M.D. Unraveling in games of sharing and exchange. In.: Fronties of game theory, MIT Press, Cambrige, 1993, pl94-212.

81. Brown S.S. Optimal search for a moving target in discrete time and space. Operations Research, 1980, Vol.28, p. 1275-1289.

82. Croucher J.S. Application of the fundamental theorem of game to an example concerning antiballistic missle defence. Naval Research Logistics Quart., 1975, Vol.22, 197-203.

83. Danskin J.M. A helicopter versus submarine search game. Operations Research, 1986, Vol.16, p.509-517.

84. Dobbie J.M. A two cell modell of search for a moving target. Operations Research, 1974, Vol.22, p.79-92.

85. Fitzgerald C.H. The princess and monster differential game. SIAM J. Contol and Optimization, 1979, Vol.17, p.700-712.

86. Hamers H. A silent duel over a cake. ZOR-Methods and Models of

Operational Research, 1993, Vol.37, p.l 19-127.

245

87. Hendrics K., Weiss A., Wilson C. The war of attrition in continuous time with complete information].. International Economic Review, 1988, Vol.29, p.663-680. SIAM J. Control and Optimization, 1977, Vol. 15, p.841-856.

88. Gal S. A general search problem. Israel J. Mathematics, 1972, Vol.12, p.32-45.

89. Gal S. Minimax solutions for linear search problems. SIAM J. Appl.Math., 1974, Vol.27, p.17-30.

90. Gal S. A stochastic search game. SIAM J.Applied Mathematics, 1978, Vol.34, p.205-210.

91. Gal S. Search games with mobile and immobile hider. SIAM J. Control and Optimization, 1979, Vol.17, p.99-122.

92. Gal S. Search games. N.Y. Pergamon Perss, 1980, 298p.

93. Gal S.,Chazan D. On the optimality of the exponential functions for some minimax problems. SIAM J.Appl.Math., 1976, Vol.30, p.324-348.

94. Gal S. Continuous search games. In.: Search theory: some recent developments. New York, Marcel Dekker, 1989, p.33-53.

95. Isaacs R. The problem or arming and evasion. Naval Research logistics Quart., 1956, Vol.2, p.47-67.

96. Isaacs R. Some fundamentals of differential games. In.: Topics in differential games, North-Holland Publishing Company, Amsterdam, 1973, p.25-31.

97. Karlin S. Mathematical methods and theory in game, programming and economics, vol.11, Pergamon Press, London, 1959, 432p.

98. Lalley S.P. A one-dimensional infiltration game. Naval Research Logistics, 1988, Vol.35, p.441-446.

99. Lalley S.P., Robbins H. Stochastic search in a convex region. Probability Theoty and Related Fields, 1988, Vol.77, p.99-116.

100. Lee K.T. A firing game with a time lag. Journal of Optimization

246

Theory and Applications, 1983, Vol.41, p.548-547.

101. Lee K.T. An evasion with a destination. Journal of Optimization Theory and Applications, 1985, Vol.46, p.359-372.

102. KoopmanB.O. The theory of search. Part II,III. Operation Researchs, 1956, Vol.4, p.503-531.

103. Koopman B.O. Search and screening. N.Y. Pergamon Press, 1980,

104. Nakai T. A sequential evasion-search games with a goal. J. Operations Research of Japan, 1986, Vol.29, p.113-122.

105. Pursiheino U. On the optimal search for a target whose motion is conditionally deterministic with stochastic initial conditions on location and parameters. SIAM J.Appl.Math., Vol.32, 1977, p.105-114.

106. Reijnierse J.H., Potters J.M. Search games with immobile hider. International Journal of Game Theory, 1993, Vo.21, p.385-396.

107. Roberts D.,Gittins J. The search for an intellegent evader: strategies for searcher and evader in the two regions problem. Naval Research Logistics quart., 1978, Vol.25, p.95-106.

108. Ruckle W.H. On the constractability of solution a pair of two person search games. International Journal of Game Theory, 1980, Vol.8, p.235-240.

109. Ruckle W.H. Ambushing random walks II, Operations Research, 1981, Vol.29, p.108-120.

110. Ruckle W.H. Geometric games and their applications. Pitman Advansed Publishing Program, Boston, 1983, 187p.

111. Sakaguchi M, Sakai S. Partial information in a simplified two-person poker. Mathematica Japonica, 1981, Vol.26, p.695-705.

112. Sakaguchi M. An evasion game with a bunker. Mathematica Japonica, 1986, Vol.31, p.449-461.

113. Sakaguchi M. Marksmanship contests: non-zero-sum game of timing.

Mathematica Japonica, 1978, Vol.22, p. 585^5%.

247

114. Sakaguchi M. Some simple models of duels with random termination time. Mathematica Japonica, 1987, Vol.32, p.833-848.

115. Sakaguchi M. The value of sample information in la relance poker. Mathematica Japonica, 1988, Vol.33, p.777-800.

116. Sakaguchi M. Effect of correlation in a simple deception game. Mathematica Japonica, 1990, Vol.35, p.527-536.

117. Sakaguchi M. On two and three person exchange game. Mathematica Japonica, 1993, Vol.38, p.791-801.

118. Sarctsalo L. On the optimal search for a target whose motion is a Marcov process. J.Appl.Prob., 1973, Vol.10, p.847-856.

119. Spencer J. A deception game. American Mathematical Monthly, 1973, Vol.80, p.416-417.

120. Stone L.D. Theory of optimal search. N.Y., Academic Press, 1975, 240p.

121. Stone L.D. Search for targets with generalized conditionally deterministic motion. SIAM J.Appl.Math., 1977, Vol.33, p.456-468.

122. Subelman E.J. A hide-search game. J. Appl. Prob., 1981, Vol.18, p.628-640.

123. Sweat C.W. A single-shot noisy duel with detection uncertainty. Operations Research, 1971, Vol.19, p.170-181.

124. Teraoka Y. A two person game of timing with random termination, Journal Optimization Theory and Applications, 1983, Vol.40, p.379-396.

125. Thomas M.U.,Nisgav Y. An infiltration game with time dependent payoff. Naval Research Logistics, 1976, Vol.23, 297-303.

126. Washburn A. Search evasion game in a fixed region. Operations Research, 1980, Vol.28, p.1290-1298.

127. Worsham R.H. A discrete game with a mobile hider. In.: Differential games and control theory, N.Y.,1974, p.201-230.

128. Гарнаев А.Ю. Одна задача поиска подвижного объекта. В

248

кн.: Математические методы оптимизации и управления в сложных системах. Калинин: Изд-во Калининского гос. ун-та, 1986, с.88-96.

129. Гарнаев А.Ю. Задача поиска движущегося объекта. В кн.: Динамические системы и управление. Саранск: Изд-во Мордовского гос. ун-та, 1986, с.46-57.

130. Гарнаев А.Ю. Об одной задаче поиска на плоскости. В кн.: Многошаговые, иерархические, дифференциальные и кооперативные игры. Калинин: Изд-во Калининского ун-та, 1986, с.56-64.

131. Гарнаев А.Ю. Решение задачи поиска в области. Вестник ЛГУ, сер.1, 1987,вып.2, с.8-14.

132. Гарнаев А.Ю., Гарнаева Г.Ю. Об одной дискретной игре с неполной информацией. В кн.: Математическое и программное обеспечение задач конфликтного управления. Тез. докл. семинара ВЦ АН Арм.ССР, Ереван, 1987, с.27-30.

133. Гарнаев А.Ю. Одна дискретная игра на плоскости с запаздыванием информации. В кн.: Теоретико-игровые методы в разработке информационно-распознающей системы. Владивосток, ДО АН СССР, 1989, с.24-31.

134. Гарнаев А.Ю. Об одной теоретико-игровой задаче поиска в прямоугольнике. В кн.: Теория игр и ее приложения, Кемерово: Изд-во Кемеровского гос. ун-та, 1989, с.97-108.

135. Гарнаев А.Ю., Седых Л.Г. Об одной дискретной игре на плоскости с запаздыванием информации. В кн.: Кибернетика и вычислительная техника. Киев: Наукова думка, 1989, вып.83, с.44-49.

136. Гарнаев А.Ю., Седых Л.Г. Одна игра поиска типа "ищущий-шиущий". Автоматика, 1990, N 3, с.72-74.

137. Гарнаев А.Ю. Одна дискретная игра на плоскости с запаздыванием информации, Автоматика и телемеханика, 1989, N 12 с.27-36.

138. Гарнаев А.Ю. Одна дискретная игра на прямой с запаздывани-

249

ем информации, Автоматика и телемеханика, 1990, N 12, с.51-59.

139. Петросян JI.A., Гарнаев А.Ю. Игры поиска, Я.: Изд-во Санкт-Петербургского университета, 1992, 216с.

140. Garnaev A.Y. A search game in a rectangle. Journal of Optimization Theory and Applications, 1991, vol.69, p.531-542.

141. Garnaev A.Y. A remark on the princess and monster search game. International Journal of Game Theory, 1992, vol.20, p.269-276.

142. Garnaev A.Y. On simple mix game. International Journal of Game Theory, 1992, vol.21, p.234-247.

143. Garnaev A.Y. A remark on a helicopter-submarine game. Naval Research Logistics, 1993, vol.40, p.745-753.

144. Garnaev A.Y. On a mix game, Int. Year-B. Game Theory Appl., 1993, vol.1, p.25-33.

145. Garnaev A.Y. A remark on a customs and smuggler game. Naval Research Logistics, 1994, vol.41, p.287-293.

146. Garnaev A.Y. The value of sample information in a cover-up game, Mathematica Japonica, 1995, vol.41, p.253-259.

147. Baston V.J., Garnaev A.Y. A Teraoka-type two-person nonzero-sum silent duel. Journal of Optimization Theory and Applications, 1995, vol.87, p.539-551.

148. Garnaev A.Y. On a Sakaguchi's problem in non-zero-sum games of timing. Mathematica Japonica, 1996, vol.44, p.291-301.

149. Baston V.J., Garnaev A.Y. A fast infiltration game on n arcs. Naval Research Logistics, 1996, vol.43, p.481-489.

150. Garnaev A.Y., Garnaeva G.Y. An infiltration game on a circumference. Game Theory and Applications, 1996, vol. 2, p.11-16.

151. Garnaev A.Y. On a problem in timing games. In: Proceeding of

the 7th Int. Symposium on Dynamic Games and Applications. Eds. J.A.

Filar, V. Gaitsgory and F. Imado. Birkhauser Publisher, 1996, p.271-282.

250