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

□□3462555

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

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

МпО^

Фалько Анна Антоновна

ИГРЫ НАИЛУЧШЕГО ВЫБОРА С НЕСКОЛЬКИМИ УЧАСТНИКАМИ

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

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

003462555

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

Научный доктор физико-математических наук,

руководитель: профессор Владимир Викторович Мазалов

Официальные доктор физико-математических наук,

оппоненты: профессор Александр Валерианович Колногоров

кандидат физико-математических наук, доцент Николай Анатольевич Зенкевич

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

Санкт-Петербургский экономико-математический институт РАН

Защита состоится .кШ?гЯ\<?.. 200.5"г. в 1.С час. на заседании совета Д-212.232.59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, В.О., Средний пр., д. 41/43, ауд.

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

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

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

диссертационного совета —-

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

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

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

Классическая задача наилучшего выбора имеет различные названия: „задача о разборчивой невесте", „задача о секретаре" и т.д. (Дын-кин (1967), Линдли (1961)). Существуют различные постановки задачи наилучшего выбора в зависимости от степени информированности о качествах наблюдаемых объектов: задачи с отсутствием информации, задачи с полной информацией (качество рассматривается как случайная величина с известным законом распределения, Гильберт, Мостел-лер (1966), Ширяев (1976)) и частичной информацией (например, закон распределения качества известен, но неизвестны его параметры). Также исследуются задачи с другими критериями оптимальности, такими как „максимизация ожидаемого качества объекта" (Мозер (1956)) в задаче с полной информацией и „минимизация ожидаемого абсолютного ранга объекта" в задачах как с отсутствием информации (Роббинс и др. (1977)), так и с полной информацией. Классическая постановка задачи наилучшего выбора относится к задачам с отсутствием информации о качествах объектов и критерием оптимальности „максимизация вероятности выбрать наилучший объект". Задачи с многократным выбором исследовались в работах Николаева (1977,1998). Задача, в которой осуществляется взаимный выбор партнеров рассмотрена в работе Альпер-на (2005).

В теории игр широко представлен класс задач наилучшего выбора (Сакагучи, Фергюсон, Шайовский, Доманский и др.). Указанные выше задачи входят в этот класс как частный случай игр с одним участником. Для нахождения решения в данных задачах применяется некооперативная теория игр нескольких лиц.

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

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

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

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

3. задача двустороннего и трехстороннего выбора с полной информацией;

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

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

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

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

игроков из игры. Доказано, что в задаче без перераспределения вероятностей каждый игрок может вести себя независимо от общего числа игроков.

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

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

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

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

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

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

3. Найдено равновесие в задаче двустороннего и трехстороннего взаимного выбора с полной информацией. Доказано, что в задаче двустороннего выбора с пополнением групп оптимальное поведе-

ние игроков совпадает с поведением игрока в задаче одностороннего выбора.

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

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

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

1. Российско-скандинавский симпозиум 'Probability Theory and Applied

Probability", 26-31 августа 2006, Петрозаводск.

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

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

4. Международный конгресс "Нелинейный динамический анализ", 48 июня 2007, Санкт-Петербург.

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

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

7. Девятая Всероссийская научная конференция "Электронные библиотеки: перспективные методы и технологии, электронные коллекции (RCDL)", Семинар "Интернет-математика 2007", 15-18 октября 2007, Переславль-Залесский.

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

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

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

11. Третья Всероссийская школа молодых ученых "Математические методы в экологии", 24-29 августа 2008, Петрозаводск.

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

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

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

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

В первой главе рассматривается задача т лиц наилучшего выбора с ранговым критерием оптимальности. Комиссии из то человек (игроков) требуется совместно принять на работу секретаря. Всего имеется N претендентов на свободное место, которые рассматриваются последовательно в случайном порядке так, что все N\ перестановок равновероятны. Для каждого из игроков претенденты упорядочены по качеству (например, знание иностранного языка, навыки работы на компьютере и т. п.), т. е. каждому претенденту приписан абсолютный ранг, однако абсолютные ранги претендентов для каждого из игроков свои. Ранг 1 имеет наилучший претендент, ранг N — наихудший. Во время собеседования с очередным претендентом каждый игрок наблюдает его ранг относительно всех предыдущих (вычисляет относительный ранг) и на основе этой информации решает принять или отвергнуть текущего претендента. Абсолютные и относительные ранги одного и того же претендента для разных игроков независимы. Рассматриваются два способа принятия окончательного решения: с помощью арбитражной

процедуры и голосованием. Схема вынесения общего решения с помощью арбитражной процедуры следующая: если I членов комиссии согласны принять претендента, то он принимается с вероятностью и отвергается с вероятностью I = 0,1,...,т. В схеме голосования претендент принимается, если не менее к членов комиссии решают его принять. Если же претендент отвергается, то игроки переходят к рассмотрению кандидатуры следующего. При этом к отвергнутому претенденту нельзя будет вернуться в дальнейшем. На Л/-м шаге игроки вынуждены принять последнего претендента. В рассматриваемой задаче каждый игрок стремится минимизировать ожидаемый абсолютный ранг выбранного претендента.

