автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Резервные цены в асимметричных аукционах

На правах руке

ё

Топинский Валерий Александрович

Резервные цены в асимметричных аукционах

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

2 0 НОЯ 2014

005555556

Москва — 2014

005555556

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования Национальном Исследовательском Университе «Высшая Школа Экономики».

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Воронцов Константин Вячеславович,

доктор физико-математических наук

Шаповал Александр Борисович,

доктор физико-математических наук,

Федеральное государственное бюджетное учреждение науки

Финансовый университет

при Правительстве Российской Федерации,

профессор

Савватеев Алексей Владимирович,

доктор физико-математических наук, Российская Экономическая Школа, Лаборатория исследования социальных отношений и многообразия общества, ведущий научный сотрудник

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук

Защита состоится «25» декабря 2014 г. в 13:00 часов на заседании диссертационного совета Д 002.017.04 при Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук по адресу: 119333, Москва ул. Вавилова, д.40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке и на официальном сайте (http: / /www. ccas . ru/) ВЦ РАН.

Автореферат разослан « 2014 года.

Ученый секретарь диссертационного совета, доктор физико-математических наук, профессор .М. Новикова

Общая характеристика работы

Актуальность темы. Наиболее значимым теоретическим достижением в теории аукционов является так называемая теорема об эквивалентности по доходу, которая при некоторых достаточно разумных условиях устанавливает существование классов эквивалентности различных форматов аукционов. Например, аукцион первой цены и аукцион второй цены для симметричных участников в ожидании приносят одинаковый доход аукционисту. Первым эту теорему (хотя и в частном случае) доказал в 1961-1962 Вильям Викри. В большей степени за это он и получил Нобелевскую премию.

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

При этом асимметричность участников в последнее время стала де-факто стандартным предположением, при котором эквивалентности по доходу у аукционов даже с простыми форматами достичь не удается [Ма$кт&КПеу,2000]. На практике же часто выбирается формат, который более прост в реализации. И становится очевидным необходимость изучить вопрос о том, каким образом можно оптимизировать доход в таких аукционах из практики в случае асимметричных участников? Кроме того, часто аукционисту не доступна такая детальная информация про участников, как в оптимальном аукционе Майерсона. Поэтому важно понять, а какая информация вообще важна для такого рода задач оптимизации? Известным и часто применяемым на практике инструментом оптимизации ожидаемой прибыли от аукциона является инструмент резервных цен. Поэтому естественно возникают вопросы относительно применимости резервных цен в случае асимметричных аукционов, в частности, в условиях анонимности участия покупателей. Но кроме этих вопросов существуют вопросы и относительно симметричного случая. От чего зависит эффективность резервных цен в терминах потенциального увеличения доходности? Данный вопрос является также практически значимым, так как любая попытка оптимизировать аукцион влечет за собой риски и издержки. Таким образом, необходимо быть уверенным, что в конкретных случаях возможная оптимизация аукциона стоит свеч.

Одним из наиболее релевантных примеров появления таких практических вопросов и задач являются интернет-аукционы. Так, самый крупный на данный момент интернет-аукцион «eBay» и практически все аукционы интернет-рекламы используют некоторые обобщения простого аукциона второй цены. Поэтому важно понимать, каким образом можно оптимизировать такие аукционы, где кроме всего прочего появляется новая особенность: многотовар-ность.

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

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

Целью исследования является решение следующих вопросов.

1. Необходимо понять, какова эффективность инструмента резервных цен для оптимизации фиксированных форматов аукциона.

2. Какие свойства в контексте аукциона влияют на эту эффективность резервной цены?

3. Имеет ли значение информация, которой обладает аукционист про участников, в асимметричной ситуации, и, если имеет, то какая информация важна для задачи оптимизации и почему?

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

5. Отдельно стоит отметить необходимость изучения вопроса о практической применимости теоретических результатов на примере многотоварных аукционов интернет-рекламы.

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

4

неизвестных параметров аукциона при ранее не рассматриваемых ограничениях: анонимности и неполноты наблюдений.

