Диссертация (Резервные цены в асимметричных аукционах), страница 2

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

Был разработан комплекс программ для оптимизации рекламных аукционов в компании«Яндекс» и проведены эксперименты, показавшие значительное увеличение дохода аукционов.Достоверность изложенных в работе результатов подтверждена строгими математическими доказательствами теоретических утверждений, их верификацией с помощью модельных экспериментов и экспериментальной проверкойметодов оптимизации на реальных и синтетических данных.Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях:1. The Sixth International Workshop on Data Mining for Online Advertising andInternet Economy, ACM SIGKDD 2012.

Пекин, Китай, 2012.2. The 21st ACM International Conference on Information and KnowledgeManagement. Мауи, Гавайи, США, 2012.3. 22nd International World Wide Web Conference. Рио-де-Жанейро, Бразилия,2013.64. 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 SocialScience Associations Annual Meeting.

Филадельфия, США, 2014.8. Econometric Society Australasian Meeting, 2014. Хобарт, Австралия, 2014.Публикации. Основные результаты по теме диссертации изложены в 5печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 3— в рецензируемых трудах международных конференций.Содержание работыВо введении обоснована актуальность темы, сформулированы цели и задачи исследования, научная новизна, теоретическая и практическая значимостьполученных результатов, основные положения, выносимые на защиту, а такжеприведены данные о структуре диссертации.В первой главе описываются основные результаты и определения теории аукционов и оптимальных механизмов, используемые в диссертации.

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

Т.е. предполагается, что в торгах участвует рискнейтральных покупателей; пусть = {1, . . . , } есть множество покупателей,а индекс 0 зарезервирован за аукционистом. Каждый покупатель ∈ определяет ценность для выставленного на продажу объекта (данный случай однотоварного аукциона будет обобщен ниже с помощью понятия вектора качества7товаров). С точки зрения аукциониста и конкурентов покупателя его ценность есть случайная величина с некоторой известной функцией распределения,то есть ∼ (), : [0, ] → [0, 1]. Тогда предположение о независимыхчастных ценностях есть ни что иное, как предположения: (i) о совокупной независимости случайных величин ∀ ∈ , (ii) каждый участник торгов точнознает значение реализации своей ценности = и (iii) функции распределений ценностей всех участников ∀ ∈ и значение ценности аукциониста0 от обладания объектом в случае несостоявшейся продажи1 являются общеизвестными.

Случайный вектор ценностей покупателей будем обозначать как⃗ , а его конкретную реализацию – ⃗ , причем пространство возможных значений есть декартово произведение интервалов [0, ], которое для краткости будемобозначать через . Индекс −, например, − , используется для обозначениясоответствующих величин, относящихся ко всем участникам аукциона кромеучастника .Основной решаемой задачей в работе является оптимизация аукциона всмысле максимизации ожидаемой прибыли аукциониста.В рамках теоретико-игровой интерпретации аукционов участники делают свои ставки согласно некоторым стратегиям, которые могут формироватьравновесие. В некоторых случаях, например, при закрытом формате аукциона,равновесную стратегию участника удается описать в виде отображения, которое определяет его ставку в зависимости от значения его ценности и его знанияо других участниках.

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

Остается лишь определитьправило, согласно которому участники будут платить.Прежде чем завершить формальное описание стандартных аукционов,определим выше упомянутый вектор качества товаров для описания случая многотоварности в условиях единичного спроса2 .12Т.е. ценность аукциониста 0 = 0 есть вырожденная случайная величина.Т.е. предполагается, что любой покупатель заинтересован в приобретении лишь одного объекта продажи.8Определение (вектор качества товаров). Для аукциона с товарами и покупателями определим вектор качества товаров ∈ R следующим образом.1.

1 = 1;нормирование относительно наиболее качественного.2. ≥ +1 ;товары упорядочены по убыванию качества.3. +1 = · · · = = 0;отсутствие товара эквивалентно товару с нулевым качеством.Таким образом, вектор качества порождает естественный порядок на множестве товаров = {1, . . . , }.

При этом ценность покупателя ∈ длятовара с номером определяется как произведение:, = · ,где конкретное значение = , ценности за единицу товара, определяет типпокупателя3 .Таким образом, с помощью вектора качества товаров покрываются случаи:– = 1, однотоварного аукциона;– 1 = · · · = , аукциона с единичным спросом и одинаковыми товарами;– ∃ < : > +1 > 0, аукциона с единичным спросом и неоднороднымитоварами или позиционный аукцион.В силу известного в литературе принципа откровенности (см.[Krishna’09,The Revelation Principle]) можно ограничиться рассмотрением лишьаукционов с равновесием «правдиво сообщать свой тип».

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

