Задача о продаже недвижимости: Теоретико-игровой подход тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Фалько, Игорь Антонович

• Фалько, Игорь Антонович
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Фалько, Игорь Антонович

Введение.

Глава I.

Задача о продаже недвижимости.

§1. Задача о продаже недвижимости на конечном интервале времени.

§2. Задача о продаже недвижимости с доходом в единицу времени.

§3. Продажа недвижимости с переменными порогами.

Глава II.

Задача о продаже недвижимости в теоретико-игровой постановке.

§1. Продажа одного дома двумя фирмами. Игровая задача Г}'1.

§2. Игровая задача ГСлучай произвольного N.

§3. Игровая задача Случай нескольких домов.

Глава III.

Задача о продаже недвижимости в условиях неполной информации.

§1. Случай неизвестных значений наблюдений.

§2. Случай с ненулевой платой.

§3. Случай с полной информацией для одного из игроков.

§4. Игра на правило остановки с допуском.

Введение диссертации (часть автореферата) на тему «Задача о продаже недвижимости: Теоретико-игровой подход»

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

Задача на правило остановки возникла после появления работ американского статистика А.Вальда [60] по статистическому последовательному анализу (1947). Предложенная им процедура была оригинальной и практически важной.

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

Классическая задача о секретаре имеет много общего с задачей о продаже недвижимости, поэтому приведём постановку задачи о секретаре в виде, предложенном Фергюсоном в [13]:

Задача - оптимально выбрать секретаря из фиксированного множества последовательно представляемых претендентов при условиях:

1. Вакантна одна должность секретаря.

2. Известно п - число претендентов на эту должность.

3. Претенденты проходят собеседование последовательно в случайном порядке, то есть все п! перестановок равновероятны.

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

5. Отвергнутый претендент не может быть возвращён позднее.

6. Вы очень привередливы и будете довольны только лучшим. Это означает, что ваш выигрыш 1, если вы выбрали лучшего из п претендентов, и 0 - в противном случае.

Решение этой задачи принадлежит классу правил остановки таких, что для некоторого целого г > 1 необходимо отвергнуть первых г — 1 претендентов, а затем принять такого из следующих претендентов, ранг которого окажется лучшим среди всех, опрошенных ранее. Вероятность фп(г) выбрать лучшего из претендентов есть 1 /п для г = 1, а для г > 1 г — 1 п 1 Фп(г) = (—)Ет п j=r j - 1

При п —^ оо максимум этой вероятности достигается когда г/п —> 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].

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

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

Задача может быть сформулирована и решена в соответствии с принципами стохастического динамического программирования. В дискретном случае оптимальное правило принятия решения может быть найдено из рекуррентного соотношения ущк = pE{ma.x.[X+avn-iík-i,avn-lík\}+(l-p)avn^lík = pTF(dnik)+aVn-iik, где а - дисконтирующий фактор и р - вероятность того, что наблюдение может быть получено на текущем шаге, а функция Тр, определённая для каждой функции распределения F с конечным математическим ожиданием, имеет вид roo roo

Tp(s) = / (х — s)dF(x) = / тах(х, s)dF(x) — s.

Js J — 00 где vn k ~ оптимальное текущее значение процесса при условии, что осталось п периодов до конца процесса и игрок имеет к домов, с начальными условиями vnfi = О, v0¿ = Sk (S > 0) и dn¿ = a(vn„ljk - vn-ljk-i) определяет критерий принятия текущего предложения х = X.

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

-= ATF(Vk(t) - X4-i(í)) - 0Vk(t), где к - количество домов у игрока и t - оставшееся время. Начальные условия в этом уравнении Vo(t) = 0 и Vk(0) = Sk (S > 0). Также e~eAt, в > 0 определяется как дисконтирующий фактор и Л - параметр, определяющий интенсивность процесса поступления предложений.

Эти рекуррентные уравнения дают нам в качестве решений пороги принятия решений, пользуясь которыми игрок может определить, принимать ему текущее предложение или отвергать его. Не всегда представляется возможным найти аналитические решения этих уравнений; даже получить эти уравнения в явном виде можно только для некоторых простых семейств функций распределений для малых значений п. Смысл функции Тр, которая также может быть получена в явном виде только в специальных случаях - определить поведение последовательности {vn¡k} или множества функций {Vk(t)}.

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

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

4 = Р>(<4) - 7>(4)], к > О,

