Pinyan Lu

Pinyan Lu

Auto-generated profile, based on publicly available information

Pinyan Lu

Shanghai University of Finance and Economics China

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

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

Representative Publications

View All Publications
8 July 2024
Verified
Conference Paper
Open access
PLPinyan Lu
Pinyan Lu
ZWZongqi Wan
Zongqi Wan
JZJialin Zhang
Jialin Zhang
The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper [Goldberg et al, 2001], they introduce the competitive analysis framework of online algorithm design into the traditional revenue-maximizing auction design problem. While the competitive analysis framework only cares about the worst-case bound, a growing body of work in the online algorithm community studies the learning-augmented framework. In this framework, designers are allowed to leverage imperfect machine-learned predictions of unknown information and pursue better theoretical guarantees when the prediction is accurate(consistency). Meanwhile, designers also need to maintain a nearly-optimal worst-case ratio(robustness). In this work, we revisit the competitive auctions in the learning-augmented setting. We leverage the imperfect predictions of the private value of the bidders and design the learning-augmented mechanisms for several competitive auctions with different constraints, including: digital good auctions, limited-supply auctions, and general downward-closed permutation environments. We also design the learning-augmented mechanism for online auctions. For all these auction environments, our mechanisms enjoy 1-consistency against the strongest benchmark OPT. In contrast, it is impossible to achieve O(1)-competitiveness against OPT without predictions. At the same time, our mechanisms also maintain the O(1)-robustness against all benchmarks considered in the traditional competitive analysis, including ℱ(2), maxV, and EFO(2). Considering the possible inaccuracy of the predictions, we provide a reduction that transforms our learning-augmented mechanisms into an error-tolerant version, which enables the learning-augmented mechanism to ensure satisfactory revenue in scenarios where the prediction error is moderate. We also prove a 3 robustness ratio lower bound for mechanisms with perfect consistency. The lower bound is strictly greater than the optimal 2.42 competitive ratio of digital good auctions, showing the impossibility of maintaining the optimal worst-case bound with perfect consistency.

14 October 2023 in Journal of the ACM
Verified
Journal Article
Open access
YJYaonan Jin
Yaonan Jin
PLPinyan Lu
Pinyan Lu
We prove that the PoA of First Price Auctions is 1-1/ e 2 ≈ 0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

19 August 2017
Verified
Book Chapter
Closed access
PDF file
PLPinyan Lu
Pinyan Lu
TXTao Xiao
Tao Xiao

8 July 2024
Verified
Conference Paper
Open access
HFHu Fu
Hu Fu
PLPinyan Lu
Pinyan Lu
ZTZhihao Gavin Tang
Zhihao Gavin Tang
HWHongxun Wu
Hongxun Wu
JWJinzhao Wu
Jinzhao Wu
QZQianfan Zhang
Qianfan Zhang
The classical prophet inequalities problem introduced by Krengel and Sucheston [1977, 1978] assumed complete knowledge of distributions. However, such an assumption may be unrealistic both in practice and for some applications. We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, no constant-factor competitive algorithm with even a sublinear number of samples was known for general matroids. Adding more to the stake, the single-sample version of the question for general matroids has close (two-way) connections with the long-standing matroid secretary conjecture. In this work, we give a (1/4 - ε)-competitive matroid prophet inequality with only Oε (poly log n) samples. Our algorithm consists of two parts: (i) a novel quantile-based reduction from matroid prophet inequalities to online contention resolution schemes (OCRSs) with Oε(log n) samples, and (ii) a (1/4 - ε)-selectable matroid OCRS with Oε (poly log n) samples which carefully addresses an adaptivity challenge. A full version of this paper can be found at https://arxiv.org/abs/2406.12799.


22 June 2020 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
JCJin-Yi Cai
Jin-Yi Cai
PLPinyan Lu
Pinyan Lu
MXMingji Xia
Mingji Xia