Но в случаемноготоварных аукционов удобно во избежание путаницы использовать термин тип для указания ценностиучастника для единицы товара максимального качества.9он может выиграть в ходе данного аукциона. То есть() =∑︁ · (),=1где () есть вероятность события, заключающегося в том, что тип = оказался -ым по величине типом среди всех типов участников, то есть−1 () = −1 () − .−1 (1 − ())Здесь неявно предполагается симметрия среди участников аукциона, тоесть одинаковость функций распределения их типов, = () ∀ ∈ . Ниже,при рассмотрении асимметричных аукционов, у всех обозначений будет явноуказан индекс, определяющий, относительно какого участника рассматриваетсяданный термин.Название «количество товара» в определении оправдано тем фактом, чтотовар № с качеством можно воспринимать как часть или долю товара№1 с наибольшим качеством 1 = 1.

То есть для каждого покупателя с типом = значение () есть его ожидание того, какое количество товара (часть отмаксимального качества) он может получить в ходе аукциона. Согласно теоремеоб эквивалентности по доходу (см. [Krishna’09, Revenue Equivalence]), функцияожидаемого платежа () участника с типом = полностью определеначерез функцию количества товара:∫︁ ∫︁ () = · () −() = ().(1)00Таким образом, удалось свести описание симметричного аукциона к одной функции4 количества товара (), что вполне достаточно для решаемойздесь задачи оптимизации ожидаемой прибыли от аукциона, т.к. данная задачарешается аукционистом в среднем.

Подобное описание аукциона принято называть приведенной формой.Резервной ценой называется цена, ниже которой продажа товара невозможна. То есть, если некоторый покупатель имеет тип < , то, согласноправилам аукциона и играемому равновесию, он достоверно не может выигратьтовар. Следовательно, в терминах приведенной формы для любого покупателя,чей тип меньше установленной резервной цены, ожидаемое количество товараравно нулю:∀ < , (; ) = 0.4Естественно, в асимметричном случае количество различных функций количества товара будет совпадать сколичеством различных распределений типов участников.10Причем,∀ ≥ ,(; ) = (; 0) ≡ ().Тогда, учитывая выражение для ожидаемого платежа (1) и IPV-модель,можно явно выписать выражение для ожидаемой прибыли аукциониста Eℛ взависимости от величины резервной цены .Eℛ() = E∑︁∫︁∫︁( ) = (; ) ()∈∫︁∫︁00∫︁ () (; ) = =0(1 − ()) ().

(2)Естественно положить за определение оптимальной резервной цены значение ⋆ , доставляющее наибольшее значение ожидаемой прибыли:⋆ = arg max Eℛ().Задачу оптимизации дохода будем называть регулярной, если функцияожидаемого дохода Eℛ() имеет только одну точку максимума. Случай иррегулярных задач освещается в параграфе 1.3.3. Далее, здесь будет предполагатьсярегулярность рассматриваемых задач.Определение (Эффективность резервной цены). Эффективностью резервнойцены в аукционе будем называть величину относительного прироста ожидаемой прибыли аукциониста с установленной оптимальной резервной ценой отожидаемой прибыли в аукционе без резервной цены,=Eℛ(⋆ )− 1.Eℛ(0)(3)Для описания конкретного аукциона в работе предлагается рассматривать аукцион как пару ⟨, ⟩, где первая часть пары есть описание правилразмещения и платежей, т.е.

формат аукциона, а вторая — , контекст в которомданный аукцион проводится. При этом сам контекст предлагается описывать кактройку = ⟨, , ()⟩, состоящую из вектора качества товаров, множестваучастников и функции распределения их типов5 .Оптимальный аукцион приносит доход аукционисту за счет двух компонент: оптимально установленной резервной цены и уровня конкуренции. В[McAfee&McMillan’96] прибыль от ненулевой резервной цены объесняется какреализация переговорной силы (bargaining power) через право отказать в продаже объекта, которая интерпретируется как аналог искусственного участникас соответствующей ставкой среди естественной конкуренции. Обе компоненты5В ситуации асимметричных аукционов необходимо обобщить определение контекста, где вместо однойфункции распределения должно указываться отображение { ∈ ↦→ ()}.11направлены на увеличение дохода, но известным фактом считается правило: чемвыше уровень конкуренции, тем меньше эффект от резервной цены.Обширный анализ современной литературы по теории аукционов показал, что понятие конкуренции в аукционе четко не определено.