В разделе 1.1 для схемы с арбитражной процедурой оптимальные пороги принятия претендента х* определяются в следующей теореме

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

Х1-1 = + ^^ - ^ (Ы + 1) (*< - ё).

где г = 1,2,..., ЛГ — 1, = у, [ач] — целая часть а^.

Рассматривая как функцию (то), зависящую от т, приходим к утверждению

Теорема 2 Оптимальные пороги х^^т), г = 1,2, ...,N — 1, возрастают по т.

В следующей теореме представлены границы для порогов х^тп), тп > 2.

Теорема 3 Оптимальные пороги х^т) удовлетворяют следующему неравенству:

< < *±! - < = 5,6,..., N-2; N>10.

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

где £дг_1 = у, [ж»] - целая часть гг*. Имеет место следующая теорема

Теорема 4 При N > 19 оптимальный выигрыш в задаче трех лиц наилучшего выбора с голосованием больше, чем в задаче двух лиц с арбитром.

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

2г2(г +1)

^ т—к

х»-1 = 2гт-*(»+1) Е

3=О к-1

(&([*,] + 1 + г)^'(г - [х,])*

4__2

(¿+1)

и■ - х-^-

иг — ¿г ¿^1 )

хм-1 = у;

Е

¿=0

£&Ы'(г- Ы)

т—у

где г = 1,..., N — 1, [¡г*] - целая часть а^.

Следующая формула дает явные выражения для оптимальных порогов

„. 1 ^Г-1 *0 = 2" —

; . От—1 ^ >

I

п

р=3

3 . 2т_1 ' ' I

р=2

[£]'(*-!-[£]Г~*+1 П'ео»-!)

_Р^з_

ЛГ-1

п Рт-1(р + 1) р=2

к-1

- +

где иР~ 1) = Е [^Г (Р - 1 - •

Рассматривая хо как функцию от к, при больших т и к = ат + е, а > | получим, что минимум хо достигается при нечетном N только при одном значении а = а при четном N — точками экстремума являются точки ах = а2 = а3 = ' пРичем. Для

./V > 4 минимум достигается в точке

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

=5<1*г+Ц р] [(М + (^М2 + - Ы) + 3(1 - р){г - Ы)2

+р1[х¿](г - [а*]) + 2(1 - р)г(г - [¡т4])2 +2х*(г - [хг]) ^3(1 - р)[ж4]2 + Зр[^](г - [®4]) + (г - [х4])2

где г — 1,..., N — 1; = [х»1 — целая часть х¿.

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

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

Имеется т фирм, каждая из которых хочет нанять секретаря. Всего имеется N претендентов на свободное место и качество каждого определяется равномерно распределенной на отрезке [0,1] случайной величиной. Директора фирм (игроки) по очереди беседуют с каждым претендентом, и после этого выносят решение принять его на место секретаря или отвергнуть. Если ^'-ый игрок решает предложить претенденту работу, то претендент соглашается принять предложение с вероятностью Рз, ] = 1,2, ...,т, р\ + Р2 + ... + Рт < 1. Если j-ъ¡R игрок принимает претендента, то он выходит из игры. При этом его выигрыш равен ожидаемому среднему значению качества выбранного секретаря. Если все игроки отвергают текущего претендента, то рассматривается следующий, причем, отвергнув претендента, к нему нельзя будет вернуться

в дальнейшем. Если фирма не приняла секретаря, то она терпит убытки С из-за нехватки специалистов, С 6 [0,1]. Каждый игрок стремится максимизировать свой выигрыш.

Если какой-то игрок остался один, то его ожидаемый выигрыш на шаге г равен

«.-(Р) = f (1 - ^+1(Р))2 + «Î+i(p),^+I(P) =0,г= 1,2,..., N.

Без ограничения общности р\ > р2 > ■■■ > рт- Обозначим v"1'3 — выигрыш j-ro игрока на г-ом шаге в игре m лиц, j = 1,2, ...,m, i = 1,2,..., N. Решение задачи приводится в теореме.

Теорема 5 В игре m лиц наилучшего выбора с возможностью отказа претендента от предложения каждый игрок ведет себя независимо от числа игроков в игре, т.е. v™'3=v\(pj), j=l,2,...,m; i = l,...,N— 1; v/v(Pj) = + Pj С для любого т.

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

1=1,w

j = 1,2,..., m,

где

v?'3 = v™,3{pi,...,pm),

= (pi,...,pm), = "I+i (Pl, -,Pm),

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

максимизировать сумму качеств выбранных претендентов. В силу преимущества первого игрока, его ожидаемые выигрыши и у} г при выборе первого секретаря на шаге г и второго на шаге г равны ь} г = у^г, у} = Уг, г = 1,2,..., ЛГ, г = г + 1,..., ЛГ, УМ+1 = 0, = О,

«; + 1-1>г,>+1 1

Уг = «¿,¿+1 + / (Щ+1 / хйх

— II п, ^ I + г'г,« + 1)3_____ I 1 + (<Л+1-У<|<+1)2.

— Щ,г+1 + \Щ+1 — Viti+l) н--2--— им+Н--2-'

г,('т'+1 1 и. г Ч2

Щ,т = / + / х(1х = .

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

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

у?г(В) — выигрыш второго игрока в случае, когда оба уже выбрали по одному секретарю;

у?г(Н) — выигрыш второго игрока в случае, когда первый игрок еще не выбрал первого секретаря, а второй выбрал;

у?(В) — выигрыш второго игрока в случае, когда первый игрок выбрал первого секретаря, а второй нет;

и? (Я) — выигрыш второго игрока в случае, когда оба игрока не выбрали ни одного секретаря.

Лемма 1 Для оптимальных порогов принятия претендента справедливы следующие равенства у} г+1 =у]г+1{В) и у^+1(В)—у^г+1(В) = у1г+1(Н), г = 1,2,...,ЛГ.

С учетом леммы ожидаемые выигрыши второго игрока вычисляются по следующим формулам

уЦН) = Е (тах{Хг]ь1г+1(НУ,у1+1(В)}) — иг,г+А**) "1 2