1 — а где (¿о = +оо. Если объекты поступают в соответствии с однородным пуассоновским процессом, то коэффициент ар/( 1 — а) заменяется на е.

В экономической литературе эта задача также известна как задача поиска работы и была рассмотрена Макнамара и Коллинзом в работах [7, 24], а также Сакагучи в [51].

Впервые задача о продаже недвижимости была рассмотрена как часть более общих инвестиционных проектов, характеризуемых большой степенью неопределённости в будущих доходах в работах Фишера [15] и Кауфмана [17]. Также эта задача рассматривалась Олбрайтом [1], Олб-райтом и Дерманом [3] и Сакагучи [40, 41]. Саарио продолжил исследования в этой области в работе [33], указав некоторые свойства последовательностей {уп>к} и {¿п>к}. В частности было показано, что последовательность доминируется сак, а {г^} —» рЕ(Х)/( 1 — а) при к —>- оо.

Задача о продаже недвижимости также рассматривалась как специальный случай задачи более широкого класса - проблемы размещения ресурсов - в работах Райтера [30] и Сакагучи [42, 41, 43]. Кауфман [17] использовал модели такого типа с их двумерными расширениями для оптимизации инвестиционных решений с налоговыми ожиданиями. Экспериментальные данные показали, что оптимальные правила принятия решений сравнимы с человеческим поведением.

В дальнейшем Саарио [34, 12, 36], Саарио и Сакагучи [37, 38] продолжили исследования основной постановки задачи в различных случаях, таких как:

1) предложения о продаже поступают дискретно,

2) предложения о продаже поступают в соответствии с пуассонов-ским процессом,

3) предложения о продаже поступают в соответствии с пуассонов-ским процессом, но игрок имеет т возможностей задержать любое предложение для рассмотрения его в будущем. Здесь же рассмотрена игра двух игроков, каждый из которых хочет максимизировать ожидаемый выигрыш, который равен максимальному из полученных наблюдений. Игроки I и II имеют гп\ и тч возможностей выбрать предложения, но приоритет отдаётся игроку 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 рассматривается игровая постановка задачи о продаже недвижимости как игры на правило остановки с допуском.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Фалько, Игорь Антонович

ЗАКЛЮЧЕНИЕ

Подытожим результаты, полученные в данном исследовании.

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

В главе 1 рассматривается неигровой вариант задачи о продаже недвижимости.

В §1 рассматривается классическая постановка задачи.

Игрок имеет п неделимых одинаковых объектов (в дальнейшем мы будем называть их домами), стоимость каждого из которых - неотрицательная величина R. В течении N периодов игрок получает предложения о продаже домов - в течении одного периода поступает ровно одно предложение; каждое предложение имеет свою цену X - сумма денег у покупателя. Предполагается, что все значения предложений - независимые одинаково распределённые случайные величины с непрерывной функцией распределения F(x). Перед тем, как получить очередное предложение игрок устанавливает цену продажи s, и, если поступившее предложение X не меньше этой цены, то игрок продаёт один из домов за цену s. Если поступившее предложение X оказывается меньше значения s, то предложение отвергается, и в дальнейшем не рассматривается.

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

Обозначая через К™ ожидаемый доход игрока за т шагов до конца игры при условии, что у него п домов и он использует оптимальную стратегию s*, имеем:

Утверждение 1.1

В ситуации с п домами и т периодами до конца игры оптимальной стратегией будет цена

1 Кп — кп1 -.

ожидаемый выигрыш игрока есть

К! = КшЛ + М2, где Щ = пЯ.

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

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

В §2 рассматривается задача о продаже недвижимости с доходом в единицу времени.

Приведём постановку задачи. Игрок использует стратегии из класса пороговых стратегий вида (йь., вп), где вг - цена за г-й дом. Это означает, что игрок, начиная с первого шага устанавливает цену 5х и держит её до тех пор, пока не поступит предложение X, не меньшее В этом случае он продаёт один дом за цену вх и устанавливает новую цену

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

Функция выигрыша в этой задаче имеет вид:

*•('!,■ ■■,"«)= £ (,!• •• • I'"! ПР(Ь = ь) =

»!=!,.,¿„=1 +. + гп)

= (*! +. + *„) Е 7-Т-тттп^га-«)

»1=1,.,г„=1 (п + • • • + гп) ¿=1 Для данной постановкии задачи справедлива следующая

