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

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

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

Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин Xi, Х2,., Xjv и последовательностью функций выигрыша Уо, yi{x), 2/2(^1? Х2), Vn (x, Х2-, определенной на реализации этой случайной последовательности. Различные постановки задачи наилучшего выбора возникают путем изменения способов задания данных последовательностей. Рассматриваются модели с полной информацией, в которых предполагается, что наблюдатель знает закон распределения поступающих случайных величинмодели без информации, когда решение о моменте остановки принимается на основе знания лишь относительного ранга текущего наблюдения среди всех ранее просмотренныхмодели с частичной информацией, в которых известна лишь часть информации о характере распределения случайных величин. При рассмотрении последних моделей приходится применять адаптивные алгоритмы для оценки неизвестных параметров. Исследуются модели, допускающие возвращение к просмотренным ранее наблюдениям, допускающие возможность сделать выбор несколько раз и т. д. Кроме того, спектр рассматриваемых постановок расширяется за счет задания функций выигрыша. В классической задаче о секретаре необходимо максимизировать вероятность нахождения самого лучшего претендентав задаче с полной информацией требуется максимизировать ожидаемый выигрыш.

Следует отметить, что результаты, полученные при решении задачи наилучшего выбора, привели к созданию теории оптимальной остановки в области управляемых случайных процессов, которая, в свою очередь, нашла широкое приложение, в том числе, в задаче различения статистических гипотез (Вальд [6]), в задаче быстрейшего обнаружения изменения свойств случайных процессов (так называемая «задача о разладке» (Ширяев [30])), в задачах о продаже недвижимости (Олбрайт [32], Дерман, Либерман, Росс [43], Мазалов, Саарио, Сакагучи [66,77,78]), в задачах стохастической финанасовой математики (Ширяев [31]).

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

Цель работы заключается в следующем:

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

2. Построение адаптивных алгоритмов нахождения оптимальной стратегии.

3. Решение многошаговой задачи наилучшего выбора.

4. Исследование игровых задач наилучшего выбора.

Исторически задача оптимальной остановки была предложена Кейли в 1875 году [39]. Задача состояла в следующем. Существует набор из т объектов с известными значениями х, ¦¦¦, хтИз этого набора разрешается последовательно просмотреть п объектов (п ^ т). После просмотра очередного объекта необходимо либо принять его, получив выигрыш в размере его значения, либо отвергнуть и перейти к просмотру следующего объекта. Отвергнутый объект удаляется из набора. Если не выбран ни один из просмотренных ранее объектов, принимается последний просматриваемый объект. Кейли нашел решение этой задачи для набора из 4 объектов со значениями 1,2,3,4. (формулировку можно найти в [11]).

Мозер [67] в 1956 году сформулировал задачу Кейли для набора из т объектов, значения которых -^m — независимые равномерно распределенные на [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, Х2,., Хдг, с известным законом распределения, за просмотр каждого наблюдения берется плата с\ затем ему необходимо определить момент остановки при просмотре последовательности случайных величин У[, ., У/v, с платой С2 за просмотр, вид закона распределения случайных величин Y, У2, •••, Улг5 известен, а его параметры зависят от результатов выбора на первом этапе. Во втором параграфе рассмотрена игра двух лиц с выбором из двух наблюдений. Игрок I может наблюдать предложения Х, Х2, игрок II -2/1,2/2- Каждый игрок просматривает первое наблюдение и может принять его или отвергнуть и получить второе наблюдение. После этого игроки сравнивают полученные наблюдения и побеждает игрок, имеющий большее значение. В третьем параграфе рассмотрена симметричный вариант предыдущей игровой задачи, в котором предлагаемые наблюдения зависимы. В четвертом параграфе исследована игра с обманом с платой за наблюдения. Дана бесконечная последовательность независимых случайных величин. Играют два игрока: Игрок I первым просматривает значение случайного наблюдения и решает, предложить его Игроку II в открытом виде или в закрытом. Игрок II решает, принять предложенное наблюдение или отвергнуть его и перейти на следующий шаг. В начале игры Игрок / имеет т возможностей для закрытия. Рассматривается игра с нулевой суммой, в которой игроки имеют противоположные интересы.

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

ЗАКЛЮЧЕНИЕ

.

В работе получены следующие результаты.

1. Получены точные выражения для асимптотических оценок математического ожидания и дисперсии оптимального момента остановки в различных моделях задачи наилучшего выбора.

В теореме 1.1.2 доказано, что в модели без информации (задача о секретаре) оптимальный момент остановки обладает следующими асимптотическими свойствами:

При Nь оо,.

EtN 2 DTN 2 5 ~ ё' ~W е~.

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

При N оо,.

Etn 1 DtN J ~N~ ~* 3' ~W 18'.

Доказана лемма 1.2.1 о том, что имеет место следующая оценка для порогов Vj, определяющих оптимальную стратегию в модели с полной информацией: где.

Wi ^ Vi < Wi + Qfi, оц = (N — i = N — 1,., 1.

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

При N оо,.

ETN.

J2c.

Dtn.

1 — у/2с.

2с.

Доказана лемма 1.3.1 о том, что для порога v^, в модели с платой за наблюденя можно использовать в качестве нижней и верхней оценки выражения Wi и 1 — у/2с соответственно, где w г) = Wi=(-y/2c).

2 у/2с.

1 + - (1 — у/Тс), i = N — 1,., 1.

В теореме 2.1.2 доказано, что в модели с полной информацией, допускающей возвращение к просмотренным ранее наблюдениям, имеют место следующие асимптотические оценки:

При N -> оо,.

Etn у/Тс.

Вт N.

1 — у/Тс 2с '.

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

3. Решена многошаговая задача наилучшего выбора, когда на первом этапе случайные величины Х^ ., Xjy равномерно распределены на.

0,1], с платой с за просмотра на втором этапе случайные величины Ух, У2, Yn равномерно распределены на [0,b (t)], где t — результат выбора на первом этапе, плата за просмотр с2. Рассмотрен случай с бесконечным числом наблюдений.

Оптимальная стратеги на втором этапе имеет пороговый вид и определяется порогом V2 = b (t) — y/2b (t)c2.

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

В случае, когда Ь^)имеет вид: b (t) = (t + I)2, наблюдателю необходимо получить на первом этапе как можно большую величину, тогда это позволит ожидать и больший выигрыш на втором этапе.

Оптимальное значение порога v, используемого для принятие решения об остановке на первом этапе, находится из уравнения:

В случае b (t) = (1 — i)2, возникают две возможности. При выполнении условия сх ^ С2, существует единственный порог v = 1 — у/2сх, и на первом этапе оптимально принимать наблюдение, имеющее значение большее, чем v.

При выполнение условия с > с2, возникает ситуация с двумя порогами г>х, V2, и необходимо принимать наблюдение на первом этапе, если его значение меньше v или превосходит v2.

Значения порогов v и v2 находятся из уравнений (2у/2с2 — l) v + (2с2 — V2ii) — с2 + сх = О, V2 = 1 — V — у/2С2.

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

В игре двух лиц с двумя независимыми наблюдениями, Игроки I и II получают случайные наблюдения распределенные по законам F (x) и F2(x) соответственно. На первом шаге игроки используют пороговые стратегии zi и z2. Ситуация равновесия определяется уравнениями оо.

Fi{Z2) = F^Zi).