«?(Я) = Е (тах{Х, + ^+1(Я);г;2+1(В);г;2+1(Я)})'

_ 2 /т ("?.<+! (В))3+(1>?+1 (Д)-»?+1 (В)+»,'.<+1 (В))г

~ г+1Л / 2

В модели выбора двух секретарей с перераспределением вероятностей ожидаемые выигрыши игрока удовлетворяют следующим выражениям:

и.-,г(Рл) = Е (тах {РзХг + РМ,г+ЛРз)\^.Г+ЛРз)}) . »• = X + 1, М, Члг+1(Рл) =

Для игры т лиц имеет место следующая теорема:

Теорема 6 В игре т лиц наилучшего выбора двух секретарей без перераспределения вероятностей отказа претендента от предложения каждый игрок ведет себя независимо от числа игроков в игре, т.е. У?'* - у}(Р1),г = = ь1М,г = г + 1 =

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

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

Индивидуумы из двух групп (например, мужчины и женщины или работники и работодатели) хотят выбрать партнера (супруга, бизнес-партнера) из противоположной группы, т.е. создать пару. Индивидуумы выбирают друг друга в зависимости от показателя качества (например, уровень доходов или привлекательность). Каждый индивидуум заинтересован в выборе партнера с наибольшим значением качества, при этом значение собственного качества остается неизвестным. Если один из партнеров согласен принять другого, то второй может и не согласиться. Поэтому правило выбора должно касаться обоих партнеров. Рассмотрим многошаговую игру, в которой индивидуумы из разных групп (игроки) случайно попарно встречаются на каждом шаге. На первом шаге каждый из игроков встречает партнера, качество которого представляет случайную величину, равномерно распределенную на отрезке [0, 1]. Если игроки принимают друг друга, то они создают пару и покидают игру. При этом выигрыш каждого игрока равен значению качества выбранного партнера. Оставшиеся игроки переходят на следующий шаг. Так как на каждом шаге игроки выбывают из игры, то, следовательно, распределение игроков по качеству на следующем шаге меняется. На последнем шаге игроки вынуждены принять партнеров с

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

Каждый игрок использует пороговую стратегию с порогами ги!,...,адп_1, где 0 < гип_1 < ... < гюх < гио = 1. После г-го шага в игре останется игроков

IV?

^=2x01--;^, г = 1,...,п- 1,_ЛГ0 = 1.

^г-1

При этом распределение игроков по качеству после г-го шага будет иметь плотность вида

0 < х < Wi,

Мх) = \ ПЦ Щ+1 <X<Wj,j = i- 1,..., 1,

где г = 1,...,п — 1.

Уравнение оптимальности на г-м шаге имеет следующий вид

Уг(х) = тах{а;,Ег;4+1(а;4+1)}.

Тогда функция уп-\{х) примет вид

, V Г 0 < x < v)

П~ 1 >

ьп-1{х) - | ^ < х < х

Получим, что оптимальные пороги принятия партнера удовлетворяют уравнениям

Г"'1 У а л. гп_2 У ± ± [1

—

2М

1-1

г—1

к=О

,г = 1,...,п — 2.

В разделе 3.2 исследован вариант задачи двустороннего выбора с пополнение групп новыми игроками на каждом шаге. В Задаче с пополнением групп игроки используют пороговую стратегию с порогами

тих,...,!!},!-1, где 0 < гу„_1 < ... < ги\ < гио = 1- При этом на каждом шаге группы увеличиваются на Д* индивидуумов, г = 1, ,.,п — 1.