Теорема 2.2 Для любого п

Si = S2 = • • • = sn

п dn-H-bilzfl]

(n - 1)! dsnl

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

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

В §3 рассматривается такая постановка задачи, в которой игрок изменяет свою стратегию, назначая цену не за каждый дом в отдельности, а в зависимости от того, сколько времени осталось до конца игры. Другими словами, стратегия игрока выглядит следующим образом: на первом шаге игрок устанавливает цену si, на втором - s2, и так далее до шага га; начиная с шага (га + 1) игрок устанавливает постоянный порог s, который и использует до конца игры. Игрок продаёт один из своих домов в том случае, если на шаге t он получит предложение о продаже X, не меньшее st (если t < га), либо не меньшее s (если t > га). Игра продолжается до тех пор, пока игрок не продаст все дома. Цель игрока прежняя - максимизировать доход в единицу времени.

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

Теорема 3.2 1) Оптимальная стратегия игрока при продаже п домов за га шагов на шаге i есть вектор (s*, Sj+1,., sm), где

ТТП—l T/n—1 I т>п— 1

* ui+1 vi+1 г ni+1

i о Г>п— 1

и уравнения для нахождения Sj (j = i + 1,., m) имеют вид:

Е (Ai(Bfri - в+1) + - (1 - г^в^й1)) = о,

2) При использовании такой оптимальной стратегии игрока ожидает выигрыш:

Ц? = 1 + (1 - + = 0.

Здесь \к-, ^ находятся из системы:

Хк3 = Х^з^ + - ^--1) + -

/4 - 3-1 + $-¡{1 - 83 - 1);

3 г13 и' г+1 — — 1>

к = 1,., п — 1, ] = г + 1,. га,

в{ = зкВ3к+1 + (1 - зк)В{-1; -Вш+1 = =

га' к /г — 1

= + (1 - + У1+1 = 0; Ук = 0.

при этом ] — 1,., п — 1; к = г + 1,., га

Глава 2 рассматривает задачу о продаже недвижимости в игровой постановке.

Приведём постановку задачи в общем виде.

Определим игру Г^ следующим образом. Игроки I и II владеют т и к одинаковыми домами соответственно. Игра состоит из N периодов. Каждый из игроков в начале каждого периода п — 1,2,., N устанавливает цену своего дома (э для игрока I и 1 для игрока II), после чего с вероятностью р к игроку I поступает предложение Хп. Если значение Хп больше или равно значению в, то игрок I принимает это предложение, продает свой дом за цену э, и игра переходит к следующему периоду. Если же значение Хп меньше цены э, то предложение переходит к игроку И. Игрок II, в свою очередь, принимает это предложение, если оно не меньше его цены то есть продает свой дом за цену Ь, и отвергает его, если оно меньше В обоих случаях игра переходит к следующему периоду.

Аналогично, с вероятностью (1-р) игрок II первым получает предложение Хп, и если оно не меньше значения то он принимает его,

продает свой дом за цену 1;, и игра переходит к следующему периоду. Если же значение Хп меньше Ь, то игрок II отвергает предложение, и оно переходит к игроку I. В этом случае игрок I примет предложение Хп, если оно не меньше э, и продаст свой дом за цену в, и отвергнет его, если предложение меньше е. В обоих случаях игра переходит к следующему периоду.

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

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

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

В §1 рассматривается игра Г{'\ Оказывается, что в данной игре в зависимости от значения р существует множество стратегий. Перечислим их все.

1) В классе чистых стратегий стратегии игроков и соответствующие им выигрыши определяются Теоремой 1.1

Теорема 1.1. (г) Если р удовлетворяет неравенству

р3 + Зр2 + 8р - 4 > О,

то в игре Г*'1 в классе чистых стратегий оптимальные стратегии игроков I и II есть:

* 1 + Я 2-р + 2Я + рЯ

я = —^—, £ ------—

с выигрышами

) = Я + |(1 - Я)2, Н2(з\ £*) = Я + - Д)

(гг) Также, если р удовлетворяет неравенству

р3 + Зр2 + 8р - 4 > 0, где р— 1 - р,

то в игре Г^'1 в классе чистых стратегий оптимальные стратегии игроков I и II есть:

„ 1+р + ЗД-рД „ 1 + Д б =-:-, ъ — —-— соответственно

