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

Пешков, Николай Валерьевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Петрозаводск МЕСТО ЗАЩИТЫ
2003 ГОД ЗАЩИТЫ
   
01.01.09 КОД ВАК РФ
Диссертация по математике на тему «Свойства оптимального момента остановки в задаче наилучшего выбора»
 
 
Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Пешков, Николай Валерьевич

ВВЕДЕНИЕ.

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

§ 1. Задача о секретаре.

§ 2. Задача наилучшего выбора с полной информацией.

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

ГЛАВА II. Оптимальный момент остановки в задаче наилучшего выбора с возвращением и в адаптивных моделях.

§ 1. Задача наилучшего выбора с возвращением в условиях полной информации.

§ 2. Задача наилучшего выбора с возвращением в условиях отсутствия информации.

§ 3. Адаптивная модель задачи наилучшего выбора с частичной информацией.

ГЛАВА III. Свойства оптимального момента остановки в многошаговых и игровых задачах наилучшего выбора.

§ 1. Многошаговая задача наилучшего выбора.

§ 2. Игра двух лиц с выбором из двух наблюдений.

§ 3 Симметричная игра двух лиц с выбором из двух зависимых наблюдений.

§ 4 Игра с обманом с платой за наблюдения.

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

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

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

Задача наилучшего выбора, в которой необходимо определить оптимальный момент остановки, задается последовательностью случайных величин 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с

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

1

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. Ситуация равновесия определяется уравнениями оо

00

Fi{Z2) = F^Zi)

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

Z 1

00

00

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*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 )с.

 
Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Пешков, Николай Валерьевич, Петрозаводск

1. Аркин В.И., Пресман Э.Л., Сонин И.М. Оптимальный выбор в условиях неполной информации//Экономика и математические методы, 1975. - Т.11, N3.

2. Беллман Р., Гликсберг И., Гросс О. Некоторые вопросы математической теории процессов управления. М.: ИЛ, 1962.

3. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. - 400 с.

4. Березовский Б.А., Гнедин А.В. Задача наилучшего выбора. М.: Наука, 1984. - 196 с.

5. Боярский А.Я. Введение в теорию порядковых статистик. М.: Статистика, 1970.- 415 с.

6. Брейман Л. Задачи о правилах остановки//Прикладная комбинаторная математика. М.: Мир, 1968. - С. 159-203.

7. Вальд А. Последовательный анализ. М.: Физматгиз, 1960. - 328 с.

8. Гаек Я., Шидак 3. Теория ранговых критериев. М.-Наука,1971.-375 с.

9. Де Гроот М. Оптимальные статистические решения. М.: Мир, 1974.-496 с.

10. Демидович Б.П., Марон И.А. Основы вычислительной математики.-М.: Физ.-мат.лит.,1960, 660с.

11. Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. М.: Наука, 1967. - 232 с.

12. Дынкин Е.Б. Оптимальный выбор момента остановки марковского процесса.- ДАН СССР, 1963. Т. 150, N2.

13. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

14. Кифер Ю.И. Игры с оптимальной остановкой//Теория вероятностей и ее применения. 1969. - T.13,Nl.-c. 183-188.

15. Мазалов В.В. Игровые моменты остановки. Новосибирск: Наука. Сиб. отд-ние, 1987. - 189с.

16. Мазалов В.В., Винниченко С.В. Моменты остановки и управляемые случайные блуждания.-Новосибирск: Наука.Сиб.отд-ние, 1992. -104 с.

17. Мазалов В.В., Домбровский Ю.А., Перрин Н. Теория оптимальной остановки: Приложения к экологии поведения//0бозрение прикладной и промышленной математики, сер. матем. методы экологии, 1994, Т.1,-в.6,-с.893-900.

18. Мазалов В.В., Кочетов Э.А., Перрин Н., Панова С.В. Экологические задачи выбора с неполной информацией//Обозрение прикладной и промышленной математики, сер. матем. методы экологии, 1996.-Т.З, в.3,-с.191-194.

19. Мазалов В.В., Пешков Н.В. Об асимптотических свойствах оптимального момента остановки.// Теория вероятностей и ее применение., 2003.-t.48. вып.3,с.583-589.

