Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Моделирование аукционов

Покупка
Артикул: 712487.01.99
Книга представляет собой подробный конспект лекций курса по моделированию аукционов. В первой главе обсуждаются разные виды аукционов и теорема об эквивалентности доходностей, согласно которой при независимости игроков все аукционы приносят одинаковый доход организатору. Цель второй главы — заполнить пробелы по теории вероятностей, описать технику решения задач с помощьюо-малых и объяснить концепцию аффилированных сигналов. Третья глава посвящена сравнению доходностей организатора аукциона в случае, когда игроки зависимы в силу того, что получают общую информацию о товаре. В четвертой главе аукционы описываются с помощью общего языка теории механизмов. Помимо теоретической части приводится огромное количество задач с решениями. Издание предназначеностудентам вузов, знакомыхстеорией игр и теорией вероятности, а также будет полезно широкому кругу читателей.
Демешев, Б.Б. Моделирование аукционов / Б.Б Демешев. - Москва : ДМК Пресс, 2016. - 152 с. - ISBN 978-5-97060-523-3. - Текст : электронный. - URL: https://znanium.com/catalog/product/1028143 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Москва, 2016

Б. Б. Демешев

Моделирование аукционов

УДК 658.727
ББК 65.42-80
 
Д30

Р е ц е н з е н т ы:

кандидат геолого-минералогических наук 

Национальный исследовательский университет «Высшая Школа Экономики», 

Шагин В.Л.

кандидат экономических наук, 

Национальный исследовательский университет «Высшая Школа Экономики», 

доцент Пильник Н.П.

Демешев Б. Б.

Д30
Моделирование аукционов. – М.: ДМК Пресс, 2016. – 152 с.: ил.

ISBN 978-5-97060-523-3

Книга представляет собой подробный конспект лекций курса по моделированию 

аукционов. 

В первой главе обсуждаются разные виды аукционов и теорема об эквивалентности 

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

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

а также будет полезно широкому кругу читателей. 

                       УДК    658.727
                       ББК    65.42-80

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы 

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

Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность 

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

  © Демешев Б. Б., 2016

ISBN 978-5-97060-523-3
 © Оформление, издание, ДМК Пресс, 2016

Оглавление

Предисловие
5

1
Аукционы бывают разные
7

1.1
Три аукциона и три модели . . . . . . . . . . . . . . . . . . . . . . . . .
7

1.2
Поиск оптимальных стратегий
. . . . . . . . . . . . . . . . . . . . . . .
12

1.3
Теорема об одинаковой доходности
. . . . . . . . . . . . . . . . . . . .
20

1.4
Пример с коррелированными ценностями
. . . . . . . . . . . . . . . .
24

1.5
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28

1.6
Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

1.7
Контрольная работа 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35

1.8
Решение контрольной работы 1 . . . . . . . . . . . . . . . . . . . . . . .
36

2
Общая ценность, аффилированные сигналы
38

2.1
Напоминалка по теории вероятностей . . . . . . . . . . . . . . . . . . .
38

2.2
Большая сила о-малых! . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40

2.3
Старые формулы на вероятностном языке
. . . . . . . . . . . . . . . .
44

2.4
Просто разные примеры . . . . . . . . . . . . . . . . . . . . . . . . . . .
48

2.5
Супермодулярные функции . . . . . . . . . . . . . . . . . . . . . . . . .
54

2.6
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59

2.7
Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61

2.8
Контрольная работа 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68

2.9
Решение контрольной работы 2 . . . . . . . . . . . . . . . . . . . . . . .
70

3
Сравнение аукционов в общем случае
72

3.1
Про симметричность
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72

3.2
Ещё об аффилированности . . . . . . . . . . . . . . . . . . . . . . . . . .
74

3.3
Решение трёх аукционов . . . . . . . . . . . . . . . . . . . . . . . . . . .
80

ОГЛАВЛЕНИЕ

3.4
Теорема о сравнении доходностей . . . . . . . . . . . . . . . . . . . . .
87

3.5
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89

3.6
Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91

3.7
Контрольная работа 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98

3.8
Решение контрольной работы 3 . . . . . . . . . . . . . . . . . . . . . . .
99

3.9
Домашняя работа 3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

3.10 Решение домашней работы 3
. . . . . . . . . . . . . . . . . . . . . . . . 105

4
Язык механизмов
109

4.1
Описание всех задач на языке механизмов . . . . . . . . . . . . . . . . 109

4.2
Правдивость и другие желательные свойства . . . . . . . . . . . . . . . 115

4.3
Механизм VCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

4.4
Оптимальный аукцион . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

4.5
Спасибо! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.6
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

4.7
Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

4.8
Контрольная работа 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

4.9
Решение контрольной работы 4 . . . . . . . . . . . . . . . . . . . . . . . 135

4.10 Догонялка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.11 Подсказки к догонялке . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.12 Прочие задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.13 Немного решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Впечатления о курсе
144

Предметный указатель
148

Литература
151

Предисловие

Эта книга — подробный конспект лекций курса по моделированию аукционов.