В диссертации получены следующие основные новые научные результаты, выносимые на защиту:

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

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

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

4. Проведены численные эксперименты по сравнительному анализу существующих методов структурной эконометрики многотоварных аукционов. Вы-

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

1. The Sixth International Workshop on Data Mining for Online Advertising and Internet Economy, ACM SIGKDD 2012. Пекин, Китай, 2012.

2. The 21st ACM International Conference on Information and Knowledge Management. Мауи, Гавайи, США, 2012.

3. 22nd International World Wide Web Conference. Рио-де-Жанейро, Бразилия, 2013.

4. The Fourteenth ACM Conference on Electronic Commerce. Филадельфия, США, 2013.

5. Econometric Society Australasian Meeting, 2013. Сидней, Австралия, 2013.

6. Asian Meeting of the Econometric Society. Сингапур, Сингапур, 2013.

7. Econometric Society 2014 North American Winter Meeting at the Allied Social Science Associations Annual Meeting. Филадельфия, США, 2014.

8. Econometric Society Australasian Meeting, 2014. Хобарт, Австралия, 2014.

Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 3 — в рецензируемых трудах международных конференций.

Содержание работы

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

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

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

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

В работе я провожу анализ в рамках модели независимых частных ценностей (IPV-модель). Т.е. предполагается, что в торгах участвует N риск-нейтральных покупателей; пусть N = {1,..., 7V} есть множество покупателей, а индекс 0 зарезервирован за аукционистом. Каждый покупатель i £ Af определяет ценность Vi для выставленного на продажу объекта (данный случай одно-

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

1

товаров). С точки зрения аукциониста и конкурентов покупателя г его ценность Уг есть случайная величина с некоторой известной функцией распределения, то есть V* ~ ^(и), Рг : [0,ы] —>• [0,1]. Тогда предположение о независимых частных ценностях есть ни что иное, как предположения: (¡) о совокупной независимости случайных величин Уг \/г £ Л/", (11) каждый участник торгов точно знает значение реализации своей ценности Ц = и, и (ш) функции распределений ценностей всех участников !•], Уj Е Л/" и значение ценности аукциониста г>о от обладания объектом в случае несостоявшейся продажи1 являются общеизвестными. Случайный вектор ценностей покупателей будем обозначать как V, а его конкретную реализацию - V, причем пространство возможных значений есть декартово произведение интервалов [0, со], которое для краткости будем обозначать через X. Индекс —г, например, используется для обозначения соответствующих величин, относящихся ко всем участникам аукциона кроме участника г.

Основной решаемой задачей в работе является оптимизация аукциона в смысле максимизации ожидаемой прибыли аукциониста.

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

