Проектирование онлайн-аукционов с использованием непараметрического квантификации неопределённости с приложениями к электронной коммерции

Основная информация

• ID статьи: 2405.07038
• Название: Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce
• Авторы: Jiale Han (UCLA), Xiaowu Dai (UCLA)
• Классификация: cs.GT cs.LG stat.ML
• Время публикации/конференция: К публикации в Journal of the American Statistical Association
• Ссылка на статью: https://arxiv.org/abs/2405.07038

Аннотация

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

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема онлайн-аукционов заключается в проектировании механизмов, совместимых со стимулами, для максимизации дохода платформы при неизвестном распределении стоимостей участников. Это особенно важно в практических приложениях, таких как аукционы eBay и онлайн-реклама.

Важность проблемы

1. Экономическая ценность: Онлайн-аукционы генерируют значительную долю доходов основных платформ
2. Практическая применимость: В реальности распределение стоимостей участников неизвестно, а количество участников неопределённо
3. Гетерогенность: Различные участники и товары имеют различные характеристики, требующие персонализированного подхода

Ограничения существующих методов

1. Предположение о распределении: Классические методы, такие как Myerson (1981), предполагают известное распределение стоимостей участников
2. Фиксированная конфигурация: Предположение о фиксированном наборе участников и товаров
3. Единая резервная цена: Традиционные методы используют унифицированную резервную цену, неспособную обработать гетерогенность
4. Эффективность данных: Существующие методы обучения требуют большого количества образцов для оценки распределений, специфичных для участников

Исследовательская мотивация

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

Основные вклады

1. Предложение механизма COAD: Первая структура, объединяющая конформное предсказание и проектирование аукционов, обеспечивающая непараметрическую квантификацию неопределённости
2. Персонализированные резервные цены: Проектирование персонализированных резервных цен на основе нижних доверительных границ оценок участников, превосходящих традиционные единые резервные цены
3. Интеграция характеристик: Одновременное рассмотрение характеристик участников и товаров, адаптация к гетерогенной среде
4. Теоретические гарантии: Предоставление теоретического анализа совместимости со стимулами и нижних границ дохода
5. Эмпирическая проверка: Проверка эффективности метода на реальных данных eBay

Детальное описание методов

Определение задачи

Входные данные:

• Исторические данные аукциона $D = \{(x_j, z_j, v_j) | j = 1,2,...,N\}$
• Характеристики участника $x^*_i$ и товара $z^*$ в новом аукционе

Выходные данные:

• Правило распределения $a_i(\vec{v}^*, \vec{x}^*, z^*)$
• Правило платежа $p_i(\vec{v}^*, \vec{x}^*, z^*)$

Ограничения: Совместимость со стимулами (IC) и индивидуальная рациональность (IR)

Архитектура модели

1. Регрессионная модель

Предполагается, что стоимость участника следует регрессионной модели: $v = \mu(x, z) + \epsilon$ где $\mu(x, z) = E[v|x, z]$ представляет ожидаемый эффект характеристик на стоимость.

2. Построение конформного интервала предсказания

Для каждого участника $i$ строится интервал предсказания $(1-\alpha)$: $[\hat{v}^L_i, \hat{v}^U_i] = [\hat{\mu}_n(x^*_i, z^*) - S^*, \hat{\mu}_n(x^*_i, z^*) + S^*]$

где $S^*$ определяется методом конформного предсказания, гарантирующим условное покрытие.

3. Псевдовиртуальная стоимость

Определение псевдовиртуальной стоимости: $c_i(v^*_i, x^*_i, z^*) = v^*_i \mathbf{I}\{v^*_i \geq \hat{v}^L_i\}$

4. Механизм COAD

Правило распределения: Товар распределяется участнику с наивысшей псевдовиртуальной стоимостью Правило платежа: Победитель платит минимальную выигрышную ставку $r_i(\vec{v}^*_{-i}, \vec{x}^*, z^*)$

Технические инновации

1. Применение конформного предсказания: Первое применение конформного предсказания в проектировании аукционов, обеспечивающее непараметрическую квантификацию неопределённости
2. Персонализированный механизм: Каждый участник имеет различную резервную цену, основанную на его характеристиках и интервале предсказания
3. Управление характеристиками: Одновременное использование характеристик участников и товаров, адаптация к гетерогенной среде
4. Совместимость с машинным обучением: Возможность интеграции с различными алгоритмами МО (случайные леса, нейронные сети и т.д.)

Экспериментальная установка

Наборы данных

1. Данные eBay: 149 аукционов Palm Pilot M515 PDA продолжительностью 7 дней, 813 исторических записей
2. Конфигурация характеристик:
   • Характеристики товара: идентификация продавца (3 основных продавца)
   • Характеристики участника: время ставки, рейтинг, средняя историческая ставка

Метрики оценки