Курс был прочитан дистанционно в НИУ-ВШЭ в 2011 году. Самое важное отличие
книги от других книг по моделированию аукционов — огромное количество задач
с решениями!

Из книги любопытный читатель узнает, например:

• что аукцион — это не обязательно «дядя с молоточком»;

• как устроены самые крупные аукционы;

• почему не всегда победитель аукциона платит ту сумму, которую поставил;

• как влияют на прибыль организатора разные правила проведения аукциона;

• при каких условиях может нарушиться закон спроса.

В книге четыре главы. Первая — про разные виды аукционов и теорему об экви
валентности доходностей, которая утверждает, что при независимости игроков все
аукционы приносят одинаковый доход организатору аукциона. Вторая глава — техническая. Её цель — заполнить пробелы по теории вероятностей, рассказать технику решения задач с помощью о-малых и объяснить концепцию аффилированных
сигналов. Третья глава посвящена сравнению доходностей организатора аукциона в случае, когда игроки зависимы из-за того, что получают общую информацию
о товаре. Четвертая глава излагает аукционы с помощью общего языка теории механизмов. В главе вводится механизм Викри—Кларка—Гровса и доказывается оптимальность аукциона второй цены с резервной ценой.

Моделирование аукционов — довольно сложная и сильно математизированная

дисциплина. Именно из-за теоретической сложности она редко встречается в программе бакалавриата. Моей целью было сделать этот курс максимально доступным

для бакалавров. Поэтому я старался, во-первых, снизить входные требования к уровню подготовки, во-вторых, включить в курс максимальное количество задач с решениями.
Для чтения книги требуется немного теории игр и теории вероятностей. Из теории игр — понимание равновесия Нэша. Из теории вероятностей — умение считать
условные вероятности и математические ожидания дискретных и непрерывных
случайных величин.
Выражаю большую благодарность рецензентам Вадиму Львовичу Шагину и Николаю Петровичу Пильнику за ценные замечания.
Для удобства поиска внутри книги нумерация формул идёт постраничная. Например, формула (27.3) — это третья формула на 27-й странице. Конец доказательства обозначается значком □.
Читателю могут также оказаться полезными видеолекции курса, vimeo.com/album/
1530587, и блог, бывший активным в 2011 году, auctiontheory.wordpress.com/.
Удачи в освоении теории аукционов!

Борис Демешев

bdemeshev@hse.ru

Национальный исследовательский университет
«Высшая школа экономики»

Глава 1

Аукционы бывают разные

1.1. Три аукциона и три модели

• Английский аукцион. Именно этот аукцион описан в «12 стульях» Ильфа

и Петрова. Игроки по очереди называют ставки. Каждая последующая ставка
должна быть больше, чем предыдущая. Товар достаётся тому, кто назвал наибольшую цену. Победитель платит за товар столько, сколько он сам поставил1.
По этому принципу устроен самый крупный современный онлайн-аукцион
товаров в Интернете, eBay, http://www.ebay.com/.

• Голландский аукцион цветов. Большинство цветов, продающихся в России,

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

• Аукцион интернет-рекламы. Когда пользователь набирает в поисковике (в

Яндексе, Гугле или любом другом) какое-нибудь слово, к примеру «НИУ-ВШЭ»,
поисковик выдает найденные страницы и рекламные ссылки. Естественно,
рекламодатели платят за то, что поисковик показывает их рекламные ссылки.
Более того, рекламные ссылки продаются на аукционе! Представим себе, что

1 Про оплату комиссионого сбора в 12 стульях мы, конечно, помним.

1.1. ТРИ АУКЦИОНА И ТРИ МОДЕЛИ

поисковик продаёт одно рекламное место. Желающие рекламодатели независимо друг от друга направляют свои заявки: «я готов платить за него 5 копеек
за клик», «я готов платить 10 копеек за клик», «я готов платить 7 копеек за
клик». Побеждает, естественно, тот, кто готов платить больше других. Но пла-
тит он не ту сумму, которую заявил в своей заявке! Победитель платит вторую
по величине ставку! В нашем примере с тремя заявками рекламное место достаётся тому, кто был готов платить 10 копеек за клик, но платить он будет
7 копеек за клик. В реальности всё чуть сложнее. Например, рекламных мест
может быть несколько, тогда тот, кому досталось второе по притягательности
место, платит ставку того, кому досталось третье. Гугл продаёт свои рекламные ссылки на adwords.google.com.

Этим трём реальным примерам мы сопоставим три простые модели.
Общее между тремя моделями:
На аукционе продаётся единица неделимого товара, скажем одна морковка. За
право получить морковку борятся n покупателей.

1. Кнопочный аукцион. У каждого покупателя есть кнопка. Стартовая цена равна нулю. Изначально все покупатели давят на свои кнопки. Затем цена начинает расти. Как только игрок отпускает свою кнопку, он покидает аукцион.
Аукцион прекращается, когда остаётся лишь один игрок, жмущий на кнопку.
Товар достаётся этому игроку по цене, сложившейся на момент остановки.

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

2. Закрытый аукцион первой цены. Покупатели одновременно делают свои
ставки. Товар достаётся тому покупателю, который назвал самую высокую
цену. Победитель платит продавцу свою ставку.

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

