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

Москва, 2023

Б. Б. Демешев

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

2-е издание, электронное

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

Р е ц е н з е н т ы: 
кандидат геолого-минералогических наук 
Национальный исследовательский университет «Высшая Школа Экономики», 
В. Л. Шагин

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

Д30
Демешев, Борис Борисович.
Моделирование аукционов / Б. Б. Демешев. — 2-е изд., эл. — 1 файл pdf : 153 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital 
Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-645-6

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

УДК 658.727 
ББК 65.42-80

Электронное издание на основе печатного издания: Моделирование аукционов / Б. Б. Демешев. — Москва : 
ДМК Пресс, 2016. — 152 с. — ISBN 978-5-97060-523-3. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских 
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-645-6
© Демешев Б. Б., 2016
© Оформление, издание, ДМК Пресс, 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}.