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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Ивашко Евгений Евгеньевич

ЗАДАЧИ НАИЛУЧШЕГО ВЫБОРА С РАЗЛАДКОЙ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 6 НОЯ 2009

Санкт-Петербург - 2009 г.

003484836

Работа выполнена в Учреждении РАН Институт прикладных математических исследований Учреждения РАН Карельский научный центр Российской академии наук.

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

Ведущая организация:

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

доктор физико-математических наук, профессор Андрей Юрьевич Гарнаев кандидат физико-математических наук Виктория Леонидовна Крепе

Новгородский государственный университет им. Ярослава Мудрого

Защита состоится " Р^.ХгФ&р.?. 200$ г. и^.-ЗРч&с. на заседании совета Д.212.232.59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, В.О., Средний пр., д.41/43, ауд.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: С.Петербург, Университетская наб., 7/9.

Автореферат разослан 200$г.

Ученый секретарь

диссертационного совета -^С."

доктор физ.-мат. наук, профессор / В. Д. Ногин

Общая характеристика работы

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

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

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

В работе исследуются следующие основные задачи:

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

2. Максимизация ожидаемого выигрыша в задаче наилучшего выбора с полной информацией с разладкой; решение строится в классе многопороговых и однопороговых стратегий.

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

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

Научная новизна работы заключается в формулировке, исследовании и решении новых постановок задач наилучшего выбора, обобщеп-

ных па случай ожидаемого изменения вероятностных характеристик случайного процесса (разладки).

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

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

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

В задаче максимизации ожидаемого значения принятой случайной величины из последовательности наблюдений исследованы две игровые постановки. Рассмотрены частные случаи абсолютного приоритета одного из игроков и бесконечно большого числа наблюдений; построены функции выигрыша и найдены оптимальные пороговые стратегии.

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения.

1. Байесовская стратегия в задаче наилучшего выбора с разладкой с неполной информацией о наблюдениях в моделях с дисконтированием выигрыша и платой за наблюдения.

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

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

Связь работ с научными программами, темами. Основные результаты диссертации были получены при проведении исследований в рамках работ по грантам Отделения математических наук РАН (программа "Математические и алгоритмические проблемы информационных систем нового поколения") и Российского фонда фундаментальных исследований.

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

1. Международная конференция "Optimal Stopping and Stochastic Control", 22-26 августа 2005 г., Петрозаводск.

2. Российско-финская летняя школа "Dynamic Games and Multicriteria Optimization", 2-7 сентября 2006 г., Петрозаводск.

3. V Московская международная конференция по исследованию операций, посвященная 90-летию со дня рождения академика Н. Н. Моисеева, 10-14 апреля 2007 г., Москва.

4. Международная конференция 'Теория игр и менеджмент", 28-29 июня 2007 г., Санкт-Петербург.

5. II летняя школа Российского журнала менеджмента, 9-20 июля 2007 г., Санкт-Петербург.

6. Международный семинар "Graduate School Seminar: Citations as impacts of research - who reads our papers?", 5-7 декабря 2007 г., Финляндия-Швеция.

7. VII Международная петрозаводская конференция "Вероятностные методы в дискретной математике", 1-6 июня 2008 г., Петрозаводск.

8. Вторая международная конференция "Теория игр и менеджмент", 26-27 июня 2008 г., Санкт-Петербург.

9. XIII Международный симпозиум "Dynamic Games and Applications", 30 июня-З июля 2008 г., Вроцлав, Польша.

10. Третья международная конференция "Теория игр и менеджмент", 24-26 июня 2009 г., Санкт-Петербург.

11. Рабочее совещание "Сетевые игры и менеджмент (NGM-2009)", 28-30 июня 2009 г., Петрозаводск.

По материалам диссертации опубликовано 14 работ, из них 7 статей [1, 2, 3, 4, 5, 6, 7] и тезисы 7 докладов [8, 9, 10, 11, 12, 13, 14].

Структура и объем работы. Диссертационная работа состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации составляет 107 страниц. Список литературы включает 90 па-именований.

Содержание работы

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

В общем виде задачи наилучшего выбора с разладкой описываются следующим образом (модель (А)): рассмотрим производяп(ую систему, генерирующую последовательность из п независимых случайных величин Xi,..., Xo-i, Xg, Xo+i,..., Хп. В случайный момент 9 происходит разладка и закон распределения случайных величин изменяется.

Величины Х1, Х2, ...,Хо-1 описываются абсолютно непрерывной функцией распределения ^(ж), а величины Хо,Ху+1, ■ ■■,Хп — абсолютно непрерывной функцией распределения /^(гг). Будем говорить, что до разладки система находится в состоянии £1, а после — в состоянии £2.

Момент разладки в имеет геометрическое распределение с параметром а (0 < а < 1). То есть изначально система находится в состоянии 5х, а перед генерацией каждой новой случайной величины состояние системы изменяется согласно следующей матрице переходов:

¿51 ¿>2

5х а 1 — а

52 0 1

Наблюдателю (или нескольким наблюдателям) известны функции распределения случайных величин в состояниях ^ и £2, а также вероятность разладки 1 — а, но истинное состояние системы остается неизвестным. После получения каждого из значений случайных величин наблюдателю требуется решить: принять значение случайной величины (и закончить процесс наблюдений) или отклонить. При этом нельзя пи отвергнуть все наблюдения, ни вернуться к наблюдению, которое было отвергнуто ранее. Задача наблюдателя заключается в том, чтобы принять максимальное значение из последовательности случайных величин.

В случае нескольких наблюдателей задачу необходимо исследовать теоретико-игровыми методами. Такую теоретико-игровую модель наилучшего выбора с разладкой будем называть моделью (В).

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

В диссертационном исследовании рассматриваются два класса стратегий наблюдателя: однопороговые и многопороговые стратегии. Многопороговая стратегия — это такая стратегия, при которой наблюдатель па каждом шаге г (г = 1, ...,п) устанавливает порог qi и принимает случайную величину Хг в случае, если XI > qi, отвергая ее в противном

случае. Однопороговая стратегия — это такая многопороговая стратегия, при которой Цг — д, г — 1, ...,п.

Первая глава посвящена исследованию байесовской постановки задачи наилучшего выбора с разладкой.

В разделе 1 представлена постановка задачи: пусть наблюдатель действует в условиях модели (А). Информация о наблюдениях неполна — на каждом шаге известно лишь о том, превышает или нет полученная случайная величина установленный наблюдателем порог. Цель наблюдателя — максимизировать среднее выбранное значение из случайной последовательности наблюдений. Решение ищется в классе байесовских пороговых правил следующего вида. Перед шагом к, оценив апостериорную вероятность нахождения системы в состоянии 5ь наблюдатель устанавливает порог д = , - ■ -, 1) и принимает наблюдение Хк, если оно превышает этот порог. В противном случае наблюдение отвергается. То есть наблюдатель использует многопороговую стратегию с оценкой апостериорной вероятности возникновения разладки.

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