• Сравнение среднего дохода
• Вероятность покрытия конформного интервала предсказания
• Производительность при различных объёмах данных

Методы сравнения

1. Аукцион второй цены: Механизм, используемый eBay в настоящее время
2. Эмпирический аукцион Майерсона: Механизм Майерсона, основанный на оценке распределения из исторических данных

Детали реализации

• Уровень недопокрытия: $\alpha = 0.1$
• Разделение данных: обучающие/калибровочные данные составляют по 50%
• Метод регрессии: квадратичная полиномиальная регрессия
• Повторения экспериментов: 1000 раз

Результаты экспериментов

Основные результаты

1. Преимущество в доходе: COAD превосходит базовые методы во всех конфигурациях
2. Эффективность данных: Доход COAD стабильно растёт с увеличением объёма данных
3. Гарантии покрытия: Интервалы конформного предсказания достигают целевого уровня покрытия 90%

Имитационные эксперименты

Эксперименты с нейронными сетями

• Конфигурация: 20-мерные характеристики, 30 типов товаров
• Результаты: Доход COAD растёт с увеличением количества участников, подтверждая теоретические предсказания

Эксперименты с полиномиальной регрессией

• Конфигурация: 100-мерные характеристики, более сложная регрессионная модель
• Результаты: COAD сохраняет преимущество в высокомерных конфигурациях

Анализ робастности

При нарушении основных предположений (независимость данных, ограниченность ошибок) COAD по-прежнему показывает хорошие результаты, демонстрируя практическую применимость метода.

Связанные работы

Оптимальное проектирование аукционов

• Классическая теория: Myerson (1981), Riley & Samuelson (1981)
• Методы обучения: Cole & Roughgarden (2014), Huang et al. (2015)

Обучение резервным ценам

• Единая резервная цена: Cesa-Bianchi et al. (2014), Mohri & Medina (2016)
• Персонализированная резервная цена: Применение Even-Dar et al. (2008) в практических системах

Конформное предсказание

• Теоретические основы: Vovk et al. (2005), Lei et al. (2018)
• Условные гарантии: Методы условного покрытия Gibbs et al. (2025)

Заключение и обсуждение

Основные выводы

1. COAD успешно решает проблему неизвестного распределения в реальных аукционах
2. Персонализированные резервные цены значительно превосходят единые резервные цены
3. Конформное предсказание обеспечивает надёжную квантификацию неопределённости

Ограничения

1. Предположения: Теоретические гарантии зависят от предположений, таких как независимость данных
2. Вычислительная сложность: Требуется построение интервала предсказания для каждого участника
3. Зависимость от характеристик: Производительность метода зависит от качества характеристик

Будущие направления

1. Бюджетные ограничения: Расширение на сценарии с повторяющимся участием и ограниченными бюджетами
2. Динамическая среда: Обработка ситуаций, когда распределение данных изменяется со временем
3. Многотоварные аукционы: Расширение на сложные конфигурации многотоварных аукционов

Глубокая оценка

Преимущества

1. Высокая инновационность: Первое применение конформного предсказания в проектировании аукционов, пионерская работа
2. Полнота теории: Предоставление строгого теоретического анализа совместимости со стимулами и гарантий дохода
3. Высокая практическая ценность: Метод применим к реальным гетерогенным средам, таким как eBay и онлайн-реклама
4. Полнота экспериментов: Включает проверку на реальных данных и всесторонние имитационные эксперименты

Недостатки

1. Ограничения предположений: Некоторые теоретические результаты зависят от сильных предположений независимости
2. Вычислительные издержки: Требуется отдельное построение интервала предсказания для каждого участника
3. Инженерия характеристик: Производительность метода в значительной степени зависит от выбора и качества характеристик

Влияние

1. Академический вклад: Связывает три области — машинное обучение, статистику и экономику
2. Практическая ценность: Предоставляет практическое решение для проектирования аукционов онлайн-платформами
3. Методологическое значение: Демонстрирует потенциал применения конформного предсказания в проектировании механизмов

Применимые сценарии

1. Онлайн-реклама: Торги в реальном времени на платформах Google, Meta и т.д.
2. Электронные аукционы: Аукционы товаров на платформах eBay и т.д.
3. Распределение ресурсов: Общие проблемы проектирования механизмов, требующие обработки неопределённости

Библиография

1. Myerson, R. B. (1981). Optimal auction design. Mathematics of Operations Research, 6(1), 58-73.
2. Gibbs, I., Cherian, J. J., & Candès, E. J. (2025). Conformal prediction with conditional guarantees. Journal of the Royal Statistical Society Series B.
3. Cole, R., & Roughgarden, T. (2014). The sample complexity of revenue maximization. STOC.
4. Even-Dar, E., et al. (2008). Position auctions with bidder-specific minimum prices. WINE.

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