20. Мазалов В.В., Пешков Н.В. Игра с обманом с платой за наблюдения// Математический анализ и его приложения. Сборник тру-дов.ЧГПИ, 1994.в.1.-е.39-43.

21. Николаев M.JI. Об одном обобщени задачи наилучшего выбора// Теория вероятностей и ее применения, 1978,-Т.22,N 1.

22. Пешков Н.В. Свойства оптимального момента остановки в задачах наилучшего выбора с возвращением//Методы математического моделирования и информационные технологии. Труды ИПМИ КарНЦ РАН, 2003.-в.4.-с.92-97.

23. Пешков Н.В. Асимптотические свойства оптимального момента остановки в задачах с полной информацией с платой за наблюдения //Обозрение прикладной и промышленной математики. Тез.докл.IV Всеросс.симп.,2003.-т.10.-вып.2.-с.507

24. Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов//Теория вероятностей и ее применения. 1972. - Т.20, Вып.4 - с.785 -796.

25. Пресман Э.Л., Сонин И.М. Игровые задачи оптимальной остановки. Существование и единственность точек равновесия//Вероятностные проблемы управления в экономике. М.: Наука, 1977.- с.115-144.

26. Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.:Наука, 1977. - 168 с.

27. Сонин И.М. Игровые задачи, связанные с наилучшим выбором// Кибернетика, 1976, N 3.

28. Феллер В. Введение в теорию вероятностей и ее приложения.-М.:Мир, 1964, Т.1, 1967, Т.2.

29. Ширяев А.Н. Статистический последовательный анализ. М.:Наука, 1976, 272 с.

30. Ширяев А.Н. Основы стохастической финансовой математики. -М.:Фазис, 1998, 1017 с.

31. Albright S.C. A Bayesian approach to a generalised house-selling problem //Man.Sci.,1977.-V.24.-P.432-440.

32. Ano К. On a partial information miltiple selection promlem.//Game Theory and Appl.,1998.-V.4.-P.l-10.

33. Assaf D., Samuel-Calm E. The secretary problem: minimizing the expected rank with i.i.d. random variables//Adv.Appl.Probab.,1996.-V.28. -P.828-852.

34. Bruss F.T. A unified approach to a class of best choice problems with an unknown number of options.//Ann.Probab.,1984.-V.12.-P.882-889.

35. Bruss F.T., Fergusson T.S. Minimizing the expected rank with full information//J.Appl.Probab.,1993.-V.30.-P.616-624.

36. Bruss F.T., Fergusson T.S. Multiple buying or selling with vector offers//J.Appl.Probab.,1997.-V.34. -P.959=973.

37. Campbell G., Samuels S.M. Choosing the best of the current crop// Adv.Appl. Probab.,1981.-V.13.-P.510-532.

38. Cayley A. Mathematical question with their solution// The Collected mathematical papers of Arthur Cayley. Vol X (1896) Cambridge Univ. Press., 1875.-P.587-588.

39. ChenW.-C., Starr N. Optimal stopping in an urn//Ann.Probab.,1980.-V.8. -P.451-464.

40. Chitashvilli R. Ya., Elbakidze N.V. Optimal stopping by two players// Statistic and control of stochastic processes. Transl. Ser. Math. Engrg. New York: Optimization Software, Inc. Publications Division, 1985. - P. 10-53.

41. Chow Y.S., Moriguti S.,Robbins H., and Samuels S.M. Optimal selection based on relative rank(the "secretary problem")//Israel J.Math.,1964.-V.2. -P.81-90.

42. Derman C.,Liberman G.J., Ross S.M. A sequential stochastic assignment problem //Man.Sci., 1972.-V. 18.-P. 349-355.

43. Engen S., Seim E. Uniformly best invariant stopping rules// J.Appl. Probab. , 1987.-V.24.-P.77-87.

44. Enns E.G. Selecting the maximum of a sequence with imperfect information //J.Amer. Statist.Ass.,1975. V.70,N 351.-P.640-643.

45. Enns E.G., Ferenstein E.Z. The horse game//J.Oper.Soc.Japan,1985.-V.28. -P.51-62.

46. Enns E.G., Ferenstein E.Z. Optimal sequentual selection from a known distribution with holding costs//J.Amer.Statist.Ass., 1988.-V.83,N 402. -P.382-386.

