Содержание к диссертации
Введение
Глава I. Задача о продаже недвижимости .
1. Задача о продаже недвижимости на конечном интервале времени 9
2. Задача о продаже недвижимости с доходом в единицу времени 15
3. Продажа недвижимости с переменными порогами 21
Глава II. Задача о продаже недвижимости в теоретико-игровой постановке .
1. Продажа одного дома двумя фирмами. Игровая задача Т 36
2. Игровая задача Г Случай произвольного N 48
3. Игровая задача Г Случай нескольких домов 59
Глава III. Задача о продаже недвижимости в условиях неполной информации .
1. Случай неизвестных значений наблюдений 65
2. Случай с ненулевой платой 71
3. Случай с полной информацией для одного из игроков 79
4. Игра на правило остановки с допуском 82
Заключение 86
Библиография 101
- Задача о продаже недвижимости с доходом в единицу времени
- Продажа одного дома двумя фирмами. Игровая задача Т
- Игровая задача Г Случай нескольких домов
- Случай с полной информацией для одного из игроков
Введение к работе
В работе исследуется класс проблем последовательного наилучшего выбора, имеющих отношение к так называемой задаче о продаже недвижимости. Эти задачи принадлежат классу задач на правило остановки.
Задача на правило остановки возникла после появления работ американского статистика А.Вальда [60] по статистическому последовательному анализу (1947). Предложенная им процедура была оригинальной и практически важной.
Среди популярных задач в теории оптимальной остановки отметим задачу выбора наилучшего объекта (так называемая задача о секретаре), задачу о разладке случайных процессов, задачу о парковке автомобиля, задачу о разорении игрока, задачу о продаже дома и другие.
Классическая задача о секретаре имеет много общего с задачей о продаже недвижимости, поэтому приведём постановку задачи о секретаре в виде, предложенном Фергюсоном в [13]:
Задача - оптимально выбрать секретаря из фиксированного множества последовательно представляемых претендентов при условиях:
Вакантна одна должность секретаря.
Известно п - число претендентов на эту должность.
Претенденты проходят собеседование последовательно в случайном порядке, то есть все п! перестановок равновероятны.
Предполагается, что вы можете присвоить каждому претенденту ранг от лучшего до худшего; решение о принятии или непринятии претендента должно основываться только на относительных рангах ранее опрошенных претендентов.
Отвергнутый претендент не может быть возвращён позднее.
Вы очень привередливы и будете довольны только лучшим. Это означает, что ваш выигрыш 1, если вы выбрали лучшего из п претендентов, и 0 - в противном случае.
Решение этой задачи принадлежит классу правил остановки таких, что для некоторого целого г > 1 необходимо отвергнуть первых г — 1 претендентов, а затем принять такого из следующих претендентов, ранг которого окажется лучшим среди всех, опрошенных ранее. Вероятность
фп(г) выбрать лучшего из претендентов есть 1/п для г = 1, а для г > 1
г — 1 п 1
«0 = (—),—-
При п —> оо максимум этой вероятности достигается когда г/п —> 1/е ~ 0.3679. Таким образом, оптимально просмотреть около 37% претендентов и затем принять лучшего из всех опрощенных. Вероятность, что этот претендент окажется лучшим из всех претендентов также равна примерно 37%.
Различные постановки этой задачи рассматривались, в частности, в работах таких исследователей как: Дынкин, Юшкевич [66], Де Гроот [65], Ширяев [83], Роббинс, Сигмунд, Чао [76], Пресман, Сонин [74], Кован, Забжик [67].
А теперь приведём постановку задачи о продаже недвижимости.
Игрок (некоторая фирма, торгующая недвижимостью) наблюдает процесс, представляющий собой последовательность предложений о продаже объектов. В начале процесса игрок имеет фиксированное количество неделимых объектов одинакового качества, или домов, которые он должен продать. Предложения о продаже - одинаково и независимо распределённые неотрицательные случайные величины, имеющие известную функцию распределения с конечным математическим ожиданием. Предложения поступают последовательно и наблюдаются непосредственно после прибытия. В момент поступления текущего предложения игрок должен решить, принять ему это наблюдение (продать один из домов и перейти к следующему наблюдению) или отвергнуть его. Задача игрока - максимизировать ожидаемый выигрыш, равный сумме всех продаж. Этой задаче были посвящены исследования следующих авторов: Фишер [15], Кауфман [17], Олбрайт [1], Олбрайт и Дер-ман [3], Сакагучи [40, 41, 42, 43, 51], Саарио [33, 34, 12, 36], Сакагучи и Саарио [37, 38], Мазалов и Саарио [21], Макнамара, Коллинз [7, 24], Брюсе, Фергюсон [6], Райтер [30].
В дальнейшем мы можем использовать также термин "продавец" в том же смысле, что и термин "игрок".
Эта задача имеет практический интерес в том смысле, что иссле-
дование различных моделей поведения на рынке важно для понимания психологии участников рынка.
Задача может быть сформулирована и решена в соответствии с принципами стохастического динамического программирования. В дискретном случае оптимальное правило принятия решения может быть найдено из рекуррентного соотношения
vn,k = рЕ{тах{Х+ауп-і)к-і,оіуп-і>к]}+{1-р)сіУп-ігк = p2>(d„}fc)+aK-i,A,
roo roo
Tf(s) = (x — s)dF(x) = / max(x,s)dF(x) — s.
JS J — OQ
где а - дисконтирующий фактор и р - вероятность того, что наблюдение может быть получено на текущем шаге, а функция Тр, определённая для каждой функции распределения F с конечным математическим ожиданием, имеет вид
где vnk - оптимальное текущее значение процесса при условии, что осталось п периодов до конца процесса и игрок имеет к домов, с начальными условиями уПго = 0, vQik = Sk (S > 0) и d„iA = a(vn-itk - vn-i,fc-i) определяет критерий принятия текущего предложения X = X.
В непрерывном случае соответствующая рекуррентная функция приобретает вид дифференциального уравнения
д-^- = \TF{Vk{t) - Vk^{t)) - 0Vk{t),
где к - количество домов у игрока и t - оставшееся время. Начальные условия в этом уравнении Vo(t) = 0 и Vk(0) = Sk (S > 0). Также е-б»Л^ 0 у q определяется как дисконтирующий фактор и Л - параметр, определяющий интенсивность процесса поступления предложений.
Эти рекуррентные уравнения дают нам в качестве решений пороги принятия решений, пользуясь которыми игрок может определить, принимать ему текущее предложение или отвергать его. Не всегда представляется возможным найти аналитические решения этих уравнений; даже получить эти уравнения в явном виде можно только для некоторых простых семейств функций распределений для малых значений п. Смысл функции Тр, которая также может быть получена в явном виде только в специальных случаях - определить поведение последовательности {t>n,fc} или множества функций {Vk(t)}.
Наличие дисконтирующего фактора делает модель более реалистичной и применимой в реальных экономических задачах, где будущие выигрыши всегда дисконтируются по отношению к настоящему времени.
Предполагая, что в конце процесса непроданные объекты теряются, мы легко получаем правило принятия решения для отвергания или принятия предложений из конечного множества возможностей. В случае, когда процесс продолжается в течение бесконечного времени, последовательность {dk} - правило принятия решения при к непроданных объектах может быть найдена из семейства уравнений
dk = ^~~ [TF{dk) - TF(dk)], к > О, 1-а
где do — +00. Если объекты поступают в соответствии с однородным пуассоновским процессом, то коэффициент сф/(1 — а) заменяется на Х/в.
В экономической литературе эта задача также известна как задача поиска работы и была рассмотрена Макнамара и Коллинзом в работах [7, 24], а также Сакагучи в [51].
Впервые задача о продаже недвижимости была рассмотрена как часть более общих инвестиционных проектов, характеризуемых большой степенью неопределённости в будущих доходах в работах Фишера [15] и Кауфмана [17]. Также эта задача рассматривалась Олбрайтом [1], Олб-райтом и Дерманом [3] и Сакагучи [40, 41]. Саарио продолжил исследования в этой области в работе [33], указав некоторые свойства последовательностей {vn>k} и {dnjk}- В частности было показано, что последовательность {dU;k} доминируется сак, а {г^} —) рЕ(Х)/(1 — а) при к —> со.
Задача о продаже недвижимости также рассматривалась как специальный случай задачи более широкого класса - проблемы размещения ресурсов- в работах Райтера [30] и Сакагучи [42, 41, 43]. Кауфман [17] использовал модели такого типа с их двумерными расширениями для оптимизации инвестиционных решений с налоговыми ожиданиями. Экспериментальные данные показали, что оптимальные правила принятия решений сравнимы с человеческим поведением.
В дальнейшем Саарио [34, 12, 36], Саарио и Сакагучи [37, 38] продол-
жили исследования основной постановки задачи в различных случаях, таких как:
предложения о продаже поступают дискретно,
предложения о продаже поступают в соответствии с пуассонов-ским процессом,
предложения о продаже поступают в соответствии с пуассонов-ским процессом, но игрок имеет т возможностей задержать любое предложение для рассмотрения его в будущем. Здесь же рассмотрена игра двух игроков, каждый из которых хочет максимизировать ожидаемый выигрыш, который равен максимальному из полученных наблюдений. Игроки I и II имеют тп\ и т,2 возможностей выбрать предложения, но приоритет отдаётся игроку I.
В 1997 году Брюсе и Фергюсон [6] рассмотрели случай, когда предложения о продаже имеют векторный вид, причём за возможность наблюдать каждый такой вектор игрок должен заплатить цену с > 0.
Наконец, Мазалов и Саарио [21] предложили такую постановку задачи, в которой игрок должен максимизировать свой доход в единицу времени, устанавливая в начале игры цену за каждый из домов в отдельности.
В главе 1 данной работы рассматривается неигровая постановка задачи о продаже недвижимости, то есть такая постановка, когда присутствует только один игрок, желающий максимизировать свой выигрыш. В 1 приводится постановка задачи в случае, когда игрок имеет га идентичных неделимых объектов для продажи и игра продолжается п периодов, в каждый из которых игроку поступает предложение о продаже одного из объектов, а игрок решает, принять ему текущее наблюдение или перейти к следующему наблюдению, устанавливая в начале каждого периода пороговую цену за свой дом. Задача игрока в этом случае -максимизировать сумму полученных предложений.
В 2 условия задачи меняются, и игрок должен уже максимизировать доход в единицу времени, устанавливая в начале игры отдельную цену за каждый из домов. Оказывается, что все эти цены будут одинаковы, и с ростом количества домов стремятся к 0.5, а ожидаемый доход в
единицу времени стремится к 0.25.
Интуитивно ясно, что игрок в этом случае ведёт себя "недостаточно оптимально", так как его стратегия не меняется в зависимости от того, сколько времени он провёл на рынке, хотя его выигрыш убывает со временем. С учётом этого в 3 мы исследуем эту задачу в случае, когда игрок может менять цены на свои дома в зависимости от времени, а не от количества непроданных объектов. Для решения этой задачи мы используем метод динамического программирования, исследуя уравнение Беллмана. Результаты показывают, что наше предположение о том, что такой подход к назначению цены себя оправдывает и игрок получает больший выигрыш по сравнению с полученным в 2.
Задача о продаже недвижимости может быть рассмотрена также в условиях, когда борьбу за одно предложение ведут одновременно несколько продавцов. В этом случае значение максимизирующего функционала для каждого игрока зависит не только от случая и выбранной им стратегии, но и от поведения других игроков, то есть, возникает игровая ситуация. В главе 2 рассматривается конфликтная ситуация, когда продавец, желая привлечь покупателя, старается установить цену за свой дом меньше, чем у противника, но всё же так, чтобы не понести слишком больших убытков. Обычно в задачах такого типа один из игроков имеет постоянный на протяжении игры приоритет в наблюдении, то есть рассматривает поступающие предложения первым; мы же предлагаем выбирать приоритетного игрока случайным образом. Такая модель более приближена к реальному человеческому поведению.
Классическая задача предполагает, что игроку известны значения поступающих наблюдений, но это предположение может быть подвергнуто критике в том смысле, что в реальной жизни продавец не всегда знает, сколько готов заплатить тот или иной покупатель за предложенный ему объект. В главе 3 конструируется такая модель продажи недвижимости, в которой игрок информируется только о том, больше или меньше поступившее предложение о продаже установленной им цены. Задачи подобного типа, также известные как задачи с неполной информацией в различное время рассматривали Эннс и Ференштейн [11], Ма-залов, Перрин, Домбровский [22], Мазалов, Кочетов, Перрин, Панова [68],
Porosinski [27], Сакагучи [52, 46], Szajowski [55], Neumann, Porosinski и Szajowski [26]. В 1 мы решаем игровую задачу о продаже недвижимости с неизвестными наблюдениями с двумя игроками, причём цель игрока - выбрать предложение большее, чем у противника.
В реальной жизни продавец практически всегда вынужден нести расходы, например, на поддержание товарного вида своих товаров или на рекламу. В игровых моделях мы можем ввести такие расходы в виде некоторой платы, которую игрок вынужден вносить за каждое наблюдение. В 2 рассматривается именно такая модификация задачи из 1.
Случай с полной информацией для одного из игроков, то есть такая ситуация, когда одному из игроков известны значения предложений, рассмотрен в 3. Как и следовало ожидать, обладание большей, чем у противника информацией приносит больший выигрыш.
И, наконец, в 4 главы 3 рассматривается игровая постановка задачи о продаже недвижимости как игры на правило остановки с допуском.
Задача о продаже недвижимости с доходом в единицу времени
В экономической литературе эта задача также известна как задача поиска работы и была рассмотрена Макнамара и Коллинзом в работах [7, 24], а также Сакагучи в [51].
Впервые задача о продаже недвижимости была рассмотрена как часть более общих инвестиционных проектов, характеризуемых большой степенью неопределённости в будущих доходах в работах Фишера [15] и Кауфмана [17]. Также эта задача рассматривалась Олбрайтом [1], Олб-райтом и Дерманом [3] и Сакагучи [40, 41]. Саарио продолжил исследования в этой области в работе [33], указав некоторые свойства последовательностей {vn k} и {dnjk}- В частности было показано, что последовательность {dU;k} доминируется сак, а {г } —) рЕ(Х)/(1 — а) при к — со. Задача о продаже недвижимости также рассматривалась как специальный случай задачи более широкого класса - проблемы размещения ресурсов- в работах Райтера [30] и Сакагучи [42, 41, 43]. Кауфман [17] использовал модели такого типа с их двумерными расширениями для оптимизации инвестиционных решений с налоговыми ожиданиями. Экспериментальные данные показали, что оптимальные правила принятия решений сравнимы с человеческим поведением. В дальнейшем Саарио [34, 12, 36], Саарио и Сакагучи [37, 38] продолжили исследования основной постановки задачи в различных случаях, таких как: 1) предложения о продаже поступают дискретно, 2) предложения о продаже поступают в соответствии с пуассонов-ским процессом, 3) предложения о продаже поступают в соответствии с пуассонов-ским процессом, но игрок имеет т возможностей задержать любое предложение для рассмотрения его в будущем. Здесь же рассмотрена игра двух игроков, каждый из которых хочет максимизировать ожидаемый выигрыш, который равен максимальному из полученных наблюдений. Игроки I и II имеют тп\ и т,2 возможностей выбрать предложения, но приоритет отдаётся игроку I. В 1997 году Брюсе и Фергюсон [6] рассмотрели случай, когда предложения о продаже имеют векторный вид, причём за возможность наблюдать каждый такой вектор игрок должен заплатить цену с 0. Наконец, Мазалов и Саарио [21] предложили такую постановку задачи, в которой игрок должен максимизировать свой доход в единицу времени, устанавливая в начале игры цену за каждый из домов в отдельности.
В главе 1 данной работы рассматривается неигровая постановка задачи о продаже недвижимости, то есть такая постановка, когда присутствует только один игрок, желающий максимизировать свой выигрыш. В 1 приводится постановка задачи в случае, когда игрок имеет га идентичных неделимых объектов для продажи и игра продолжается п периодов, в каждый из которых игроку поступает предложение о продаже одного из объектов, а игрок решает, принять ему текущее наблюдение или перейти к следующему наблюдению, устанавливая в начале каждого периода пороговую цену за свой дом. Задача игрока в этом случае -максимизировать сумму полученных предложений.
В 2 условия задачи меняются, и игрок должен уже максимизировать доход в единицу времени, устанавливая в начале игры отдельную цену за каждый из домов. Оказывается, что все эти цены будут одинаковы, и с ростом количества домов стремятся к 0.5, а ожидаемый доход в единицу времени стремится к 0.25.
Интуитивно ясно, что игрок в этом случае ведёт себя "недостаточно оптимально", так как его стратегия не меняется в зависимости от того, сколько времени он провёл на рынке, хотя его выигрыш убывает со временем. С учётом этого в 3 мы исследуем эту задачу в случае, когда игрок может менять цены на свои дома в зависимости от времени, а не от количества непроданных объектов. Для решения этой задачи мы используем метод динамического программирования, исследуя уравнение Беллмана. Результаты показывают, что наше предположение о том, что такой подход к назначению цены себя оправдывает и игрок получает больший выигрыш по сравнению с полученным в 2.
Задача о продаже недвижимости может быть рассмотрена также в условиях, когда борьбу за одно предложение ведут одновременно несколько продавцов. В этом случае значение максимизирующего функционала для каждого игрока зависит не только от случая и выбранной им стратегии, но и от поведения других игроков, то есть, возникает игровая ситуация. В главе 2 рассматривается конфликтная ситуация, когда продавец, желая привлечь покупателя, старается установить цену за свой дом меньше, чем у противника, но всё же так, чтобы не понести слишком больших убытков. Обычно в задачах такого типа один из игроков имеет постоянный на протяжении игры приоритет в наблюдении, то есть рассматривает поступающие предложения первым; мы же предлагаем выбирать приоритетного игрока случайным образом. Такая модель более приближена к реальному человеческому поведению.
Классическая задача предполагает, что игроку известны значения поступающих наблюдений, но это предположение может быть подвергнуто критике в том смысле, что в реальной жизни продавец не всегда знает, сколько готов заплатить тот или иной покупатель за предложенный ему объект. В главе 3 конструируется такая модель продажи недвижимости, в которой игрок информируется только о том, больше или меньше поступившее предложение о продаже установленной им цены. Задачи подобного типа, также известные как задачи с неполной информацией в различное время рассматривали Эннс и Ференштейн [11], Ма-залов, Перрин, Домбровский [22], Мазалов, Кочетов, Перрин, Панова [68], Porosinski [27], Сакагучи [52, 46], Szajowski [55], Neumann, Porosinski и Szajowski [26]. В 1 мы решаем игровую задачу о продаже недвижимости с неизвестными наблюдениями с двумя игроками, причём цель игрока - выбрать предложение большее, чем у противника.
В реальной жизни продавец практически всегда вынужден нести расходы, например, на поддержание товарного вида своих товаров или на рекламу. В игровых моделях мы можем ввести такие расходы в виде некоторой платы, которую игрок вынужден вносить за каждое наблюдение. В 2 рассматривается именно такая модификация задачи из 1.
Случай с полной информацией для одного из игроков, то есть такая ситуация, когда одному из игроков известны значения предложений, рассмотрен в 3. Как и следовало ожидать, обладание большей, чем у противника информацией приносит больший выигрыш.
И, наконец, в 4 главы 3 рассматривается игровая постановка задачи о продаже недвижимости как игры на правило остановки с допуском.
Продажа одного дома двумя фирмами. Игровая задача Т
Вернёмся к классической постановке задачи о продаже недвижимости и для дальнейшего исследования введём в рассмотрение второго игрока. Так как игроки играют роль продавцов на рынке недвижимости, наличие нескольких игроков позволит нам рассмотреть механизм возникновения конкуренции, то есть изменения цены с целью увеличения ожидаемого выигрыша.
Определим игру ГІ следующим образом. В игре участвуют 2 игрока: игрок I и игрок II; каждый из них владеет одним домом, стоимость которого - неотрицательная величина R. Игра состоит из одного периода, в начале которого игроки I и II устанавливают цены каждый за свой дом (s и t соответственно). Далее возможны 2 варианта: - с вероятностью р игрок I получит предложение о продаже дома, величина которого - случайная независимая величина X с непрерывной функцией распределения F(x). Если X s, то игрок I продаст свой дом за цену s. Если предложение X окажется меньше s, то игрок I отвергнет его, после чего это предложение получит игрок II, и, если X , то он продаст свой дом за цену t, а если X t, то игрок II отвергнет это предложение; - с вероятностью (1 — р) игрок II получит предложение о продаже X первым, и, если X окажется не меньшим , то игрок II примет это предложение и продаст свой дом за цену . Если же X t, то игрок II отвергнет это предложение, и оно перейдёт к игроку I, который, в свою очередь, примет его при условии X s, либо отвергнет его, если X окажется меньше цены s. В обоих случаях игра заканчивается, и каждый из игроков получает выигрыш, равный сумме, вырученной от продажи дома, если она состоялась, и R - в противном случае. Задача каждого из игроков - найти оптимальную цену так, чтобы максимизировать ожидаемый выигрыш. Как и в главе I, для упрощения выкладок будем рассматривать случай равномерного распределения предложений F(x) = ж, ж Є [0,1]. Пусть Hi(s,t) - ожидаемый выигрыш игрока I при условии, что он использует стратегию s, а игрок II использует стратегию t. Аналогично определим H2(s,t) - ожидаемый выигрыш игрока II при тех же условиях. Проведём рассуждения за игрока Г. 1) Если s t, то - с вероятностью р игрок I получает предложение X первым. Тогда с вероятностью (1 — s) это предложение окажется не меньшим s и игрок I продаст свой дом за цену s. С вероятностью (s — t) предложение X будет отвергнуто игроком I, но принято игроком II - в этом случае игрок I получает R. И, с вероятностью s предложение будет отвергнуто обоими игроками, в результате чего игрок I получит Л; - с вероятностью (1 — р) игрок II получит предложение X первым. Тогда с вероятностью (1 — t) X окажется не меньшим t и игрок II примет это предложение, а игрок I закончит игру с выигрышем R. С вероятностью t предложение X будет отвергнуто игроком II, но так как t s, игрок I также отклонит это предложение и получит R. 2) Если s t, то - с вероятностью р игрок I получает предложение X первым. Тогда с вероятностью (1 — s) это предложение окажется не меньшим s и игрок I продаст свой дом за цену s. С вероятностью s игрок I отвернет предложение X и получит в качестве выигрыша R; - с вероятностью (1 — р) игрок II получит предложение X первым. Тогда с вероятностью (1—t) X окажется не меньшим t и игрок II примет это предложение, а игрок I закончит игру с выигрышем R. С вероятностью (t — s) предложение X будет отвергнуто игроком II, но принято игроком I, в результате чего игрок I выигрывает s. И, с вероятностью s предложение X будет отвергнуто обоими игроками, и игрок I получит R. Аналогичные рассуждения игрока II можно опустить. Пользуясь вышесказанным, получим функции выигрыша игроков I и II: Анализ выражений (1.1) и (1.2) показывает, что, возможно, будет иметь смысл объявлять цену, меньшую, чем у противника, в надежде привлечь дополнительных покупателей. Замечание 1.1. Следует также обратить внимание на тот факт, что функции выигрыша игроков (1.1 - 1.2) симметричны относительно замены р на р — 1—р. Таким образом, результаты, полученные для одного из игроков, могут быть распространены на другого игрока заменой р на 1 — р. Задача поиска оптимальных стратегий разбивается на 3 подзадачи: (1) Поиск оптимальных стратегий игроков в чистых стратегиях. (2) Поиск оптимальных стратегий игроков в стратегиях вида ХІ{х аі} + (1- а)1{х а2} где /{ } - индикатор множества А. (3) Поиск оптимальных стратегий игроков в классе непрерывных смешанных стратегий на интервале [а, Ь].
Игровая задача Г Случай нескольких домов
В предыдущем параграфе мы полностью исследовали задачу о продаже одного дома за один шаг. В этом параграфе мы найдём решение аналогичной задачи, но в случае N шагов.
Определим игру TJY следующим образом. Игроки I и II владеют каждый одним домом. Игра состоит из N периодов. Каждый из игроков в начале каждого периода п = 1, 2,..., N устанавливает цену своего дома (s для игрока I и t для игрока II), после чего с вероятностью р к игроку I поступает предложение Хп. Если значение Хп больше или равно значению s, то игрок I принимает это предложение, продает свой дом за цену s, и игра переходит к следующему периоду. Если же значение Хп меньше цены s, то предложение переходит к игроку П. Игрок II, в свою очередь, принимает это предложение, если оно не меньше его цены t, то есть продает свой дом за цену t, и отвергает его, если оно меньше t. В обоих случаях игра переходит к следующему периоду.
Аналогично, с вероятностью (1-р) игрок II первым получает предложение Хп, и если оно не меньше значения t, то он принимает его, продает свой дом за цену t, и игра переходит к следующему периоду. Если же значение Хп меньше t, то игрок II отвергает предложение, и оно переходит к игроку I. В этом случае игрок I примет предложение ХП1 если оно не меньше s, и продаст свой дом за цену s, и отвергнет его, если предложение меньше s. В обоих случаях игра переходит к следующему периоду.
Решения о принятии или непринятии предложения делаются игроками немедленно после получения предложения. Возврат к ранее отвергнутым предложениям не допускается.
После прошествия N периодов игра заканчивается и, если игрок не успел реализовать свой дом, то он получает за него заранее установленную цену R.
Задача каждого из игроков - найти оптимальные значения цены таким образом, чтобы максимизировать ожидаемый выигрыш, равный сумме всех продаж плюс стоимость всех непроданных объектов. В данном случае это будет либо R, либо значение цены продажи. Пусть Hn i(s,t) - выигрыш игрока I при условии, что у него 1 дом, и он устанавливает цену s; у игрока II - 1 дом, и он устанавливает цену t; и до конца игры осталось п шагов.
Соответственно, Hn (s,t) - выигрыш игрока II при условии, что у него 1 дом, и он устанавливает цену t; у игрока 1-1 дом, и он устанавливает цену s; и до конца игры осталось п шагов. Найдем Hnji(s,t) - выигрыш на шаге п, рассуждая за игрока I: 1) если s t, то а) с вероятностью р игрок I получает предложение Хп первым. Тогда с вероятностью (1-s) оно окажется не меньшим, чем s, и игрок I продаст свой дом за цену s, после чего игра для него закончится с выигрышем s. А с вероятностью (s) он отвергнет предложение, но его его при мет игрок II и игрок I получит выигрыш K _v И, с вероятностью t, предложение будет меньше t (и, соответственно s) и будет отвергнуто обоими игроками, после чего игра перейдет в состояние Тг _1 с выигры шем Hn-iti(s,t) для игрока I. б) с вероятностью (1-р) игрок II получает предложение Хп первым. Тогда с вероятностью (І) оно окажется не меньшим, чем t, и игрок II продаст свой дом, после чего игра для него закончится, а игрок I полу чит выигрыш К\_х. А с вероятностью t предложение окажется меньше, чем t (и, соответственно s), и будет отвергнуто обоими игроками, пос ле чего игра перейдет в состояние Гп _і с выигрышем Hn-iti(s,t) для игрока I. 2) если s t, то а) с вероятностью р игрок I получает предложение Хп первым. Тогда с вероятностью (1-s) оно окажется не меньшим, чем s, и игрок I продаст свой дом за цену s, после чего игра для него закончится с выигрышем s. А с вероятностью s предложение будет меньше, чем s (и, соответственно t) и будет отвергнуто обоими игроками, после чего игра перейдет в состояние Гп _і с выигрышем iJn_i;i(s,t) для игрока I. б) с вероятностью (1-р) игрок II получает предложение Хп первым. Тогда с вероятностью (І) оно окажется не меньшим, чем t, и игрок II продаст свой дом, после чего игра для него закончится, а игра игрок I получит выигрыш Kn-i- А с вероятностью (t-s) предложение окажется меньше, чем t, но больше, чем s и игрок I примет его и закончит игру с выигрышем s. И, с вероятностью s предложение Хп окажется меньше, чем s (и, соответственно t), и будет отвергнуто обоими игроками, после чего игра перейдет в состояние Гп _і с выигрышем #„_i,i(s, t) для игрока I. Аналогичные рассуждения можно провести за игрока II. Далее для упрощения записи будем полагать Кп = К\ - ожидаемый выигрыш игрока при продаже одного дома в неигровой задаче. Этот выигрыш был найден в параграфе 1 Главы 1. Пользуясь вышесказанным, мы получаем функции выигрыша игроков I и И: Замечание 2.1. Нетрудно заметить, что функции выигрыша игроков симметричны относительно замены р = 1—р} что позволяет нам распро странить все результаты, полученные для одного из игроков, на другого, заменив в формулах р па р и Япд на Яп 2 При поиске оптимальных стратегий игроков мы будем предполагать, что игрок I относится к игроку II "доброжелательно", то есть, если игрок I имеет несколько оптимальных стратегий, то он выберет ту из них, которая позволяет игроку II получить больший выигрыш, (см. параграф 1 Главы 2)
Случай с полной информацией для одного из игроков
В завершение этой главы исследуем случай, когда игроки имеют не один, а несколько домов.
Определим игру Г]у следующим образом. Игроки I и II владеют m и к одинаковыми домами соответственно. Игра состоит из N периодов. Каждый из игроков в начале каждого периода п — 1,2, ...,iV устанавливает цену своего дома (s для игрока I и t для игрока II), после чего с вероятностью р к игроку I поступает предложение Хп. Если значение Хп больше или равно значению s, то игрок I принимает это предложение, продает свой дом за цену s, и игра переходит к следующему периоду. Если же значение Хп меньше цены s, то предложение переходит к игроку П. Игрок II, в свою очередь, принимает это предложение, если оно не меньше его цены t, то есть продает свой дом за цену t, и отвергает его, если оно меньше t. В обоих случаях игра переходит к следующему периоду.
Аналогично, с вероятностью (1-р) игрок II первым получает предложение Хп, и если оно не меньше значения t, то он принимает его, продает свой дом за цену t, и игра переходит к следующему периоду. Если же значение Хп меньше t, то игрок II отвергает предложение, и оно переходит к игроку I. В этом случае игрок I примет предложение Хп, если оно не меньше s, и продаст свой дом за цену s, и отвергнет его, если предложение меньше s. В обоих случаях игра переходит к следующему периоду.
Решения о принятии или непринятии предложения делаются игроками немедленно после получения предложения. Возврат к ранее отвергнутым предложениям не допускается. После прошествия N периодов игра заканчивается и, если игрок не успел реализовать все свои дома, то он получает за каждый из них заранее установленную цену R. Задача каждого из игроков - найти оптимальные значения цены таким образом, чтобы максимизировать ожидаемый выигрыш, равный сумме всех продаж плюс стоимость всех непроданных объектов. Пусть H i (s, t) - выигрыш игрока I при условии, что у него m домов, и он устанавливает цену s; у игрока II - к домов, и он устанавливает цену t; и до конца игры осталось п шагов. Соответственно, Н2 (s, t) - выигрыш игрока II при условии, что у него к домов, и он устанавливает цену t; у игрока I - m домов, и он устанавливает цену s; и до конца игры осталось п шагов. Найдем Н{ (5 Ї) " выигрыш на шаге п, рассуждая за игрока I: 1) если s t, то а) с вероятностью р игрок I получает предложение Хп первым. Тог да с вероятностью (1-s) оно окажется не меньшим, чем s, и игрок I продаст свой дом за цену s, после чего игра перейдет к следующему периоду с выигрышем для игрока І Н_Гіі (s,t). А с вероятностью (s) он отвергнет предложение, но его его примет игрок II и игра перейдет к следующему периоду с выигрышем для игрока I Н!- (s,t). И, с веро ятностью t, предложение будет меньше t (и, соответственно s) и будет отвергнуто обоими игроками, после чего игра перейдет в состояние Т!_\ с выигрышем Hj_n(s,t) для игрока I. б) с вероятностью (1-р) игрок II получает предложение Хп первым. Тогда с вероятностью (І) оно окажется не меньшим, чем t, и игрок II продаст свой дом, после чего игра перейдет к следующему периоду с выигрышем для игрока I Н±{ _ (s,t). А с вероятностью t предложение окажется меньше, чем t (и, соответственно s), и будет отвергнуто обо ими игроками, после чего игра перейдет в состояние T li с выигрышем Hlii(s,t) для игрока I. 2) если s t, то а) с вероятностью р игрок I получает предложение Хп первым. Тогда с вероятностью (1-s) оно окажется не меньшим, чем s, и игрок I продаст свой дом за цену s, после чего игра перейдет к следующему периоду с выигрышем для игрока I Н \_{ (s,t). А с вероятностью s предложение будет меньше, чем s (и, соответственно t) и будет отвергнуто обои ми игроками, после чего игра перейдет в состояние Гп _і с выигрышем Hliti(s,t) для игрока I. б) с вероятностью (1-р) игрок II получает предложение Хп первым. Тогда с вероятностью (І) оно окажется не меньшим, чем t, и игрок II продаст свой дом, после чего игра переидет к следующему периоду с выигрышем для игрока I Н1{ (s,t). А с вероятностью (t-s) предложение окажется меньше, чем t, но больше, чем s и игрок I примет его и игра перейдет к следующему периоду с выигрышем для игрока I Н -\\ {s,t). выигрышем s. И, с вероятностью s предложение Хп окажется меньше, чем s (и, соответственно t), и будет отвергнуто обоими игроками, после чего игра перейдет в состояние Г1г с выигрышем HJ_n(s,t) для игрока I.