J Fy (t)dF2(t) + F2(Zl) + J F^dF^t),.

Z 1.

2(22) J Fl (t)dF2(t) + J Fl{t)dF2(t) + F2(z1)F2(z2)-l = 0. 0 22 Значения порогов z и z2 находятся из уравнений.

F2(Z2)F2{ZI) = F2(Z2).

00 00.

J F2{t)dFx{t) — I + Fx (z2)^ + J F^dF^t),.

Z2.

OO.

OO.

1 + F^Zi) Fi (z2) = Fi (zi) IJ Fi (t)dF2(t) + F2(Zl) + J F^dF^t).

0 Z.

В случае равномерного распределения ситуация равновесия определяется системой уравнений.

2 bzl (a + z) = a (b2z + az + ab2) b2z2 — bz + 2aziz2 — 2ab2 + 63.

В случае экспоненциального распределения ситуация равновесия задается системой оо f (1 — e~Al')A2e-Xltdt + 1 — e" AlZl + о.

1 e-A^)(l — e~Al22) = (1 — e~XlZl] 00 /(1 — e~Xlt)dt.

Zi.

1 е~х***)(1—) + 1 — е-Азг2—^е-(Л1+л3)г2 +.

Ai + Ai + Л2 (1 — e~x^)(l — e²*2) -1 = 0.

В симметричной игре двух лиц с двумя зависимыми наблюдениями, в которой плотность систем случайных величин имеет вид /i (rci, х2) = h-tic1 — 2ari)(l — 2я?2), и /2(2/1, уг) = 1 + 72(1−2j/i)(1−22/2) для Игрока i и II соответственно, порог используемый для принятия решения на первом шаге, находится из уравнения.

67Z4 — 127г3 + (3 + 77) г2 + (3 — i) z — 3 = 0.

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

В игре с обманом с платой за наблюдения Игроку II, при принятии решения об остановке, в случае когда он получает наблюдение в открытом виде, необходимо использовать пороговую стратегию h = 1 — у/Тс, и следует вступать в игру только при выполнении условия Значение игры вычислятся по формуле.

Vm = 1 + тс — у/2(га+ 1) с.