Свойства оптимального момента остановки в задаче наилучшего выбора
Диссертация
Автор: Пешков, Николай Валерьевич
Название: Свойства оптимального момента остановки в задаче наилучшего выбора
Справка: Пешков, Николай Валерьевич. Свойства оптимального момента остановки в задаче наилучшего выбора : диссертация кандидата физико-математических наук : 01.01.09 Петрозаводск, 2003 102 c. : 61 04-1/368
Объем: 102 стр.
Информация: Петрозаводск, 2003
Содержание:
ГЛАВА L Асимптотические свойства оптимального момента остановки в задаче наилучшего выбора
§1 Задача о секретаре
§2 Задача наилучшего выбора с полной информацией
§3 Задача наилучшего выбора с полной информацией и платой за наблюдения
ГЛАВА
II Оптимальный момент остановки в задаче наилучшего выбора с возвращением и в адаптивных моделях
§1 Задача наилучшего выбора с возвращением в условиях полной информации
§2 Задача наилучшего выбора с возвращением в условиях отсутствия информации
§3 Адаптивная модель задачи наилучшего выбора с частичной информацией
ГЛАВА
III Свойства оптимального момента остановки в многошаговых и игровых задачах наилучшего выбора
§1 Многошаговая задача наилучшего выбора
§2 Игра двух лиц с выбором из двух наблюдений
§Симметричная игра двух лиц с выбором из двух зависимых наблюдений
§Игра с обманом с платой за наблюдения
Введение:
Работа посвящена исследованию структуры оптимальных правил остановки в различных моделях задачи выбора наилучшего объекта.Задача наилучшего выбора занимает центральное место в классе задач оптимальной остановки. При решении задачи наилучшего выбора необходимо определить оптимальную стратегию поведения, т.е. оптимальный момент остановки и получаемый при использовании этой стратегии ожидаемый выигрыш. ^ Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин Xi,X2, ,Хдг и последовательностью функций выигрыша г/о, 7/i(rci), 2/2(3:1,3:2), ,ум{х1,Х2,, XN), определенной на реализации этой случайной последовательности. Различные постановки задачи наилучшего выбора возникают путем изменения способов задания данных последовательностей. Рассматриваются модели с полной информацией, в которых предполагается, что наблюдатель знает закон распределения поступаюп1ИХ случайных величин; модели без информа•^^ ции, когда решение о моменте остановки принимается на основе знаШГ ния лишь относительного ранга текущего наблюдения среди всех ранее просмотренных; модели с частичной информацией, в которых известна лишь часть информации о характере распределения случайных величин. При рассмотрении последних моделей приходится применять адаптивные алгоритмы для оценки неизвестных параметров. Исследуются модели, допускающие возвращение к просмотренным ранее наблюдениям, допускающие возможность сделать выбор несколько раз и т.д. Кроме того, спектр рассматриваемых постановок расширяется за ^ счет задания функций выигрыша. В классической задаче о секретаре необходимо максимизировать вероятность нахождения самого лучшего претендента; в задаче с полной информацией требуется максимизировать ожидаемый выигрыш. r^i Следует отметить, что результаты, полученные при решении задачи наилучшего выбора, привели к созданию теории оптимальной остановки в области управляемых случайных процессов, которая, в свою очередь, нашла широкое приложение, в том числе, в задаче различения статистических гипотез (Вальд [6]), в задаче быстрейшего обнаружения изменения свойств случайных процессов (так называемая "задача о разладке" (Ширяев [30])), в задачах о продаже недвижимости (Олбрайт [32], Дерман, Либерман, Росс [43],Мазалов, Саарио, Сакагучи [66,77,78]), в задачах стохастической финанасовой математики (ШиряИг< ев [31]).Очевидно, что сталкиваясь с практической задачей, наблюдатель часто имеет определенные ограничения, связанные с периодом времени, в течении которого необходимо сделать выбор, или с потерями, которые он несет, обычно, финансового характера. Поэтому очень важно получить оценку длительности самого процесса выбора. Большое влияние на характер поведения момента остановки оказывают параметры задачи наилучшего выбора: информированность выбирающего о характере распределения поступающих наблюдений, наличие платы за •Г^ просмотр предлагаемых вариантов, возможность возвращаться к ра^ нее просмотренным предложениям. В связи с этим, крайне актуальной является задача оценки свойств ожидаемого момента остановки для различных постановок задачи наилучшего выбора. При рассмотрении реальных условий выбора наилучшего из предложений следует учитывать степень информированности о качестве поступающих вариантов и использовать информацию в максимально полном объеме.Для этого необходимо оценивать поступающую информацию и прогно|А» зировать ожидаемый результат, принимая во внимание уже просмотренные предложения. Поэтому очень важным представляется построение "адаптивных" алгоритмов для решения задач в условиях неполной информированности. Не менее существенным является тот факт, что многие практические задачи определения лучшего объекта очень часг ^ г то бывают многоэтапными, сделав выбор из одной последовательности предлагаемых вариантов, тут же необходимо решать другую задачу выбора, причем её условия могут во многом зависеть от того, какой результат был получен на первом этапе; при этом необходимо отметить, что эта зависимость может иметь различный характер. До сих пор, в основном, рассматривались лишь одноэтапные задачи наилучшего выбора. Таким образом, крайне важным представляется проведение исследований оптимальных правил остановки в многошаговых моделях задачи наилучшего выбора. Вместе с тем, отметим, что сталкиваясь на практике с проблемой поиска лучшего варианта, выбирающий часто оказывается в условиях, когда ему приходится конкурировать с другими лицами, решающими схожую задачу или даже имеющими прямо противоположные интересы. В связи с этим, очень важным, с практической точки зрения, является изучение игровых постановок задачи наилучшего выбора; моделирование и исследование оптимального поведения игроков в ситуациях, учитывающих конкуренцию и противоположные интересы участников выбора.Цель работы заключается в следующем: 1. Определение асимптотических свойств характеристик оптимального момента остановки в различных постановках задачи наилучшего выбора.2. Построение адаптивных алгоритмов нахождения оптимальной стратегии.3. Решение многошаговой задачи наилучшего выбора.4. Исследование игровых задач наилучшего выбора.Исторически задача оптимальной остановки была предложена Кейли в 1875 году [39]. Задача состояла в следующем. Существует набор из т объектов с известными значениями xi,rc2, •••,а:т- Из этого набора разрешается последовательно просмотреть п объектов {п ^ т ) .После просмотра очередного объекта необходимо либо принять его, получив выигрыш в размере его значения, либо отвергнуть и перейти /-л« .-чр* к просмотру следующего объекта. Отвергнутый объект удаляется из набора. Если не выбран ни один из просмотренных ранее объектов, принимается последний просматриваемый объект. Кейли нашел решение этой задачи для набора из 4 объектов со значениями 1,2,3,4. (формулировку можно найти в [11]).Мозер [67] в 1956 году сформулировал задачу Кейли для набора из т объектов, значения которых а;1,Ж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], _^j Ано [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], Ассафа, gjl^ Самуель-Кана [34]. Фундаментальный обзор полученных результатов в различных моделях задачи наилучшего выбора сделан в монографии Березовского, Гнедина [4] и в работе Фергюсона [48].В первой главе диссертационнной работы исследованы асимптотические свойства математического ожидания и дисперсии оптимальнотш( го момента остановки для различных постановок задачи наилучшего выбора. В первом параграфе рассмотрена классическая задача о секретаре (модель без информации), в которой наблюдатель принимает решение об остановке, основываясь исключительно на знании относительного ранга текущего кандидата среди всех ранее просмотренных; во втором параграфе рассмотрена модель с полной информацией, в которой полностью известен закон распределения поступающих наблюдений; в третьем параграфе исследована модель с полной информацией и платой за наблюдения: закон распределения известен и необходимо вносить фиксированную плату для просмотра очередного наблюдения.Во второй главе исследуются свойства оптимального момента остановки в задачах наилучшего выбора с возможностью возвращения к посмотренным ранее наблюдениям и в адаптивных моделях. В первом параграфе рассмотрен случай с полной информацией, найдены оптимальная стратегия, ожидаемый выигрыш и определены асимптотические свойства момента остановки; во втором параграфе рассмотрен случай без информации, когда используются алгоритмы, применяемые при работе с порядковыми статистиками; проведены анализ и срав• ^ нение адаптивных алгоритмов, используемых при решении задач без информации; в третьем параграфе расмотрен случай с частичной информацией, когда известен вид закона распределения, но не известны его параметры и применяется адаптивный алгоритм для оценки этих параметров.В третьей главе исследуются теоретико-игровые задачи наилучшего выбора. В первом параграфе рассмотрена многошаговая модель задачи.В заключении сформулированы основные полученные результаты. т т
|
