Yifeng Teng

Yifeng Teng

Auto-generated profile, based on publicly available information

Yifeng Teng

Google Research, New York, USA

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 July 2023
Verified
Conference Paper
Open access
PDPaul Dütting
Paul Dütting
EGEvangelia Gergatsouli
Evangelia Gergatsouli
RRRojin Rezvan
Rojin Rezvan
YTYifeng Teng
Yifeng Teng
ATAlexandros Tsigonias-Dimitriadis
Alexandros Tsigonias-Dimitriadis
We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing a value at each step, the decision-maker has to either select it and stop or irrevocably discard it. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one. In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark; the online optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. As a warm-up, we present a quasi-polynomial time approximation scheme (QPTAS) achieving a (1 − ε)-approximation in O(npoly log n· f(ε)) time through careful discretization and non-trivial bundling processes. Using the toolbox developed for the QPTAS, coupled with a novel frontloading technique that enables us to reduce the number of decisions we need to make, we are able to remove the dependence on n in the exponent and obtain a polynomial time approximation scheme (PTAS) for this problem.

7 July 2023
Verified
Conference Paper
Open access
RLRenato Pase Leme
Renato Pase Leme
BSBalasubramanian Sivan
Balasubramanian Sivan
YTYifeng Teng
Yifeng Teng
PWPratik Worah
Pratik Worah

13 May 2024
Verified
Conference Paper
Open access
YDYuan Deng
Yuan Deng
JMJieming Mao
Jieming Mao
VMVahab Mirrokni
Vahab Mirrokni
YTYifeng Teng
Yifeng Teng
SZSong Zuo
Song Zuo
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.

2 July 2025
Verified
Conference Paper
Open access
YTYifeng Teng
Yifeng Teng
YWYifan Wang
Yifan Wang

31 December 2023
Verified
Book Chapter
Closed access
PDF file
SCShuchi Chawla
Shuchi Chawla
RRRojin Rezvan
Rojin Rezvan
YTYifeng Teng
Yifeng Teng
CTChristos Tzamos
Christos Tzamos

30 April 2023
Verified
Conference Paper
Open access
ZTZihan Tan
Zihan Tan
YTYifeng Teng
Yifeng Teng
MZMingfei Zhao
Mingfei Zhao
We study the worst-case welfare of item pricing in the tollbooth problem. The problem was first introduced by Guruswami et al. [27], and is a special case of the combinatorial auction in which (i) each of the m items in the auction is an edge of some underlying graph; and (ii) each of the n buyers is single-minded and only interested in buying all edges of a single path. We consider the competitive ratio between the hindsight optimal welfare and the optimal worst-case welfare among all item-pricing mechanisms, when the order of the arriving buyers is adversarial. We assume that buyers own the tie-breaking power, i.e. they can choose whether or not to buy the demand path at 0 utility. We prove a tight competitive ratio of 3/2 when the underlying graph is a single path (also known as the highway problem), whereas item-pricing can achieve the hindsight optimal if the seller is allowed to choose a proper tie-breaking rule to maximize the welfare [6, 11]. Moreover, we prove an O(1) upper bound of competitive ratio when the underlying graph is a tree. For general graphs, we prove an Ω(m1/8) lower bound of the competitive ratio. We show that an mΩ(1) competitive ratio is unavoidable even if the graph is a grid, or if the capacity of every edge is augmented by a constant factor c. The results hold even if the seller has tie-breaking power.