с выигрышами

Я1(а*,о = д + (1|/)2(1-Д)2, Я2(в*,0 = Д + -(1-Д)2.

2) В классе стратегий вида

Г*(в) = а/{5>а1} + (1 - а)/{5>а2},

стратегии игроков и соответствующие им выигрыши определяются Теоремой 1.2

Теорема 1.2.(г) Если р удовлетворяет системе неравенств

р3 + Зр2 + 8р - 4 > О,

<н2(г\е)ш е [о,1],

то оптимальной стратегией игрока I является стратегия

= а/{5>а1} + (1 - а)/{5>а2}, г<?е - индикатор множества А.

д + ^м1-й) 1 + Д р(1 + ур) - 2(1 - ур)

а1 =-2-• = — а =--•

Оптимальной стратегией игрока II является чистая стратегия

Д+(1-Д)^-р

1 ' 1 — р

Выигрыши

Н^*,?) = Д + |(1- Д)2 г,,™- (1 - ур)(Д + р - рД + рЯ2 + 2 Дур)

соответственно.

(гг) Если р удовлетворяет системе неравенств

р3 + Зр2 + 8р - 4 > О,

Н^в*) < Я^С*^ б [0,1], то оптимальной стратегией игрока I является чистая стратегия

а оптимальной стратегией игрока II является стратегия где

Д+Ур(1-Д) 1 + Д р(1 + V?) - 2(1 - у/$) о 1 =---, о 2 = —-—, р — —

Выигрыши

Р{3\/р — 1)

(1 - у?)(Д + р - рД + рД2 + 2Вл/р) 3^-1

Я2(Я*,Г) = Д+|(1-Д)'

соответственно.

3) В классе непрерывных стратегий стратегии игроков и соответствующие им выигрыши определяются Теоремой 1.3

Теорема 1.3.В классе непрерывных стратегий оптимальные стратегии игроков существуют только при р — при этом они совпадают и имеют следующий вид:

Функция распределения стратегии игрока I:

0 , при в Е [0,а].

8(5 - Д)2 - (1 - Д)2

; при в £ [а, Ь], при 8 Е [6, 1].

Функция распределения стратегии игрока II:

О , при £ £ [О, а],

, при Ь Е [а, Ь], ; при £ Е [Ь, 1].

8(*- Д)2-(1- Д); 4(* - Л)2

а — К-\—:——, о =

2л/2 ' " 2

Выигрыши игроков равны и Н\(]?*, й*) = Я2(.Р*, С?*) = Д +

9. 64 1 - Г 1 1 1

\/2-1. 6—2\/2 1 1 12 1

1 8 13 1 —1- 2' —1- 1' -1-^

1 \/2—1 8 б-2л/2

Рис.4 Выигрыши игроков для различных равновесий при р = 1/2.

Замечание 1.2 Заметим, что множество равновесий игроков в зависимости от р содержит от 1 до 5 равновесий.

Для примера рассмотрим случай р = 1/2, Л = 0. Множество равновесий игроков содержит 5 равновесий с различными выигрышами для игроков. Они представлены на рис.4- Видно, что равновесие, найденное в Теореме 1.3 (точка 3), доминируется равновесиями из Теоремы 1.2 (точки 2 и 2'), которые, в свою очередь, доминируются равновесиями из Теоремы 1.1 (точки 1 и 1'). Тем не менее, мы имеем две недоминируемые чистые стратегии (точки 1 и V).

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

В §2 находится решение игры Г^1. Справедливы следующие теоремы:

„ 1 + K ^ 1 -p + ps* + H2 Л p+(l-p)t* + HX

s = -, t = ---, s = ---.

то в игре Гд^1 оптимальной стратегией игрока I является s*, а оптимальной стратегией игрока II является t*. При этом выигрыши равны

то в игре Г^1 оптимальной стратегией игрока I является s*, а оптимальной стратегией игрока II является t*. При этом выигрыши равны

Наконец, в §3 предлагается алгоритм нахождения оптимальных стратегий и соответствующих выигрышей в игре

Теорема 3.1 В игре существуют следующие оптимальные

стратегии игроков I и II соответственно:

1 ттт—1,к тттп,к— 1 * 1 — Ппц + Лп1 1

1 I * ттТП,к—\ ттТП.к

,* 1-Р+Р5 Яп-1,2 + #п-1,2 * - 2 если б* и удовлетворяют системе неравенств (3.7), где