47. Ferguson T.S. Who solved the secretary problem?//Statistical Science, 1989.- V.4.-P.282-296.

48. Ferguson T.,S., Hardwick J.P., Tamaki M. Maximizing the duration of owning a relatively best object//Contemporary Mathematics, 1992.-V.125. -P.37-57.

49. Frank A.Q., Samuels S.M. On a optimal stopping problem of Gusein-Zade// Stoch.Processes Appl.,1980.-V.10.-P.299-311.

50. Garnaev A. On a Sakaguchi's problem in Non-Zero-Sum Games of Timing.// Math.Japonica, 1996.-V.44.-P.291-301.

51. Garnaev A., Garnaeva G. An infiltrated game on a circumference//Nova J. Math. Game Theory and Algebra,1996.-V.5.-P.235-240.

52. Garnaev A. Value of information in optimal stopping games//Nova Sci.Publ. ,Commack New-York,2000.-V.V.-P.55-64.

53. Gilbert J., Mosteller F. Recognizing the maximum of a sequence//J.Amer. Statist.Ass., 1966. -V.61.-P.35-73.

54. Gnedin A.V. A solution to the game of Googol// Ann.Appl.Probab., 1994. -V.22.-P. 1588-1595.

55. Gusein-Zade S.M. The problem of choice and the optimal stopping rule for a sequential of a independent trials//Theor.Prob. and Its.Appl., 1966. -V. 11.-P.472-476.

56. Guttman I. On a problem of L. Mozer//Can.Math.Bull.,1960.-V.3.-P.35-39.

57. Henke M. Expectations and variances of stopping variables in sequential selection processes.//J.Appl.Probab.,1973.-V.10.-P.786-806.

58. Hill T.P., Krengel U. On the game Googol//International J.Game Theory, 1992.-V. 21.-P. 151-160.

59. Hill T.P., Kennedy D.P. Sharp inequalities for optimal stopping with rewards based on ranks//Ann.Appl.Probab.,1992.-V.2.-P.503-517.

60. Irle A. On the best-choice problem with random population size//Ztschr. Oper.Res.A.,1980.-V.24,N 5.-P.177-190.

61. Kurano M., Yasuda M., Nakagami J. Multi-variate stopping problem with a majorite rule//J.Oper.Soc.Japan, 1980.-V.23,N 3.-P.205-223.

62. Lindley D. Dynamic programming and decision theory.- Appl.Statist., 1961,-V.10,N1.-P.39-51.

63. Mazalov V.V. A game related to optimal stopping of two sequences of independent random variables having different distribution// Math. Japonica, 1996 .-V.43.-P. 121-128.

64. Mazalov V.V., Peshkov N.V. Game with selection among two observations of two persons//Proceedings of AMSE SCI'94, Wuhan, 1994.-V.1.-P.68-73.

65. Mazalov V.V., Saario V. The house-selling problem with rewardrate criterion //J.Appl.Probab.,2002.-V.39,-P.644-649.

66. Mozer L. On a problem of Cayley//Scripta Math.,1956.-V.22.-P.289-292.

67. McNamara J.M., Collins E.J. The job-search problem as an employer candidate game// J.Appl.Probab.,1990.-V.28.-P.815-827.

68. Mucci A.G. On a class of secretary problems//Ann.Prob.,1973.-V.l.-P.417- 427.

69. Petruccelli J. Best-choice with partial information.- //Ann.Statist., 1980.-V.9.-P.1171-1174.

70. Petruccelli J. Pull-information best-choice problrms with recall ofobservations and uncertainty of selection depending on the observation.-// Adv.Appl. Probab.,1982.-V.14,N2.-P.340-358.

71. Petruccelli J. The best-choice problem when the number of observations is random//J.Appl.Probab.,1983.-V.20.-P. 165-171.

72. Rasmussen W.,Robbins H. The candidate problem with unknown population size// J.Appl.Probab.,1975.-V.12.-P.692-701.

73. Rasmussen W. A generalized choice problem//J.Optim.Theory and Appl., 1975.-V. 15,-N3.-P.311-325.

74. Rocha A.L. The infinity secretary problem with recall// Ann.Appl. Probab., 1993.-V.21.-P.898-916.

