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

Забайкальский государственный педагогический университет им. Н.Г.Чернышевского

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

Панова Светлана Викторовна

Динамические игры с оптимальной остановкой

Специальность 01.01.09 (математическая кибернетика)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

доктор физико-математических

наук, профессор Мазалов Владимир Викторович

Чита-98

' ¿Ж

,\У -1 »

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..........................3

ГЛАВА 1. Теоретико-игровая модель покера ........... 13

§1. Многошаговая модель покера.............13

§2. Решение задачи в случае Л* = 3............15

§3. Решение задачи для произвольного N.........20

§4. Асимптотический вариант ..............27

§5. Результаты моделирования..............36

ГЛАВА 2. Задачи выбора партнера и места питания.......40

§1. Задача наилучшего выбора со случайным числом наблюдений и неизвестным законом распределения наблюдений 40

§2. Игровая задача выбора с неизвестным законом распределения наблюдений ...................50

§3. Эволюционно-устойчивые стратегии в задаче миграции животных ........................59

ГЛАВА 3. Теоретико-игровая задача взаимного выбора.....65

§1. Игровой вариант задачи наилучшего выбора с дисконтированием ........................65

§2. Решение задачи наилучшего выбора в случае фиксированного числа шагов...................73

ЗАКЛЮЧЕНИЕ......................78

ЛИТЕРАТУРА ......................86

Приложение ........................94

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

Исторически первая задача оптимальной остановки была предложена А.Кэли более 100 лет назад, где была рассмотрена задача типа лотереи (формулировку этой задачи можно найти в [9]). Систематическое изучение задач оптимальной остановки началось значительно позднее и было связано с пионерскими работами А.Вальда по последовательному анализу и статистическим решающим функциям [5]. Общая постановка задачи оптимальной остановки случайных процессов с дискретным временем была сформулирована в работе Снелла [75]. Общая теория изложена в монографиях Роббинса, Сигмунда и Чао [21] и Де Гроота [8].

Приведем постановку задачи оптимальной остановки процессов с дискретным временем. Пусть (О, Т, Р) - некоторое вероятностное пространство, Т\ С Тч С ... неубыващая последовательность под-ст-алгебр Т и ... - последовательность случайных вели-

чин таких, что Хп измеримы относительно Тп,п = 1,2,.... Пара последовательностей {Х^Т-п}1^ называется стохастической последовательностью. Тп интерпретируется как совокупность событий, которые могут быть наблюдены к моменту п, а Хп - как выигрыш, который мы получаем при прекращении наблюдений в момент п. Правилом остановки называется случайная величина т со значен-

ниями 1,2, ...,оо такая, что т < ос с вероятности) 1 и {г — п} £ Тп для любого п = 1,2,.... Случайная величина

Г Л"„. если г = п, п = 1, 2,.... 1 0. если т = оо

а г=у: А'„/{г=„}

п= 1

представляет собой выигрыш, который мы получаем при прекращении наблюдений в случайный момент г, а математическое ожидание МХГ (если оно существует) трактуется как средний выигрыш, соответствующий правилу остановки т. Цена V стохастической последовательности {Хп^Тп}^ определяется как БирМХг, где супремум берется по множеству всех правил остановки, для которых это математическое ожидание существует. Задача оптимальной остановки состоит в нахождении оптимального правила остановки, для которого средний выигрыш равен г. В случае конечного числа наблюдений конструктивно находить оптимальное правило нередко помогает метод обратной индукции.

Изучение задачи остановки марковского случайного процесса было начато в работе Дынкина [10]. Результаты исследований в этом направлении подитожены в монографии Ширяева [23].

Одна из прикладных задач на правило остановки - задача выбора наилучшего объекта, она имеет много других названий, среди прочих такие, как задача о секретаре, задача о выборе жениха или невесты. Формулировка этой задачи следующая. Имеется п объектов, упорядоченных по качеству. Объекты поступают в моменты времени 1, 2, ...,п в случайном порядке, т.е. все п! перестановок равновероятны. После поступления очередного объекта можно сравнить уже поступившие объекты, но ничего не известно о том, каковы будут последующие. Необходимо выбрать лучший по качеству объект с максимальной вероятностью. Решение задачи известно, оптимальная стратегия носит пороговый характер и заключается в следующем: существует номер к* = к*, такой что первые к* — 1 объ-

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

