Yifeng Teng
I'm a research scientist in the Algorithms and Optimization team at Google Research NYC since Oct 2021. I'm broadly interested in theoretical computer science and its intersection with economics, primarily in algorithmic mechanism design and online algorithms.
Prior to joining Google Research, I received my Ph.D. (2021) and M.S. (2018) in Computer Sciences from University of Wisconsin-Madison, where I was fortunate to be advised by Prof. Shuchi Chawla. Before joining UW-Madison, I received my B.Eng (2015) in Computer Science from Tsinghua University. See my personal webpage https://pages.cs.wisc.edu/~yifengt/ for more about my research.
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Preview abstract
Multi-item mechanisms can be very complex offering many different randomized bundles to the buyer.
Such complexity is thought to be necessary as the revenue gaps between optimal mechanisms and simple mechanisms are unbounded.
Our work shows these gaps do not apply to most natural situations: they require that the mechanism
overcharges the buyer for a bundle while selling individual items at much lower prices. We study revenue maximization under the buy-many constraint: the buyer is allowed to purchase any number of (randomized) bundles as he pleases. The revenue of any buy-many mechanism is at most O(log n) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. No family of mechanisms of subexponential description complexity can achieve better than a logarithmic approximation even for additive valuations.
View details
Pricing Ordered Items
Shuchi Chawla
Rojin Rezvan
Christos Tzamos
ACM Symposium on Theory of Computing (STOC) (2022) (to appear)
Preview abstract
We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O(log n) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O(\sqrt{n}).
Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totally-ordered and a buyer’s value for a bundle depends only on the best item contained from every category.
We show that item-pricing guarantees an O(log k) approximation to the optimal (buy-many) revenue and provide a PTAS for computing the optimal item-pricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NP-hard even when k = 1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable.
View details
No Results Found