А : [0,И ->№+.

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

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

'Т.е. ценность аукциониста У0 = и0 есть вырожденная случайная величина.

2Т.е. предполагается, что любой покупатель заинтересован в приобретении лишь одного объекта продажи.

Определение (вектор качества товаров). Для аукциона с К товарами и N покупателями определилt вектор качества товаров a £ R'V следующим образом.

1. ах = 1;

нормирование относительно наиболее качественного.

2. сч > ai+i;

товары упорядочены по убыванию качества.

3. ак+1 = • • • = aN = О/

отсутствие товара эквивалентно товару с нулевым качеством.

Таким образом, вектор качества ос порождает естественный порядок на множестве товаров К, = {1,..., К}. При этом ценность покупателя i £ Л/" для товара с номером к определяется как произведение:

Vi,k = Oik-Vi,

где конкретное значение V, = и.,, ценности за единицу товара, определяет тип покупателя1,.

Таким образом, с помощью вектора качества товаров покрываются случаи:

- К = 1, однотоварного аукциона;

- а\ = • ■ • = ак, аукциона с единичным спросом и одинаковыми товарами;

- 3i < К : оц > Qj+i > 0, аукциона с единичным спросом и неоднородными товарами или позиционный аукцион.

В силу известного в литературе принципа откровенности (см. [Krishna'09,The Revelation Principle]) можно ограничиться рассмотрением лишь аукционов с равновесием «правдиво сообщать свой тип». Тогда можно определить следующее ключевое для данной работы понятие функции количества товара.

Определение (функция количества товара). Для стандартного аукциона по продаже К товаров с вектором качества а среди N покупателей с единичным спросом функцией ожидаемого количества товара q(v) для покупателя с типом v будем называть математическое ожидание качества товара, которое

3Термины тип и ценности в данной работе часто используются как равноправные синонимы. Но в случае многотоварных аукционов удобно во избежание путаницы использовать термин тип для указания ценности участника для единицы товара максимального качества.

он может выиграть в ходе данного аукциона. То есть

к

¿=1

где 7Ti{v) есть вероятность события, заключающегося в том, что тип V = v оказался i-ым по величине типом среди всех N типов участников, то есть

■Ki{v) = Ci^l{l-F{v))i-1F{v)N-i.

Здесь неявно предполагается симметрия среди участников аукциона, то есть одинаковость функций распределения их типов, Fj = F(v) Vi £ ЛЛ Ниже, при рассмотрении асимметричных аукционов, у всех обозначений будет явно указан индекс, определяющий, относительно какого участника рассматривается данный термин.

Название «количество товара» в определении оправдано тем фактом, что товар №к с качеством 0/: можно воспринимать как часть или долю Q/,. товара №1 с наибольшим качеством а\ = 1. То есть для каждого покупателя с типом V. = v значение q(v) есть его ожидание того, какое количество товара (часть от максимального качества) он может получить в ходе аукциона. Согласно теореме об эквивалентности по доходу (см. [Krishna'09, Revenue Equivalence]), функция ожидаемого платежа m(v) участника с типом V, = v полностью определена через функцию количества товара:

pv rv

m(v) = v ■ q(v) — / q(s)ds= / sdq(s). (1)

Jo Jo

Таким образом, удалось свести описание симметричного аукциона к одной функции4 количества товара q(v), что вполне достаточно для решаемой здесь задачи оптимизации ожидаемой прибыли от аукциона, т.к. данная задача решается аукционистом в среднем. Подобное описание аукциона принято называть приведенной формой.

Резервной ценой R называется цена, ниже которой продажа товара невозможна. То есть, если некоторый покупатель i имеет тип vl < R, то, согласно правилам аукциона и играемому равновесию, он достоверно не может выиграть товар. Следовательно, в терминах приведенной формы для любого покупателя, чей тип меньше установленной резервной цены, ожидаемое количество товара равно нулю:

Vv < R, q(v; R) = 0.

4Естественно, в асимметричном случае количество различных функций количества товара будет совпадать с количеством различных распределений типов участников.

10

Причем,

д(и;Д) = д(17;0)=д(г;).

Тогда, учитывая выражение для ожидаемого платежа (1) и 1РУ-модель, можно явно выписать выражение для ожидаемой прибыли аукциониста ШЛ. в зависимости от величины резервной цены Я.

ruj rv

ЕЩп) = Е Y\m{Vi) = N / / sdq(s\ R) dF(v)

геЛГ Jo Jo

= N í í dF(s) v dq(v; R) = N í «(1 -F{v))dq{v). (2) JO Jv JR

Естественно положить за определение оптимальной резервной цены значение R*, доставляющее наибольшее значение ожидаемой прибыли:

Я* = argmaxE ЩЯ).

R

Задачу оптимизации дохода будем называть регулярной, если функция ожидаемого дохода Е72.(7?) имеет только одну точку максимума. Случай иррегулярных задач освещается в параграфе 1.3.3. Далее, здесь будет предполагаться регулярность рассматриваемых задач.

Определение (Эффективность резервной цены). Эффективностью резервной цены в аукционе будем называть величину относительного прироста ожидаемой прибыли аукциониста с установленной оптимальной резервной ценой от ожидаемой прибыли в аукционе без резервной цены,

Е7г(Д*)

(3)

Для описания конкретного аукциона в работе предлагается рассматривать аукцион как пару {Л, С), где первая часть пары Л есть описание правил размещения и платежей, т.е. формат аукциона, а вторая — С, контекст в котором данный аукцион проводится. При этом сам контекст предлагается описывать как тройку С = (а,Л/", F(v)), состоящую из вектора качества товаров, множества участников и функции распределения их типов5.

Оптимальный аукцион приносит доход аукционисту за счет двух компонент: оптимально установленной резервной цены и уровня конкуренции. В [McAfee&McMillan'96] прибыль от ненулевой резервной цены объесняется как реализация переговорной силы (bargaining power) через право отказать в продаже объекта, которая интерпретируется как аналог искусственного участника с соответствующей ставкой среди естественной конкуренции. Обе компоненты

5В ситуации асимметричных аукционов необходимо обобщить определение контекста, где вместо одной функции распределения F должно указываться отображение I■',(!:)}.

11

направлены на увеличение дохода, но известным фактом считается правило: чем выше уровень конкуренции, тем меньше эффект от резервной цены.

Обширный анализ современной литературы по теории аукционов показал, что понятие конкуренции в аукционе четко не определено. Что зачастую под конкуренцией авторы понимают лишь число конкурентов в аукционе. Для данного исследования подобного рода определения недостаточно. Поэтому я предложил собственное определение конкуренции в аукционе, через понятие «давление конкуренции».

Каждый покупатель обладает некоторым типом V (V = у) — его ценность от обладания единицей товара. Назовем средней стоимостью единицы товара для покупателя с типом V отношение ожидаемого платежа к ожидаемому количеству товара:

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

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

Определение (давление конкуренции). Давлением конкуренции ср(ь) назовем производную функции среднего платежа за единицу товара, то есть

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

Определение. Будем говорить, что аукцион (А\,С\) доминирует аукцион (Л'2,Со) в смысле давления конкуренции и обозначать {А\,С\) Уср (Ач,С-Д

(4)

и(у) = V — рр(у).

(5)

ср(у) = —рр{у) или рр(у) = Ср{1)

если

ср\(у) > Ср2{у).

Определение. Будем говорить, что аукцион ,Су) доминирует аукцион (Л2,С2) в смысле уровня конкуренции и обозначать {Л\,С\) >-С1 (Л2,С2), если отношение их функций ожидаемого количества товара Ч\{у)/ц2{у) не убывает по V.

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

Лемма 1.

1. {А1,С1)уср(А2,С2) => (ЛиСг) (Л2,С2).

2. (ЛиС\) Уы (Л,С2) => Уи, здл(и) >рр2(ь).

Теорема 1.

(ЛиСу) ус1 {Л2,С2) => Р1ЛМ <р[Л2,,С2].

Важной характеристикой контекста аукциона является вектор качества товаров ос. Для того, чтобы продемонстрировать пример, какие свойства в аукционе влияют на уровень конкуренции, рассмотрим случай, когда вектор качества товаров можно описать тройкой параметров, (Дг. К,д),:

а = (аь ... ,адг), Ч/г > К, аг- = О,

Уг < К, а<+1 =дщ (0 < д < 1).

Таким образом, вектор ее, определенный через тройку (АГ, К, д), описывает случай аукциона по продаже К товаров с N покупателями, где качество товаров дисконтируется на постоянный знаменатель д.

Определение.

Пусть даны два контекста аукциона, Су = («1, Л/^, Р(ъ>)) и С2 = (а2,ЛГ2,Г{ь)), гдесху = (Ыу, Ку,ду) и а2 = (М2,К2,д2).

Тогда будем говорить, что Су доминирует С2 по вектору качества товаров (Су С2), если выполнено одно из следующих условий:

СО ^ > Кг = К2; <п = д2-

(и) АГ1 = Д'2. Ку < К2, ду = д2-(т) Му = А^ Ку = К2, (]у < д,\

Лемма 2.

С!УаС2 => {Л,С1)^с1{Л,С2).

Важной частью данной главы является параграф 1.3.3, где обсуждается данная проблема в контексте иррегулярности задачи и дается определение важному понятию отношения над участниками быть сильнее6 (обозначается как

^Ьг)-

Во второй главе представлены основные теоретические результаты по оптимизации аукциона второй цены и его обобщения с помощью резервной цены при различных случаях доступной аукционисту информации про силу участников. Для простоты изложения и выкладок предполагается существование лишь двух различных классов участников, N — Ми, и М8„ причем Уг £ЛГ,Ц~ ВД, где Д € ^

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

(Б) Детальная информация (эталон). Продавец обладает информацией про все детали: знает точные распределения ценностей каждого участника, то есть для любого г аукционист достоверно знает вид функции Гг.

(Ап) Анонимизированная информация. Аукционист лишь знает вид распределений сильного и слабого участников, то есть вид функций и Кроме того, аукционист знает общее число слабых участников Лг„, и сильных Лг,,

Лг = +

(Рг) Вероятностная информация. Аукционист знает, что с заданной вероятностью р конкретный участник может быть из сильного класса, то есть

Уг елг, р = ¥{1еЛГ3}.

(Ау) Усредненная информация (симметризованная). Данный случай соответствует модели, где продавец считает, что все участники симметричны с одним и тем же распределением ценностей Р,\,,('о).

Теорема 2. Оптимальные значения резервных цен и значения ожидаемой прибыли при них совпадают в случаях (Б) и (Ап),

В° = Я,Ап, ЩП°] =Е[7гЛп],

6Данное понятие определяется в различных вариантах с помощью соответствующих понятий стохастического доминирования для случайных величин V* — типов участников. В работе используется вариант определения, построенный на основе понятия доминирования в смысле функции отказов или Ьг-с.д.

и также совпадают для пары случаев (Рг) и (А\'),

ЯРг = ЩПРг) = Е[ПЛу].

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

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

Теорема 3. Пусть ЯАп и ЯЛу есть оптимальные значения резервных цен для анонимного и усредненного случаев соответственно. Кроме того, пусть /?,,. и /?., есть оптимальные резервные цены для моделей, в которых все участники слабые или сильные соответственно.

Если предположить, что ;>=/,,■ Ру_, и что РЛ,, регулярна, то можно показать, что

Л» < ЯЛу < ЯЛп < Яз-

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

В параграфе 2.3 выводятся обобщения данного результата сравнения на случаи многотоварных аукционов с единичным спросом. Наиболее простое обобщение аукциона второй цены на случай К объектов для продажи представляет собой аукцион равномерной цены.

Теорема 4. Пусть иЯ^1' есть оптимальные значения резервных цен для анонимизированного и симметризованного случаев соответственно в аукционе равномерной цены с К идентичными объектами на продажу. Тогда, для любого 1 < К < N имеем,

= ЯА\

и, более того, для любого 1 < К < N — 1,

Дл" > > ямп =

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

15

Например, для обобщенного аукциона второй цены с К рекламными позициями в предположении, что участники следуют равновесию, описанному в работе [Ес1е1тап й а1.'07], с платежами эквивалентными аукциону Викри можно получить следующий результат.

Теорема 5. Пусть и есть оптимальные значения резервных цен в

обобщенном аукционе второй цены с К объектами на продажу и вектором качества а в случаях (Ли) и (Ап) соответственно.

Тогда для любого числа объектов 1 < К < N имеем

туАу _ г>АУ

ла,К ~ п 1

более того, для любого 1 < К < N — 1,

г>Ап \ г>Ап \ г>Ап \ г>Ау Ка,К > На,К+1 - V - К ■

При этом, если сравнить с оптимальной резервной ценой /?д-п аукциона равномерной цены, который соответствует вектору а„ = ПЛ^НЮ.Д то

к

имеем

туАп г?Ап ла,К лК ■

Таким образом, для всех рассмотренных аукционов устанавливается значимость информации про точное число сильных покупателей для задачи оптимизации ожидаемой прибыли. Суммарно все результаты полученных теорем представлены на Рис. 2, где явно виден дополнительный эффект убывания возможной разницы в оптимальных резервных ценах с ростом числа объектов на продажу.

Глава 3 посвещена практическим вопросам возможной оптимизации позиционных аукционов с помощью резервных цен.

В параграфе 3.1 описываются правила аукциона для продажи рекламы в компании «Яндекс». Дается интерпретация рекламе на поисковом интернет-сервисе как модели с тремя типами участников: компания-поисковик, рекламодатели и интернет-пользователи — чьи интересы должны быть учтены при возможном изменении правил аукциона.

В параграфе 3.2 описаны существующие подходы к восстановлению неизвестных функций распределений. Один из подходов описан на примере реализации авторской модификации, реализованный в комплексе программ в рамках проекта оптимизации рекламных аукционов компании «Яндекс». Данная модификация отличается от первоначальной аналога из [0я1го\'яку&8с11\уаг7'09] следующими моментами:

0.80 0.75

и

i. 0.70

(U

щ 0.65

numerical results

0J

0.60

1.36

о 1,34 2

^ 1.32

0J

Э

¡1.30

1.28 1.3

1.7 с

1.8

*—* averaged - • anonymous

.. - ■

... -

---

3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2 с

1.9

2.0

♦—♦ averaged — anonymous 1 -

j

(а) Пример равномерных распределений: = £/[0,1], ^ = Л/[0, с], для с > 1. Здесь пз — Пш — 1 — то есть рассматривается аукцион с 2 асимметричными участниками.

0.90

0.85

0J U 0.80

а. 0.75

CD

г 01 0.70

a 0.65

0.60

0.55

1.07

1.06

_о 1.05

га

U1 1.04

01

С 1.03

0>

> г; 1.02

1.01

1.00

numerical results

- *—» averaged - - anonymous . 1

...

;___*------ 1 1

10 12 с

20

. ♦—♦ averaged . — anonymous i i

__f-- t t— ? !

10

12

14

16

18

(Ь) Пример степенных распределений: Рп(х) = хЧс, Рв(х) = хс, х е (0,1). Здесь Пц = 1, пю = 5 — то есть рассматривается аукцион с 6 участниками: 1 сильным и 5

слабых.

Рис. 1: Результаты численных экспериментов. 17

Рис. 2: Оптимальные резервные цены для аукциона равномерной цены и позиционного аукциона в зависимости от числа объектов на продажу.

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

2. Для восстановления функции распределения с помощью обобщенного метода моментов использовался расширенный набор статистик;

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

4. В качестве метода оценки использовалась панельная регрессия, что в итоге позволило за короткие сроки эксперимента получить значимые оценки эффектов.

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

Точность реализованного подхода на реальных аукционах компании «Яндекс» была сравнена с альтернативной. Альтернативный метод, описанный в [Кеу&Рт'11], смог показать лучшую точность лишь для восстановления индивидуальных ценностей. Попытка реализовать аналог сравнимый с алгоритмом из [051гоУ5ку&БсЬ\¥агг'09] показала, что точности обоих методов одинаково не идеальны.

На Рисунке 3 представлены результаты вычисления средней позиции по данным согласно двум описанным моделям: OstN - аналог модели Островско-

18

3.0

2.5 2.0 1.5 1.0

1.0 1.5 2.0 2.5 3.0

Рис. 3: Восстановленные по ставкам позиции в среднем, согласно двум моделям: OstN -атворская модель на базе [C)strovsky&Schwarz'09], a PinCl - модель [Key&Pin'll], real -значения, соответствующие реальным средним позициям посчитанным по данным. Ось ординат показывает предсказанную, согласно модели, позицию в среднем, а ось абсцисс отображает реальную среднюю позицию.

го и Швраца, a PinCl - немного модифицированная для корректного сравнения модель Пина и Кея. Небольшая модификация последней модели касалась тех данных, на которых она настраивалась, и была необходима для корректного сравнения подходов. Из результатов видно, что качество моделей далеко от идеального и здесь есть обширное поле для дальнейшего улучшения методов. Нельзя выделить лучший из этих двух, они оба отклоняются от реальных значений, причем в разные стороны: согласно подходу Островского, восстановленные позиции тяготели к более низким местам, чем в реальных данных, а в методе Пина - наоборот, к завышению позиций.

Подобная проблема с точностью вычислений может объясняться существованием асимметричных рекламодателей, так как оба подхода основаны на предположении о симметричности. Для возможного обнаружения асимметричности рекламодателей в параграфе 3.3 предлагается описание статистического теста, основанного на обобщении для позиционного аукциона теста из [Haily&Tamer'03] для однотоварного английского аукциона.

Для построения такого теста необходимо дополнительно сделать следующие два предположения:

(al) Участники не делают ставок, которые были бы больше их ценностей.

* * real ♦ ♦ PinCl ■ • OstN *

* * * *

4 t у * у

* < * «гТ • + S * % ♦ • -

(а2) Участники не позволят конкуренту получить желаемый товар по цене, которую они сами могли бы заплатить.

Исходя их этих двух предположений, Хайли и Тамер для однотоварного английского аукциона построили нижнюю Ь\ и верхнюю Fjj границы для родительского распределения F в предположении симметричности участников. В их работе также доказана асимптотическая нормальность построенных ими оценок. При этом нарушение свойства упорядоченности, Vu Fi{v) < Fjj(v), может служить критерием невыполнения предположения о симметричности модели аукциона в рамках IPV модели. Таким образом, если принять за истину модель независимых частных ценностей, то данный критерий может служить статистическим тестом на нарушение предположения симметричности участников.

Для случая позиционного аукциона можно обобщить этот тест. В параграфе 3.3.2 детально описаны предложенные автором обобщения для оценок Fl и Ff/, которые также сохраняют свойство асимптотической нормальности.

В заключении приведены основные результаты и выводы диссертации.

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

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

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

4. Проведен эмпирический сравнительный анализ существующих методов структурной эконометрики многотоварных аукционов.

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

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

Публикации автора по теме диссертации

1. Топинский В.А. Эффективность резервной цены и давление конкуренции в аукционах // Управление большими системами. 2014. № 50. С. 110-142.

2. Оптимизация прогноза вероятности посещения контекстной рекламы в поисковой системе «Яндекс» / К.Е. Бауман, A.H. Корнетова, В.А. Топинский [и др.] // Научно-техническая информация. Сер.2, Информационные процессы и системы. 2013. № 4. С. 1-8.

3. Chervonenkis Alexey, Sorokina Anna, Topinsky Valery. Optimization of ads allocation in sponsored search // Proceedings of the 22nd international conference on World Wide Web companion. WWW '13 Companion. International World Wide Web Conferences Steering Committee, 2013. C. 121-122.

4. Kolesnikov Alexander, Logachev Yury, Topinskiy Valeriy. Predicting CTR of new ads via click prediction // Proceedings of the 21st ACM international conference on Information and knowledge management. CIKM '12. ACM, 2012. C. 2547-2550.

5. Trofimov Ilya, Kornetova Anna, Topinskiy Valery. Using boosted trees for click-through rate prediction for sponsored search // Proceedings of the Sixth International Workshop on Data Mining for Online Advertising and Internet Economy. ADKDD '12. ACM, 2012. C. 1-6.

В совместных работах Топинскому В.А. принадлежат основные результаты и идеи относительно алгоритмов размещения объявлений в рекламных аук-

21

ционах, соавторы помогали в редактировании текста, проведении экспериментов и построении улучшенных моделей оценки качества объявлений.

Подписано в печать 23.10.2014 г. Формат А4/2 Бумага офсетная. Печать цифровая. Тираж 100 Экз. Заказ № 4674-10-14 Типография ООО "Ай-клуб" (Печатный салон 119146, г. Москва, Комсомольский пр-кт, д Тел. 8-495-782-88-39