14 citations · 29 across the 15 of their papers we have counts for
19 papers
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Yaonan Jin, Pinyan Lu
We study revenue maximization in the unit-demand single-buyer setting. Our main result is that \textsf{Uniform-Ironed-Virtual-Value Item Pricing} guarantees a {\em tight} -appro…
Anonymous Pricing in Large Markets
Yaonan Jin, Yingkai Li
We study revenue maximization when a seller offers identical units to ex ante heterogeneous, unit-demand buyers. While anonymous pricing can be worse than optimal i…
Tight Regret Bounds for Bilateral Trade under Semi Feedback
Yaonan Jin
The study of \textit{regret minimization in fixed-price bilateral trade} has received considerable attention in recent research. Previous works [CCC+24a, CCC+24b, AFF24, BCCF24, CJ…
The Query Complexity of Uniform Pricing
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \textit{pricing query complexity} problem in Mechanism Design. The previou…
Fully Dynamic Euclidean k-Means
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad +3
We consider the Euclidean -means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of centers) subje…
Local Search for Clustering in Almost-linear Time
Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou +1
We propose the first \emph{local search} algorithm for Euclidean clustering that attains an -approximation in almost-linear time. Specifically, for Euclidean -Means, our a…
Tight Regret Bounds for Fixed-Price Bilateral Trade
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(…
Beyond Regularity: Simple versus Optimal Mechanisms, Revisited
Yiding Feng, Yaonan Jin
A large proportion of the Bayesian mechanism design literature is restricted to the family of regular distributions [Mye81] or the family of monotone hazard…
The Price of Stability for First Price Auction
Yaonan Jin, Pinyan Lu
This paper establishes the Price of Stability (PoS) for First Price Auctions, for all equilibrium concepts that have been studied in the literature: Bayes Nash Equilibrium $\subset…
First Price Auction is Efficient
Yaonan Jin, Pinyan Lu
We prove that the {\sf PoA} of {\sf First Price Auctions} is , closing the gap between the best known bounds .
Average-Case Subset Balancing Problems
Xi Chen, Yaonan Jin, Tim Randolph +1
Given a set of input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time $O^*…
Fourier growth of structured -polynomials and applications
Jarosław Błasiok, Peter Ivanov, Yaonan Jin +3
We analyze the Fourier growth, i.e. the Fourier weight at level (denoted ), of various well-studied classes of "structured" -polynomials. This stud…
Tight Revenue Gaps among Multi-Unit Mechanisms
Yaonan Jin, Shunhua Jiang, Pinyan Lu +1
This paper considers Bayesian revenue maximization in the -unit setting, where a monopolist seller has copies of an indivisible item and faces unit-demand buyers (whose…
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
Yaonan Jin, Daogao Liu, Zhao Song
The ability to resolve detail in the object that is being imaged, named by resolution, is the core parameter of an imaging system. Super-resolution is a class of techniques that ca…
Learning Reserve Prices in Second-Price Auctions
Yaonan Jin, Pinyan Lu, Tao Xiao
This paper proves the tight sample complexity of {\sf Second-Price Auction with Anonymous Reserve}, up to a logarithmic factor, for each of all the value distribution families stud…
On Asymptotically Tight Tail Bounds for Sums of Geometric and Exponential Random Variables
Yaonan Jin, Yingkai Li, Yining Wang +1
In this note we prove bounds on the upper and lower probability tails of sums of independent geometric or exponentially distributed random variables. We also prove negative results…
Optimal Budget-Feasible Mechanisms for Additive Valuations
Nick Gravin, Yaonan Jin, Pinyan Lu +1
In this paper, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio…
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi +2
We consider two canonical Bayesian mechanism design settings. In the single-item setting, we prove tight approximation ratio for anonymous pricing: compared with Myerson Auction, i…
Tight Revenue Gaps among Simple Mechanisms
Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang +1
We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessari…