Содержание к диссертации
Введение
1 Игра 771 лиц наилучшего выбора с ранговым критерием 15
1.1 Схема с арбитражной процедурой 16
1.2 Схема с голосованием 23
1.2.1 Задача с тремя игроками и голосованием 23
1.2.2 Задача голосования для т игроков 29
1.3 Общий случай арбитражной процедуры для трех игроков . 35
1.4 Результаты 38
2 Максимизация ожидаемого выигрыша в игре т лиц наилучшего выбора с полной информацией 40
2.1 Игра наилучшего выбора с возможностью отказа претендента от предложения 40
2.1.1 Модель без перераспределения вероятностей 40
2.1.2 Модель с перераспределением вероятностей 44
2.2 Теоретико-игровая задача выбора двух объектов с полной информацией 50
2.2.1 Игра двух лиц с доминирующим игроком 50
2.2.2 Игра лиц с возможностью отказа от предложения . 55
2.3 Результаты 58
3 Модели наилучшего взаимного выбора 60
3.1 Решение задачи наилучшего взаимного выбора 61
3.2 Задача наилучшего взаимного выбора с пополнением популяции 68
3.3 Трехмерная задача наилучшего выбора 77
3.4 Результаты 84
4 Максимизация вероятности наилучшего выбора двух объектов 86
4.1 Задача с отсутствием информации 86
4.2 Задача с полной информацией 89
4.3 Игра двух лиц с доминирующим игроком 95
4.4 Результаты 97
Заключение 98
Литература 100
- Общий случай арбитражной процедуры для трех игроков
- Игра лиц с возможностью отказа от предложения
- Задача наилучшего взаимного выбора с пополнением популяции
- Игра двух лиц с доминирующим игроком
Введение к работе
Задачи наилучшего выбора составляют важный класс задач, изучаемых теорией игр и теорией оптимальной остановки. Они отражают существенные особенности реальных процессов выбора, имеют простую содержательную постановку и легко интерпретируемые решения, что делает их применимыми в таких науках, как экономика, социология и психология.
Постановка классической задачи наилучшего выбора выглядит следующим образом [1, 29].
Дано N упорядоченных по качеству объектов, из которых требуется выбрать всего один. Ознакомление с объектами происходит в случайном порядке. На каждом шаге очередной объект можно сравнить со всеми предыдущими. Основываясь на данных о ранее просмотренных объектах, необходимо принять решение: остановиться на текущем объекте или отвергнуть его и продолжить процесс выбора, потеряв возможность возвращения к этому объекту в дальнейшем. Требуется найти стратегию, максимизирующую вероятность найти наилучший объект.
Классическая задача наилучшего выбора имеет различные названия: „задача о разборчивой невесте", „задача о секретаре"и т.д. Также задача наилучшего выбора известна под названием „задача Googl"— выбор наибольшего из неизвестного набора чисел. Макквин и Миллер в 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].
Общий случай арбитражной процедуры для трех игроков
Многокритериальная задача, в которой необходимо с максимальной вероятностью выбрать объект, лучший хотя бы по одному критерию, рассмотрена в [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. задача наилучшего выбора двух объектов, в которой необходимо максимизировать вероятность выбрать сначала наилучший, затем наихудший по качеству объект с различной информацией о качествах объектов, а также игровая постановка данной задачи. Научная новизна работы заключается в исследовании новых постановок задач наилучшего выбора и нахождении их решений. В задаче т лиц наилучшего выбора с ранговым критерием оптимальности исследованы два способа принятия общего решения: с помощью арбитражной процедуры и голосованием. Для первой схемы доказано возрастание оптимальных порогов с увеличением числа игроков, а также найдены границы для значений оптимальных порогов. Во второй схеме для трех игроков доказано, что процедура голосования комиссии из трех человек дает лучший результат, чем арбитражная процедура в игре двух лиц. Для случая трех игроков с арбитражной процедурой более общего вида найдены численные значения ожидаемых выигрышей и оптимальных порогов принятия решений при различных значениях параметров.
В задаче т лиц наилучшего выбора одного и двух объектов с полной ин формацией и критерием оптимальности в виде максимума ожидаемого среднего качества объекта (секретаря) исследованы модели с возможностью отказа претендента на должность от предложения игрока. Рассмотрены варианты задачи без перераспределения вероятностей принять предложения игроков и с их перераспределением. Доказано, что в задачах без перераспределения вероятностей каждый игрок может вести себя независимо от общего числа игроков.
Игра лиц с возможностью отказа от предложения
В данной главе рассмотрена некооперативная игра т лиц наилучшего выбора с ранговым критерием. Исследованы два способа принятия общего решения: с помощью арбитражной процедуры и голосования. В главе приведены оптимальные выигрыши игроков и пороги принятия претендентов для всех рассмотренных моделей.
Для случая арбитражной процедуры доказано возрастание порогов по числу игроков, а также найдены границы для значений оптимальных порогов.
В задаче с голосованием получены границы для значений оптимальных порогов для трех игроков, которые доказывают, что оптимальные пороги принятия претендента при голосовании комиссии из трех человек ниже, чем оптимальные пороги в игре двух лиц с арбитражной процедурой. Найдены явные выражения для оптимальных порогов при т 3, и исследован вид оптимального правила принятия решения в зависимости от порога голосования к.
Для случая трех игроков с более общей арбитражной схемой, в который как частные случаи входят игра с голосованием и игра с арбитражной процедурой, найдены численные значения полученных выигрышей и порогов принятия решений для различных значений параметров.
Результаты данной главы были представлены на Российско-скандинавском симпозиуме "Probability theory and applied probability", (Петрозаводск, 26-31 августа 2006 г., ИПМИ КарНЦ РАН), на Российско-финской школе "Dynamic Games and Multicriteria Optimization" (Петрозаводск, 1-7 сентября 2006 г., ИПМИ КарНЦ РАН), на Международной конференции "Теория игр и менеджмент" (Санкт-Петербург, 28-29 июня 2007 г., Высшая школа менеджмента СПб-ГУ, СПбГУ), а также отражены в статьях: в журнале Обозрение прикладной и промышленной математики, 2005, в журнале Вестник СПбГУ, 2008, в сборнике статей Международной конференции "Теория игр и менеджмент" (Санкт-Петербург, 28-29 июля 2007 г.) "Успехи теории игр и менеджмента", 2007.
В данной главе рассматриваются игровые постановки задачи наилучшего выбора с полной информацией, в которых каждый игрок стремится максимизировать свой ожидаемый средний выигрыш. Качества претендентов являются одинаково распределенными случайными величинами XI,X2,...,XN С известной функцией распределения F(x). Обычно для простоты рассматривают случайные величины, равномерно распределенные на отрезке [0,1]. В общем случае с произвольной функцией распределения F(x) задача сводится к случаю равномерного распределения на единичном отрезке заменой Х\, Х2,..., Х Ha.F(X1),F(X2)1...,F(XN).
Имеется т фирм, каждая из которых хочет нанять секретаря. Всего имеется N претендентов на свободное место и качество каждого определяется равномерно распределенной на отрезке [0,1] случайной величиной. Директора фирм (игроки) по очереди беседуют с каждым претендентом, и после этого выносят решение принять его на место секретаря или отвергнуть. Если j -ый игрок решает предложить претенденту работу, то претендент соглашается принять Предложение с вероятностью.
Если j-ый игрок принимает претендента, то он выходит из игры. При этом его выигрыш равен ожидаемому среднему значению качества выбранного секретаря. Если все игроки отвергают текущего претендента, то рассматривается следующий, причем, отвергнув претендента, к нему нельзя будет вернуться в дальнейшем. Если фирма не приняла секретаря, то она терпит убытки С из-за нехватки специалистов, С Є [0,1]. Каждый игрок стремится максимизировать свой выигрыш.
В работе [44] был исследован сценарий для одного и двух игроков. Сначала рассмотрим случай с одним игроком. Каждый претендент имеет качество х, которое определяется равномерно распределенной на отрезке [0, 1] случайной величиной. Вероятность того, что претендент согласится принять предложение равна р, р 1. Тогда р = 1 — р - вероятность отказа от предложения. Если на шаге г игрок отказывает претенденту, то он переходит к собеседованию с (г + 1)-ым претендентом. Обозначим vj(p) - ожидаемый выигрыш игрока на шаге г , г = 1,2,..., N.
Если г — iV, то игрок должен предложить претенденту работу независимо от его качества, так как в противном случае он потерпит убытки.
Задача наилучшего взаимного выбора с пополнением популяции
В задачах наилучшего выбора, как правило, принимает решение только одна сторона, а вторая всегда согласна с выбором. Например, в задаче выбора секретаря претенденты не могут осуществлять выбор работодателя. В данной главе рассмотрены модели многостороннего или взаимного выбора. Такие задачи имеют приложения в биологии, социологии, экономике и других науках, например, при выборе брачного партнера, в задачах поиска работы (отношения работодатель-работник), при моделировании рыночных отношений (продавец и покупатель осуществляют взаимный выбор).
Первый параграф данной главы посвящен многошаговой модели двустороннего взаимного выбора, в которой индивидуумы из двух групп выбирают брачных партнеров. Рассмотрен вариант задачи с пополнением групп на каждом шаге. Во втором параграфе исследовано обобщение задачи взаимного выбора на случай трех групп игроков.
Приведем постановку задачи двустороннего выбора, предложенной в работе [31]. Индивидуумы из двух групп (например, мужчины и женщины или работники и работодатели) хотят выбрать партнера (супруга, бизнес-партнера) из противоположной группы, т.е. создать пару. Индивидуумы выбирают друг друга в зависимости от показателя качества (например, уровень доходов или привлекательность). Каждый индивидуум заинтересован в выборе партнера с наибольшим значением качества, при этом значение собственного качества остается неизвестным. Если один из партнеров согласен принять другого, то второй может и не согласиться. Поэтому правило выбора должно касаться обоих партнеров. Рассмотрим многошаговую игру, в которой индивидуумы из разных групп (игроки) случайно попарно встречаются на каждом шаге. На первом шаге каждый из игроков встречает партнера, качество которого представляет случайную величину, равномерно распределенную на отрезке [0, 1]. Если игроки принимают друг друга, то они создают пару и покидают игру. При этом выигрыш каждого игрока равен значению качества выбранного партнера. Оставшиеся игроки переходят на следующий шаг. Так как на каждом шаге игроки выбывают из игры, то, следовательно, распределение игроков по качеству на следующем шаге меняется. На последнем шаге игроки вынуждены принять партнеров с любым качеством, иначе они останутся без пары и их выигрыш будет равен 0. Каждый игрок стремится максимизировать свой ожидаемый выигрыш.
Рассмотрим популяцию, состоящую из двух групп — мужчины и женщины. Количество индивидуумов в группах одинаково, и их качества равномерно распределены на отрезке [0,1]. Обозначим качество женщин через х, мужчин -через у (х,у Є [0,1]), а соответствующие группы — X и У. Случайным образом выберем двух индивидуумов разного пола, т.е. пару (х,у). Рассмотрим многошаговую игру, в которой на каждом шаге моделируются случайные встречи всех индивидуумов из двух групп. Будем искать равновесие в данной игре среди пороговых стратегий. Предположим, что каждый из игроков имеет некий порог для качества партнера, ниже которого он не желает создавать с ним пары. Если по крайней мере один из партнеров не согласен, пара не создается и возвращается в популяцию. Если оба партнера согласны, пара создается и покидает популяцию. При этом выигрыш каждого игрока равен значению качества выбранного партнера. Оставшиеся игроки переходят на следующий шаг. Таким образом, после каждого шага число индивидуумов с высоким качеством становится меньше, так как они образуют пары и выбывают из игры. Следовательно, и распределение игроков по качеству должно измениться. Рассмотрим вначале игру из двух шагов.
На первом шаге все игроки из данных групп встречаются друг с другом, и, если они устраивают друг друга, выбывают из игры. На втором шаге оставшиеся игроки опять случайным образом встречаются друг с другом и независимо от качеств партнеров создают пару. Опишем оптимальное поведение игроков.
Будем предполагать, что в каждой группе все игроки используют одну и ту же пороговую стратегию (для X и У пороги могут различаться). В двухша-говой модели игрок из группы Y (X) может получать наблюдения х\, Х2 (соответственно, г/і, г/г) и при этом использует пороговое правило w : 0 wr 1 ( w" : 0 w" 1). В силу симметрии равновесие по Нэшу будет достигаться среди правил с одним и тем же порогом w = w" = w для обоих полов. Если встретившийся партнер имеет качество меньше, чем w, то он отвергается, и игроки переходят к следующему шагу. Если качества обоих больше или равно w, создается пара, и игрокрі покидают игру. Тогда, если на первом шаге распределение игроков одного пола по качеству было равномерно на отрезке [0,1], то после первого шага оно изменится, поскольку игроки с качеством больше w частично покинут популяцию (см. рис. 3.1).
Игра двух лиц с доминирующим игроком
В данной главе представлены результаты исследования моделей задачи наилучшего взаимного выбора.
Рассмотрена постановка задачи двустороннего выбора с полной информацией, в которой на каждом шаге популяции пополняются вновь прибывшими индивидуумами. Для данной задачи найдены равновесные стратегии игроков. Доказано, что при большом значении коэффициента рождаемости в задаче с пополнением популяций оптимальные пороги стремятся к оптимальным порогам задачи наилучшего одностороннего выбора с полной информацией.
Рассмотрено обобщение задачи взаимного выбора на случай трех групп игроков. В задаче каждый игрок стремится выбрать двух партнеров, максимизировав при этом сумму их качеств. Найдены оптимальные стратегии игроков и представлены численные результаты полученных порогов принятия партнеров.
Результаты данной главы были представлены на VII Международной петрозаводской конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 10-16 июня 2008 г., ИПМИ КарНЦ РАН), на Второй Международной конференции "Теория игр и менеджмент" (Санкт-Петербург, 28-29 июня 2008 г., ВШМ СПбГУ, СПбГУ), на XIII Международном симпозиуме "Dynamic Games and Applications" (Вроцлав, Польша, ЗО июня-Зиюля 2008 г.), на Третьей Всероссийской школе молодых ученых "Математические методы в экологии"(Петрозаводск, 24-29 августа 2008г., ИПМИ КарНЦ РАН).
В данной главе рассматриваются задачи наилучшего выбора двух объектов с одним игроком. Игрок стремится с наибольшей вероятностью выбрать сначала наилучший объект, а затем наихудший. Исследуются варианты задачи с отсутствием и полной информацией о качествах наблюдаемых объектов.
Последовательный выбор двух объектов необходим, например, при покупке-продаже финансового актива. В этом случае в течение определенного периода времени необходимо приобрести актив по наименьшей цене, а затем продать по наибольшей.
Рассматривается задача наилучшего выбора двух объектов с отсутствием информации об их качествах. Дано N объектов, которые упорядочены по качеству, т.е каждому объекту приписан абсолютный ранг. При этом ранг 1 имеет наилучший объект, ранг N — наихудший. Ознакомление с объектами происходит в случайном порядке. На каждом шаге качество очередного объекта можно сравнить со всеми предыдущими. Основываясь па данных об уже просмотренных объектах (относительные ранги), необходимо решить, остановиться ли на текущем объекте или, отвергнув его и потеряв возможность вернуться к этому объекту в дальнейшем, продолжить процесс выбора. О распределении качеств объектов ничего неизвестно. Необходимо с наибольшей вероятностью выбрать сначала наилучший объект, потом наихудший.
Два объекта (сначала наилучший, затем наихудший) можно выбрать с максимальной вероятностью, если действовать следующим образом: первые к — 1 объектов нужно пропустить, начиная с к и до I — 1 нужно выбрать первый объект с относительным рангом 1, если такого нет, то, начиная с I , нужно выбрать сначала объект с относительным рангом 1, а потом относительно худший объект. При N —» со вероятность удачного выбора стремится к числу 0.102. Дано N объектов, поступающих последовательно в случайном порядке. Качества объектов XL,.X2,... ,XJV — последовательность независимых и одинаково распределенных на отрезке [0,1] случайных величин. Необходимо с наибольшей вероятностью выбрать сначала объект с наименьшим качеством, потом с наибольшим. В задаче наилучшего выбора необходимо найти оптимальную стратегию ( т ,т ), 1 ст т 7V, для которой Р(Ха = min{Xb ..., XN}, Хт = max{Xb ..., XN}) = supP (Xa = min{Xi,...,XN},XT = max{Xi,..., Xjy}). far) Пусть на шаге і выбран объект с наименьшим качеством, « = 1,2,...,7V-1. Обозначим V{r(x, у)— выигрыш при остановке на шаге г, если объект с наименьшим качеством выбран на шаге г. Vir(x,y) вычисляется по формуле.