Плотность распределения игроков по качеству на каждом шаге зависит от общего числа индивидуумов. Вначале распределение качеств игроков равномерно на отрезке [0, 1]. После г-го шага (г = 1 ,...,п — 1) общее число индивидуумов в каждой группе равно

3 = 1

^Ц+Е Дз) 2__1=1_

+ ДьЛГ0 = 1.

При этом Д* находятся по формулам

Д;

3=1

где — число индивидуумов, создавших пару на г-м шаге, /3 — коэффициент рождаемости.

Тогда плотность распределения игроков по качеству после г-го шага (г = 1,2,..., п — 1) будет иметь следующий вид

1+ Е

3 = 1

лг4 >

(1+ Е А,)-^

3-1_' '

«зСИ-Е А ) 3 = 1

3 = 1

ЛГ;

3 = 1

^2

л,-)

3 = 1

О < х < ул\

Wi < X < 1;

гик<х<1ик-1; к = 2,...,г — 1;

■> < Я < 1.

(1)

Теорема 7 Равновесие по Нэшу в п-шаговой игре наилучшего взаимного выбора с пополнением групп определяется с помощью порогов и;*,

г = 1,...,п — 1, удовлетворяющих рекурсии

1

wn-1 = Jyfn-i(y)dy;

0

tüf = / tüi+i/iCyJdy-)- f yfi{y)dy, г = 1,2,..., n — 2,

0 u>i-t-i

где fi{y) удовлетворяют соотношениям (1) Лемма 2 Длл всех г = 1,..., п — 1 lim /¿(х) = 1.

ß—юо

Из теоремы 7 и леммы 2 вытекает

Следствие 1

При ß -+ оо оптимальные пороги Wi (г = 1, ...,п — 1) удовлетворяют следующим рекуррентным соотношениям

1 + ги?+1

шг =-2~'г== !>•••> ™ ~ 2; w„_i = 1/2.

Раздел 3.3 посвящен задаче трехстороннего выбора. В задаче трехстороннего взаимного выбора на шаге г тройка создается, если х + у > Wi, у + z > Wi и х + z > Wi, i = 1,2,..., п - 1, где Wi — порог принятия партнера, а x,y,z — значения качеств игроков из разных групп.

Обозначим fi(x) — плотность распределения игроков по качеству после г-го шага.

Значение оптимального порога Wi удовлетворяет системе рекуррентных уравнений

1

wn =2/ xf„(x)dx;

0

m+i 1

Wi =wi+1 f f?+Y(z)dz+ f zf*+Y(z)dz, ¿ = 1,2,..., n — 1,

0 1D,+1

где f*+Y{z) плотность распределения вероятностей случайной величины Z (Z — X + Y), X и У имеют плотность распределения /¿(х), i = 1,2, ...,п — 1.

Для случая двух шагов оптимальный порог равен w\ = у^(10 — \/34) = 0.758, а для п = 3 оптимальные пороги принятия партнера равны W2 = 0.823, wy — 0.449.

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

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

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

Обозначим a¿ абсолютный ранг г-го объекта, j/¿ относительный ранг г-го объекта, i = 1,2, • • • , N,

В задаче наилучшего выбора оптимальная стратегия (сг*,т*), 1 < а* < т* < N имеет вид

а* — min{¿ > к* : y¡ = 1},

т* = min{r > i, г > Г : уг = г} на {и> : а* = г}.

Полагал limjv^oo jj — си и linijV—>оо jj = Р, для достаточно больших N получаем, что вероятность удачного выбора вычисляется по формуле