В разделе 2 рассмотрен вариант задачи, в котором выигрыш наблюдателя на каждом следующем шаге дисконтируется с коэффициентом Л. Согласно условию задачи, наблюдатель не знает истинного состояния системы (51 или 5г). Однако эта неопределенность может быть компенсирована с помощью оценки вероятности разладки. По значениям наблюдений вычисляется апостериорная (после получения информации о том, что х < <?) вероятность нахождения системы в состоянии :

, х РК| . , Р(Зг)Р(х < 915!) атг^(д) = »(«) = ПБ^х <я}= р{х < я) = -рг^.

Здесь ч = Цг ~ порог, установленный наблюдателем за г шагов до завершения наблюдений, 7г - априорная вероятность нахождения системы в состоянии ¿>1 (до получения информации о том, что х < <7), а

Рк(ч) = Т-РЧ«?) + ^2(9), ГДе 7Г = 1 — 7Г.

Пусть иг(тг) — это выигрыш наблюдателя за i шагов до окончания наблюдений. Тогда уравнение оптимальности с учетом коэффициента дисконтирования А будет следующим:

Уг (тт) = шах [А?;,-!^)^ (<?) + -кЕх (<г) + 7тЕ2 (<?)], г > 1,

^о(тт) = О \/7Г.

Здесь Ek(q) = f xdFk(x),k = 1,2. <?

Обозначим выражение n квадратных скобках через \\(jг, q). Тогда за i шагов до окончания наблюдений оптимальный порог q-t будет определяться решением оптимизационной задачи = argmaxV¡(7r,qi).

я

В диссертационной работе мы ограничились построением оптимального правила остановки и классе стационарных стратегий, когда порог q выбора наблюдений зависит только от 7Г и не зависит от номера шага.

Верпа следующая теорема о виде функции выигрыша.

Теорема 1.1 При фиксированном значении q последовательность функций Vi(ir,q) можно представить в виде

уг(ж,д) = 7гСМ + гШ,

где Gi и Ti удовлетворяют следующим рекуррентным соотношениям:

GM) = aaF1(q)Gi^l(q) + AT¿_i(q)(Fi(g) - F2(q)) + E1(q) - E2(q), i > 1, Tt(q) = F2(q)\Ti-X(q) + E2(q), i > 1, Go = T0 = 0.

При i. —► oo компоненты Gi(q) и T¿(q) сходятся соответственно к G(q) И T(q):

- (1-\а*\(д))(1-\У2(д))

Tía) = E'2(q) 1yi) J-A F3(q)-

Соответственно V¿(7r, q) —> V(ir,q), где

V(TT,q)=KG(q)+T(q). Порог принятия наблюдений q = q(ir) определяется как

q = argmax У(7Г, q).

я

Верна следующая теорема.

Теорема 1.2 Для любых непрерывных функций распределения Fi (ж) и F>(:г) таких, что F\(x) стохастически доминирует F-2(x), существует решение байесовской задачи наилучшего выбора с разладкой.

Используя те же рассуждения, что и в случае дисконтирования выигрыша, в разделе 2 строится байесовская стратегия для случая платы за наблюдения.

Обозначим с — значение, которое наблюдатель платит за каждое новое полученное наблюдение. Цель наблюдателя -- максимизировать ожидаемый выигрыш с учетом платы за наблюдения. Выигрыш наблюдателя находим следующим образом:

Повторяя рассуждения, используемые при доказательстве теоремы раздела 2, можно показать, что в классе стационарных стратегий выражение для У,(тг, д) имеет аналогичный вид:

= тгС.(д)

где С?г(д) и Тг(д) удовлетворяют следующим рекуррентным соотношениям:

с1(д)=аР,1(д)(?4_1 ((?)+№_!(9) -с)(ед -ед^ад-ад,» > 1,

ВД = Г2(Ч)(Т^(д) ~с) + Е2{4), г > 1, во = Т0 = 0.

При этом при к —> оо компоненты Ск(о) и ТЦд) предельной функции выигрыша сходятся соответственно к С (с;) и Т(д) вида

= Ег (д) (1 - 02 (д))-Е2(д) (1 - У, (?)) (<?) - (<?)) _

— Ei{q)-cF2(q)

(l-aFi(q))(l-/''3(q))

__„?)

