Содержание к диссертации
Введение
ГЛАВА I. Асимптотические свойства оптимального момента остановки в задаче наилучшего выбора 10
1. Задача о секретаре 10
2. Задача наилучшего выбора с полной информацией 16
3. Задача наилучшего выбора с полной информацией и платой за наблюдения 29
ГЛАВА II. Оптимальный момент остановки в задаче наилучшего выбора с возвращением и в адаптивных моделях 41
1. Задача наилучшего выбора с возвращением в условиях полной информации 41
2. Задача наилучшего выбора с возвращением в условиях отсутствия информации 47
3. Адаптивная модель задачи наилучшего выбора с частичной информацией 58
ГЛАВА III. Свойства оптимального момента остановки в многошаговых и игровых задачах наилучшего выбора 62
1. Многошаговая задача наилучшего выбора 62
2. Игра двух лиц с выбором из двух наблюдений 73
3 Симметричная игра двух лиц с выбором из двух зависимых наблюдений 81
4 Игра с обманом с платой за наблюдения 84
Заключение 89
Литература 94
- Задача наилучшего выбора с полной информацией
- Задача наилучшего выбора с возвращением в условиях отсутствия информации
- Игра двух лиц с выбором из двух наблюдений
- Игра с обманом с платой за наблюдения
Введение к работе
Работа посвящена исследованию структуры оптимальных правил остановки в различных моделях задачи выбора наилучшего объекта.
Задача наилучшего выбора занимает центральное место в классе задач оптимальной остановки. При решении задачи наилучшего выбора необходимо определить оптимальную стратегию поведения, т.е. оптимальный момент остановки и получаемый при использовании этой стратегии ожидаемый выигрыш.
Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин Xi,X2,...,Xn и последовательностью функций выигры-ша Уо, Уі{хі)і У2{хі,Х2), ,yN(xi,X2,..., #лг), определенной на реализации этой случайной последовательности. Различные постановки задачи наилучшего выбора возникают путем изменения способов задания данных последовательностей. Рассматриваются модели с полной информацией, в которых предполагается, что наблюдатель знает закон распределения поступающих случайных величин; модели без информации, когда решение о моменте остановки принимается на основе знания лишь относительного ранга текущего наблюдения среди всех ранее просмотренных; модели с частичной информацией, в которых известна лишь часть информации о характере распределения случайных величин. При рассмотрении последних моделей приходится применять адаптивные алгоритмы для оценки неизвестных параметров. Исследуются модели, допускающие возвращение к просмотренным ранее наблюдениям, допускающие возможность сделать выбор несколько раз и т.д. Кроме того, спектр рассматриваемых постановок расширяется за счет задания функций выигрыша. В классической задаче о секретаре необходимо максимизировать вероятность нахождения самого лучшего претендента; в задаче с полной информацией требуется максимизировать ожидаемый выигрыш.
Следует отметить, что результаты, полученные при решении задачи наилучшего выбора, привели к созданию теории оптимальной остановки в области управляемых случайных процессов, которая, в свою очередь, нашла широкое приложение, в том числе, в задаче различения статистических гипотез (Вальд [6]), в задаче быстрейшего обнаружения изменения свойств случайных процессов (так называемая "задача о разладке" (Ширяев [30])), в задачах о продаже недвижимости (Олбрайт [32], Дерман, Либерман, Росс [43],Мазалов, Саарио, Сакагучи [66,77,78]), в задачах стохастической финанасовой математики (Ширяев [31]).
Очевидно, что сталкиваясь с практической задачей, наблюдатель часто имеет определенные ограничения, связанные с периодом времени, в течении которого необходимо сделать выбор, или с потерями, которые он несет, обычно, финансового характера. Поэтому очень важно получить оценку длительности самого процесса выбора. Большое влияние на характер поведения момента остановки оказывают параметры задачи наилучшего выбора: информированность выбирающего о характере распределения поступающих наблюдений, наличие платы за просмотр предлагаемых вариантов, возможность возвращаться к ранее просмотренным предложениям. В связи с этим, крайне актуальной является задача оценки свойств ожидаемого момента остановки для различных постановок задачи наилучшего выбора. При рассмотрении реальных условий выбора наилучшего из предложений следует учитывать степень информированности о качестве поступающих вариантов и использовать информацию в максимально полном объеме. Для этого необходимо оценивать поступающую информацию и прогнозировать ожидаемый результат, принимая во внимание уже просмотренные предложения. Поэтому очень важным представляется построение "адаптивных" алгоритмов для решения задач в условиях неполной информированности. Не менее существенным является тот факт, что многие практические задачи определения лучшего объекта очень час- то бывают многоэтапными, сделав выбор из одной последовательности предлагаемых вариантов, тут же необходимо решать другую задачу выбора, причем её условия могут во многом зависеть от того, какой результат был получен на первом этапе; при этом необходимо отметить, что эта зависимость может иметь различный характер. До сих пор, в основном, рассматривались лишь одноэтапные задачи наилучшего выбора. Таким образом, крайне важным представляется проведение исследований оптимальных правил остановки в многошаговых моделях задачи наилучшего выбора. Вместе с тем, отметим, что сталкиваясь на практике с проблемой поиска лучшего варианта, выбирающий часто оказывается в условиях, когда ему приходится конкурировать с другими лицами, решающими схожую задачу или даже имеющими прямо противоположные интересы. В связи с этим, очень важным, с практической точки зрения, является изучение игровых постановок задачи наилучшего выбора; моделирование и исследование оптимального поведения игроков в ситуациях, учитывающих конкуренцию и противоположные интересы участников выбора. Цель работы заключается в следующем:
1. Определение асимптотических свойств характеристик оптималь ного момента остановки в различных постановках задачи наилучшего выбора.
2. Построение адаптивных алгоритмов нахождения оптимальной стратегии.
Решение многошаговой задачи наилучшего выбора.
Исследование игровых задач наилучшего выбора. Исторически задача оптимальной остановки была предложена Кей- ли в 1875 году [39]. Задача состояла в следующем. Существует набор из т объектов с известными значениями xi,X2,-~,xm. Из этого набора разрешается последовательно просмотреть п объектов {п ^ т). После просмотра очередного объекта необходимо либо принять его, получив выигрыш в размере его значения, либо отвергнуть и перейти к просмотру следующего объекта. Отвергнутый объект удаляется из набора. Если не выбран ни один из просмотренных ранее объектов, принимается последний просматриваемый объект. Кейли нашел решение этой задачи для набора из 4 объектов со значениями 1,2,3,4. (формулировку можно найти в [11]).
Мозер [67] в 1956 году сформулировал задачу Кейли для набора из га объектов, значения которых #i,2, ,^т - независимые равномерно распределенные на [0,1] случайные величины.
Автор классической задачи о секретаре неизвестен. Мостеллер утверждает [54], что услышал о ней в 1955 году от Глисона, который, в свою очередь, слышал о ней от кого-то другого. Задача стала популярной в начале 60-х годов, она появлялась в различных журналах в разделах головоломок. Например, она приводится в книгах Мостеллера "Пятьдесят занимательных вероятностных задач с решениями" и Гарднера "Математические игры". Решение задачи приведено в работах Дынки-на и Юшкевича [11], Лин дли [63]. Можно привести обширный список работ, в которых задача рассматривалась: Де Гроот [9], Гильберт и Мостеллер [54], Ширяев [29], Робине, Сигмунд и Чао [27]. После этого появился ряд работ, рассматривающих различные постановки этой задачи. Задача со случайным числом наблюдений была впервые изучена в работе Пресмана и Сонина [28]. Более глубоко эта постановка рассматривалась затем в работах Расмуссена и Робинса [73], Тамаки [95], Ирле [61], Расмуссена [74], Петручелли [72], Олбрайта [31]. Ир-ле [61] предложил новый метод нахождения оптимальной стратегии, модифицирующий метод последовательных приближений Ховарда, хорошо известный в динамическом программировании и не требующий редукции к марковскому случаю. Задача с полной информацией была решена в работах Гильберта и Мостеллера [54], Самуэльса [85], Сака-гучи [80]. Решение задач наилучшего выбора с возможностью сделать нескольких попыток было получено в работах Гильберта и Мостеллера [54], Сакагучи [79], Тамаки [96], Николаева [22], Франка, Самуэльса [50],
Ано [33]. В работе Шайовского, Шушалко [94] решена задача выбора объекта, принадлежащего определенному классу качества. Байесовская постановка задачи с частичной информацией предложена в работе Стюарта [93]. В работе Хенке [58] приводятся реккурентные формулы для математических ожиданий и дисперсий оптимальных правил остановки. Задача наилучшего выбора, определенная на траекториях процессов голосования, результаты которой могут быть применены к анализу биржевых операций, рассмотрена в работах Чжена, Старра [40], Шеппа [88] и Тамаки [101]. Постановки, допускающие возвращение к просмотренным наблюдениям, изучались в работах Смита [89], Янга [102], Петручелли [71], Сакагучи [81], Хилла, Кеннеди [60], Роча [75]. Задачи с неполной информацией изучались у Петручелли [70], Энса [45], Кэмпбелла, Самуэльса [38]. Модели, предусматривающие плату за наблюдения или дисконтирование размера выигрыша, были рассмотрены у Сакагучи и Тамаки [83], Мазалова, Винниченко [16], Эннса, Ференштейна [47]. Игровые постановки задачи наилучшего выбора рассматривались в работах Гильберта и Мостеллера [54], Курано, Ясиды, Накагами [62], Аркина, Пресмана, Сонина [1,25,26,28], Сакагучи [82,84], Читашвили, Елбакидзе [41], Эннса, Ференштейна [46], Гарнаева [51,52,53], Мазалова [15,64,65]. Задачи наилучшего выбора с неполной информацией, требующие использования адаптивных алгоритмов, рассматривались в работах Тамаки [99], Мазалова, Домбровского, Перина [17,18]. Ранговые задачи наилучшего выбора рассматривались в работах Линдли[63], Муцци [69], Чао, Моригути, Роббинса, Самуэльса [42], Смита, Дили [90], Гусейн-Заде [56], Кэмпбелла, Самуэльса [38],Роуза [76], Фергюсона, Хардвига, Тамаки [49], Брюса, Фергюсона [36], Ассафа, Самуель-Кана [34]. Фундаментальный обзор полученных результатов в различных моделях задачи наилучшего выбора сделан в монографии Березовского, Гнедина [4] и в работе Фергюсона [48].
В первой главе диссертационнной работы исследованы асимптотические свойства математического ожидания и дисперсии оптимально- го момента остановки для различных постановок задачи наилучшего выбора. В первом параграфе рассмотрена классическая задача о секретаре (модель без информации), в которой наблюдатель принимает решение об остановке, основываясь исключительно на знании относительного ранга текущего кандидата среди всех ранее просмотренных; во втором параграфе рассмотрена модель с полной информацией, в которой полностью известен закон распределения поступающих наблюдений; в третьем параграфе исследована модель с полной информацией и платой за наблюдения: закон распределения известен и необходимо вносить фиксированную плату для просмотра очередного наблюдения.
Во второй главе исследуются свойства оптимального момента остановки в задачах наилучшего выбора с возможностью возвращения к посмотренным ранее наблюдениям и в адаптивных моделях. В первом параграфе рассмотрен случай с полной информацией, найдены оптимальная стратегия, ожидаемый выигрыш и определены асимптотические свойства момента остановки; во втором параграфе рассмотрен случай без информации, когда используются алгоритмы, применяемые при работе с порядковыми статистиками; проведены анализ и сравнение адаптивных алгоритмов, используемых при решении задач без информации; в третьем параграфе расмотрен случай с частичной информацией, когда известен вид закона распределения, но не известны его параметры и применяется адаптивный алгоритм для оценки этих параметров.
В третьей главе исследуются теоретико-игровые задачи наилучшего выбора. В первом параграфе рассмотрена многошаговая модель задачи. На первом этапе наблюдатель должен остановить последовательности случайных величин Xi,X2,..., Хдг, с известным законом распределения, за просмотр каждого наблюдения берется плата с\\ затем ему необходимо определить момент остановки при просмотре последовательности случайных величин Уі,}, ...,Yn, с платой сі за просмотр, вид закона распределения случайных величин Уі,І2, ...,УлГ) известен, а его параметры зависят от результатов выбора на первом этапе. Во втором параграфе рассмотрена игра двух лиц с выбором из двух наблюдений. Игрок I может наблюдать предложения х\,Х2, игрок II -2/1,2/2- Каждый игрок просматривает первое наблюдение и может принять его или отвергнуть и получить второе наблюдение. После этого игроки сравнивают полученные наблюдения и побеждает игрок, имеющий большее значение. В третьем параграфе рассмотрена симметричный вариант предыдущей игровой задачи, в котором предлагаемые наблюдения зависимы. В четвертом параграфе исследована игра с обманом с платой за наблюдения. Дана бесконечная последовательность независимых случайных величин. Играют два игрока: Игрок / первым просматривает значение случайного наблюдения и решает, предложить его Игроку II в открытом виде или в закрытом. Игрок II решает, принять предложенное наблюдение или отвергнуть его и перейти на следующий шаг. В начале игры Игрок / имеет т возможностей для закрытия. Рассматривается игра с нулевой суммой, в которой игроки имеют противоположные интересы.
В заключении сформулированы основные полученные результаты.
Задача наилучшего выбора с полной информацией
Задача наилучшего выбора с полной информацией возникает, когда необходимо определить момент оптимальной остановки последовательности случайных величин Х\,Х2, .., Gv, закон распределения которых известен. После получения на шаге j очередного наблюдения принимается решение: принять его, получив выигрыш Xj, или отвергнуть и перейти к следующем шагу. В задаче с полной информацией требуется выбрать момент остановки т, который, в отличие от классической задачи о секретаре, максимизирует не вероятность выбрать лучший объект, а математическое ожидание ЕХТ, т.е. ожидаемый выигрыш. Без ограничения общности можно предположить, что 1, 2,.., XN— независимые равномерно распределенные на [0,1] случайные величины. В об можно представить в виде: , ч , V{, ЄСЛИ 0 X Vi, в задачах оптимальной остановки и называется последовательностью Мозера [67]. # Непрерывным аналогом уравнения (1.7) является дифференциальное уравнение Покажем, что выражения w и ii7i+(iV—г)" являются соответственно верхней и нижней оценкам для порога і»,-, і = N — 1,..., 1. Лемма 1.2.1. Имеет место следующее неравенство: Доказательство проведем индукцией по г. Сначала докажем левую часть двойного неравенства. При і = N, VN = WN = 0. При г — N — 1, г л/_1 = ад-ь Пусть утверждение истинно для г + 1, тогда Теперь рассмотрим правую часть неравенства. При г = N - 1, VN-I = \ w/v-i + &N-I = і + 1 = . Используя (7.1), нетрудно непосредственно проверить, что неравенство выполняется для г = N — 1,..., TV — 25. где выражения в квадратных скобках в числителе (1.12) обозначим соответственно как f(t) и g(t). Так как выражение знаменателя всегда больше нуля, оценим f(t) — g(t). Определим верхнюю границу t для положительных корней уравнения f2(t)-g2(t) = 0. (1.13) А Очевидно, что t будет являться верхней границей и для корней урав нения f(t) — g(t) = 0. Представим выражение f2(t) — g2(t) в виде знакопеременной суммы: Qi(x) - Q2(x) + Q3(x) - Q4{x) + ... + Q2m-i(z) - Q2m(x) = где Q\ - сумма последовательных членов полинома с положительными коэффициентами, начиная со старшей степени, Q2 - сумма последовательных членов полинома с отрицательными коэффициентами, непосредственно примыкающих к членам первой суммы, и т.д. Тогда Согласно метода знакопеременных щем случае вместо последовательности Х\,Х2, ..,-Х"лг можно рассматривать последовательность случайных величин F(Xi), F(X2),.., F(Xjy), которые будут равномерно распределены на [0,1]. Для решения задачи воспользуемся методом динамического программирования [3]. На последнем шаге оптимальный выигрыш равен На шаге г, получив наблюдение Х{ = х, можно остановиться с выигрышем ж, либо продолжить наблюдения с ожидаемым выигрышем
Если на шаге г вычислено, согласно (1.5), значение Ц,(х), то оптимальная стратегия т определяется как момент первого попадания в множество Г = {(х,г) : Vi(x) = х}. Таким образом, это момент остановки вида: (1.5) не зависит от х, нетрудно о видеть, что УІ(Х), і = 1,..., N — 1, можно представить в виде: , ч , V{, ЄСЛИ 0 X Vi, в задачах оптимальной остановки и называется последовательностью Мозера [67]. # Непрерывным аналогом уравнения (1.7) является дифференциальное уравнение Покажем, что выражения w и ii7i+(iV—г)" являются соответственно верхней и нижней оценкам для порога і»,-, і = N — 1,..., 1. Лемма 1.2.1. Имеет место следующее неравенство: Доказательство проведем индукцией по г. Сначала докажем левую часть двойного неравенства. При і = N, VN = WN = 0. При г — N — 1, г л/_1 = ад-ь Пусть утверждение истинно для г + 1, тогда Теперь рассмотрим правую часть неравенства. При г = N - 1, VN-I = \ w/v-i + &N-I = і + 1 = . Используя (7.1), нетрудно непосредственно проверить, что неравенство выполняется для г = N — 1,..., TV — 25. где выражения в квадратных скобках в числителе (1.12) обозначим соответственно как f(t) и g(t). Так как выражение знаменателя всегда больше нуля, оценим f(t) — g(t). Определим верхнюю границу t для положительных корней уравнения f2(t)-g2(t) = 0. (1.13) А Очевидно, что t будет являться верхней границей и для корней урав нения f(t) — g(t) = 0. Представим выражение f2(t) — g2(t) в виде знакопеременной суммы: Qi(x) - Q2(x) + Q3(x) - Q4{x) + ... + Q2m-i(z) - Q2m(x) = где Q\ - сумма последовательных членов полинома с положительными коэффициентами, начиная со старшей степени, Q2 - сумма последовательных членов полинома с отрицательными коэффициентами, непосредственно примыкающих к членам первой суммы, и т.д. Тогда Согласно метода знакопеременных сумм [10], верхняя граница t уравнения (1.13) находится как тах(ск), где Q - положительные числа, такие, что и, с учетом замены, получаем, что правое неравенство истино и для i = N -26,..,1. Лемма доказана.
Задача наилучшего выбора с возвращением в условиях отсутствия информации
Работа посвящена исследованию структуры оптимальных правил остановки в различных моделях задачи выбора наилучшего объекта. Задача наилучшего выбора занимает центральное место в классе задач оптимальной остановки. При решении задачи наилучшего выбора необходимо определить оптимальную стратегию поведения, т.е. оптимальный момент остановки и получаемый при использовании этой стратегии ожидаемый выигрыш. Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин XI,X2,...,XN И последовательностью функций выигры-ша Уо, Уі{хі)і У2{хі,Х2), ,yN(xi,X2,..., #лг), определенной на реализации этой случайной последовательности. Различные постановки задачи наилучшего выбора возникают путем изменения способов задания данных последовательностей. Рассматриваются модели с полной информацией, в которых предполагается, что наблюдатель знает закон распределения поступающих случайных величин; модели без информации, когда решение о моменте остановки принимается на основе знания лишь относительного ранга текущего наблюдения среди всех ранее просмотренных; модели с частичной информацией, в которых известна лишь часть информации о характере распределения случайных величин. При рассмотрении последних моделей приходится применять адаптивные алгоритмы для оценки неизвестных параметров. Исследуются модели, допускающие возвращение к просмотренным ранее наблюдениям, допускающие возможность сделать выбор несколько раз и т.д. Кроме того, спектр рассматриваемых постановок расширяется за счет задания функций выигрыша. В классической задаче о секретаре необходимо максимизировать вероятность нахождения самого лучшего претендента; в задаче с полной информацией требуется максимизировать ожидаемый выигрыш.
Следует отметить, что результаты, полученные при решении задачи наилучшего выбора, привели к созданию теории оптимальной остановки в области управляемых случайных процессов, которая, в свою очередь, нашла широкое приложение, в том числе, в задаче различения статистических гипотез (Вальд [6]), в задаче быстрейшего обнаружения изменения свойств случайных процессов (так называемая "задача о разладке" (Ширяев [30])), в задачах о продаже недвижимости (Олбрайт [32], Дерман, Либерман, Росс [43],Мазалов, Саарио, Сакагучи [66,77,78]), в задачах стохастической финанасовой математики (Ширяев [31]). Очевидно, что сталкиваясь с практической задачей, наблюдатель часто имеет определенные ограничения, связанные с периодом времени, в течении которого необходимо сделать выбор, или с потерями, которые он несет, обычно, финансового характера. Поэтому очень важно получить оценку длительности самого процесса выбора. Большое влияние на характер поведения момента остановки оказывают параметры задачи наилучшего выбора: информированность выбирающего о характере распределения поступающих наблюдений, наличие платы за просмотр предлагаемых вариантов, возможность возвращаться к ранее просмотренным предложениям. В связи с этим, крайне актуальной является задача оценки свойств ожидаемого момента остановки для различных постановок задачи наилучшего выбора. При рассмотрении реальных условий выбора наилучшего из предложений следует учитывать степень информированности о качестве поступающих вариантов и использовать информацию в максимально полном объеме. Для этого необходимо оценивать поступающую информацию и прогнозировать ожидаемый результат, принимая во внимание уже просмотренные предложения. Поэтому очень важным представляется построение "адаптивных" алгоритмов для решения задач в условиях неполной информированности. Не менее существенным является тот факт, что многие практические задачи определения лучшего объекта очень час то бывают многоэтапными, сделав выбор из одной последовательности предлагаемых вариантов, тут же необходимо решать другую задачу выбора, причем её условия могут во многом зависеть от того, какой результат был получен на первом этапе; при этом необходимо отметить, что эта зависимость может иметь различный характер. До сих пор, в основном, рассматривались лишь одноэтапные задачи наилучшего выбора. Таким образом, крайне важным представляется проведение исследований оптимальных правил остановки в многошаговых моделях задачи наилучшего выбора. Вместе с тем, отметим, что сталкиваясь на практике с проблемой поиска лучшего варианта, выбирающий часто оказывается в условиях, когда ему приходится конкурировать с другими лицами, решающими схожую задачу или даже имеющими прямо противоположные интересы. В связи с этим, очень важным, с практической точки зрения, является изучение игровых постановок задачи наилучшего выбора; моделирование и исследование оптимального поведения игроков в ситуациях, учитывающих конкуренцию и противоположные интересы участников выбора. Цель работы заключается в следующем: 1. Определение асимптотических свойств характеристик оптималь ного момента остановки в различных постановках задачи наилучшего выбора. 2. Построение адаптивных алгоритмов нахождения оптимальной стратегии. 3. Решение многошаговой задачи наилучшего выбора. 4. Исследование игровых задач наилучшего выбора. Исторически задача оптимальной остановки была предложена Кей ли в 1875 году [39]. Задача состояла в следующем. Существует набор из т объектов с известными значениями xi,X2,- ,xm. Из этого набора разрешается последовательно просмотреть п объектов {п т). После просмотра очередного объекта необходимо либо принять его, получив выигрыш в размере его значения, либо отвергнуть и перейти к просмотру следующего объекта. Отвергнутый объект удаляется из набора. Если не выбран ни один из просмотренных ранее объектов, принимается последний просматриваемый объект. Кейли нашел решение этой задачи для набора из 4 объектов со значениями 1,2,3,4. (формулировку можно найти в [11]). Мозер [67] в 1956 году сформулировал задачу Кейли для набора из га объектов, значения которых #i,2, , т - независимые равномерно распределенные на [0,1] случайные величины.
Игра двух лиц с выбором из двух наблюдений
Автор классической задачи о секретаре неизвестен. Мостеллер утверждает [54], что услышал о ней в 1955 году от Глисона, который, в свою очередь, слышал о ней от кого-то другого. Задача стала популярной в начале 60-х годов, она появлялась в различных журналах в разделах головоломок. Например, она приводится в книгах Мостеллера "Пятьдесят занимательных вероятностных задач с решениями" и Гарднера "Математические игры". Решение задачи приведено в работах Дынки-на и Юшкевича [11], Лин дли [63]. Можно привести обширный список работ, в которых задача рассматривалась: Де Гроот [9], Гильберт и Мостеллер [54], Ширяев [29], Робине, Сигмунд и Чао [27]. После этого появился ряд работ, рассматривающих различные постановки этой задачи. Задача со случайным числом наблюдений была впервые изучена в работе Пресмана и Сонина [28]. Более глубоко эта постановка рассматривалась затем в работах Расмуссена и Робинса [73], Тамаки [95], Ирле [61], Расмуссена [74], Петручелли [72], Олбрайта [31]. Ир-ле [61] предложил новый метод нахождения оптимальной стратегии, модифицирующий метод последовательных приближений Ховарда, хорошо известный в динамическом программировании и не требующий редукции к марковскому случаю. Задача с полной информацией была решена в работах Гильберта и Мостеллера [54], Самуэльса [85], Сака-гучи [80]. Решение задач наилучшего выбора с возможностью сделать нескольких попыток было получено в работах Гильберта и Мостеллера [54], Сакагучи [79], Тамаки [96], Николаева [22], Франка, Самуэльса [50], Ано [33]. В работе Шайовского, Шушалко [94] решена задача выбора объекта, принадлежащего определенному классу качества. Байесовская постановка задачи с частичной информацией предложена в работе Стюарта [93]. В работе Хенке [58] приводятся реккурентные формулы для математических ожиданий и дисперсий оптимальных правил остановки. Задача наилучшего выбора, определенная на траекториях процессов голосования, результаты которой могут быть применены к анализу биржевых операций, рассмотрена в работах Чжена, Старра [40], Шеппа [88] и Тамаки [101]. Постановки, допускающие возвращение к просмотренным наблюдениям, изучались в работах Смита [89], Янга [102], Петручелли [71], Сакагучи [81], Хилла, Кеннеди [60], Роча [75]. Задачи с неполной информацией изучались у Петручелли [70], Энса [45], Кэмпбелла, Самуэльса [38]. Модели, предусматривающие плату за наблюдения или дисконтирование размера выигрыша, были рассмотрены у Сакагучи и Тамаки [83], Мазалова, Винниченко [16], Эннса, Ференштейна [47].
Игровые постановки задачи наилучшего выбора рассматривались в работах Гильберта и Мостеллера [54], Курано, Ясиды, Накагами [62], Аркина, Пресмана, Сонина [1,25,26,28], Сакагучи [82,84], Читашвили, Елбакидзе [41], Эннса, Ференштейна [46], Гарнаева [51,52,53], Мазалова [15,64,65]. Задачи наилучшего выбора с неполной информацией, требующие использования адаптивных алгоритмов, рассматривались в работах Тамаки [99], Мазалова, Домбровского, Перина [17,18]. Ранговые задачи наилучшего выбора рассматривались в работах Линдли[63], Муцци [69], Чао, Моригути, Роббинса, Самуэльса [42], Смита, Дили [90], Гусейн-Заде [56], Кэмпбелла, Самуэльса [38],Роуза [76], Фергюсона, Хардвига, Тамаки [49], Брюса, Фергюсона [36], Ассафа, Самуель-Кана [34]. Фундаментальный обзор полученных результатов в различных моделях задачи наилучшего выбора сделан в монографии Березовского, Гнедина [4] и в работе Фергюсона [48]. В первой главе диссертационнной работы исследованы асимптотические свойства математического ожидания и дисперсии оптимально го момента остановки для различных постановок задачи наилучшего выбора. В первом параграфе рассмотрена классическая задача о секретаре (модель без информации), в которой наблюдатель принимает решение об остановке, основываясь исключительно на знании относительного ранга текущего кандидата среди всех ранее просмотренных; во втором параграфе рассмотрена модель с полной информацией, в которой полностью известен закон распределения поступающих наблюдений; в третьем параграфе исследована модель с полной информацией и платой за наблюдения: закон распределения известен и необходимо вносить фиксированную плату для просмотра очередного наблюдения. Во второй главе исследуются свойства оптимального момента остановки в задачах наилучшего выбора с возможностью возвращения к посмотренным ранее наблюдениям и в адаптивных моделях. В первом параграфе рассмотрен случай с полной информацией, найдены оптимальная стратегия, ожидаемый выигрыш и определены асимптотические свойства момента остановки; во втором параграфе рассмотрен случай без информации, когда используются алгоритмы, применяемые при работе с порядковыми статистиками; проведены анализ и сравнение адаптивных алгоритмов, используемых при решении задач без информации; в третьем параграфе расмотрен случай с частичной информацией, когда известен вид закона распределения, но не известны его параметры и применяется адаптивный алгоритм для оценки этих параметров. В третьей главе исследуются теоретико-игровые задачи наилучшего выбора. В первом параграфе рассмотрена многошаговая модель задачи. На первом этапе наблюдатель должен остановить последовательности случайных величин Xi,X2,..., Хдг, с известным законом распределения, за просмотр каждого наблюдения берется плата с\\ затем ему необходимо определить момент остановки при просмотре последовательности случайных величин Уі,}, ...,YN, С платой сі за просмотр, вид закона распределения случайных величин Уі,І2, ...,УлГ) известен, а его параметры зависят от результатов выбора на первом этапе. Во втором параграфе рассмотрена игра двух лиц с выбором из двух наблюдений. Игрок I может наблюдать предложения х\,Х2, игрок II -2/1,2/2- Каждый игрок просматривает первое наблюдение и может принять его или отвергнуть и получить второе наблюдение. После этого игроки сравнивают полученные наблюдения и побеждает игрок, имеющий большее значение. В третьем параграфе рассмотрена симметричный вариант предыдущей игровой задачи, в котором предлагаемые наблюдения зависимы. В четвертом параграфе исследована игра с обманом с платой за наблюдения. Дана бесконечная последовательность независимых случайных величин. Играют два игрока: Игрок / первым просматривает значение случайного наблюдения и решает, предложить его Игроку II в открытом виде или в закрытом. Игрок II решает, принять предложенное наблюдение или отвергнуть его и перейти на следующий шаг. В начале игры Игрок / имеет т возможностей для закрытия. Рассматривается игра с нулевой суммой, в которой игроки имеют противоположные интересы. В заключении сформулированы основные полученные результаты.
Игра с обманом с платой за наблюдения
В работе [84] рассмотрена игра ГТО)П с обманом. Дана последовательность из п независимых случайных величин Х\,Х2,..., Хп с общей функцией распределения F(x). Играют двое: Игрок І в начале игры имеет га(га п) возможностей для закрытия; он первый просматривает значение очередной случайной величины и определяет, предложить ее Игроку II в открытом виде или в закрытом. Игрок II должен принять предложенное значение или отвергнуть его и тогда игра переходит на следующий шаг. Если в состоянии (т,п) Игрок I наблюдает случайную величину X = х, то стратегии у игроков следующие: %п{х) = Р{ Игрок I откроет случайную величину X = х, в состоянии (га,п)}, (3% = Р{ Игрок II примет случайную величину, если Игрок I предлагает ее в закрытом виде в состоянии (т,п)}. При этом оптимальное значение для данной игры определяется следующим образом: Оптимальные стратегии и значение игры для этой п—шаговой игры с га возможностями для закрытия определяет следующая теорема. Теорема 3.4.1. [Сакагучи М.,1992] Оптимальные стратегии игроков в состоянии (га,п): Игрок I, наблюдая случайную величину X — х, должен открывать ее, если а х V 1 и закрывать в противном случае. Игрок II должен использовать стратегию /3 , 1 — (3 , где (5 - вероятность принять случайную величину в закрытом состоянии. Значения а и (3 определяются из соотношений Рассмотрим модификацию данной игры Гт, с бесконечной последовательностью равномерно распределеных на [0,1] случайных величин Хі,..., Хдг,...; кроме того, Игрок II должен вносить фиксированную плату в размере с в тех случаях, когда случайные величины предъявляются ему в открытом виде и когда он принимает закрытую случайную величину. Аналогично (3.28) определим значение Vm игры Гт. Определим теперь при каком соотношении параметров га и с Игроку II не выгодно вообще вступать в игру. откуда Итак, т = 1 - величина порога, который определяет, стоит 2с ли Игроку II вступать в игру при данной фиксированной плате с за наблюдение. Например, при с = имеет смысл вступать в игру, если
Игрок I может закрыть наблюдение не более трех раз. Таким образом, имеет место следующая теорема Теорема 3.4.2. Оптимальная стратегия игрока II игре Гт: принимать случайную величину, предлагаемую в открытом виде, если ее значение больше h = 1 — л/2с, и отвергать в противном случае. Не вступать в игру вообще, если выполняется условие 1. Получены точные выражения для асимптотических оценок математического ожидания и дисперсии оптимального момента остановки в различных моделях задачи наилучшего выбора. В теореме 1.1.2 доказано, что в модели без информации (задача о секретаре) оптимальный момент остановки обладает следующими асимптотическими свойствами: В теореме 1.2.2 доказано, что в модели с полной информацией о характере распределения поступающих случайных величин имеют место следующие асимптотические оценки оптимального момента остановки: Доказана лемма 1.2.1 о том, что имеет место следующая оценка для порогов i j, определяющих оптимальную стратегию в модели с полной информацией: В теореме 1.3.2 доказано, что в модели с полной информацией, предусматривающей предварительную фиксированную плату с за просмотр каждого наблюдения, оптимальный момент остановки обладает следующими асимптотическими свойствами: Доказана лемма 1.3.1 о том, что для порога vi, в модели с платой за наблюденя можно использовать в качестве нижней и верхней оценки выражения u i и 1 — у/2с соответственно, где В теореме 2.1.2 доказано, что в модели с полной информацией, в случаях полной информации и без информации. Проведены анализ и сравнение адаптивных алгоритмов, используемых в условиях отсутствия информации или частичной информации. 3. Решена многошаговая задача наилучшего выбора, когда на первом этапе случайные величины XI,X2,...,XN равномерно распределены на [0,1], с платой с\ за просмотр; а на втором этапе случайные величины Уі,У2, -.., Улг равномерно распределены на [0, &()], где t - результат выбора на первом этапе, плата за просмотр с . Рассмотрен случай с бесконечным числом наблюдений. Оптимальная стратеги на втором этапе имеет пороговый вид и определяется ПОРОГОМ V2 = b(t) — y/2b(t)c2. Найдены оптимальные стратегии поведения на первом этапе, в случаях, когда существует прямая зависимость между результатом, по-лученым на первом этапе и ожидаемым выигрышем на втором, и обратная. В случае, когда Ь()имеет вид: b(t) = ( + I)2, наблюдателю необходимо получить на первом этапе как можно большую величину, тогда это позволит ожидать и больший выигрыш на втором этапе. Оптимальное значение порога t i, используемого для принятие решения об остановке на первом этапе, находится из уравнения: В случае b(t) = (1 — )2, возникают две возможности. При выполнении условия ci С2, существует единственный порог V = 1 — у/2с\, и на первом этапе оптимально принимать наблюдение, имеющее значение большее, чем V. При выполнение условия сі С2, возникает ситуация с двумя порогами г»і, г 2, и необходимо принимать наблюдение на первом этапе, если его значение меньше v\ или превосходит г 2 Значения порогов v\ и vi находятся из уравнений