Р(а, /3) = а(31п ¡3 + а - а/3 - а/31п2 /3 + а/31п /31п а.

При а* = е-4+е яа 0.278 и ¡3* = е-1 ss 0.368 получаем наибольшее значение Р(а*,/3*) = е~5+е « 0.102.

Два объекта (сначала наилучший, затем наихудший) можно выбрать с максимальной вероятностью, если действовать следующим образом: первые к* — 1 объектов нужно пропустить, начиная с к* и до I* — 1 нужно выбрать первый объект с относительным рангом 1, если такого

нет, то, начиная с I*, нужно выбрать сначала объект с относительным рангом 1, а потом относительно худший объект.

При N —> оо вероятность удачного выбора стремится к числу 0.102.

В разделе 4.2 исследована задача наилучшего выбора с полной информацией. В задаче качества объектов Х\, Х2, ■ ■ ■, Х^ являются последовательностью независимых и одинаково распределенных на отрезке [0,1] случайных величин. Необходимо с наибольшей вероятностью выбрать сначала объект с наименьшим качеством, потом с наибольшим.

Оптимальное правило имеет вид

а* = гшп{г: Х1 = шт{Х1,..., X»}, < х^-г},

г* = тт{г,г < г : Хг = тах{Х1,... ,ХГ},ХГ > * '

Пороги ум-г удовлетворяют уравнению

£ ^ /п+1- = 1,У0=Х.

п=г+1

Лемма 3 Оптимальные пороги уы-г, г = г + 1, г + 2,..., убывают по г.

Пороги хм-г для выбора объекта с наименьшим качеством удовлетворяют уравнениям ^¿(х, у') = ТУ^х, у'), г = 1,2,... ,N—1, где ^(х, г/') и ТУг(х, у') находятся по формулам

У{{х,у') = БирР{Х» = тт{Хь...,Х^},Хг = тах{Хь...,

т

Х{ — тт{Хь..., .Х*} = х,тах{Х1,..., Х{}=у'}.

Выигрыш при продолжении равен

ЛГ-1-г х

Т^(х,у')= £ (у'-х)п-1№+п(ъ+п,у,)<Ьц+п

п=1 О

ЛГ-1-т-1 1 х

п—2 р=1 у' О

В разделе 4.3 рассмотрен игровой вариант данной задачи. Дано N объектов, качества которых являются случайными величинами, равномерно распределенными на отрезке [0, 1]. Два игрока последовательно наблюдают значения качеств объектов. Первый игрок имеет5 приоритет в выборе объекта и стремится с наибольшей вероятностью выбрать сначала объект с наименьшим значением качества, а затем с наибольшим.

Цель второго игрока — выбрать объект с наименьшим значением качества.

Первый игрок в силу его доминирующего положения использует пороговую стратегию, имеющую вид (2). Найдены пороги принятия объекта для второго игрока = 1,г = 2,3,— 1, дающие наибольшее значение вероятности удачного выбора.

Список опубликованных работ по теме диссертации

[1] Мазалов В. В., Фалько А. А. Голосование в задаче наилучшего выбора с ранговым критерием // Обозрение прикладной и промышленной математики. - 2006. - Т.13, Вып. 4. - С. 577-588, (вклад диссертанта 50%).

[2] Мазалов В. В., Фалько А. А. Арбитражная процедура в задаче совместного наилучшего выбора для т лиц // Вестник СПбГУ. Серия 10. - 2008. - Вып. 4. - С. 52-59, (вклад диссертанта 50%).

[3] Мазалов В. В., Фалько А. А. Задача наилучшего выбора и ее применение в рекламных кампаниях поисковой системы Яндекс // "Интернет-математика 2007". - Екатеринбург: Изд-во Урал, ун-та, 2007. - С. 126-134, (вклад диссертанта 50%).

[4] Фалько А. А. Игра наилучшего выбора с возможностью отказа от предложения и перераспределением вероятностей // Методы математического моделирования и информационные технологии. Труды ИПМИ. - Петрозаводск: КарНЦ РАН, 2006. - Вып. 7. - С. 87-94.

[5] Falko A. A. Secretary problem with group choice // 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. - P. 123-129.

[6] Фалько А. А. Задача наилучшего выбора двух объектов // Методы математического моделирования и информационные технологии. Труды ИПМИ. - Петрозаводск: КарНЦ РАН, 2007. - Вып. 8. - С. 34-42.

[7] Mazalov V. V., Falko A. A. Voting in the best-choice problem with rank criterion / / Extended abstracts of Russian-Finnish Graduate School Seminar "Dynamic Games and Multicriteria Optimization", IAMR, Petrozavodsk, 2006. - P. 59-61, (вклад диссертанта 50%).

[8] Mazalov V. V., Falko A. A. Full-information best-choice problem with two stops // Proceedings of V Moscow International Conference on Operations Research (ORM2007), dedicated to the outstanding

Russian scientists Nikita N. Moiseev 90th birthday: Moscow, April 10-14, 2007. - P. 174, (вклад диссертанта 50%).

[9] Мазалов В. В., Фалько А. А. Задача совместного наилучшего выбора для двух игроков: Сборник тезисов Международного Конгресса "Нелинейный динамический анализ-2007", посвященного 150-летию со дня рождения академика A.M. Ляпунова, - СПб, 4-8 июня, 2007. - С. 327, (вклад диссертанта 50%).

[10] Мазалов В. В., Фалько А. А. Задача взаимного выбора // Обозрение прикладной и промышленной математики. - 2008. - Т.15, Вып. 3. - С. 561-562, (вклад диссертанта 50%).

[11] Mazalov V. V., Falko A. A. Mutual choice problem// 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 Schooll of Management, SPbSU, 2008. - P. 52-53, (вклад диссертанта 50%).

[12] Mazalov V. V., Falko A. A. Multidimensional mutual choice problem // 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 26. - 2008. - P. 158, (вклад диссертанта 50%).

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

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

Введение

1 Игра т лиц наилучшего выбора с ранговым критерием

1.1 Схема с арбитражной процедурой.

1.2 Схема с голосованием.

1.2.1 Задача с тремя игроками и голосованием.

1.2.2 Задача голосования для т игроков

1.3 Общий случай арбитражной процедуры для трех игроков

1.4 Результаты.

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

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

2.1.1 Модель без перераспределения вероятностей.

2.1.2 Модель с перераспределением вероятностей.

2.2 Теоретико-игровая задача выбора двух объектов с полной информацией

2.2.1 Игра двух лиц с доминирующим игроком.

2.2.2 Игра т лиц с возможностью отказа от предложения

2.3 Результаты.

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

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

3.2 Задача наилучшего взаимного выбора с пополнением популяции

3.3 Трехмерная задача наилучшего выбора.

3.4 Результаты.

4 Максимизация вероятности наилучшего выбора двух объектов

4.1 Задача с отсутствием информации.

4.2 Задача с полной информацией.

4.3 Игра двух лиц с доминирующим игроком.

4.4 Результаты.

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

Постановка классической задачи наилучшего выбора выглядит следуюл щим образом [1, 29].

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

Классическая задача наилучшего выбора имеет различные названия: „задача о разборчивой невесте", „задача о секретаре"и т.д. Также задача наилучшего выбора известна под названием „задача Googol"— выбор наибольшего из неизвестного набора чисел. Макквин и Миллер в 1960 году предложили вариант задачи наилучшего выбора под названием „задача о парковке" („задача о велосипедисте").

Существуют различные постановки задач наилучшего выбора, но характерные черты задачи следующие:

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

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

• эффект выбора зависит только от сравнения выбранных объектов со всеми остальными объектами и от некоторых внешних факторов (например, от затрат на проведение наблюдений);

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

Задача наилучшего выбора была независимо решена в 1961 г. Дынкиным и Линдли. Решение Дынкина [5] основывалось на теории марковских процессов. Линдли предложил решение методом динамического программирования. Изящное решение задачи приводит к неожиданному результату. Оказывается, необходимо пропустить примерно 37 процентов всех объектов, а затем остановиться на первом объекте, который лучше всех просмотренных ранее. При этом вероятность удачного выбора при N —> оо равна 1 /е.

Задача наилучшего выбора дала толчок к развитию теории оптимальной остановки случайных процессов. Эта математическая дисциплина нашла широкое приложение в задачах о продаже недвижимости, различении статистических гипотез, скорейшего обнаружения момента изменения свойств случайных процессов (так называемая „задача о разладке" [25, 30]), в стохастической финансовой математике.

В дальнейшем на основе классической постановки сформировался целый класс задач наилучшего выбора. Постановки различались степенью информированности о качествах наблюдаемых объектов: к задачам с отсутствием информации о качествах добавились задачи с полной информацией (качество рассматривается как случайная величина с известным законом распределения [1, 24, 46]) и частичной информацией (например, закон распределения качеств известен, но неизвестны его параметры [9, 32, 55]). Также начали исследоваться сценарии задач с другими критериями оптимальности, такими как максимизация ожидаемого качества объекта в задаче с полной информацией [54] и минимизация ожидаемого абсолютного ранга объекта в задачах как с отсутствием информации [37, 57], так и с полной информацией [33, 35, 36]. Классическая постановка задачи наилучшего выбора относится к задачам с отсутствием информации о качествах объектов и критерием оптимальности „максимизация вероятности выбрать наилучший объект". Другим обобщением задачи является вариант, когда число объектов является случайным ([22, 48, 56]) или бесконечным ([45]). Задача наилучшего выбора с неполной информацией, в которой распределение случайных величин известно, а точное значение наблюдаемой случайной величины не известно, рассмотрена в [40]. Задачи о секретаре с возможностью отказа претендента от предложения рассмотрены в [65, 68]. Существует ряд задач наилучшего выбора, в которых вероятностные характеристики самого случайного процесса зависят от выбранных управлений, например, „задача о двуруком бандите"([6, 7, 23]).

В теории игр широко представлен класс задач наилучшего выбора ([8]). Указанные выше задачи входят в этот класс как частный случай игр с одним участником. Для нахождения решения в данных задачах используется общая теория игр двух и более лиц ([2, 19, 20]). Игровые задачи наилучшего выбора без информации с критерием оптимальности „минимизация ожидаемого абсолютного ранга объекта"рассмотрены в [61, 62, 64], с максимизацией среднего качества объекта — в работах [34, 44, 63].

Многокритериальная задача, в которой необходимо с максимальной вероятностью выбрать объект, лучший хотя бы по одному критерию, рассмотрена в [3]. В играх т лиц наилучшего выбора, в которых принимается совместное решение о выборе объекта, также осуществляется многокритериальный выбор. Здесь возможны различные варианты выработки общего решения. Один из них — арбитражная процедура, при которой общее решение принимается при помощи третьей стороны — арбитра. В литературе такие задачи представлены в основном играми двух лиц, в которых приоритет игрока в решении определяется заданной вероятностью ([58, 64]). Применение арбитражной процедуры в играх трех лиц рассмотрено в работах [59, 63]. В случае трех и более игроков одним из вариантов принятия общего решения является голосование. При этом правила принятия решения могут быть различными, например, выбор претендента большинством голосов или согласно порогу голосования. В [49] рассмотрена игра нескольких лиц с голосованием, в которой целью каждого игрока является максимизировать свой ожидаемый выигрыш, и общее решение выносится большинством голосов. В [43] исследована задача о продаже недвижимости с голосованием и платой за наблюдения. Игра голосования, когда решение принимается посредством монотонного правила, останавливающего процесс просмотра, если число голосов не меньше заданного числа, рассмотрена в [69].

Задачи о выборе объекта с одним из заданных рангов рассмотрены в [4, 67]. В работах [15, 16, 17, 18, 21, 26] были исследованы задачи с отсутствием информации и многократным выбором. В [66] рассмотрена задача двукратной остановки: необходимо выбрать два объекта, максимизировав ожидаемую разность их качеств. Игровые задачи выбора двух объектов с полной информацией рассмотрены в работе [60]. Игровые задачи с оптимальной остановкой случайных процессов рассмотрены в [38, 39].

В приведенных выше постановках задачи выбор осуществляла только одна сторона, то есть считалось, что объект (или секретарь) всегда согласен с решением игрока. Такие задачи можно назвать задачами одностороннего выбора. Если объект также является лицом, принимающим решение, то приходим к задачам так называемого двустороннего или взаимного выбора. Данные задачи имеют широкое применение в биологии и социологии (выбор партнера), в задачах поиска работы (отношения работодатель-работник), при моделировании рыночных отношений (продавец и покупатель осуществляют взаимный выбор). Задачи двустороннего выбора с отсутствием информации о качествах игроков исследованы в работе [41], с полной информацией — в работах [31, 47].

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

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

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

3. задача двустороннего и трехстороннего выбора с полной информацией;

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

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

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

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

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

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

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

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

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

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

3. Найдено равновесие в задаче двустороннего и трехстороннего взаимного выбора с полной информацией. Доказано, что в задаче двустороннего выбора с пополнением групп оптимальное поведение игроков совпадает с поведением игрока в задаче одностороннего выбора.

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

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

1. Российско-скандинавский симпозиум "Probability Theory and Applied Probability", 26-31 августа 2006, Петрозаводск.

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

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

4. Международный конгресс "Нелинейный динамический анализ", 4-8 июня 2007, Санкт-Петербург.

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

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

7. Девятая Всероссийская научная конференция "Электронные библиотеки: перспективные методы и технологии, электронные коллекции (RCDL)", Семинар "Интернет-математика 2007", 15-18 октября 2007, Переславль-Залесский.

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

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

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

11. Третья Всероссийская школа молодых ученых "Математические методы в экологии", 24-29 августа 2008, Петрозаводск.

По материалам диссертации опубликовано 12 работ, из них 6 статьей [10, 11, 13, 27, 28, 42] и тезисы 6 докладов [12, 14, 50, 51, 52, 53]. Диссертация поддержана грантами РФФИ (проект 06-01-00128-а), Отделением математических наук, ООО "Яндекс" (конкурс "Интернет-математика-2007").

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

6. Колногоров А. В. О минимаксном подходе к оптимальному целесообразному поведению в стационарных средах на конечном времени // Известия АН СССР, Техническая кибернетика. 1988. - N 6. - С. 143-146.

7. Колногоров А. В. О целесообразном управлении средним уровнем случайных помех // Автоматика и телемеханика. 2000. - N 1. - С. 70-80.

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

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

10. Мазалов В. В., Фалько А. А. Арбитражная процедура в задаче совместного наилучшего выбора для га лиц j j Вестник СПбГУ. Серия 10. 2008. - Вып. 4. - С. 52-59.

11. Мазалов В. В., Фалько А. А. Голосование в задаче наилучшего выбора с ранговым критерием // Обозрение прикладной и промышленной математики. 2006. - Т. 13, Вып. 4. - С. 577-588.

12. Мазалов В. В., Фалько А. А. Задача взаимного выбора // Обозрение прикладной и промышленной математики. 2008. - Т. 15, Вып. 3. - С. 561-562.

13. Мазалов В. В., Фалько А. А. Задача наилучшего выбора и ее применение в рекламных кампаниях поисковой системы Яндекс // "Интернет-математика 2007". Екатеринбург: Изд-во Урал, ун-та, 2007. - С. 126-134.

14. Николаев М. Л. Об одном обобщении задачи наилучшего выбора // Теория вероятностей и ее применения. 1977. - Т. 22, Вып. 1. - С. 191-194.

15. Николаев М. Л. Об оптимальной многократной остановке марковских последовательностей // Теория вероятностей и ее применения. 1998. - Т.43, Вып. 2. С. 374-382.

16. Николаев М. JI. Оптимальные правила многократной остановки // Обозрение прикладной и промышленной математики. 1998. - Т.5, Вып. 2. -С. 309-348.

17. Николаев М. JL, Софронов Г. Ю., Полушина Т. В. Задача последовательного выбора нескольких объектов с заданными рангами // Известия Высших учебных заведений, С.-К. per., ест. науки, 2007. Т.4. - С. 11-14.

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

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

20. Полушина Т. В. Об одном обобщении задачи Гусейн-Заде // Обозрение прикладной и промышленной математики. 2007. - Т. 14, Вып. 2. - С. 225-229.

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

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

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

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

25. Софронов Г. Ю., Кроуз Д. П., Кейтз Д. М., Николаев М. JI. Об одном способе моделирования порогов в задаче многократного наилучшего выбора // Обозрение прикладной и промышленной математики. 2006. - Т.13, Вып. 6. - С. 975-983.

26. Фалько А. А. Задача наилучшего выбора двух объектов // Методы математического моделирования и информационные технологии. Труды ИПМИ. Петрозаводск: КарНЦ РАН, 2007. - Вып. 8. - С. 34-42.

27. Фалько А. А. Игра наилучшего выбора с возможностью отказа от предложения и перераспределением вероятностей // Методы математического моделирования и информационные технологии. Труды ИПМИ. Петрозаводск: КарНЦ РАН, 2006. - Вып. 7. - С. 87-94.

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

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

30. Alpern S., Reyniers D^ Strategic mating with common preferences // Journal of Theoretical Biology. 2005. - Vol. 237, N 4. - P. 337-354.

31. Ano K. On a partial information multiple selection problem // Game Theory and Application. 1998. - Vol. 4. - P. 1-10.

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

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

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. 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.

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

38. 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.

39. 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.

40. Eriksson K., Strimling P., Sjostrand J. Optimal expected rank in a two-sided secretary problem // Oper. Res. 2007. - Vol. 55, N 5. - P. 921-931.

41. Falko A. A. Secretary problem with group choice // Contributions to game theory and management. Collected papers presented on the International Conference Game Theory and Management / Editors Leon A. Petrosjan,

42. Nikolay A. Zenkevich. SPb.: Graduate Schooll of Management, SPbSU, 2007. - P. 123-129.

43. Ferguson T. Selection by committee // Annals of the International Society of Dynamic Games, Advances in Dynamic Games Application to Economics, Finance, Optimization and Stochastic Control. 2005. - Vol. 7. - P. 203-209.

44. Garnaev A., Solovyev A. On a two department multi stage game // Extended abstracts of International Workshop "Optimal Stopping and Stochastic Control", August 22-26, 2005, Petrozavodsk, Russia, 2005. P. 24-37.

45. Gianini J., Samuels S. The infinite secretary problem // The Annals of Probability. 1976. - Vol. 4, N 3. - P. 418-432.

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

47. McNamara J., Collins E. The job search problem as an employer-candidate game // J. Appl. Prob. 1990. - Vol. 28. - P. 815-827.

48. Kawai M., Tamaki M. Choosing either the best or the second best when the number of applicants is random // International Journal Computers and Mathematics with Applications. 2003. - Vol. 46. - P. 1065-1071.

49. Mazalov V., Banin M. N-person best-choice game with voting // Game Theory and Applications. 2003. - IX, edited by L. Petrosjan and V. Mazalov. - P. 45-53.

50. Mazalov V. V., Falko A. A. Full-information best-choice problem with two stops // Proceedings of V Moscow. International Conference on Operations

51. Research (ORM2007), dedicated to the outstanding Russian scientists Nikita N. Moiseev 90th birthday: Moscow, April 10-14, 2007. P. 174.

52. Mazalov V. V., Falko A. A. Voting in the best-choice problem with rank criterion // Extended abstracts of Russian-Finnish Graduate School Seminar "Dynamic Games and Multicriteria Optimization", IAMR, Petrozavodsk, 2006. P. 59-61.

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

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

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

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

57. Sakaguchi M. Multistage non-zero-sum arbitration game // Scientiae Mathematicae Japonicae. 2003. - Vol. 58, N 2. - P. 183-189.

58. Sakaguchi M. Multistage three-person game with arbitration // Scientiae Mathematicae Japonicae. 2004. - Vol. 60, N 2. - P. 403-410.

59. Sakaguchi M. Non-zero-sum best-choice games where two stops are required // Scientiae Mathematicae Japonicae. 2003. - Vol. 58, N 1. - P. 137-176.

60. Sakaguchi M. Non-zero-sum games related to the secretary problem // J. Oper. Res. Sos. Jap. 1980. - Vol. 23, N 3. - pp. 287-293.

61. Sakaguchi M. Three-member committee where odd-man's judgment is paid regard // Scientiae Mathematicae Japonicae. 2007. - Vol. 66, N 1. - P. 31-36.

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

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

64. 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.

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

66. 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.

67. 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.