Pricing Query Complexity of Revenue Maximization
- Dr. Yifeng Teng, Google Research
- Time: 2023-04-27 16:00
- Host: Dr. Tongyang Li
- Venue: Room 204, Courtyard No.5, Jingyuan
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.