75. Rose J. Optimal Sequential Selection based on relative ranks with renewable call options//J.Amer.Statist.,1984.-V.79.-P.430-435.

76. Saario V. Comparison of the discrete and continuous-time stochastic selling models//Engineering Costs and Production Economics, 1986.-V.12.-P.15-20.

77. Saario V., Sacaguchi M. Some generalized house-selling problems //Math. Japon. ,1990.-V.35.-P.861-873.

78. Sakaguchi M. A note on the dowry problem// Repts.Stat.Appl.Res.Union Jap. Sci and Eng.,1973 -V.20.-N.1.-P.11-17.

79. Sakaguchi M. Dowry problems and OLA-policies// Repts.Stat.Appl.Res. Union Jap. Sci and Eng.,1978 -V.25.-P.124-128.

80. Sakaguchi M. A generalised secretary problem with uncertain employment //Math.Japonica,1978.-V.23,-P.647-653.

81. Sakaguchi M. Non-zero-sum games related to the secretary problem //J.Oper.Res.Soc.Jap.,1980.-V.23,N 3.-P.287-293.

82. Sakaguchi M., Tamaki M. Optimal stopping problems associated with a nonhomogeneous Markov process//Math.Japonica,1980.-V.25,N6.

83. Sacaguchi M. Sequential deception games//Math. Japonica, 1992.-V.37. -S.813-826.

84. Sakaguchi M. Informatoin structures and perfect information in simple exchange games//Game theory and applications, New York: Nova Science Publishers, 1996.-P. 168-186.

85. Samuels S.M. On explicit formula for limiting optimal success probability in the full information best-choice problem//Purdue Univ. Dep. Statist. Mimeograph Ser.,1980.

86. Samuels S.M. Minimax stopping rules when the underlying disrtibution is uniform//J.Amer.Statist.Assoc., 1981.-V.76.-P. 188-197.

87. Samuels S.M. Secretary problems//In B.K. Ghosh and P.K. Sen(eds.): Handbook of Sequential Analysis.New York: Marcel Dekker,1991,-P.381-405.

88. Shepp L.A. Explicit solution to some problems of optimal stopping.// Ann.Math.Stat., 1969.-V.40.-P. 993-1010.

89. Smith M. A secretary problem with uncertain employment//J.Appl. Probab., 1975.-V.12,N 3.-P.620-624.

90. Smith M., Deely J.J. A secretary problem with finite memory//J.Amer. Assoc.,1975.-V.70.-P.357-361.

91. Snell J. Application of martingale system theorems//Trans.Amer.Math. Soc.,1955.-V.73,N 2.-P.293-512.

92. Stewart T. The secretary problem with unknown number of options// Oper.Res.,1981.-V.29,N 1.

93. Steward T. Optimal Selection from a random sequence with learning of the underlying distribution//J.Amer.Statist.Assoc.,1978.-V.73,N 364. -P. 775-780.

94. Suchwalko A., Szajowski K. Nonstandard, noninformation secretary problems//Sci.Math.Jap.,2001.-V.56.-P.443-456.

95. Tamaki M. OLA policy and the best-choice problem with random number of object//Math.Jap.,1979.-V24.-P.451-457.

96. Tamaki M. A secretary problem with double choices//J.Oper.Res.Soc. Jap., 1979.-V.22.-P. 257-265.

97. Tamaki M. Optimal selection with two choices-full information case// Mathematica Japonica, 1980.-V.25.-P.359-368.

98. Tamaki M. The secretary problem with optimal assignment// Oper.Res., 1984. -V.32.-P.847-858.

99. Tamaki M. Adaptive approax to some stopping problems//J.Appl.Probab., 1985 .-V.22.-P. 644-652.

100. Tamaki M. A full-information best choice problem with finite memory/ / J.Appl. Probab.,1986.-V.23,N 3.-P.718-735.

101. Tamaki M. Optimal stopping on trajectories and the ballot problem.// J.Appl.Probab.,2001.-V.38.-P.946-959.

102. Yang M.C.K. Recognizing the maximum of a random sequence based on relative rank with backward solicitation//J.Appl.Probab.,1974.-V.11.-P.504-512.