»<*._! <^ + (2 + ^).

е ее

Вероятность выбора наилучшего объекта стремится к £ при п —> ос-.

Неизвестно, кто является автором классической задачи. Ф.Мос-теллер утверждает [36], что узнал о ней в 195-5 году от Э.Глисона. который, в свою очередь слышал о ней от кого-то другого. В начале 60-х годов задача быстро стала популярной и появилась под различными названиями в нескольких журналах в разделе головоломок. Вот неполный список статей и монографий, где эта задача содержится: Дынкин и Юшкевич [9], Де Гроот [8], Джилберт и Мостеллер [36], Линдли [41], Ширяев [23], Роббинс, Сигмунд и Чао [21].

Решение этой задачи приведено, в частности, в [9], где основным моментом является ее сведение к задаче об оптимальной остановке некоторой марковской цепи с ограниченным числом шагов и конечным числом состояний. Цепь образована моментами появления объектов, которые лучше всех предыдущих.

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

В статье Э.Л.Пресмана и И.М.Сонина [18] изучалась задача обнаружения наилучшего объекта в ситуации, когда число объектов заранее неизвестно, а является случайной величиной, распределение которой задано. Эта задача тоже сведена к задаче об оптимальной остановке марковской цепи, но уже с бесконечным числом состояний и неограниченным числом шагов. Результаты этой работы изложены в [1]. Впоследствии эта задача изучалась и другими авторами: Рассмуссен и Роббинс [53], Тамаки [80], Ирле [39]. Ир-ле [39], ссылаясь на неопубликованную работу Раше, использовал новый метод нахождения оптимальных правил в общей задаче оста-

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

Задача наилучшего выбора, связанная с пуассоновским процессом изучалась Кованом и Забжиком [29].

Решение задачи с полной информацией (где при ознакомлении с очередным объектом информация о нем не исчерпывается только его относительным рангом, а имеется числовая шкала, по которой можно оценить качество каждого объекта в момент его появления: оценки различных объектов являются независимыми случайными величинами, имеющими одну и ту функцию распределения; эта функция предполагаеся известной) с заданным общим числом объектов было получено в работах Джилберта и Мостеллера [-36], Сакагучи [63].

Задача с полной информацией и пуассоновскими моментами наблюдений изучалась Сакагучи [67].

Задача выбора наилучшего объекта с нескольких попыток была решена Джилбертом и Мостеллером [36], Сакагучи [64], Тамаки [81].

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

Байесовская постановка задачи с частичной информацией предложена в работе Стюарта [78]. Стюарт рассматривал семейство

равномерных распределений на отрезке с двумя неизвестными концами, давая им двустороннее распределение Парето. Доказательство минимаксности порогового правила из классической задачи в указанном классе распределений содержится в работах Самуэль-са [72], Березовского и Гнедина [-3]. Задача с частичной информацией содержится в работе Энс [31].

Упомянем некоторые другие постановки.

Задачи с вероятностными ограничениями на доступность пропущенных вариантов изучались Смитом [73], Петручелли [51], Сака-гучи [65], Тамаки [82].

Задачи со случайными моментами наблюдений (и неизвестным числом вариантов) изучались Сакагучи и Тамаки [68], Стюартом [77]

Плата за наблюдения или дисконтированный выигрыш вводится в работах Сакагучи и Тамаки [68], Сакагучи [67], Расмуссена и Плиски [52], Гранта [37].

Еще одна разновидность рассматриваемых задач - ранговые задачи наилучшего выбора. В задачах этого типа исходят из предположения о том, что потери, которые соответствуют выбору того или иного объекта, определяются абсолютным рангом выбранного объекта, причем потери тем больше, чем выше этот ранг. Впервые ранговая задача с неклассической функцией потерь рассматривалась в работе Линдли [41]. Результаты исследований в этом направлении подитожены в монографии Березовского и Гнедина [3].

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

Игровые задачи наилучшего выбора изучались в цикле работ

Аркина, Пресмана и Сонина [1. 20, 19, 22], основные результаты здесь связаны с доказательством оптимальности или асимптотической оптимальности некоторого набора пороговых правил остановки (в смысле равновесия по Нэшу). В работе Сакагучи [66] более подробно изучен частный случай с двумя игроками. Другие игровые постановки изучались Джилбертом и Мостеллером [36], Грантом [37], Курано, Иосида и Накагами [40], Энс и Ференштейн [30].

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

