9 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…
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Î…
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…
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…
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…