1-F2((,)

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

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

В разделе 1 рассматривается следующая многопороговая задача наилучшего выбора с полной информацией с разладкой. Пусть в условиях модели (А) наблюдателю требуется максимизировать ожидаемое значение принятой случайной величины (получаемое им в качестве выигрыша). Известно, что в состоянии Si система генерирует случайные величины, равномерно распределенные на отрезке [0,1], в состоянии 5г — равномерно распределенные на отрезке [0,6].

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

Описанная задача является обобщением на случай разладки проблемы, рассмотренной в работе Мозера (1956).

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

Представленные выше выкладки для значений параметров Ь > 1 и Ъ < 1 обобщаются в следующей теореме.

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

для 1 < к < п — 1.

При а = 1 или Ь = 1 формулы, определяющие значения оптимальных порогов, сводятся к "последовательности Мозера".

Раздел 2 посвящен игровой задаче наилучшего выбора с разладкой, в которой каждый из двух игроков, используя однопороговую стратегию, стремится максимизировать ожидаемое значение принятой им случайной величины. Игроки соперничают за наблюдения, что выражается вероятностными приоритетами, с которыми каждая новая случайная величина передается тому или другому игроку. Решение ищется в классе однопороговых стратегий. В и. 1 раздела 2 рассмотрена следующая неконкурентная постановка игровой задачи наилучшего выбора с разладкой: пусть в условиях модели (В) каждый из двух наблюдатели"! (игрок I и игрок II) стремится максимизировать ожидаемое значение принятой случайной величины, получаемое им в качестве выигрыша. Известно, что в состоянии ¿>1 система генерирует случайные величины, равномерно распределенные на отрезке [0,1], в состоянии ¿2 — равномерно распределенные на отрезке [О, Ь]. На каждом шаге г (г = 1 ,..,тг) случайная величина Хг передается одному из игроков согласно заданным приоритетам: с вероятностью р наблюдение получает игрок I, с вероятностью 1 — р — игрок II. Таким образом, каждый из игроков получает лишь часть случайной последовательности Х?...,Хп. Если один из игроков на некотором шаге к (1 < к < п) принял наблюдение

Яп-к - <

Xk, то другому игроку каждое новое наблюдение из оставшейся случайной последовательности -ЙГь+ъ ...,Хп все также предоставляется с вероятностью, соответствующей его приоритету (это условие задачи и подразумевается под "неконкурентностыо"). Если игрок за п шагов не принял наблюдения, то он получает выигрыш, равный пулю.

Решение ищется в классе однопороговых стратегий (пороги q\ и г/2 для игроков I и II соответственно), значения порогов устанавливаются перед началом наблюдений и не могут быть изменены в дальнейшем.

Предположим, что игрок II имеет больший приоритет выбора наблюдений (то есть р < если это не так, то перенумеруем игроков таким образом, чтобы это условие выполнялось. Очевидно, что в таком случае ожидаемый выигрыш (а значит и значение оптимального порога) игрока I также будет меньше ожидаемого выигрыша игрока II.

Оптимальные значения порогов ql и будут определяться, решением следующей оптимизационной задачи:

q{ = arg тахЯ®1^,^) ql = arg таxH^{q^q2).

<72

При увеличении количества наблюдений (п —+ оо) функция выигрыша игрока I выглядит следующим образом:

Н3'{ци<ь) = lim H*(qi,q2) =

к—*со

{(аК£ + Ц* < Ь)( 1 - + орЬЙ +

I(Ql < Ь)Р—Ь-(рвН-(1-р)тгп(9а,Ь)7] l=a(pq, '

Тот же предельный переход в формуле функции выигрыша игрока II дает

HsHQi,Q3)= Hm fff (9ь®) =

к—* оо

(«Т* + ^ - < Ü) +«(! - +

Н<12<Ь)(1-а) ( b2-ql (h ч ,П „^-¿W 1_

Ь-р91-(1-р)92 \2{b-ql)PV> <Ш + l1 P)~2~J] l-a(№ + (l-p>ft) '

В диссертационной работе рассмотрен также случай, когда один из игроков имеет абсолютный приоритет принятия наблюдений (то есть р = 0). Фактически, это означает, что игрок II действует независимо от

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

В случае, если игрок II имеет абсолютный приоритет, а число наблюдений велико (п —> со и р = 0) функция выигрыша игрока I принимает следующий вид:

Я* (91,92)= Нт Н^ (<7Ь = [(«^ + 1{91 < Щ1 - + 1(02 < Ь)(I - а)^} ^

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

Теорема 2.2 В неконкурентной постановке игровой задачи наилучшего выбора с разладкой при бесконечном числе наблюдений и абсолютном приоритете оптимальная стратегия II игрока определяется как

ссли > Ь о: 7 а —

6 — 0 иначе, при этом ожидаемый выигрыш равен

11ЬЧ>11,?5)=тах а---- + --¿,1(Ъ < -)--.

\ 2(1 - аЬ) 1 — ао а а I

В п. 2 раздела 2 рассмотрена следующая игровая постановка задачи наилучшего выбора с разладкой: пусть каждый из двух наблюдателей (игрок I и игрок II) в условиях модели (В) стремится максимизировать ожидаемое значение принятой случайной величины (получаемое им в качестве выигрыша). Известно, что в состоянии система генерирует случайные величины равномерно распределенные на отрезке [0,1], в состоянии ¿?2 — равномерно распределенные на отрезке [0,6]. При этом игроки конкурируют за наблюдения — одна и та же случайная величина не может быть принята обоими игроками. Если оба игрока готовы принять наблюдение, то с вероятностью р приоритет выбора предоставляется игроку I, а с вероятностью (1 —р) — игроку II. Если один из игроков на каком-то шаге принял наблюдение, то другому игроку предоставляется возможность без конкуренции выбрать наблюдение из оставшейся случайной последовательности.

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

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

Далее будем считать, что игрок II имеет больший приоритет выбора наблюдений (р < а значит, и значение оптимального порога игрока

I также будет меньше значения оптимального порога игрока II.

При большом количестве наблюдений (п —> оо) функция выигрыша игрока I дает

#5>(<71,92) = Нт Я®1 (91,®) = [а3^ + ар^+

к—* оо I.

(1 - аЩдг < &)£ < Ъ) + + (1 _р){Ь _ ^^ +

Тот же предельный переход в формуле функции выигрыша игрока

II приводит к

Я51 (91.9а) = Я®1 (91,92) =

к—>оо

[а1-^ + (1 - аУ(92 <Ь)*±*] ^(92 - 91 + р(1 - 92))+ а(1 -+ (1 - а)/(92 < Ь) (^(92 - 91) + ^

"91

1

В диссертационной работе рассмотрен также случай абсолютного приоритета (р = 0). Применительно к задаче конкурентного поведения в экономике это означает, что игрок II доминирует на рынке, и значение его оптимального порога не зависит от поведения игрока I.

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

В разделе 1 рассмотрена задача наилучшего выбора с полной информацией с разладкой, в которой наблюдателю требуется максимизировать вероятность удачного выбора. Постановка задачи следующая: при условиях модели (А) наблюдатель стремится максимизировать вероятность выбора наибольшего значения из последовательности случайных величин, используя однопороговую стратегию. Известно, что в состоянии 51 случайные величины, наблюдаемые игроком, распределены равномерно на отрезке [0,1], а в состоянии 52 — равномерно на отрезке [0,6] (6 < 1 — параметр задачи).

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

Следующие формулы определяют вероятность удачного выбора как функции от параметров п,а и Ь при значениях порога д > Ь (функция Р1(п,5,а,Ь)) и д < Ь (функция Р2(п, д, а, Ь)):

Я (», д, а, Ь) = а- £ ±

' п — 7 1 — ад п

3=0 .3 = 1

и/ гл п V«1 , /1 П ~1_аЬ)п {я/ЬУ(1-(ч/Ь)п-') .

Р2(п,д,а,6) = а" Е „Л- + (* ~ а> 1 -ы> Е Ш п- -'+

3=0 ¿=0

п-2 п-г-1 ■ ,

(1-а)ЕИГ £ ^^

п-1

г=0

3=1

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

а^ шах

тах (п, д, а, Ь), тах Р2 {п, д, а, Ь)

<7>Ь <?</>

при этом вероятность удачного выбора вычисляется следующим образом:

Р(п.д*,а, Ь) = шах ( тахР1(п,д, а, Ь), тах Р2(п, д, а, Ь) ) .

V9<ь /

При большом числе наблюдений верна следующая лемма. Лемма 3.1 Для любых значений параметров а и Ь: 0 < а, Ь < 1 выполняется следующее неравенство:

Ыч2,а,Ъ) > Р1(д*,а,6).

С учетом леммы, решение задачи при большом числе наблюдении определяется следующей теоремой.

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

«Г =Ь,

при этом вероятность удачного выбощ

0.517 +

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

В разделе 2 рассмотрена следующая задача: каждый из т игроков независимо от остальных участников получает в качестве наблюдения значение случайной величины Х\. Игрок должен принять решение: остановиться на этом наблюдении или продолжить и получить еще одно наблюдение — значение случайной величины Х->. Побеждает тот игрок, чья сумма очков (равная значению случайной величины Х^, если игрок принял решение остановиться на первом наблюдении, или сумме значений случайных величин Х\ и А'г, если игрок решил продолжи ть) окажется наиболее близкой, но не превышающей 1. Если очки всех игроков превысили 1, то побеждает тот игрок, чья сумма очков оказалась наименьшей. Игроки не знают ни значений наблюдений, ни решений, принятых другими игроками. Целью каждого из игроков является максимизация вероятности собственного выигрыша. Для принятая решения об остановке юта продолжении игроки используют однопороговую стратегию.

При равномерном распределении наблюдений на отрезке [0,1] оптимальное значение порога определяется из уравнения

л ~2уп „2т—1 2(т-1) = 1 , <?_

4 т(д + 1) 2т-1(2т-1}'

В случае, если наблюдения распределены равномерно на отрезке [0,6], где Ь > 1, уравнение оптимальности выглядит следующим образом:

[ъч-ч + ч2 + ъ{ъ-1)}т-1 =

1 [ь2т-(ьд-д+93+ь(ь~:1)Г , (ф-1 + §)+ь(ь-1)Г-(4)т , 92"'-1

Ь т(ь+ч) ^ {д+Ь)т "г 2™~Ч2т-1) •

При Ь = 2 (следовательно, и при Ь > 2) значение оптимального порога д = 0. Это означает, что игрок должен остановиться на первом же наблюдении вне зависимости от полученного значения.

Теперь рассмотрим вариант задачи, в котором случайная величина Х1 имеет равномерное распределение на отрезке [0,1], а Х2 — равномерное распределение на отрезке [0,6], где Ъ > 1. Тогда значение оптимального порога я определяется из уравнения

При увеличении Ь, значение оптимального порога стремится к нулю.

Рассмотрим обобщение игры, описанной в модели В, на случай разладки. Пусть изначально распределение наблюдений является равномерным на отрезке [0,1]. В случайный момент времени (перед первым илп перед вторым наблюдением) может произойти разладка, и распределение случайных величин изменится на равномерное на отрезке [0,6], где 6 > 1. Момент разладки — это случайная величина, имеющая геометрическое распределение с параметром а. Разладка происходит для всех наблюдателей одновременно.

Решение этой игры можно представить как комбинацию решений трех рассмотренных ранее игр:

«ь-1+2Г-(§Г)]+

( 2 сх^ 1 \ д2т.— 1

+ Г + ь) 2™-1(2т-1)-

Ьт-(дЬ+д2-д)"

т,(Ь+д)

+дГ1

-1(2т-1)

Список литературы

[1] Мазалов В. В., Ивашко Е. Е. Байесовская модель в задаче наилучшего выбора с "разладкой" // Вестник СПбГУ. Серия 10. - 2009.

- Вып. 4. - С. 142-151, (вклад диссертанта 50%).

[2] Мазалов В. В., Ивашко Е. Е. Задача наилучшего выбора с полной информацией с разладкой // Обозрение прикладной и промышленной математики. - 2007. - Т. 14, вып. 2. - С. 215-224, (вклад диссертанта 50%).

[3] Мазалов В. В., Ивашко Е. Е. Задача выбора оптимального объема запрашиваемых ресурсов в условиях ожидаемой "разладки" сервера // Системы управления и информационные технологии.

- 2009. - №1.2(35). - С. 249-252, (вклад диссертанта 50%).

[4] Ивашко Е. Е. Игровая задача наилучшего выбора с разладкой с вероятностными приоритетами // Сборник трудов ИПМИ. - 2008.

Вып. 8. - С. 44-52.

[5] Ивашко Е. Е. Многопороговая задача наилучшего выбора с полной информацией с разладкой // Сборник трудов ИПМИ. - 2007.

- Вып. 7. - С. 11-15.

[6] Ивашко Е. Е. Многопороговая модель определения оптимального объема запрашиваемых ресурсов при ожидаемой "разладке" сервера // Информационные технологии моделирования и управления.

- 2009. - №2(54). - С. 261-264.

[7] Ivashko Е. Е. Random priority two-person full-information best-choice game with disorder // Contributions to game theory and management. Collected papers presented on the International Conference Game Theory and Management / Editors Leon A. Petrosjan, Nikolay A. Zenkevich. - SPb.: Graduate Schooll of Management, SPbSU, 2007.

- Vol. II. - P. 179-187.

[8] Мазалов В. В., Ивашко Е. Е. Задача наилучшего выбора с неполной информацией с разладкой. Тезисы доклада // Обозрение прикладной и промышленной математики. - 2008. - Т. 15, Вып. 3. -С. 553, (вклад диссертанта 50%).

[9] Ivashko Е. Е. Random priority zero-sum best choice game with disorder // Networking games and management. Extended abstracts.

- Petrozavodsk: IAMR KRC RAS, 2009. - P. 26-27.

[10] Ivashko E., Mazalov V. Best choice game with disorder // Game theory and management. Collected abstracts of papers presented on the Second International Conference Game Theory and Management / Editors Leon A. Petrosjan, Nikolay A. Zenkevich, - SPb.: Graduate School of Management, SPbSU, 2008. -P. 88-89, (вклад диссертанта 50%).

[11] Mazalov V. V., Ivashko E. E. Bcst-choice problem with disorder //' Proceedings of V Moscow International Conference on Operations Research (ORM2007), dedicated to the outstanding Russian scientists Nikita N. Moiseev 90th birthday: Moscow, 2007. - P. 174, (вклад диссертанта 50%).

[12] Mazalov V. V., Ivashko E. E. Bcst-clioice problem with disorder //' Proceedings of Dynamic Games and Multicriteria Optimization (DGMO-2006): Petrozavodsk, 2006. - P. 78. (вклад диссертанта 50%).

[13] Mazalov V. V., Ivashko E. E. Best choice problem with disorder and imperfect observations // Scientific papers of the Institute of Mathematics and Computer Science of Wroclaw University of Technology, "13th International Symposium on Dynamic Games and Applications", Wroclaw, Seria: Conferences 5. - N 2G. - 2008. - P. 160, (вклад диссертанта 50%).

[14] Mazalov V. V., Ivashko E. E. Random priority zero-sum best choice game with disorder and imperfect observation // Game theory and management. Collected abstracts of papers presented on the Third International Conference Game Theory and Management / Editors Leon A. Petrosjan, Nikolay A. Zenkevich. - SPb.: Graduate School of Management, SPbSU, 2009. -P. 166-167, (вклад диссертанта 50%).

Формат 60x84 '/16. Бумага офсетная. Гарнитура «Times». Уч.-изд. л. 1,0. Усл. печ. л. 1,0. Подписано в печать 06.11.09. Тираж 100 экз. Изд. № 72. Заказ № 832.

Карельский научный центр РАН Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50

Введение

1 Байесовская модель задачи наилучшего выбора с разладкой

1.1 Постановка задачи.

1.2 Байесовская модель наилучшего выбора с дисконтированием выигрыша.

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

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

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

Проблемы наилучшего выбора впервые были представлены в 40-х годах в работах известного американского статистика А. Вальда в связи с задачами последовательного различения гипотез [3]. Основная особенность этих задач состоит в том, что наблюдатель последовательно обозревает независимые одинаково распределенные случайные величины с неизвестным законом распределения, и целью является определение типа распределения этих наблюдений. В отличие от классических методов ма тематической статистики, в которых число производимых наблюдений фиксируется заранее, методы последовательного анализа характеризуются тем, что момент прекращения наблюден ий (момент остановки) является случайным и определяется наблюдателем в зависимости от значений наблюдаемых случайных величин. Преимущество последовательных методов было продемонстрировано А. Вальдом на задаче различения двух простых гипотез по результатам независимых наблюдений. При этом было установлено, что подобные методы требуют в среднем меньшего числа наблюдений по сравнению с любым другим способом различения с фиксированным объемом выборки при тех же вероятностях ошибочных решений. Более того, А. Вальд указал и тот последовательный метод (названный критерием последовательных отношений вероятностей), который является оптимальным в классе всех последовательных методов [28].

Однако больший интерес использование последовательных методов представляет при изучении класса задач наилучшего выбора. Начиная с момента опубликования первой задачи этого класса ("задачи о секретаре"), было рассмотрено большое количество различных постановок. Однако можно выделить общие свойства, присущие задачам наилучшего выбора [1, 45):

• выбор осуществляется в несколько этапов, то есть растянут во времени;

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

• эффект выбора (выигрыш) тем выше, чем лучше выбранные варианты.

Классической постановкой задачи наилучшего выбора является следующая "задача о секретаре" (также называемая "задачей выбора невесты") [1, 45, 50]: в компании имее тся одно вакантное место секретаря, на которое пре тендует п соискателей, проранжированных по качеству - лучший претендент имее т (абсолютный) ранг 1, худший - ранг п. С претендентами последовательно в случайном порядке проводятся собеседования (равновероятны все последовательности, в которой будут приглашаться на собеседование претенденты). Решение о принятии претендента или отказе в занятии вакансии основывается на относительном ранге - оценке качества текущего претендента относительно качеств предыдущих претендентов. Решение должно быть объявлено соискателю сразу же по окончании собеседования с ним, причем нельзя принять соискателя, которому ранее было отказано в занятии вакансии. Требуется с наибольшей вероятностью принять лучшего из всех претендентов (если принятый претендент лучший из всех, то выигрыш равен 1, в противном случае выигрыш равен 0).

Описанная задача была решена в 1961 г. независимо друг от друга Е. Б. Дынкиным (основываясь на теории марковских процессов [7]) и Д. Линдли (с помощью метода динамического программирования [61]). Оба решения приводят к неожиданному и красивому результату. Оказывается, необходимо пропустить (запоминая относительные ранги) примерно треть всех претендентов (п/е), а затем из оставшихся принять соискателя, который окажется лучше всех просмотренных ранее. При этом вероятность удачного выбора при п —» оо равна 1/е.

В последующие годы было изучено большое число новых постановок задачи наилучшего выбора (см. например, работы, содержащие исторические обзоры [35, 45, 47]). При этом было выделено два подкласса задач относительно информированности наблюдателя: задачи с полной и с отсутствием информации. Задачей с отсутствием информации называют вариант задачи наилучшего выбора, в котором распределение случайных величин неизвестно, а качество наблюдений может быть оценено лишь сравнением с предыдущими наблюдениями. В частности, к задачам с отсутствием информации относится и "задача о секретаре" (а также задачи, рассмотренные, например, в работах [21, 29, 38, 49, 87, 881).

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

Эвристическое решение этой задачи было впервые представлено в работе [50], а в статье [34] дано строгое доказательство полученного результата. Оптимальным правилом остановки является многопороговая стратегия - на каждом шаге / (1 < г < п) наблюдатель устанавливает порог и принимает первое наблюдение Х^. Х{ > с^ (уравнение для вычисления значений оптимальных порогов можно найти, например, в [50]). Вероятность успешного выбора при большом числе наблюдений равна примерно 0.58. Различные постановки задач наилучшего выбора с полной информацией были рассмотрены авторами работ [36, 51, 52, 58, 68, 73, 74, 75] и другими.

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

Помимо четко разграниченных подклассов задач с полной и с отсутствием информации, рассматривают также задачи с различными ограничениями на доступную информацию о наблюдениях - задачи с частичной информацией, в которых, например, известен закон распределения, но неизвестны его параметры, либо неизвестны точные значения наблюдаемых случайных величин и т.д. (см., например, [70, 71, 72]).

Для каждого из подклассов было рассмотрено большое количество различных постановок задач наилучшего выбора. Интерес к этим задачам обусловлен следующими причинами. Во-первых, задачи наилучшего выбора отражают существенные особенности реальных процессов выбора в условиях неопределенности; во-вторых, они всегда имеют содержательную постановку и легко интерпретируемые решения в экологии, информационных технологиях, экономике и других науках (см. [13, 15, 77]).

Задача обнаружения разладки. В теории обнаружения и статистическом контроле часто приходится сталкиваться с задачами, в которых вероятностные характеристики наблюдаемых величин могут измениться в случайный момент времени (момент появления "разладки"). При этом возникает проблема скорейшего обнаружения момента изменения вероятностных характеристик последовательности случайных величин. Эта проблема описана в монографии А. Н. Ширяева (так называемая задача "о разладке" [28]), в которой, в частности, приводятся решения задачи о разладке винеровско-го процесса и задачи в байесовской постановке. Задача "о разладке", послужившая отправной точкой представленного диссертационного исследования, состоит в следующем: пусть 0 - случайная величина, принимающая значения 0,1,., а наблюдения Хх,^,. таковы, что при условии в = п величины Х\: Х2:., Х„-1 независимы и одинаково распределены и имеют функцию распределения ^о(аг), а ХП1 Хп^\,. — также независимы и одинаково распределены, но имеют функцию распределения Р\{х) ф То есть в момент в происходит изменение вероятностных характеристик у наблюдаемого процесса. Возникает задача, как, последовательно наблюдая величины Х2) ■■• решить вопрос о том, в какой момент следует сделать вывод о произошедшей "разладке" — изменении вероятностных характеристик, но так, чтобы с одной стороны избежать ошибки классификации (объявления о "разладке" в тот момент, когда она еще в действительности не произошла), а с другой стороны — минимизировать время между возникновением "разладки" и ее фактическим обнаружением.

Задача о "разладке" была решена А.Н. Ширяевым в 1971 году. Различным вариантам этой задачи было посвящено также большое количество работ других авторов (см., например, [24, 30, 54]).

Модели, связанные с обнаружением разладки, применяются, например, при статистическом анализе историчесЕсих текстов и установлении авторства [2], контроле качества технологических операций [26] и т.д.

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

В общем виде задачи наилучшего выбора с разладкой описываются следующим образом (в дальнейшем на эту базовую постановку мы будем ссылаться как на модель (А)): рассмотрим производящую систему, генерирующую последовательность из п независимых случайных величин Х\,Х2, •■•, Хо, Хо+1,., Хп. В случайный момент 9 происходит разладка и закон распределения случайных величин изменяется. Так, величины Хь Л'2,., Хв-1 описываются абсолютно непрерывной функцией распределения ^(х), а величины Хо, Хд+\,., Хп - абсолютно непрерывной функцией распределения ^(.т). Будем считать, что до разладки система находится в состоянии ¿>1, а после — в состоянии ¿)2.

Момент разладки 9 имеет геометрическое распределение с параметром а (0 < а < 1). То есть изначально система находится в состоянии ¿>1, а перед генерацией каждой новой случайной величины состояние системы изменяется согласно следующей матрице переходов: а 1 — а

2 0 1

Наблюдателю известны функции распределения случайных величин в состояниях £>1 и <5*2, а также вероятность разладки 1 — а, но истинное состояние системы остается неизвестным. После получения каждого из значений случайных величин наблюдателю требуется решить: принять значение случайной величины (и закончить процесс наблюдений) или отклонить. При этом нельзя ни отвергнуть все наблюдения, ни вернуться к наблюдению, которое было отвергнуто ранее. Задача наблюдателя заключается в том, чтобы принять максимальное значение из последовательности случайных величин.

В случае нескольких наблюдателей задачу необходимо исследовать теоретико-игровыми методами. Такую теоретико-игровую модель наилучшего выбора будет называть моделью (В).

Особенностью (и дополнительной сложностью) задач наилучшего выбора с разладкой является то, что на неопределенность, связанную со значениями будущих наблюдений, накладывается неопределенность, связанная с текущим состоянием системы (произошла разладка или нет). На основе моделей (А) и (В) в представленном диссертационном исследовании рассмотрен ряд постановок задач, отличающихся целями наблюдателей (максимизация либо вероятности выбора максимального значения, либо ожидаемого значения принятой случайной величины), наличием конкурентов при выборе (игровые постановки), возможностями варьирования порогов в процессе наблюдения (значения порогов могут быть зафиксированы до начала наблюдений или наоборот, наблюдатель может иметь возможность изменять значения порогов, учитывая оценку вероятности нахождения системы в определенном состоянии) и т.д.

В диссертационном исследовании рассматриваются два класса стратегий наблюдателя: однопороговые и многопороговые стратегии. Многопороговая стратегия — это такая стратегия, при которой наблюдатель на каждом шаге г (г = 1, .,п) устанавливает порог <7/ и принимает случайную величину Х^ в случае, если х1 > отвергая ее в противном случае. Однопорого-вая стратегия — это такая многопороговая стратегия, при которой ^ = д,

I = 1, .,77.

Впервые вариант задачи наилучшего выбора с разладкой был рассмотрен в работе [78], где в условиях модели (А) необходимо максимизировать ожидаемое принятое значение из последовательности случайных величин. При этом наблюдатель оценивает вероятность нахождения системы в одном из состояний, на основе чего модифицирует значения порогов.

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

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

В работе исследуются следующие основные задачи:

Заключение

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

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

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

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

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

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

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

2. Бродский Б. Е., Дарховский Б. С. Методы обнаружения ''разладки" случайных процессов и их применение для анализа исторических текстов. Из Фоменко А. Т. "Методы статистического анализа исторических текстов", в 2-х томах. М.: Крафт+Леап, 1999, - 832+908 с.

3. Вач1ьд А. Последовательный анализ. Пер. с англ. М.: Наука, 1960, -328 е.;

4. Воробьев Н. Н. Теория игр. Лекции для экономистов-кибернетиков. -Л.: Изд-во Ленингр. ун-та, 1974. 160 с.

5. Гнедин А. В. Многокритериальная задача об оптимальной остановке процесса выбора // Автоматика и телемеханика. 1980. N 7. - С. 161 166.

6. Гусейн-Заде А. А. Задача выбора и оптимальное правило остановки последовательности независимых испытаний // Теория вероятностей и ее применения. 1966. - Т. 11, N 3. - С. 534 537.

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

8. Ивашко Е. Е. Игровая задача наилучшего выбора с разладкой с вероятностными приоритетами // Сборник трудов ИПМИ. 2008. - Вып. 8. С. 44-52.

9. Ивашко Е. Е. Многопороговая задача наилучшего выбора с полной информацией с разладкой // Сборник трудов ИПМИ. 2007. - Вып. 7. -С. 11-15.

10. Ивашко Е. Е. Многопороговая модель определения оптимального объема запрашиваемых ресурсов при ожидаемой ''разладке" сервера // Информационные технологии моделирования и управления. 2009. - №2(54) - С. 261-264.

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

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

13. Мазалов В. В., Ивашко Е. Е. Байесовская модель в задаче наилучшего выбора с "разладкой" // Вестник СПбГУ. Серия 10. 2009. - Вып. 4.1. С. 142-151.

14. Мазалов В. В., Ивашко Е. Е. Задача выбора оптимального объема запрашиваемых ресурсов в условиях ожидаемой "разладки" сервера // Системы управления и информационные технологии. 2009. - №1.2(35). - С. 249-252.

15. Мазалов В. В., Ивашко Е. Е. Задача наилучшего выбора с неполной информацией с разладкой. Тезисы доклада // Обозрение прикладной и промышленной математики. 2008. - Т. 15, Вып. 3. - С. 553.

16. Мазалов В. В., Ивашко Е. Е. Задача наилучшего выбора с полной информацией с разладкой // Обозрение прикладной и промышленной математики. 2007. Т. 14, вып. 2. - С. 215-224.

17. Мазалов В. В., Нейман П., Фалько И. А. Игровая задача оптимальной остановки наблюдений с неизвестными значениям // Дальневосточный математический сборник. 1998. - Вып. 6. - С. 74-86.

18. Оуэн Г. Теория игр. М.: Мир, 1971. - 230 с.

19. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. М.: Высшая школа, 1998. - 300 с.

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

21. Пресман Э. JL, Сонин И. М. Последовательное управление по неполным данным. Байесовский подход. -М.: Наука, 1982,- 256 с.

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

23. Розанов Ю. А. Случайные процессы (краткий курс). М.: Наука, 1971.- 288 с.

24. Сонин И. М. Игровые задачи, связанные, с наилучшим выбором // Кибернетика. 1976. - Вып. 2. - С. 70-75.

25. Томашевский А. В., Снежной Г. В. Использование последовательного критерия Вальда для обнаружения "разладок" технологических операций // Ав1ацшно-косм1чна техшка i технолопя. 2008. - Вып. 10. - С. 222-226.

26. Ширяев А. Н Вероятность: В 2-х кн. 4-е изд., переработ, и доп. М.: МЦНМО, 2007. С. 552-416.

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

28. Assaf D., Samuel-Cahn Е. The secretary problem; minimizing the expected rank with i.i.d. random variables // Adv. Appl. Prob. 1996. - Vol. 28. -P. 828-852.

29. Bassevile M., Nikiforov I. Detection of Abrupt Changes: Theory and Applications. New York: Prentice Hall, 1993. 469 p.

30. Baston V., Garnacv A. Competition for staff between two department // Game Theory and Applications. 2005. - X, edited by L. Petrosjan and V. Mazalov. - P. 13-26.

31. Bearden J. N., Murphy R. O. On generalized secretary problems. Risk and uncertainty: Mental, formal and experimental representations. New York: Springer, 2007. P. 187-206.

32. Berezovskiy B. A., Baryshnikov Yu. M., Gnegin A. V. On a class of best choice problems // Inform. Sci. 1986. - Vol. 39. - P. 111-127.

33. Bojdecki T. On optimal stopping of a sequence of independent random variables Probability maximizing approach // Stoch. Proc. Appl. - 1978. - Vol. 6. - P. 153-163.

34. Bruss F.T. What is known about Robbins' Problem? //J. Appl. Prob. -2005. Vol. 42. P. 108-120.

35. Bruss F.T., Ferguson T.S. Minimizing the expected rank with full information // J. Appl. Prob. 1993. - Vol. 30. - P. 616-626.

36. Campbell G. Optimal selection based on relative ranks of a sequence with ties // Adv. in Appl. Probab. 1984. - Vol. 16. - P. 136-146.

37. Chow Y., Moriguti D., Robbins H., Samuels S. Optimal selection based on relative rank (the "Secretary problem") // Israel J. Math. -1964. Vol. 2. -P. 81-90.

38. Cowan R., Zabczyk J. An optimal selection problem associated with the poisson process // Theory Probab. Appl. 1979. Vol. 23, issue 3. -P. 584-592.

39. Domansky V. K. Dynkin's stopping games with zero payoffs for separate stopping // Game Theory and Applications. 2006. - Vol. 2. - P. 33-47.

40. Domansky V. K. Dynkin's games with randomized optimal stopping rules// Annals of the International Society of Dynamic Games. 2004. - Vol. 7. -P. 247-262.

41. Enns E. G. Selecting the maximum of a sequence with imperfect information // Journal of the American Statistical Association. 1975. - Vol. 70, N 351.- P. 640-643.

42. Enns E. G. The Optimum Strategy for Choosing the Maximum of N Independent Random Variables // Unternehmensforsehung. 1970. Vol. 14.- P. 89-96.

43. Expert Group Report. NEXT GENERATION GRIDS 2. Requirements and Options for European Grids. Research 2005-2010 and Beyond, 2004. http://www.semanticgrid.org/docs/ngg2egfinal.pdf.

44. Ferguson F. Who solved the secretary problem? // Statistical Science. -1989. Vol. 4, N 3. - P. 282-296.

45. Finch S. Optimal stopping constants // Mathematical Constants, Cambridge. Univ. Press. 2003. - P. 361-363.

46. Freeman P. R. The secretary problem and its extensions: a review // Int. Statist. Rev. 1983. - Vol. 51. - P. 189-206.

47. Fushimi M. The secretary problem in a competitive situation // J. Oper. Res. Soc. Japan. 1981. Vol. 24. - P. 350-359.

48. Gianini J. P., Samuels S. M. The infinite secretary problem // Ann. Prob. -1976. Vol. 13. - P. 418-432.

49. Gilbert J., Mosteller F. Recognizing the maximum of a sequence // Journal of the American Statistical Association. 1966. - Vol. 61. - P. 35-73.

50. Gnedin A. V., Miretskiy D. I. Winning Rate in the Full-Information Best Choice Problem //J. Appl. Probab. 2007. - Vol. 44, N 2. P. 560-565.

51. Gnedin A. V., Sakaguchi M. On a best-choice problem related to the Poisson process // Contemporary Math. 1992. - Vol. 125. P. 59-64.

52. L. Han, D. Berry; Semantic-Supported and Agent-Based Decentralised Grid Resource, Elsevier Science, 2008.

53. Hawkins D., Olwell D. Cumulative Sum Charts and Charting for Quality Improvement. New York: Springer Verlag, 1998. 282 p.

54. Ivashko E. E. Random priority zero-sum best choice game with disorder /1 Networking games and management. Extended abstracts. Petrozavodsk: IAMR KRC RAS, 2009. - P. 26-27.

55. Karlin S. Stochastic models and optimal policy for selling an asset ed. by K. Arrow, S. Karlin and W. Scarf // Studies in Applied Probability and Management Science, Stanford University Press. Chap. 9. - 1962.

56. Kaynar B. Optimal stopping in a stochastic game // The American Statistician. 2009. - Vol. 23. - P. 51-60.

57. Lindley D. V. Dynamic programming and decision theory // Applied Statistics. 1961. - Vol. 10. - P. 39-51.

58. Lorenzen T. J. Generalizing the secretary problem // Adv. in Appl. Probab. 1979. - Vol. 11. - P. 384-396.

59. Lorenzen T. J. Optimal stopping with sampling cost // Ann. Probab. 1981.1. Vol. 9. P. 167-172.

60. Mazalov V. V., Ivashko E. E. Best-choice problem with disorder // Proceedings of V Moscow International Conference on Operations Research (ORM2007), dedicated to the outstanding Russian scientists Nikita N. Moiseev 90th birthday: Moscow, 2007. P. 174.

61. Mazalov V. V., Ivashko E. E. Best-choice problem with disorder // Proceedings of Dynamic Games and Multicriteria Optimization (DGMO-2006): Petrozavodsk, 2006. P. 78.

62. Moser L. On a problem of Cayley // Scripta Math. 1956. - Vol. 22, N 5. - P. 289-292.

63. Mucci A. G. On a class of secretary problems // Ann. Probab. 1973. - Vol. 1. - P. 417-427.

64. Neumann P., Porosinski Z., Szajowski K. On two person full-information best-choice problem with imperfect observation // Game theory and applications. -1996. Vol. II. - P. 47-56.

65. Petruccelli J. On a best choice problem with partial information // The Annals of Statistics. 1980. - Vol. 8, N 5. - P. 1171-1174.

66. Petruccelli J. D. Secretary Problem // Encyclopedia of Statistical Sciences. 1982. - Vol. 8. - P. 326-329.

67. Porosinski Z. The full-information best choice problem with a random number of observations // Stochastic Processes and their Applications. -1987. Vol. 24. P. 293-307.

68. Porosinski Z., Szajowski K. On Continuous-time Two Person Full-Information Best Choice Problem with Imperfect Observation // The Indian Journal of Statistics. 1996. - Vol. 58, ser. A - P. 186 493.

69. Porosinski Z., Szajowski K. Random priority two-person full-information best choice problem with imperfect observation / / Applicationes Mathematicae. 2000. - Vol. 27(3). - P. 251 263.

70. Robbins H. Remarks on the secretary problem // American Journal of Mathematical and Management Sciences. 1991. - Vol. 11. - P. 25-37.

71. Ryan R., Lippman S. A. Optimal exit from a deteriorating project with noisy returns // Probability in the Engineering and Informational Sciences.- 2005. Vol. 19. - P. 237-343.

72. Sakaguchi M. A best-choice problem for a production system which deteriorates at a disorder time // Scientiae Mathematicae Japonicae. 2001.- Vol. 54, N 1. P. 125 -134.

73. Sakaguchi M. Bilateral sequential games related to the no-information secretary problem // Math. Japon. 1984. - Vol. 29. - P. 961-973.

74. Sakaguchi M. Optimal stopping games. A review / / Math. Japonica/ 1995. - Vol. 42. - P. 343-351.

75. Sakaguchi M., Mazalov V. A non-zero-sum no-information best-choice game // Mathematical Methods of Operation Research. 2004. - Vol. 60. P. 437-451.

76. Sakaguchi M., Szajowski K. Single-level strategies for full-information best-choice problems. // Mathematica Japonica. 1997. - Vol. 45. - P. 183-495.

77. Samuels S. M. Exact solutions for the full information best choice problem // Purdue Univ. Stat. Dept. Mimeo Ser. 1982. - Vol. 17.

78. Samuels S. M. Why do these quite different best-choice problems have the same solutions? // Adv. Appl. Prob. 2004. - Vol. 36. - P. 398-416.

79. Sofronov G., Keith J., Kroese D. An optimal sequential procedure for a buying-selling problem with independent observations // J. Appl. Prob. -2006. Vol. 43. - P. 454-462.

80. Suchwalko A., Szajowski K. Non standard, no information secretary problems // Scientiae Mathematicae Japonicae. 2002. - Vol. 56. - P. 443456.

81. Tamaki M. Minimal expected ranks for the secretary problems with uncertain selection // Game Theory, Optimal Stopping, Probability and Statistics, ed. Bruss F.T. and Cam L.Le, Institute of Mathematical Statistics, 2000. P. 127-139.

82. Yasuda M. Asymptotic results for the best-choice problem with a random number of objects // J. Appl. Prob. 1984. - Vol. 21. - P. 521-536.

83. Yasuda M., Nakagami J., Kurano M. A multi-variate stopping problems with a monotone rule // Journal of the Operation Research, Society of Japan. -1982. Vol. 25, N 4. - P. 334-349.