Карточная игра покер состоит в следующем. В колоде 52 карты, которые делятся на четыре равные группы по масти. Масти различаются по значению (13 значений: 2, 3,..., 10, валет, дама, король, туз). В игре покер каждому из игроков сдается пять карт. Каждый из наборов карт имеет определенное значение. Иерархия значений определяется следующим образом.

1) флеш-ройяль (10,валет,дама,король,туз одной масти), вероятность ее появления равна приближенно 1.5 • 10~б.

2) каре (четыре карты одного значения), вероятность 0.0002

3) фул (три карты одного значения и две карты другого значения), вероятность 0.0014

4) стрит (пять последовательных по значению карт любой масти), вероятность 0.0035

5) тройка (три карты одного значения и две разные карты), вероятность 0.0211

6) две двойки (две пары карт одного значения в каждой паре), вероятность 0.0475

7) одна двойка (только одна пара карт одного значения), вероятность 0.4225.

После выбора карт игроки начинают делать ставки. После этого

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

Различным математическим моделям покера посвящены многочисленные публикации. Анализ покера, как математической игры привлек внимание Билля в 1938 г.. и в результате своего исследования игр типа покера он дал первое доказательство теоремы о ми-нимаксе для игр с непрерывной функцией выигрыша.

Модель упрощенного покера, решенная Беллманом и Блекуэл-лом в статье за 1949 г., состоит в следующем. В игре принимают участие 2 игрока, каждый получает карту достоинством х, у соответственно, где х,у - равномерно распределены на [0,1]. Перед на-

«_» о 1 1 Г и

чалом игры каждый игрок делает взнос, равный 1. Первый игрок имеет выбор: спасовать - и в этом случае он проигрывает взнос, или сделать ставку 21 или ^2,-2 > ¿1- Второй игрок имеет выбор: пасовать или поддержать ставку первого игрока. В случае паса первый игрок выигрывает взнос, иначе - выигрывает игрок с большей картой и получает выигрыш, равный сумме взноса и ставки.

В модели покера с повышением, предложенной Куном в 1950 г. имеется 3 возможные карты: 1.2.3. Каждый из двух игроков получает одну из этих трех карт, и ставит в банк сумму, равную а, повышение состоит в прибавлении дополнительной суммы Ь.

I II I

^пас | пас второй

<

повышение----I раскрытие

пас второй раскрытие

Если как первый, так и второй игроки пасуют, то розданные карты сравниваются и обладатель старшей карты выигрывает. Если игрок объявляет пас второй (пасует после повышения), то другой игрок выигрывает банк. Если игрок раскрывает (принимает повы-

шение), то карты сравниваются и старшая карта выигрывает.

Беллман в 19-52 г. рассмотрел модель покера с фиксированным размером ставки и одним кругом ставок. Беллман и Рестрепо в 1957 г. решили модели:

- покер с повышением, где у второго игрока имеется 3 возможности: спасовать, поддержать ставку противника (затем карты сравниваются), или повысить ставку (в этом случае первый игрок либо поддерживает повышение, либо пасует);

- покер с несколькими размерами ставок;

- покер с к кругами ставок.

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

Сакагучи [55] рассмотрена модель Hi-Lo покера. Отличительная особенность этой модели - если Игрок I пасует, то у Игрока II все же имеется возможность выбора: пасовать или нет. В случае, если оба игрока говорят пас, выигрывает игрок с меньшей картой. Эти правила, в частности, характерны для популярной игры преферанс.

Дальнейшие расширения игр этой модели покера были сделаны в работе Мазалова [42], где была рассмотрена модель преферанса с возможностью выбора дополнительной карты из прикупа, и в продолжающих эту идею совместной работе Сакагучи и Мазалова [69].

По структуре похожи с покером игры с обменом (exchange games). Постановка задач этого типа предложена Брамсом, Килгором и Де-висом [26], затем игры с обменом исследовались Гарнаевым [33, 34] и Сакагучи [61].

В представленной работе исследуется модель Hi-Lo покера с по-вышеним ставки с двумя игроками. §2 - число шагов равно 3, §3 - общий случай (шагов iV), §4 - N —» оо. В каждом случае если игрок решает продолжать игру (не пасовать), то он повышает став-

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

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

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

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

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

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