ГЛАВА 1. АУКЦИОНЫ БЫВАЮТ РАЗНЫЕ
9

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

3. Закрытый аукцион второй цены. Покупатели одновременно делают свои
ставки. Товар достаётся тому покупателю, который назвал самую высокую
цену. Победитель платит продавцу вторую по величине ставку, то есть наибольшую ставку, сделанную покупателями, за исключением его самого.

Эта модель хорошо подходит для аукциона интернет-рекламы с одним рекламным местом.

Чтобы разграничить реальность и модели, мы будем использовать слова «английский аукцион», «голландский аукцион» для описания реальных явлений, а слова «аукцион первой цены», «аукцион второй цены», «кнопочный аукцион» — для
описания моделей.
Иногда вводят понятия: открытый аукцион, то есть аукцион, где игроки видят
ставки других игроков, и закрытый аукцион, где игроки не видят ставок других
игроков. По этой классификации кнопочный аукцион является открытым, а аукционы, где игроки делают ставки одновременно, — закрытыми.
Для формального описания наших задач нам потребуется куча обозначений.
Мы их будем вводить потихоньку, поэтому пугаться не стоит. Нужно всего лишь
быть очень аккуратным и отличать заглавные и строчные буквы, например x и X.
Для удобства вынесем все обозначения в отдельный список. Встречайте…

1.1. ТРИ АУКЦИОНА И ТРИ МОДЕЛИ

Обозначения!

Событие:

• Wi — событие, состоящее в том, что победителем аукциона стал игрок i.

Случайные величины:

• Xi — случайная величина, сигнал о ценности, получаемый игроком. Значение Xi известно игроку i. Функцию распределения этой случайной величины
обозначим F(), а функцию плотности — f().

• Vi — случайная величина, ценность товара для игрока i. Если игрок точно
знает ценность товара, то Vi = Xi. Есть множество других возможностей, например Xi = Vi + ei, где ei — некая случайная ошибка.

• Bidi — случайная величина, ставка, которую сделает игрок i в равновесии
Нэша. В симметричном равновесии Нэша:

Bidi = b(Xi).
(10.1)

• Payi — случайная величина, выплата, которую делает игрок i в равновесии
Нэша.

• R — случайная величина, доход продавца в равновесии Нэша:

R = Pay1 + Pay2 + . . . + Payn.
(10.2)

• Profiti — случайная величина, выигрыш игрока i в равновесии Нэша:

Profiti = Vi · 1Wi − Payi.
(10.3)

• Y1, …, Yn−1 — случайные величины X2, …, Xn, упорядоченные по убыванию.
В частности, Y1 = max{X2, . . . , Xn} и Yn−1 = min{X2, . . . , Xn}.

ГЛАВА 1. АУКЦИОНЫ БЫВАЮТ РАЗНЫЕ
11

Детерминистические функции:

• b(·) — неслучайная функция, зависимость ставки от сигнала в равновесии Нэша;

• q(x) = P(W1|X1 = x) — вероятность выигрыша первого игрока, если X1 = x
в равновесии Нэша;

• pay1(x) = E(Pay1|X1 = x) — средняя выплата первого игрока, если X1 = x в
равновесии Нэша.

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

• π1(x, b1) = E(Profit1|X1 = x; Bid1 = b1) — средний выигрыш первого игрока, если X1 = x, он ставит константу b1, а остальные игроки используют
равновесные стратегии.

1.2. ПОИСК ОПТИМАЛЬНЫХ СТРАТЕГИЙ

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

1. Частные независимые ценности. Каждый игрок знает, какую ценность товар
представляет для него, то есть Xi = Vi. Такая ситуация возникает, если товар
сложно перепродать вне аукциона или игроки не собираются делать этого.
Для простоты ценности предполагают независимыми случайными величинами.

2. Общая ценность. Если товар можно легко перепродать и купить вне аукциона по стабильной цене, то ценность товара для каждого игрока определяется
этой рыночной ценой товара. То есть V1 = V2 = V3 = . . . = Vn = V . При
этом игроки могут не знать этого V . Каждый игрок знает лишь свой сигнал
Xi, который зависит от V , но не обязательно ему равен.

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

1.2. Поиск оптимальных стратегий

Кратко напомним предпосылки. Сигнал Xi, который получает игрок i, — это и
есть ценность товара для него, то есть Xi = Vi. Пусть ценности Xi будут независимыми и равномерными на отрезке [0; 1] случайными величинами. Мы ограничимся поиском симметричного равновесия, то есть равновесия, где все игроки используют одинаковую стратегию. Фактические ставки при этом могут отличаться!
Стратегия — это функция b() от ценности, и даже если эти фукнции b() одиковые,
величины b(Xi) будут разными в силу того, что ценности Xi будут разными.
До начала игры игроки ничем не отличаются: у них одинаковый закон распределения ценности товара, поэтому при анализе мы будем изучать поведение первого игрока.
Поехали!

1. Аукцион первой цены.

Предположим, что есть некая равновесная стратегия b(x). Предположим также, что она дифференцируема и возрастает по x.