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
Sort By
Non-uniform Bid-scaling and Equilibria for Different Auctions: An Empirical Study
Proceedings of the ACM on Web Conference 2024, 256–266
Preview abstract
In recent years, the growing adoption of autobidding has motivated the study of auction design with value-maximizing auto-bidders. It is known that under mild assumptions, uniform bid-scaling is an optimal bidding strategy in truthful auctions, e.g., Vickrey-Clarke-Groves auction (VCG), and the price of anarchy for VCG is 2. However, for other auction formats like First-Price Auction (FPA) and Generalized Second-Price auction (GSP), uniform bid-scaling may not be an optimal bidding strategy, and bidders have incentives to deviate to adopt strategies with non-uniform bid-scaling. Moreover, FPA can achieve optimal welfare if restricted to uniform bid-scaling, while its price of anarchy becomes 2 when non-uniform bid-scaling strategies are allowed.
All these price of anarchy results have been focused on welfare approximation in the worst-case scenarios. To complement theoretical understandings, we empirically study how different auction formats (FPA, GSP, VCG) with different levels of non-uniform bid-scaling perform in an autobidding world with a synthetic dataset for auctions. Our empirical findings include: * For both uniform bid-scaling and non-uniform bid-scaling, FPA is better than GSP and GSP is better than VCG in terms of both welfare and profit; * A higher level of non-uniform bid-scaling leads to lower welfare performance in both FPA and GSP, while different levels of non-uniform bid-scaling have no effect in VCG. Our methodology of synthetic data generation may be of independent interest.
View details
Preview abstract
In this paper, we investigate a problem of \emph{actively} learning threshold in latent space, where the \emph{unknown} reward $g(\gamma, v)$ depends on the proposed threshold $\gamma$ and latent value $v$ and it can be \emph{only} achieved if the threshold is lower than or equal to the \emph{unknown} latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring, etc. We first characterize the query complexity of learning a threshold with the expected reward at most $\eps$ smaller than the optimum and prove that the number of queries needed can be infinitely large even when $g(\gamma, v)$ is monotone with respect to both $\gamma$ and $v$. On the positive side, we provide a tight query complexity $\Tilde{\Theta}(1/\eps^3)$ when $g$ is monotone and the CDF of value distribution is Lipschitz. Moreover, we show a tight $\Tilde{\Theta}(1/\eps^3)$ query complexity can be achieved as long as $g$ satisfies one-sided Lipschitzness, which provides a complete characterization for this problem. Finally, we extend this model to an online learning setting and demonstrate a tight $\Theta(T^{2/3})$ regret bound using continuous-arm bandit techniques and the aforementioned query complexity results.
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
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
