close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Сер. 10. 2012. Вып. 1
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
УДК 519.833
В. В. Мазалов, А. Ю. Кондратьев
ЗАДАЧА О СДЕЛКАХ С НЕПОЛНОЙ ИНФОРМАЦИЕЙ∗)
1. Введение. Рассмотрим игру двух лиц с неполной информацией, которая относится к модели двойного закрытого аукциона [1–6]. Игроки здесь продавец и покупатель. Каждый из них обладает приватной информацией о своей резервной цене,
которую не знает другой игрок. Резервная цена – это цена, ниже которой продавец
не согласен продавать свой товар, либо максимальная цена, которую готов заплатить
покупатель. Для продавца это могут быть затраты на производство товара s, а для
покупателя – его оценка данного товара b. В работе [1] было найдено равновесие в игре
для случая, когда резервные цены и продавцов, и покупателей равномерно распределены на рынке. Было показано, что оптимальные стратегии, формирующие равновесие
по Нэшу, существуют и имеют линейный вид, соответственно 2/3s + 1/4 для продавца
и 2/3b + 1/12 для покупателя. Такая модель проведения сделок является оптимальной
в смысле суммарного дохода обоих участников [2]. В [5] приводится обзор других возможных механизмов проведения сделок. В работе [6] оптимальные стратегии построены
для линейных распределений резервных цен.
В настоящей работе построим равновесие по Нэшу для случая произвольных распределений для резервных цен. Предположим, что при случайной встрече резервные
цены продавцов s и покупателей b есть независимые случайные величины на интервале
[0, 1] с функциями распределения F (s) и G(b) соответственно (плотностями f (s) и g(b),
если они существуют).
Игроки появляются на рынке и обьявляют цену на товар (не обязательно совпадающую с резервными ценами). Будем считать их функциями от резервных цен, соответственно S = S(s) и B = B(b). Сделка происходит, если B S. Естественно полагать,
что S(s) s и B(b) b, т. е. продавец завышает, а покупатель занижает истинную цену
на продукт, чтобы получить дополнительный доход от сделки. Если сделка состоялась,
то примем, что она происходит по цене (S(s) + B(b))/2.
Выигрышами в игре является разница между резервными ценами и ценой сделки,
т. е. для продавца это (S(s)+B(b))/2−s, для покупателя – b−(S(s)+B(b))/2. Поскольку
b и s случайные величины, то в качестве выигрышей рассмотрим средние значения
S(s) + B(b)
Hs (B, S) = Eb,s
(1)
− s I{B(b)S(s)}
2
Мазалов Владимир Викторович – профессор Института прикладных математических исследований Карельского научного центра РАН. Количество опубликованных работ: 95. Научные направления: теория игр, стохастическое динамическое программирование, математическая биология. E-mail:
vmazalov@krc.karelia.ru.
Кондратьев Алексей Юрьевич – студент-магистрант Петрозаводского государственного университета. Научное направление: теория игр. E-mail: kondratiev@krc.karelia.ru.
∗) Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 10-01-00089-а) и Отделения математических наук РАН.
c В. В. Мазалов, А. Ю. Кондратьев, 2012
33
и
Hb (B, S) = Eb,s
S(s) + B(b)
b−
2
I{B(b)S(s)} .
(2)
Стратегиями в данной байесовской игре являются функции S(s) и B(b). Логично
предположить, что это неубывающие функции, поскольку чем больше затраты у продавца или оценка стоимости предмета у покупателя, то и предложения игроков должны
быть больше. Ниже подробно рассмотрим некоторые частные примеры игр и увидим,
что могут существовать байесовские равновесия, где функции S(s) и B(b) имеют пороговый или нелинейный вид. Но прежде всего нас будут интересовать решения, в которых функции S(s) и B(b) непрерывны и имеют ненулевые конечные производные справа и слева в каждой точке интервала [0,1]. Если таких решений несколько, то можно
предложить то из них, которое максимизирует суммарный выигрыш (1) и (2) продавцов
и покупателей.
Определение. Стратегии S(s) и B(b) определяют байесовское равновесие, если
для любого продавца с резервной ценой s ∈ [0, 1] его личный выигрыш как функция
предлагаемой цены S
S + B(b)
(3)
− s I{B(b)S}
Hs (S) = Eb
2
достигает наибольшего значения при S = S(s). Аналогично для любого покупателя
с резервной ценой b ∈ [0, 1] его выигрыш
S(s) + B
Hb (B) = Es b −
(4)
I{BS(s)}
2
достигает наибольшего значения при B = B(b).
2. Уравнения, определяющие равновесие в задаче о сделках. Предположим,
что резервные цены продавцов и покупателей s и b распределены на интервале [0, 1]
с непрерывными плотностями распределения соответственно f (s), s ∈ [0, 1], и g(b), b ∈
[0, 1].
Определим оптимальные стратегии игроков. Будем считать их функциями от резервных цен, соответственно S = S(s) и B = B(b). Логично предположить, что это
монотонно возрастающие функции. Тогда существуют обратные функции U = B −1
и V = S −1 , т. е. соответственно s = V (S) и b = U (B).
Для нахождения равновесия воспользуемся следующими соображениями. Сделка
происходит, если B S. Если сделка состоялась, будем считать, что она происходит
по цене (S(s) + B(b))/2. Функции выигрыша игроков имеют вид (3) и (4), где математическое ожидание берется по соответствующим распределениям. Для его нахождения
зафиксируем стратегию покупателя B(b) и установим наилучший ответ продавца для
различных значений параметра s.
Условие B(b) S эквивалентно b U (S). Выигрыш продавца равен
Hs (B, S) = Eb
S + B(b)
− s I{B(b)S} =
2
1 S + B(b)
B(b) + S
= Eb
− s I{bU(S)} =
− s g(b)db. (5)
2
2
U(S)
34
Дифференцируя (5) по S, установим наилучший ответ покупателя из условия
∂Hs
1 − G(U (S))
= −(S − s)g(U (S))U (S) +
= 0,
∂S
2
откуда получаем дифференциальное уравнение для определения оптимальных стратегий (точнее обратных фунций) U (B), V (S)
U (S)(S − V (S))g(U (S)) =
1 − G(U (S))
.
2
(6)
Аналогично, пусть S(s) – стратегия продавца. Найдем наилучший ответ покупателя
для различных значений параметра b. Его выигрыш
Hb (B, S) = Es
S(s) + B
b−
2
I{BS(s)} =
V(B)
S(s) + B
S(s) + B
= Es b −
b−
I{sV (B)} =
f (s)ds. (7)
2
2
0
Дифференцируя (7) по B, имеем наилучший ответ покупателя
1
∂Hb
= (b − B)f (V (B))V (B) − F (V (B)) = 0,
∂B
2
откуда выводим второе дифференциальное уравнение для определения оптимальных
стратегий U (B), V (S)
V (B)(U (B) − B)f (V (B)) =
1
F (V (B)).
2
(8)
Делая в (6), (8) замену u(x) = G(U (x)), v(x) = 1 − F (V (x)), приходим к системе уравнений
1 − u(x)
,
(9)
u (x) x − F −1 (1 − v(x)) =
2
1 − v(x)
v (x) x − G−1 (u(x)) =
.
(10)
2
3. Построение равновесия и границ сделки. В силу предположения V (S) –
возрастающая функция, поэтому функция v(x) убывает, т. е. v (x) < 0, x ∈ [0, 1]. Тогда
из (10) следует, что u(x) расположена над кривой G(x). График функции v(x) лежит
над кривой 1 − F (x) и u (x) > 0. На рис. 1 изображены графики функций u(x) и v(x),
где x1 и x2 – точки, где значения функций равны 1.
В точке x1 v(x1 ) = 1. Тогда из (10) следует, что u(x1 ) = G(x1 ). Аналогично из (9)
вытекает v(x2 ) = 1 − F (x2 ). Для производных u(x) и v(x) в точках x1 и x2 из (9), (10)
находим
1 − u(x1 )
1 − G(x1 )
=
(11)
u (x1 ) =
2x1
2x1
и
F (x2 )
1 − v(x2 )
v (x2 ) =
=
.
(12)
2(x2 − 1)
2(x2 − 1)
35
Рис. 1. Функции u(x), v(x)
Остается неопределенность в значениях x1 , x2 , это границы, в которых ищется решение системы уравнений (9), (10). Найдем их из следующих соображений.
Рассмотрим функцию u(x) в окрестности точки x2 . В самой точке x2 u(x2 ) = 1.
В уравнении (9) для u (x) в точке x2 неопределенность вида 0/0. Предположим, что
u (x2 ) существует и конечна. Тогда по правилу Лопиталя получаем
u (x2 ) =
−u (x2 )
1 − u(x)
# =
= "
−1
−v (x2 )
x→x2 −0 2 (x − F
(1 − v(x)))
2 1 − F (F −1
(1−v(x2 )))
lim
=
"
2 1+
−u (x2 )
v (x
2)
F (F −1 (F (x2 )))
#=
−u (x2 )
# . (13)
"
(x )
2
2 1 + vf (x
2)
Из (13) следует выполнение в точке x2 соотношения (при g(1) = 0)
3
v (x2 ) = − f (x2 ).
2
Вместе с (12) это приводит к соотношению
F (x2 ) = 3f (x2 )(1 − x2 ).
(14)
Теперь рассмотрим функцию v(x) в окрестности точки x1 . В точке x1 v(x1 ) = 1.
В уравнении (10) для v (x) в точке x1 неопределенность вида 0/0. Предположим, что
v (x1 ) существует и конечна. Тогда по правилу Лопиталя получаем
v (x1 ) =
−v (x1 )
1 − v(x)
#=
"
=
x→x1 +0 2 (x − G−1 (u(x)))
1)
2 1 − G (Gu−1(x(u(x
1 )))
lim
=
36
"
2 1−
−v (x1 )
u (x
1)
G (G−1 (G(x1 )))
#=
−v (x1 )
# . (15)
"
(x )
1
2 1 − ug(x
1)
Из (15) следует выполнение в точке x1 соотношения (при f (0) = 0)
u (x1 ) =
3
g(x1 ).
2
Вместе с (11) это приводит к соотношению
1 − G(x1 ) = 3g(x1 )x1 .
(16)
Лемма. На интервале [0, 1] существует решение уравнений (14), (16).
Д о к а з а т е л ь с т в о. Для доказательства существования решения, например,
уравнения (14) заметим, что при x2 = 0 левая часть уравнения (14) не превосходит
правой части, а при x2 = 1 наоборот, правая часть не превосходит левой. Кроме того,
функции F (x), f (x) предполагаются непрерывными. Аналогично проводятся рассуждения для уравнения (16).
Уравнения (14), (16) определяют границы x1 , x2 . Однако при этом должно выполняться x1 x2 . Перейдем от построенных решений u(x), v(x) на интервале [x1 , x2 ]
к функциям U (x), V (x) и наконец к оптимальным стратегиям. На рис. 2 приведен вид
оптимальных стратегий B(b) и S(s).
Видно, что x1 , x2 представляют собой маргинальные значения для сделки, ниже
значения x1 продавец не опускает цену, а выше значения x2 покупатель не покупает
товар.
Итак, доказано следующее утверждение.
Теорема 1. Пусть x1 , x2 – решения уравнений (14), (16), причем x1 x2 . Тогда
оптимальные стратегии в задаче о сделках с распределением F (s), G(b) резервных цен
имеют вид
S = V −1 (s), B = U −1 (b),
где функции u = G(U (x)), v = 1 − F (V (x)) определяются системой дифференциальных
уравнений (9), (10). При этом сама сделка совершается в границах цен [x1 , x2 ].
На рис. 3 представлена область сделки с криволинейной границей в данном случае.
Рис. 2. Оптимальные стратегии
Рис. 3. Область сделки (по теореме 1)
37
4. Сделки с фиксированными ценами. Предположим, что продавец использует
стратегию порогового типа
$
a, если s a,
S(s) =
s, если a s 1,
т. е. для малых значений резервных цен продавец устанавливает фиксированную цену
a, и только если s превышает значение a, он называет истинную цену s.
Установим наилучший ответ покупателя для различных значений параметра b. Заметим, что сделка происходит, только если резервная цена покупателя b не меньше a.
Если же b a, то сделка может осуществляться при условии, что B S(s).
Найдем выигрыш покупателя
Hb (B, S) = Es
S(s) + B
b−
2
I{BS(s)} =
a =
0
a+B
b−
2
B s+B
b−
f (s)ds +
f (s)ds.
2
a
Производная этой функции имеет вид
F (B)
∂Hb
= (b − B)f (B) −
.
∂B
2
(17)
Отсюда следует, что если на интервале B ∈ [a, 1] выражение (1 − B)f (B) − F (B)
неполо2
жительно, то и производная (17) будет неположительна, и тогда максимум выигрыша
будет достигаться при B(b) = a, b ∈ [a, 1].
Аналогичные рассуждения можно провести и для покупателя. Предположим, что
покупатель использует стратегию B(b) = min{a, b}, т. е. для больших b он устанавливает
фиксированную цену a, а для малых значений b a называет истинную цену.
Выигрыш продавца равен
Hs (B, S) = Eb
S + B(b)
− s I{B(b)S)} =
2
a 1 b+S
a+S
− s g(b)db +
− s g(b)db.
=
2
2
a
S
Находим производную
∂Hs
1 − G(S)
= (s − S)g(S) +
.
∂S
2
Отсюда, если для всех x ∈ [0, a] имеет место неравенство
−xg(x) +
(18)
1 − G(x)
0,
2
то и производная (18) будет неотрицательна.
Теорема 2. Пусть для некоторого a ∈ [0, 1] выполняются следующие условия:
2xg(x) 1 − G(x),
38
x ∈ [0, a],
(19)
2(1 − x)f (x) F (x),
x ∈ [a, 1].
(20)
Тогда оптимальными стратегиями в задаче о сделках являются стратегии
S(s) = max{a, s},
B(b) = min{a, b}.
При этом область сделки имеет вид, изображенный на рис. 4. Таким образом, при
выполнении условий теоремы сделка всегда происходит по фиксированной цене a.
Рис. 4. Область сделки (по теореме 2)
Замечание 1. Отметим, что если неравенство (19) выполняется на интервале [0, a1 ]
и неравенство (20) на интервале [a2 , 1] и при этом a1 a2 , то условия теоремы 2 будут
выполнены для любого a ∈ [a2 , a1 ], т. е. существует множество равновесий.
5. Сравнение оптимальных стратегий. Покажем, что множество стратегий,
найденных в теоремах 1 и 2, является достаточным для построения равновесия в любых играх. Действительно, если выполняются условия теоремы 2, то в качестве оптимальных стратегий можно использовать пороговые стратегии.
Теперь предположим, что условия теоремы 2 не выполняются. Обозначим через a1
и a2 соответственно решения уравнений
2xg(x) = 1 − G(x)
и
2(1 − x)f (x) = F (x).
Если условия теоремы 2 не выполняются, то a1 < a2 . Тогда, если x1 – корень уравнения
(16), то
1 − G(x1 ) = 3x1 g(x1 ) 2x1 g(x1 ).
Поскольку неравенство 1 − G(x) 2g(x) имеет место в области x a1 , то x1 a1 .
Аналогично показывается x2 a2 . Но в таком случае x1 x2 и равновесием являются стратегии, найденные в теореме 1.
Замечание 2. Нетрудно видеть, что условия теоремы 2 выполняются для распределений
F (s) = 1 − (1 − s)n , G(b) = bn , n 3,
39
при a = 1/2. В данном случае равновесие имеет вид
1
S(s) = max{ , s},
2
1
B(b) = min{ , b}.
2
При этом ожидаемые выигрыши составляют величину
1
1
2
(1/2 − s)n(1 − s)n−1 ds =
nbn−1 db
H b = Hs =
0
1
2
(2n − 1) (2n (n − 1) + 1)
,
2(n + 1)4n
которые при увеличении n сходятся к 1/2.
В таблице представлены оптимальные стратегии, выигрыши игроков и вероятности
сделки для различных распределений резервных цен. В симметричном случае выигрыши игроков совпадают. В четвертом и пятом примерах покупатель находится в более
предпочтительном положении, чем продавец, и его выигрыш больше. В третьем и четвертом примерах можно использовать равновесие в двух видах. При этом заметим, что
равновесие, найденное в теореме 1, предпочтительнее для обоих игроков, чем в теореме 2.
Оптимальные стратегии и выигрыши игроков
F (s)
s
1−(1−s)2
1−(1−s)3
G(b)
b
b2
b3
1−(1−s)4
b2
1−(1−s)5
b3
S(s)
+ 14
Теорема 1
Теорема 1
max{0.5, s}
Теорема 1
max{0.425, s}
max{0.438, s}
2
s
3
B(b)
1
+ 12
Теорема 1
Теорема 1
min{0.5, b}
Теорема 1
min{0.425, b}
min{0.438, b}
2
b
3
EHs
0.070
0.164
0.236
0.232
0.202
0.195
0.254
EHb
0.070
0.164
0.236
0.232
0.239
0.238
0.303
P (BS)
0.281
0.587
0.775
0.766
0.740
0.730
0.865
Литература
1. Chatterjee K., Samuelson W. Bargaining under incomplete information // Operations Research. 1983.
Vol. 31, N 5. P. 835–851.
2. Myerson R., Satterthwait M. A. Efficient mechanisms for Bilateral Trading // Journal of Economic
Theory. 1983. Vol. 29. P. 265–281.
3. Myerson R. Two-Person Bargaining Problems with Incomplete Information // Econometrica. 1984.
Vol. 52. P. 461–487.
4. Klemperer P. The Economic Theory of Auction. Northampton, MA: Edward Elgar Publishing Inc.,
2000. 692 p.
5. Зенкевич Н. А. Механизмы заключения сделки на В2В рынках: Сравнительный анализ // Вестн.
С.-Петерб. ун-та. Сер. 8: Менеджмент. 2008. Вып. 1. С. 3–30.
6. Мазалов В. В., Токарева Ю. С. Равновесие в задаче о сделках с неравномерным распределением
резервных цен // Математическая теория игр и ее приложения. 2011. Т. 3, вып. 2. C. 37–49.
Статья рекомендована к печати проф. Л. А. Петросяном.
Статья принята к печати 20 октября 2011 г.
Документ
Категория
Без категории
Просмотров
10
Размер файла
323 Кб
Теги
сделках, неполной, задачи, информация
1/--страниц
Пожаловаться на содержимое документа