Гт—1,к ттт,к р-\- [1 — р)1 — г1

1 ттт,к-1. гтт—1,к 7 1 -"п-1,2 + Пп-\,2

тттп,к—\. ттш—\,к

1 Лп-1,2 + пп-1,2

если в* и удовлетворяют системе неравенств (3.7), где

л ттгп—1,к. ттт,к—1

1 — пп-1,1 ' лп-1,1 ч = ----—•

Выигрыш игрока I составляет Н™1 (в*, а выигрыш игрока II составляет

Замечание 3.1 Теорема 3.1 даёт нам алгоритм для численного решения задачи:

АО: Задать значения Л, р, ш, п, к. Для этих значений вычислить

Н™\ = тЯ, Щк = кЯ, Н™? = К™, Н^ = К1

/II т^т ту-т-1\2

К = щ:^ + П"1 К = тя.

А1: Начиная с т = 1, п = 1, к = 1 найти в*, 5, I со-

гласно случаю (г) Теоремы 3.1. Если система (3.7) не выполняется, то перейти к шагу А2 иначе к шагу АЗ.

А2: Для текущих т, п, к найти 5*, £ согласно случаю

(п) Теоремы 3.1.

АЗ: Повторить шаг А1 для всех га, п, к.

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

Приведём постановку задачи из §1. Пусть Х\, Х2,., Хдг, N £ 14, - последовательность независимых одинаково распределенных случайных величин с известным распределением, определенным на вероятностном пространстве (П, Эти случайные наблюдения предоставляются последовательно одна за другой каждому из игроков, но точные значения переменных им неизвестны. Игроки определяют свои пороги чувствительности и они лишь узнают, больше или меньше наблюдаемая величина, чем порог, выбранный ими. Будем считать, что Игрок 1 имеет приоритет в принятии наблюдения. После того, как Игрок 1 получил случайную величину Хп, он должен принять или отвергнуть ее. Если он отвергает это наблюдение, то ход переходит к Игроку 2.

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

Пусть 8 - множество моментов остановок Хп относительно последовательности сг-алгебр где = а{Хг,Х2,.-., Хп}, п =

Так как значения наблюдений неизвестны, будем исследовать задачу в классе стратегий Яо = {т 6 8 : т = ш£{1 < п < N : Хп > ж}, ж £ д}. Предположим, что игроки выбирают стратегии из множества 8о, а приоритет Игрока 1 учтем в функции выигрыша.

Пусть Игроки 1 и 2 выбрали х Е Д и у Е Д соответственно. Рассматривая, как и ранее, случай равномерного распределения на интервале [0,1], мы находим, что функция выигрыша Игрока 1 при х < у имеет вид:

+ Е Е [(1 - у)2 - (1 - ж)(1 - у)

5 = 1 £=5 + 1

(1 - х)—-Г--{у-х)

(1 - хм1) (у*-1 - хи1)

и при х > у:

¡м{х,у) = Е - У8\х - +

в = 1 ¿=5 + 1

= N{1 - х)ум-1 - {хм - у») + I1 - - 2/) Г1 - УИ1

•{М- 1 )у

х — х у — у

1-х 1 — у

Таким образом, игра сводится к игре с нулевой суммой на единичном квадрате с функцией выигрыша (1.2-1.3). Эта функция непрерывна по обеим переменным. Это означает, что игра имеет решение в смешанных стратегиях.

Численное решение для фиксированного N дает равновесие в чистых стратегиях для обоих игроков.

Таблица 1

Решение игры с фиксированным N и приоритетом для Игрока 1

N * хы * Ун

2 1/3 0 1/3

3 0.5279 0.3854 0.3683

4 0.6446 0.5513 0.3663

5 0.7162 0.6474 0.3633

6 0.7642 0.7099 0.3608

7 0.7984 0.7537 0.3589

8 0.8240 0.7860 0.3573

9 0.8438 0.8109 0.3561

10 0.8597 0.8305 0.3551

12 0.8834 0.8598 0.3535

14 0.9002 0.8804 0.3524

16 0.9128 0.8958 0.3515

18 0.9226 0.9076 0.3509

20 0.9304 0.9170 0.3503

25 0.9444 0.9339 0.3493

100 0.9862 0.9837 0.3463

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

В §2 в дополнение к вышеуказанным условиям добавляется еще одно: игроки платят за каждое новое наблюдение величину с. Также положим, что N — оо.

Положим х = 1 — х и у = 1 — у, ив дальнейшем опустим значок (-) в обозначениях. При этих обозначениях выигрыш Игрока 1 есть:

н1(х,у) = \ осли*<» {27)

( —1 + у/х — с/х если х > у и выигрыш Игрока 2 имеет вид:

[ 1 + у/х — с(х + у)/ху если х > у

Теорема 2.1 В игре с функциями выигрыша (2.7)-(2.8) оптимальные стратегии игроков I и II находятся следующим образом:

1. При с > 2 равновесие достигается в чистых стратегиях х* У* — 0;

I?. Я/ж с* < с < 2 равновесие имеет вид: х* — 1 — ус/2, у* = 0;

3. При с < с* равновесие достигается в смешанных стратегиях вида и* = /{i-a},^* = f¿I{i-b} + (1 — /л)/|о}; находятся из системы:

f 2 $= а2-са-с

Ь2 — ас

с—2а3 ^ — Ь—2а3

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

В §3 мы рассматриваем эту же задачу в условиях неполной информации.

Полагая, что стратегия у Игрока 2 фиксирована, получим функцию выигрыша Игрока 1 следующего вида:

VN(y) = jQV VN^(y)dx + J*N-\l - 2xNl)dx+

í1 io 1 - vNl 1 + y-2yN\,

/ (2x—-----)ax =

JZN-1 1 — y 1 — y

= yVN-M + (z/v-1 -y)- ^(4-1 - yN) +

,1 -yNln 2 ч l + y-2yN\ + - --fq;-í1 ZN-1) (3.7)

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

1 - 1 - yW-1

+ ---гз^ = (3-8)

Если мы минимизируем функцию (3.7) по у, то сможем найти оптимальную стратегию у* Игрока 2 для любого N.

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

В §4 мы рассматриваем игру на правило остановки с допуском в условиях неполной информации.

Данная задача при N — 1 имеет тривиальное решение - всегда останавливаться. Для N = 2 оптимальный порог г ищется из уравнения

• г + — = 2г2 + б - 1,

левая часть которого - ожидаемый выигрыш при остановке на шаге 1, а правая - при остановке на шаге 2.

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

„ -1 + \/2б2-4б + 5

Список литературы диссертационного исследования кандидат физико-математических наук Фалько, Игорь Антонович, 2001 год

1. Albright S.C. Optimal sequential assignment with random arrival times. //Management Science, 1974, vol.21, p.60-67.

2. Albright S.C. A Bayesian approach to a generalized house selling problem. //Management Science, 1977, vol.21, p.432-440.

3. Albright S.C., Derman C. Asymptotic optimal policies for the stochastic sequential assignment problem. //Management Science, 1972, vol.19, 46-51.

4. Basawa I.V., Rao B.L.S.P. Statistical Inference for Stochastic Processes. - Academic Press, London, 1980.

5. Berger J.O. Statistical Desicion Theory: Foundations, Concepts and Methods. - Springer Verlag, New York, 1980.

6. Bruss F.Th., Ferguson Th.S. Multiple buying or selling with vector offers. //J.Appl. Prob., 1997, vol.34, p.959-973.

7. Collins E.J., McNamara J.M. The job-search problem with competition: An evolutionarily stable dynamic strategy. //Adv. Appl. Prob., 1993, vol.25, p.314-333.

8. David I., Yechiali U. Sequential assignment match processes with arrivals of candidates and offers. //Prob. Eng. Inf. Sei., 1986, vol.4, p413-430.

9. Derman C., Lieberman G.J., Ross S.M. A sequential stochastic assignment problem. //Management Sei., 1972, vol.18, p.349-355.

10. Enns E.G., Ferenstein E.Z. A competitive best-choice problem with Poisson arrivals. //J. Appl. Prob., 1990, vol.27, p.333-342.1. И.12.13.14.15.16.17.18.19.20.21.22.23.

11. Enns Е., Ferenstein Е. On a multi-person time-sequential game with priorités. //Sequential Analysis, 1987, vol.6, p.239-256.

12. Erkki P. Liski, Saario V. The feasible admission to the optimization of exploitation of tree stems. //Engineering Costs and Production Economics, 1986, vol.12, p.21-28.

13. Ferguson S.T. Who solved the secretary problem? //Statistical Science, 1989, vol.4, p.282-296.

14. Ferguson S.T. Optimal stopping problems.//(preprint)

15. Fisher J.L. A class of stochastic investment problems. //Operations Research, 1961, vol.9, p.53-65.

16. Karlin S. Stochastic models and optimal policy for selling an asset. //In Studies in Applied Probability and Management Science, 1962, Chap.9, p. 148-158. Stanford University Press, Stanford, California.

17. Kaufman G.M. Statistical decision and related techniques in oil and gas exploration. - Prenctice Hall, Englewood Cliffs, NJ, 1963.

18. Kaufman G.M. Sequential investment analysis under uncertainty. //J. Bus. University of Chicago, 1963, vol.36, p.39-64.1.onardz D. To Stop or not to Stop. - Wiley, New York, 1973.

19. Mazalov V.V., Falco I.A. House-Selling Problem in Game-Theoretic Way. //Тезисы докладов 3-й Международной конференции по исследованию операций (ORM2001), ВЦ РАН, Москва, 2001, стр. 7677.

20. Mazalov V.V., Saario V. House-selling problem with reward rate criterion, //в печати.

21. Mazalov V.V., Perrin N., Dombrovskii Y.A. Adaptive search and information updating in sequential selection. //American Naturalist, 1996, vol.148(1), p.123-136.

22. Martin J.J. Bayesian Decision Problems and Markov Chains. - Wiley, New York, 1967.272829

23. McNamara J.M., Collins E.J. The job-search problem as ail employer-candidat game. //J. Appl. Prob., 1990, vol.27, p.815-827.

24. Nakai T. An optimal selection problem for a sequence with a random number of applicants per period. //Operat. Res., 1986, vol.34, p.478-485.

25. Neumann P., Porosinski Z., Szajowski K. On two persons full-information best choice problem with imperfect information. //Game Thery and Appl. II, Nova Science Publishers, New York, 1996, p.47-55.

26. Porosinski Z. Full-information best choice problems with imperfect observation and a random number of observations. //Zastos. Matem., 1991, vol.21, p.179-192.

27. Ravindran K., Shah K.R., One and two player best choice problems with holding. //Math. Japonica, 1991, vol.36, p.1101-1114.

28. Righter R. Stochastically maximizing the number of successes in a sequential assignment problem. //J. Appl. Prob., 1990, vol.27, p.351-364.

29. Righter R.L. A resource allocation problem in a random environment. //Operations research, 1989, vol.37, p.329-338.

30. Riley J., Zeckhauser R. Optimal selling strategies, When to haggle, when to hold firm. //Q.J.Econ, 1983, vol.97, p.267-289.

31. Rose J.S. The secretary problem with a call option. //Opns. Res. Lett., 1984, vol.3, p.237-241.

32. Saario V. Limiting properties of the discounted house-selling problem. //European Journal of Operational Research, 1985, vol.20, p.206-210.

33. Saario V. Properties of a sequential stochastic allocation problem. //Proc. University of Vaasa, Research Papers 89, 1982.

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

35. Saario V. Some properties of the sequential Markovian allocation problem. //Engineering Costs and Production Economics, 1989, vol.17, p.175-182.

36. Saario V., Sakaguchi M. Some generalized house-selling problems. //Math. Japonica, 1990, vol.35(5), p.861-873.

37. Saario V., Sakaguchi M. Multistop best choice games related to the Poisson process. //Math. Japonica, 1992, vol.37(1), p.41-51.

38. Saario V. Some techiques and limiting properties of the house-selling problem. //ACTA UNIVERSITATIS TAMPERENSIS, 1994, ser.A, vol.402.

39. Sakaguchi M. Optimal stopping problems for randomly arriving offers. //Math. Japonica, 1976, vol.21, p.201-217.

40. Sakaguchi M. A sequential stochastic assignment problem with a unknown number of jobs. //Math. Japonica, 1984, vol.29, p.141-152.

41. Sakaguchi M. A sequential stochastic assignment problem associated with a non-homogenous Markov process. //Math. Japonica, 1984, vol.29(1), p.13-22.

42. Sakaguchi M. Best choice problems for randomly arriving offers during a random lifetime. //Math. Japonica, 1986, vol.31(1), p.107-117.

43. Sakaguchi M. A sequential assignment problem for randomly arriving jobs. //Rep.Stat.Appl.Res., JUSE, 1972, vol.19, p.99-109.

44. Sakaguchi M. A sequential assignment problem for randomly appearing targets. //Math. Japonica, 1976, vol.21, p.89-103.

45. Sakaguchi M. Sequential games with priority under expected value maximization. //Math. Japonica, 1991, vol.36, p.545-562.

46. Sakaguchi M. Best choice games with random priority on a two-Poisson stream. //Math. Japonica, 1991, vol.36, p.731-745.

47. Sakaguchi M. Dynamic programming of some sequential sampling design. //J. Math. Anal. Appl., 1961, vol.4, p.446-466.

48. Sakaguchi M. Optimal stopping in sampling from a bivariate distribution. //J. Operat. Res. Soc. Open., 1973, vol.16, p.186-200.

49. Sakaguchi M. When to stop: randomly appearing bivariate target values. //J. Operat. Res. Soc. Open, 1978, vol.21, p.45-58.

50. Sakaguchi M. A best-choice problem for the two streams of iid random variables. //Math. Japonica, 2000, vol.51, p.471-478.

51. Sakaguchi M. Best choice problems with full information and imperfect observation. //Math. Japonica, 1984, vol.29, p.241-250.

52. Stadje W. On multiple stopping games. //Optimization, 1985, vol.16, p.410-418.

53. Stadje W. A full information pricing problem for the sale of several identical commodities. //Operat. Res., 1990, vol.34, p.161-181.

54. Szajowski K. Double stop by two decision makers. //Adv. Appl. Probab., 1993, vol.25, p.438-452.

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

56. Березовский Б.А., Гнедин А.В. Теория выбора и задача об оптимальной остановке на лучшем объекте. //АиТ, 1981, N9.

57. Блекуэлл Д, Гиршик М.А. Теория игр и статистических решений. - М.: Изд-во иностр. лит., 1958.

58. Брейман JI. Задачи о правилах остановки. //В кн.: Прикладная комбинаторная математика. М.: Мир, 1968.

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

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

61. Винниченко С.В., Мазалов В.В. Игры на правило остановки последовательности наблюдений фиксированной длины. //Кибернетика, 1989, N1, с.119-121.

62. Гнедин A.B. Многокритериальная задача об оптимальной остановке процесса выбора. //АиТ, 1981, N7.

63. Гусейн-Заде С.М. Задача выбора и оптимальное правило остановки последовательности независимых испытаний. //Теория вероятностей и её применения, 1966, т.11, N3.

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

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

66. Кован Р., Забжик Е. Задача об оптимальном выборе, связанная с пуассоновским процессом. //Теория вероятностей и её применения, 1978, т.23, N3.

67. Мазалов В.В., Кочетов Э.А., Перрин Н., Панова C.B. Экологические задачи выбора с неполной информацией. //Обозрение прикладной и промышленной математики, 1996, т.З, в.З, с.371-383.

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

69. Миркин Б.Г. Проблема группового выбора. - М.: Наука, 1974.

70. Николаев M.JI. Об одном обобщении задачи наилучшего выбора. //Теория вероятностей и её применения, 1977, т.22, N1.

71. Петросян JI.A. Принципы оптимальности в многошаговых играх. //Соросовский образовательный журнал, 1996, №10, с.120-125.

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

73. Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов. //Теория вероятностей и её применения, 1972, т.17, N4.

74. Пресман Э.Л., Сонин И.М. Точки равновесия в обобщенной игровой задаче наилучшего выбора. //Теория вероятностей и её применения, 1975, т.20, N4.

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

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

77. Фалько И.А. Теоретико-игровая модель продажи дома. //Труды ИПМИ КарНЦ РАН, Петрозаводск, 2000, вып.2, стр.209-216.

78. Фалько И.А. Задача о продаже недвижимости в теоретико-игровой постановке. //Вопросы механики и процессов управления, изд-во С.Пб.ун-та, в печати.

79. Фалько И.А. Игра на правило остановки с допуском. //Сборник кафедры математического анализа, изд-во ЧГПИ, Чита, 1998, вып.З, стр. 89-92.

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

81. Ширяев А.Н. Вероятность. - М.: Наука, 1980.

82. Ширяев А.Н. Статистический последовательный анализ. - М.: Наука, 1969.1. РОССИЙСКАЯгосуддрс-^г:о