静5青年讲座 | Pricing Query Complexity of Revenue Maximization

Pricing Query Complexity of Revenue Maximization

报告人

Dr. Yifeng Teng, Google Research

时  间

2023年4月27日 星期四 16:00

地  点

静园五院204

Host

李彤阳 助理教授

 Abstract

The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price; then for a fresh sample from the value distribution, we learn a binary signal indicating whether the buyer's value is larger than the proposed price. How many pricing queries are needed to estimate a given parameter of the underlying distribution?

Previous known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within a small statistical (Levy) distance requires strictly more pricing queries than estimating the optimal reserve. For both problems of learning an approximately optimal reserve price, and learning the entire distribution within a small statistical distance, we give tight upper and lower bounds on the number of pricing queries necessary, for MHR, regular, and general distributions.

This is based on joint work with Renato Paes Leme, Balasubramanian Sivan, and Pratik Worah.

Biography

Yifeng Teng is a research scientist in the Algorithms and Optimization team at Google Research. He received his M.S. and Ph.D. degrees from the Department of Computer Sciences, University of Wisconsin-Madison; and his B.Eng degree from the Institute for Interdisciplinary Information Sciences, Tsinghua University. He is broadly interested in the intersection of theoretical computer science and economics, in particular algorithmic game theory, online algorithms, learning theory, and their applications to real-world mechanism design.

往 期 讲 座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报