Private Mechanism Design via Quantile Estimation
Authors: Yuanyuan Yang
Tao Xiao
Bhuvesh Kumar
Jamie Heather Morgenstern
Venue: ICLR 2025 Poster (2025)
Keywords: online auctions
differential privacy
mechanism design
Primary area: optimization
TL;DR: we demonstrate how to efficiently learn a near-optimal mechanism with pure privacy from sample data for the single item setting. We further apply this mechanism to online settings involving non-myopic and strategic bidders.

Abstract: We investigate the problem of designing differentially private (DP), revenue-maximizing single item auction. Specifically, we consider broadly applicable settings in mechanism design where agents' valuation distributions are **independent**, **non-identical**, and can be either **bounded** or **unbounded**. Our goal is to design such auctions with **pure**, i.e., $(\epsilon,0)$ privacy in polynomial time. 

In this paper, we propose two computationally efficient auction learning framework that achieves **pure** privacy under bounded and unbounded distribution settings. These frameworks reduces the problem of privately releasing a revenue-maximizing auction to the private estimation of pre-specified quantiles. Our solutions increase the running time by polylog factors compared to the non-private version. As an application, we show how to extend our results to the multi-round online auction setting with non-myopic bidders. To our best knowledge, this paper is the first to efficiently deliver a Myerson auction with **pure** privacy and near-optimal revenue, and the first to provide such auctions for **unbounded** distributions.

Published conference paper at ICLR 2025
DIFFERENTIALLY PRIVATE MECHANISM DESIGN VIA QUANTILE ESTIMATION
Yuanyuan Yang
Tao Xiao
University of Washington yyanghêcs washington. edu
Shanghai Jiao Tong University xt_19920s edu.
Bhuvesh Kumar
Jamie Morgenstern
Snap Inc. bhuvesh@snap.com
University of Washington j ami emmt css, washington.cc edu
ABSTRACT
We investigate the problem of designing differentially private (DP), revenue- maximizing single item auction. Specifically, we consider broadly applicable settings in mechanism design where agents' valuation distributions are indepen- dent, non-identical, and can be either bounded or unbounded. Our goal is to design such auctions with pure, i.e., (c, 0) privacy in polynomial time.
In this paper, we propose two computationally efficient auction learning framework that achieves pure privacy under bounded and unbounded distribution settings. These frameworks reduces the problem of privately releasing revenue-maximizing auction the private estimation of pre-specified quantiles. Our solutions increase the running time by polylog factors compared to the non-private version. As an application, we show how to extend our results to the multi-round online auction setting with non-myopic bidders. To our best knowledge, this paper is the first to efficiently deliver a Myerson auction with pure privacy and near-optimal revenue, and the first to provide such auctions for unbounded distributions.
INTRODUCTION
Though prior-dependent auctions, which adjust parameters based on samples of value distributions, often yield better revenue than prior-independen auctions, they risk leaking information about the bids they were trained upon. To address this issue, differential privacy (DP) offers promising solution (Dwork) 2006 2008; McSherry and Talwar 2007 Pai and Roth 2013), ensuring that single data point minimally affects the algorithm's output, thus preventing inference of specific data point.
We study the problem of learning a single-item auction with near-optimal revenue from samples of independent and non-identical value distributions. In this context, the optimal auction (i.e., Myerson's auction (Myerson 1979)). which relies on value distributions (i.c., deiio-de achieves optimal revenue. However, releasing the learned Myerson's 's auction raises privacy concerns, as the output mechanism may inadvertently reveal sensitive information about the distributions. To provably mitigate this risk, our goal is integrate pure DP into the learning process of such auction.
Pure Differential Privacy. Given two datasets that differ in one data point, i.c., D, D', we say an algorithm A satisfies (e, (app)-appro DP if for any given output s: Pr[A( = s] e [A(D') +5 We say A satisfies pure DP if 5 = O. Pure DP allows no slack in privacy protection, and hence more challenging achieve than approximate DP. Previous attempts (MeSherry and Talwar 2007] Nissim et al.) 2012) to integrate DP with prior-dependent auctions are computationally inefficient or guarantee approximate rather than pure DP. To our knowledge, no algorithm guarantees pure DP for Myerson's 's auction in polynomial time.
Efficiency. Incorporating DP into the mechanism often sacrifices efficiency, as achieving privacy guarantees typically incurs additional computational overhead (e.g., random noise addition or extra sampling procedure). In our context, to achieve pure DP, implementing exponential mechanism over
Work done Georgia Institute of Technology.

---

Published conference paper at ICLR 2025
all possible mechanisms would incur exponential time (See Appendix D).
To obtain pure DP more efficiently, we apply recent advances (Durfee 2023 Kaplan et al. 2022) in private quantile estimation. Our algorithm's 's running time increases by only polylog factors compared to the non-private version.
Notations We use Ma to denote the optimal mechanism distribution A, and we use Rev(M, A) to denote the revenue of deploying mechanism M to distribution A. We restricted ourselves to single item auctions; hence, MA denotes the Myerson auction fitted on distribution A, and we denote OPT(A)
Rev(MA. A) as the optimal revenue one could get from distribution A. We use 1 to denote k-dimensional vector with all entries equal to We use Ô and θ to hide polylog factors.
1.1 RESULTS
Formally, we define the problem of learning a near-optimal auction with a pure DP:
Problem 1.1 (Optimal Auction with (cp. O)-D)). Given n samples of k-dimensional distribution D, the goal is to learn single item auction M with (cp. 0)-DP, whose expected revenue D is close to the optimal revenue, i.., with prob. 1
E [[Rev (M, D) OPT(D)] for some small e.
Insight. To address this problem, we leverage the insight that, the expected optimal revenue from value distribution is insensitive small statistical shifts and discretization in the quantile and value space. Additionally, we observe that the accuracy of the points returned by private quantile estimation (QE), assuming the data points follow a distribution, directly correlates with the statistical distance between the distribution formed by the returned points and the true distribution. Thus, we can reduce private Myerson fitting from samples to private quantile estimation of pre-specified quantiles.
Achieving pure DP while maintaining meaningful revenue guarantees is challenging. A crucial aspect to ensure that the values (hence distribution) returned by DP Quantile Estimation (QE) possess meaningful and provable accuracy guarantces. To obtain such accuracy, our algorithm (Alg. T first additively discretize the empirical distribution in the value space to distribution De, then estimate the pre-specificed quantiles with DPQE. We improved the accuracy bound of DPQE (DPQUANT al. 2022)) to accommodate cases with duplicate values. This improved bound allows to upper bound the statistical distance hetween the output distribution and De thus upper bounding the revenue loss incurred from fitting a Myerson on the output distribution.
Theorem 1.2 briefly presents the near-optimal revenue of our proposed mechanism. The final privacy
parameter has a dependency on l since the output of mechanism M is of dimension 2k. We present complete details Section g and the complete theorem statement in Theorems 3.2 and 3.3
Theorem 1.2 (Revenue Guarantee of Private Myerson, Bounded). Given = θ( samples V of the joint distribution D E [0, hi] there exist a mechanism M that is 2kx, differentially private with running time ((kn) and takes ((1) pass of the distribution. With probability 1 - 5, this mechanism M satisfies: E Re D) OPT(D)) s Ō((c + 2² kh)))
The prior algorithm does not work for unbounded distributions. Our second algorithm (Alg. addresses the case for st-strongly regular value distributions by efficiently truncating them bounded distributions with small expected revenue loss. This approach enables the application of our previous mechanism (Alg. I designed for the bounded distribution case. Since the truncation point is a function of the optimal revenue, we develop Alg. 7 to approximate this point by achieving a ((k)- approximation of the optimal revenue, where k denotes the dimension of the product distribution.
Theorem 1.3 outlines the accuracy of our proposed mechanism for certain parameter settings. Since this truncation point depends adaptively the desired accuracy, the revenue gap exceeds that for the bounded case, and the tradeoff between privacy and revenue are more pronounced. We present more details in Section 4 and the complete theorem statement is in Theorems 4.1 and 1.13
Theorem 1.3 (Revenue Guarantee of Private Myerson, Unbounded). Given n = Õ samples V of strongyyy regular joint distribution D E kR. there exist mechanism M for unbounded distribution that is 2ke, differentially private with running time (kk)) and takes O(n) passes. With probability
1 - 8, this mechanism M satisfies: | [[Rev(M D) - Rev(Mp, D)] < O 20l22ee ( /cp)-
'This failure probability 8 is inevitable due to the inherent uncertainty in learning from finite sample set, Chapter Kearns and Vazirani (9944)
2

---

Published conference paper at ICLR 2025
Application: Online auction with nonmyopic bidders. We now describe how our mechanisms incentivize truthful bidding from nonmyopic bidders under practical online auction settings In the online setting, auctions are deployed iteratively and later auctions are informed by previous bids. Since future auctions can be affected by earlier bids, nonmyopic bidders may strategically bid in earlier rounds to increase winning chances and/or secure lower prices, increasing their utility.
To prevent from strategic bidding, we integrate our previous solutions (Alg. D Alg. 2 with commitment mechanism. Our DP Myerson naturally upper bound the utility gain (of future rounds) by definition, in that the change of one bid affect the outcome's 's probability by privacy parameter Ep. Our algorithm operates in two stages. In the first stage. it employs a commitment mechanism that penalizes strategic bids. In the second stage, the algorithm fits a DP Myerson auction from the collected bids and generates revenue in the remaining rounds. This approach ensures that strategic bids only lies in small neighbor of the true value; otherwise, the bidder's utility becomes negative.
We present the regret (i.e., the time-averaged revenue of the proposed mechanism compared to the optimal one) of our proposed mechanism (Alg. 3 in Theorem 1.4. which shows the accuracy of our algorithm in terms of regret. We defer readers to Section S and Theorem 5.4 for further details.
Theorem 1.4 (Revenue Guarantee of Online Mechanism), Given E [0. 1/4], under the online auction setting described in Section 5. there exists an algorithm (Alg. run with parameter T = Ö(E 2) that, with probability 1 8, achieves diminishing regret, i.e., REGRET Ö((E + /TEekh where 1) is constant specific to bidders' utility model.
1.2
PRIOR WORK
DP Mechanism Design. Emerging from McSherry and Talwar 2007). there has been interest in delivering mechanisms with DP guarantees (Nissim et al. [2112] Huang et al. 201 Sa Zhang and Zhong 2022 Huh and Kandasamy 2024). These mechanism are either no longer optimal in our setting, or doen't t generalize unbounded distribution setting.
Online Learning in Repeated Auction. Regarding the single item online auction setting, Kanoria and Nazerzadeh 2014)); Huang et al. (2018a) established near-optimal solutions when bidders' utility is discounted and valuations are i.i.d.. Deng et al. (2020); Abernethy et al. (2019) introduced specific incentive metries to quantify bidders' willingness to bid other than their true values and developed mechanisms that minimize incentives for strategic bidding under these metrics in large markets.
For detailed, complete list of related work topics, please see Appendix C
1.3 CONTRIBUTIONS
Revenue Maximizing Auctions with Pure Privacy Guarantee. Our work is the first to develop mechanism with pure DP that obtains near optimal revenue for single item auction with independent and non-identical bidders, and for both bounded and unbounded 17 n-strongly regular distributions. For bounded distributions, our mechanism achieves optimal time complexity within polylog factors.
Application to Online Auction Setting. We apply mechanism into the online auction setting with nonmyopic, independent and non-identical bidders. Combined with our designed commitment strategy, the integrated solution restricts the bids to small neighbor around the corresponding value. Consequently, these approximately truthful bids enables our solution to generate revenue guarantee that converges the optimal revenue over time, for time-discounted, or large market bidders. We generalize the i.i.d bidder setting in Huang el al. (2018)) and solve the open problem they proposed.
Extended A Anllssi of Private Quantile Algorithm. We extend the analysis of the quantile estimation oracles employed in this paper. For quantile estimation on bounded datasets (Kaplan et al.) (2022), the paper assumes that all data points are distinct and derive accuracy bounds dependent on the dataset's range. We generalize their analysis to accommodate cases where multiple data points may share identical values. Additionally, for quantile estimation of unbounded distributions (Durfee 2023), we provide theoretical accuracy guarantees, complementing the paper's 's focus on empirical performance.
Recoognizable non-i.i.d. value distributions common, e.g., Meta Ad platform (met) requires that each advertiser selects one of six objectives, corresponding different distrihutions hased on the industry ad topic.
3

---

Published conference paper at ICLR 2025
2
PRELIMINARIES
In this section, we outline the preliminaries on mechanism design, differential privacy, and quantile estimation. Additional information can be found in Appendix E
2.1 MECHANISM DESIGN BASICS
We now formally define the allocation rule and payment rule of single item auction.
Definition 2.1 (Allocation Rule and Payment Rule). Given &o bidders with bid b (b1, ........ b&).
single-item auction M consists of an allocation rule as x(b) == (21 (b))...... 2y (b)) E [o. 1] and payment rule as pbb) (p (b),..., Pa (bb) [0, 1] where Iy denotes the probability that the j-th bidder gets the item, and Py denotes her payment.
Under truthful sample access, the Myerson's 's auction maximizes the expected revenue.
Definition 2.2 (Myerson's Single Item Auction (Myerson 1981)). For discrete product distribution D D1 x ... ..... x DR (Elkind 2007). the virtual value for Dj value of with support V/ (uf,.... w is の3 (v/) = of (w(41 - v/) 1-F)(1)) where u/ are ordered in increasing order of i, (x(2) Plu r²], and (y E
((((
We say the product distribution D is 17-strongly regular if for all j. (,(()) o5(0;) 2 n/u - -1²) for every U/ > ,/y E V and 0.
For these distributions with nondecreasing virtual value, Myerson's 's allocation rule xx(U;) = (db(w)) 2 max(0, maxjæi (15)))), where 1 (() denotes the indicator function. The payment rule (b(()) [v:) 2 max(0, max34i ( ( (max((, max ()()))))
2.2 DIFFERENTIAL PRIVACY BASICS
We present the definition of pure DP and approximate DP below.
Definition 2.3 (Differential privacy). An algorithm A : IR - R is (e. -apprrxiiit DP if for neighboring dataset V, V E R, that differs in only one data point, and any possible output O, we have: Pr(A(V) O] exp (c) Pr(A(V") O] + 5. We say it satisfies pure DP for d = 0.
key property we leverage from differential privacy is its immunity to post-proceed post-prceessigg Post- processing refers to any computation or transformation applied to the output of a DP algorithm after the data has been privatized. In our context, Myerson's auction can be seen as a post-processing step. Therefore, applying Myerson's 's auction to differentially private release of the empirical distribution preserves the original privacy guarantees of the input distribution.
Lemma 2.4 (Immunity to Post-Processing). Let A RR + R be an (e, D)D algorithm, and let f: IR- + be a random function. fundtm,unnctio.. Then, f PT. + i also (c.8)-DP.
2.3 QUANTILE ESTIMATION
Quantile estimation (QE) is used for estimating value of specified quantiles from samples, Given samples from a distribution, an accurate QE from samples directly translates to an accurate CDF estimation of the underlying distribution. Below, we formally introduce the definition of QE.
Definition 2.5 (Quantile Estimation). Given range of the data H, dataset X H containing points from range H, and a set of m quantiles 0 < qu..... 4m identify quantile estimations Vl.... Um such that for every [m]. Hx X|x v;}l O
We now present the definition of statistical dominance and KS-distance below.
Definition 2.6 (Stochastic Dominance and KS- KSS-Distacc).. Given distribution D and D', we denote the CDF of them Fp, FD', respectively. Distribution D stochastically dominates distribution D' (denoted as D > D') if: (1) For any outcome x, FD(x) S (x). (2) For some FD(a) < FF The KS distance between D and D' is (D, = sup [FD(z) F (x)).
Wee define the virtual value inverse क; (Φ) as arg min (i(1) ) 2 a. Moor formally, by X the minimum value such that this quantity exceeds g,n.
4

---

Published conference paper at ICLR 2025
3 PRIVATE MYERSON'S AUCTION FOR BOUNDED DISTRIBUTIONS
In this section, we introduce the algorithm for fitting Myerson's 's auction with a pure privacy guarantee. To ensure pure privacy, since DP is immune to postprocessing, it is sufficient input private distribution estimated from samples to the Myerson. The challenge lies in finding such distributions that still yield near-optimal revenue.
Our approach leverages private quantile estimation (QE) over samples achieve the desired guarantee. However, the standard guarantees DPQE collapse when the dataset contains points that are extremely close. This is critical issue in our setting, increasing the sample size from continuous value distributions inherently causes the minimum distance between samples to approach zero. To address this, we introduce additional discretization steps to prevent non-identical points from being too close together, and we develop new DPQE guarantees specifically tailored to handle samples with identical values.
3.1 PRIVATE MYERSON FOR BOUNDED DISTRIBUTIONS
Next, we present DEMYER algorithm (Alg. D. The algorithm first value-discretize the samples of the distribution additively by Ea, then quantilediscrretize these samples by E, with pure privacy guarantee. Specifically, the quantile discretization estimates the values of the quantile set [cq. ......... 1] with pure privacy. Next, DPMYER use the estimated quantile values and the quantile set to construct distribution, then perturb it to final distribution that is stochastically dominated by the ground truth. Finally, the final distribution is then used to implement Myerson's mechanism.
Algorithm 1 DP Myerson, Bounded Distribution DPMYER (V, Cgz Caz h, Cp)
Input: n samples V E R discretization parameter Eq. upper bound h. privacy parameter Ep Discretize all values into multiples of ca; let the resulting samples be V.
2: Prepare the quantile to be estimated: Q +- {Eqg 2t ................................ ..... [(1/eg) Egg
3: For each dimension
[k], decide the prices [i.1 < QESTIMATE(C
(p..)..p).
4:
> Estimate the quantiles by DPQUANT (Alg.
5: Construct distribution D based on S, treating the valuations in S as if cach has probability Eq.
6: For each E [k)) shift the top Eg quantile of D; to the bottom, fit Myerson on this distribution.
3.2 REVENUE OPTIMALITY AND RUNNING TIME
Next, we show the revenue optimality and the efficiency of our algorithm. To upper bound the reveue loss, we derive the revenue shift theorem, which upper bounds the revenue difference between two distributions by a linear function of their statistical distance.
Theorem 3.1 (Revenue Shift Theorem). Given two product distribution D z
D' whose valuations bounded by h, with de (D;, D/) a; for any bidder i, the optimal revenue of these distribution satisfies: < E E.Rev(MD. D) - Rev(MD', D')] < (Zie(h) a.)h.
We apply this theorem to upper bound the revenue loss between 1) the and its pre- rre-tuantzzed counterpart, and 2) the distribution obtained from private quantile estimation and that from the groundtruth quantile estimation. The first one is evident, while the second arises from DPQUANTILE'S ability control the KS-distance between the estimation and the ground truth.
distribution
We now present the accuracy guarantee of the private Myerson algorithm. Provided the privacy parameter is not too small (i.e, Ep Die our guarantee implies that the optimal revenue of the distribution does not exceed the revenue of our algorithm on its samples by more than ((ekh).
Theorem 3.2 (Revenue Guarantee of Private Myerson (Alg, 1h.. Given samples V [0, kxn of the joint distribution D. DPMYER (Alg. 7 is (2kep: 0)-DP, and the expected revenue of this mechanism is close to the optimal revenue of distribution D, ie., with probability 1 8:
E[Rev (MPPMYER, D) OPT(D)I s Ō((c kc))).h)
under parameter Ea = Eq = and E -2), where we hide the polylog factors in θ and Ō
5

---

Published conference paper at ICLR 2025
Proof Sketch. We begin by deriving the privacy guarantee of our algorithm. Next, we establish an upper bound on the distance between the private distribution DP and the additively discretized distribution De This enables us to apply the revenue shift theorem (Thm 3.1) ) to upper bound the revenue loss from private quantile estimation. By aggregating this loss with the revenue loss due to
value discretization, we arrive at the final result. In this proof sketch, we omit the polylog factors that depends on K n, ò, Ea. Ep. Ey for clear presentation. Further details are provided in Appendix H.2
Privacy Guarantee. We know that the quantile estimates from DPQE is (ep, 0) private (Lem. H.2 Since DP immune to post-processing (Lem. E.4). and that the output of allocation and payment combination is 2k dimensional, by composition theorem (Lem. E.5). our algorithm is (2kep. D)-
Upper Bounding the Statistical Distance The distribution De is obtained by changing from distribution D through distribution D, the distribution D' and D (Figure []. We upper bound the statistical KS distance of these distributions: 1) By DKW inequality, we upper bound the KS-distance between D and D by ((1/vn) for each coordinate i (with probability 1 -8/2). 2) By definition, we upper bound the KS-distance between De and D by keg. 3) By developing and converting the bound of the DP quantile algorithm (Lem. H.3) into a bound on the CDF, we upper bound the KS-distance between De and De by Ke for ;= ( (Epr) (with probability 1 5/2).
Upper Bounding the Revenue Loss. We then upper bound optimal revenue loss from D to DP, This upper bound can be obtained by combining the revenue loss from the aforementioned distributions (by revenue shift theorem), with an additive ea revenue loss from discretization (by Lem. F.T. The revenue loss from statistical shift aggregates to (((1/ V + + kh) with probability 8- 8.
Putting it all together. Finally, condition the DPQUANT proceeds successfully and the samples are close to the underlying distribution (with probability 1 - 6), we get that the expected revenue of DPQUANT the underlying distribution is at least the optimal revenue from this distribution minus the revenue difference between D and D by the following inequality:
JE [Rev(M D) OPT(D)) 2 ([Rev(Mpr) D) OPT(DP) (OPT OPT(D)
where the first inequality follows from the optimality of MD on D and the second inequality follows from adding OPT (DP). By our construction of Dr this distribution is stochastically dominated by D, thus from the strong revenue monotonicity (Lem. F.3 we get that E[Rev M D) OPT( 2 0.
Thus, we concluded that the revenue gap is upper bounded by (((1/ + Ey + kh + ca). We set in the statement as 1/K of the 8 we used in this proof generate the final revenue guarantee.
Discrete Do Private 6P line in Alg.
large Ti
small ca
Discrete De line in Alg.
large
Dist. D
Emp. ò
close CDF
close Rev.
close CDF
Figure Distribution analyzed for DPMYER(Alg, We establish connections between the accuracy/revenue guarantee the original distribution D with the empirical distribution D, the value- discretized De, the quantile-discretizer De and the distribution De returned by DPQUANT(AIg:
Next, we demonstrate the efficiency of our algorithm, which is achieved through a organized im- plementation of the DP Quantile algorithm. Intuitively, given m ordered quantiles, the algorithm iteratively identifies and estimates the median (the m/2-th), followed by the m/4 and the 3m/4 quantiles, and so on. This hierarchical structure ensures that each data point is used in at most log quantile estimates (of single quantile). For more details, we refer readers to Appendix H.I
Theorem 3.3 (Time Complexity for Private Myerson, Bounded). Given the same parameters as stated in Theorem 3.2 DPMYER [A runs in @(kn) time and requires 6(1) passes of the samples.
Proof Sketch. The time dominant step is quantile estimation, which requires log( [1/cg/ 1) passes of the dataset. It takes O(k log([1/ee)) + 1)/(Eaeq)) = @(kn) time, since n Ō 2). This step calculates the utility of 1s e,_ over [1/e,] quantiles for at most 6(1) time. For full version of this
proof, please refer to Appendix H.3

---

Published conference paper at ICLR 2025
4 GENERALIZATION TO UNBOUNDED DISTRIBUTIONS
Generalizing the DP Myerson mechanism to unbounded distributions introduces new challenges. The revenue loss upper bound produced by previously introduced quantile estimation algorithm and revenue shift theorem both depends (positively) on the range of the distribution. Without a finite range, these upper bound becomes infinite and fail to effectively control the revenue loss.
We consider the widely accepted n-strongly regular distributions, which decays at least as fast as exponential distributions. A key element of our approach is appropriately truncating the distribu- tion, which enables extend the discretize-then-DDD -aaeee-thhe----uutiiiii quanttile method to the unbounded setting. Specifically, we apply the property of the regular distribution that (Devanur et al., 2016), truncating the distribution by SOPT(D) costs at most 2e fraction of the optimal revenue (Lem. L.1 Hence, for the truncation to work. it is essential to approximate the optimal revenue based on sample data. Meanwhile, incorporating the truncation with pure DP introduces additional complexities.
We are now ready to present our approach for apappooxiatioon of the optimal revenue with pure DP for y-strongly regular product distributions. Our DPKOPT (Alg. ( algorithm approximates the optimal revenue by running empirical reserve(ER) over each bidder's distribution truncated at the top (22-)) /4 quantile Summing up these estimates gives us a (k)) apprroxmiainnn of the optimal revenue, by the fact that that (OPT(D) 2 EXEMM OPT(Dx) 2 OPT(D).
Algorithm 2 DP Estimation for Optimal Revenue DPKOPT(V, Eas Ep.
Input: n samples V = (Vi,..., Vn). quantile discretization <g. additive discetization cas privacy parameter Cp. regularity parameter y).
1: for + k do
2: @ T 1/4 1/4-1////
3: Let uba +- DVQUANTU(VR2.)
> Estimate the truncation point of Da-
4: Truncate distribution Da uba Da and discretize Da by additive C, in the value space.
5: Prepare the quantile be estimated, Q (1 7, 1 Eqr
7 |بق Egg 0}.
6: Sja.j + QESTIMATE( kp..).pp)
Apply DP quantile estimate (Alg. 7: Let Fd be the distribution generated by value profile S(r..) and quantile set Q.
8: SREV < max, rEB r(1 Fa(r)).
Estimate the optimal revenue from F, (Alg. 6
9: end for
10: KREV <- EdEM SREV
11:
return KREV
To guarantee pure privacy, our algorithm estimates the optimal revenue using a DP-estimated proxy FiRI derived from the sample data. This proxy is obtained from truncating the distribution by DPQUANTU (Alg. 7) and quantile-diseretizing the distribution by DPQUANT. During this process, the truncation by DPQUANTU cost at most a constant fraction of the optimal revenue, and DPQUANT cost at most an additional θ 1 k + ca). Aggregating these revenue loss concludes that the output is 5p
a apppooxaiinn the optimal revenue. See Appendix I.4 for more details.
Our private Myerson algorithm for the unbounded distribution (Alg. integrate DPKOPT and yields the following accuracy bound. See Appendix [T.]] for formal statements and more details.
Theorem 4.1 (Revenue Guarantee of Private Myerson, Unbounded). Given E [0, 1/4], n samples
V of the joint distribution D E [0, 11 the output of Myerson fitted under DPMYERU (Alg. is (2kep, D)- and under Eg n ((e2), nu = O(e?), 4 Ve, with probability 1 - 6,
E[RRev(MDPMYEE D) Rev (Mp D)] s Õ(k2 1.5 /pp)
'Without privacy constraints, truncating at the top ///(1-n)sufficee by Lem. L.4 Our algorithm adopt
looser truncation since the DPQUANTU algorithm only return the value of given quantiles approximately.
7

---

Published conference paper at ICLR 2025
5 APPLICATION: ONLINE MECHANISM DESIGN FROM BIDS
We now study how to integrate previous solutions into the online auction setting, such that, the algorithm produces time-averaged revenue guarantee that converges to the optimal. The auction now spans multiple rounds, where each auction is informed by the bids from previous rounds. We consider the setting where bidders are non-my myopic bidders, and have incentives to bid strategically in the current round to increase their utilities over future auctions.
5.1 APPLICATION BACKGROUND
Before presenting our algorithm, we first provide the formal problem definition of the online auction setting. We study online mechanism design over time horizon I, where identical item is sold at each iteration. Each bidder has a publicly observable attribute. Bidders with the same attribute have the same valuation distribution.
We are now ready to describe interactions between bidders and the auctioneer over time horizon T, as shown in Figure We defer to Appendix J.2 for more details how bidder generates the samples.
For each time t E [T]:
The learner/auctioneer sells a fresh copy of the item.
The learner collects the bids in the form of (6), aj), where by and aj denote the bid and the attribute of the j E [dh]th bidder, respectively.
The learner decides the allocation rule x, and payment accordingly.
Figure 2: Online Auction with le Attributes.
Each item the auctioneer sells identical, and each bidder has an additive (discounted) utility of the items across rounds. We consider the bidders either have discounted utility are in large market. Definition 5.1 (Bidder's Utility). Each bidder j has quasi-linear utility function at time t: u² (f -D²), where æ of.pp, are the allocation, value, price for bidder,) j at time i, respectively. We consider two nonmypoic bidders' utility models:
Discounted Utility: For discount factor [0, 1], the bidders seek to maximize the sum of utilities discounted by y.. the t-th iteration, the discounted utility 0t Σ Ex ""n""²
Large Marker: (Anari et al. 2014 Jalaly Khalilabadi and Tardos 2018 Chen et al. 2016): The bidder only participates in subset Sy auctions, i.c., for each
>'es, u', with subset |S,] < <t
Ideally, the learner's 's objective is maximize time-averaged revenue with high probability. Our regret compare this revenue against the optimal revenue of the (unobservable) value history.
Definition 5.2 (Learner's Objective). Given 8, the learner's 's objective is to decide an allocation X1:7 and payment Pt.T that achieves sublinear regret, i.e., with probability 5,
Σ E Rev(x,, Pt, b.) - EE (OPT(v.))] o(1),
REGRET := T
LE(T)
with the expectation taken over the value distribution.
5.2 TWO-STAGE MECHANISM FOR BOUNDED DISTRIBUTION
This two-stage algorithm (Alg. 3) consists of repeated auctions over T rounds, and the participating bidders' values in each round are upper bounded by a known constant The algorithm first collects the samples for the first Ti rounds, by running commitment algorithm (Alg. 10) that punishes nontruthful bids. Then, the algorithm deploys our previously developed DP Myerson's 's Algorithm (Alg. T Alg. 9 for the remaining rounds obtain near optimal revenue. In addition to these two steps, our algorithm includes a step where all samples are reduced by v of Alg. and projected onto nonnegative value spaces. This step is designed to offset the impact of strategic bidding.
8

---

Published conference paper at ICLR 2025
Algorithm 3 Two-Stage Algorithm AROUNDED
Input: Rounds T. learning rounds Ti, parameter éa, Eqp Epp upper bound h.
1: for + I,... Ti do
Collection Stage
2: Receive bids b", and attributes a'.
3: Return (x', p²) <- COMMIT(b").
b Commitment Algorithm(Ale 10
4: b' + P [0, [b' v1,1
5: end for
6: (x(),,(.)) + DPMYER !:Ti cgg Ea. h. ep)
)
Fit Myerson's auction (Alg.
Alg. Revenue Stage
7: for + Ti + 1,... do
8: Receive bids b'. and attributes a'.
9: (x',p") t --MEESOO((())))) (()))))
10:
end for
Specifically, the parameter v is carefully calibrated to ensure that the bid distribution fed into the private Myerson mechanism is stochastically dominated by the empirical distribution. Our algorithm provides an incentive guarantee that bids within a small, controllable neighborhood of the true values. The range of this neighborhood determined by the privacy parameter ep (hence is controlled by our algorithm), and the bidders' utility functions. By setting v to match the range of this neighborhood, the resulting distribution is dominated by the empirical distribution.
5.3 REVENUE GUARANTEE OF THE ALGORITHM
Before presenting the revenue guarantee of our main algorithm, we first introduce a lemma that upper bounds how bidder's bid deviates from its true value during the collection stage. Intuitively, by the design of our commitment algorithm the bidder will incurs loss that scales (positively) with the bid deviation, compared truthful bidding. Furthermore, our private Myerson ensures that the bidder's future utility gain is upper bounded (Lem. J.5). Thus, bidders are incentivized to report bids within certain range of their true values to optimize their overall utility. More details in Appendix J..4
Lemma 5.3 (Bid Deviation). For any E [0, Ti), the bidder will bid only by such that (b, val S 20x
where v 2( 1)cphk for bidders in large market; and a
V
(27e k2 kh discounting bidder. I-7
From this lemma, we get that selecting small Gp would incentivize bid distributions that are close to the ground-truth. Let v 2a in our algorithm (line g Alg. (3) would yield distribution that stochatically dominated by, yet close in revenue guarantee to, the true distribution. Run our DP Myerson algorithm this distribution would give sublinear regret, as stated below.
Theorem 5.4 (Accuracy Guarantee of Two-stage Mechanism). Given e E 1/4], samples of the joint distribution D E [0, hijt, and Ti O log(k/8)), ((Ti), Eg tp with probability 8, Alg. generates sublinear regret, i.e.,
Under a large market, the regret is upper bounded by Ō[(E + khe)kh), for = 2 1)
Under discounting bidder, the regret is upper bounded by Ō[(e + (hi) == 22
220e kh. T-q
Proof Sketch. We denote the empirical distribution as D. the distribution after subtraction in line 4 of Alg. as D, and the (final) output distribution as DP. Then these distribution satisfies î > 1 > DP. By strong monotonicity(Lem. F.3). know that B[Rev(M D)] E(OPT(D*)) Since Mnr need not be optimal over D, we have that:
> E[Rev(M D. D) OPT(D)
2 EE[Re(( p. D) - OPT( B(OPT( Rev(Mp,
2 E[OOT(( OPT( E(OPT - -PT(( 2 -Ô((e 2 11)
where in the last inequality apply revenue shift theorem (Thm. 3.I to upper bound the first term and apply Lemma J.9 to upper bound the second term. Please refer to Appendix [.3 for more details.

---

Published conference paper at ICLR 2025
EXPERIMENTS
In this section, present the experimental results for the Differentially Private (DP) Myerson mechanism, comparing its performance against two standard mechanism design baselines: the Myerson (optimal) auction and the Vickrey (second-price) auction. The former designed to achieve near-optimal revenue for given value distribution, whereas the latter, while strategy-prom -poofff offers no revenue guarantees in settings with independent and non identical value distributions.
Our experiments are conducted on normal and lognormal distributions truncated to positive do- mains. For each value profile, we test various hyperparametters- discretization (cg), and the privacy parameter (cp) (cp)-and select the configuration with the best perfor- mance. For details on DP Myerson's sensitivity hyperparameters, see Appendix
discretization (e,). quantile
Bidder Profile
DP Myerson
Second Price
Myerson
Ref.
Normal (0.3, Lognormal (n, = (-1.87, 1.15)
0.25272
0.15154 (66.7 %)
0.32598
Table
Normal (0.3, 0.5) Normal N (0.5,, (.7)
0.37691
0.33741 (11.7 %)
0.50204
Table
Lognormal (H, O) (-1.87, 1.15)
0.13912
0.11578 (20.2 %)
0.21292
Table
Lognormal (u, = (-1.24, 1.04)
Table 1:
Empirical Revenue of DPMyerson (Alg. under 2-dimensional non-identical value distribu- tions. Each DPMyerson configuration is averaged over 50 draws, with revenue evaluated on 10, 000 samples. Percentages in parentheses represent the improvement over the second-price mechanism.
In Table under non i.i.d distribution settings where there is significant revenue gap between the Vickrey auction and the Myerson auction, DPMyerson achieves a notable revenue increase (at least 11% over the second-price mechanism.
CONCLUSION
We investigate the problem of learning a single-item auction (i.e., Myerson) from samples with pure DP. We consider the broader setting where the agents' valuations independent, non-identical, and can either be bounded or unbounded. By recognizing that the optimal auction mechanism exhibits robustness small statistical perturbations in the underlying distribution, we reduce the challenge of privately learning an optimal auction from sample data to the task of privately approximating pre-specified quantiles. Specifically, our approach ensures pure privacy while generating distribution that is closely aligned with the underlying distribution in terms of expected revenue.
We then extend this framework to the online auction setting, where later auctions fitted bids from previous auctions. In this setting, non-myopic bidders reason about their utility across rounds, and can bid strategically under (one-shot) truthful auctions. By leveraging our private Myerson mechanisms with an extra commitment mechanism, we achieve near-optimal revenue outcomes over the bidders' (unobservable) value samples, despite the strategic complexity introduced by non- myopic behavior. This result highlights the robustness of our approach in both protecting privacy and maintaining near optimal expected revenue in dynamic, strategic environments.
Several interesting directions remain in this line of work.
Private Correlation Robust Auction Design. Correlation robust auctions apply to the partial information setting where the distributions correlated but only the marginal distributions of them can observed (He and Li. 2022 Bei et al. 2019). Designing a correlation-robus auction with privacy guarantees based on samples would be valuable future direction.
Other Bidders' Utility Models. Other bidder utility functions are also widely considered in the context of online auctions and mechanism design, including the budget-constrained value maximizing bidders (Conitzer et al.) 2002), and submodular utility functions (Assadi and (angla|2000] Advancing Hivacy-preserving mechanisms for these settings would also be important.
10

---

Published conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We sincerely thank the anonymous reviewers from ICLR 2025 for their valuable discussions and sug- gestions on our experiments, which have improved this work. Yuanyuan Yang and Jamie Morgenstern supported by NSF Awards CCF-2045402 and CCF-2019844.
We gratefully acknowledge Bhuvesh Kumar for his contributions to the early discussions of this work prior to 2022, time when privacy techniques had not yet been developed. However, Bhuvesh Kumar was not involved in the substantial revisions and restructuring of the manuscript that took place from 2022 onward.
REFERENCES
The ad auction explained. ad auction (page
URL
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016. (page 23
Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. In Conference on learning theory, pages 807-823. PMLR, 2014. (page 22
Jacob D Abernethy, Rachel Cummings, Bhuvesh Kumar, Sam Taggart, and Jamie Morgenstern. Learning auctions with robust incentive guarantees. In NeurlPS, pages 11587-11597, 2019. (page
Daniel Alabi, Omri Ben-Eliezer, and Anamay Chaturvedi. Bounded space differentially private quantiles. arXiv preprint arXiv:2201 .03380, 2022. (page 22
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in Neural Information Processing Systems, 26, 2013. (page 23
Nima Anari, Gagan Goel, and Afshin Nikzad. Mechanism design for crowdsourcing: An optimal 1-1/e competitive budget-feasible mechanism for large markets. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 266-275. IEEE, 2014. (page g 40
Sepehr Assadi and Sahil Singla. Improved truthful mechanisms for combinatorial auctions with submodular bidders. ACM SIGecom Exchanges, 18(1):19-7,, 2020. (page 10)
M.-F. Balcan, A. Blum, J.D. Hartline, and Y. Mansour. Mechanism design via machine learning. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS (05), pages 605-614, 2005. doi: 10. 10.100SSCSS200055500 (page 22
Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. Item pricing for revenue maximization. In Proceedings of the 9th ACM Conference Electronic Commerce, pages 50-59, 2008. (page 22
Balcan, Tuomas Sandholm, and Ellen Vitercik. Estimating approximate incentive compatibility. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 867-867, 2019. (page) 22)
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. In Advances in Neural Information Processing Systems, pages 2083-2091 2016. (page 22
Santiago R Balseiro, Omar Besbes, and Francisco Castro. Mechanism design under approximate
incentive compatibility. Operations Research, 32(1)3355-372, 2024. (page 22
Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang. Correlation-robus analysis of single item auction. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193-208. SIAM, 2019. (page 10

---

Published conference paper at ICLR 2025
Sébastien Bubeck. Nikhil Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scat online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 2019. (page 22)
Yang Cai and Constantinos Daskalakis. Extreme-value theorems for optimal multidimensional pricing. In 201/ IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 522 521. IEEE, 2011. (page 22
Ning Chen, Xiaotie Deng, Bo Tang, and Hongyang Zhang. Incentives for strategic behavior in fisher market games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
(page 40
Richard Cole and Tim Roughgarden. The sample complexity revenue maximization. In Proceedings of forty annual ACM symposium Theory of computing, pages 243-252, 2014. (page
Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. Multiplicative pacing equilibria in auction markets. Operations Research, 70(2):963-99) 989,,,999999--- 2022. (page I0)
Xiaotie Deng, Ron Lavi, Tao Lin, Qi Qi, Wenwei Wang, and Xiang Yan. A game-theoretic analysis of the empirical revenue maximization algorithm with endogenous sampling. Advances in Neural Information Processing Systems, 33:5215-5222 5226,, 2020. (page 3 (2)
Yuan Deng, Sébastien Lahaie, Vahab Mirrokni, and Song Zuoo. Revenue-incentive tradeoffs. in dynamic reserve pricing. In International Conference on Machine Learning, pages 2601-2610.
PMLR, 2021. (page 22
Nikhil R Devanur, Zhiyi Huang, and Berritoss-Alexandeee Psomas. The sample complexity of auctions with side information. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 426-439, 2016. (page 7 22 28
John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):882225) 201, 2018
(page 22)
David Durfee.
Unbounded differentially private quantile and maximum estimation. Advances in
Neural Information Processing Systems, 36, 2023. (page 2 22
35 39
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning: Advances in differentiable economics. Journal of the ACM, 71(1):1-53, 2024. (page 22)
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956. (page 26)
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1-12. Springer, 2006. (page I
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pages 1-19. Springer, 2008 (page T
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology -EREYCRERRRRRP 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg. Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503. Springer, 2006. (page 26
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing. pages 715-724, 2010. (page
12

---

Published conference paper at ICLR 2025
Edith Elkind. Designing and learning optimal finite support auctions. 2007. (page
22
European Commission. Regulation of the european parliament and of the council the transparency and targeting of political advertising, 2024. URL https: /ttp:s///aaa./// /wtaaaaaaa..mmmmooo consiinniiioocoo wwweiiiiumm..m europa
eu/ wtlo://ocumet//e55 90 2023- INIT WAIT/een, en/ påf (page 21
Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In International Conference on Machine Learning, pages 3713-3722. PMLR, 2021. (page 22)
Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, and Huacheng Yu. Near-optimal relative eтrоr streaming quantile estimation via elastic compactors. In Proceedings the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3486-3529. SIAM, 2025. (page 22
Chenghao Guo, Zhiyi Huang. and Xinzhi Zhang. Settling the sample complexity of revenue maximization. In Proceedings the 51 Annual ACM SIGACT Symposium Theory of Computing, pages 662-673, 2019. (page 22)
Wenshuo Guo, Michael Jordan, and Emmanouil Zampetakis. Robust learning of optimal auctions. In Thirty-Fifth Conference Neural Information Processing Systems, 2021. (page 29
Meghal Gupta, Mihir Singhal, and Hongxun Wu. Optimal quantile estimation: beyond the comparison model. arXiv preprint arXiv:2404. 03847, 2024. (page
Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference World Wide Web, pages 189-198, 2008. (page 34)
Jason Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225-234- 2009. (page 22 26
Wei He and Jiangtao Li. Correlation-robust auction design. Journal of Economic Theory, 200: 10540, 2022. (page 1T)
Zhiyi Huang, Jinyan Liu, and Xiangning Wang. Learning optimal reserve price against non-myopic bidders. In Advances in Neural Information Processing Systems, 2018a. (page 3 22
Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. SIAM Journal on Computing, 47(3):651-6744 2018b. (page
34
Joon Suk Huh and Kirthevasan Kandasamy. Nash incentive-compatibe online mechanism learning via weakly differentially private online learning. ICML, 2024. (page
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Conference Learning Theory, pages 24-1. JMLR Workshop and Conference Proceedings, 2012.
(page 23)
Pooya Jalaly Khalilabadi and Éva Tardos. Simple and efficient budget feasible mechanisms for monotone submodular valuations. International Conference on Web and Internet Economics, pages 246-263. Springer, 2018. (page 8 40)
Yash Kanoria and Hamid Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014, Proceedings, volume 8877, page 232. Springer, 2014. (page 3
Yash Kanoria and Hamid Nazerzadeh. Incentive-compatible learning of reserve prices for repeated auctions. Operations Research, 69(2):509-524, 2021. (page 22
Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In International Conference on Machine Learning, pages 10751-10761. PMLR, 2022. (page 2 22
30
31
13

---

Published conference paper at ICLR 2025
Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014. (page? 21
Michael J Kearns and Umesh Vazirani. An infroduction to computational learning theory. MIT press, 1994. (page 2
Clément Lalanne, Aurélien Garivier, and Rémi Gribonval. Private statistical estimation of many quantiles. In International Conference on Machine Learning, pages 18399-18418. PMLR, 2023.
(page 22)
Yi Liu, Qirui Hu, Lei Ding, and Linglong Kong. Online local differential private quantile inference via seff-normalization. In International Conference on Machine Learning, pages 21 698-21714 PMLR, 2023. (pagel (2)
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 07), pages 94-103. IEEE, 2007. (pagel)
22 23 41
Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28, 2015. (page 22
Roger B Myerson. Incentive compatibility and the bargaining problem. Econometrica: journal of the
Econometric Society, pages 61-73, 1979. (page I 22
Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
(page 25
Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz. Approximately optimal mechanism design via differential privacy. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 203-213, 2012. (page 3
Mallesh M Pai and Aaron Roth. Privacy and mechanism design. ACM SIGecom Exchanges, 12(1): 8 8-29, 2013. (page
Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 1-18, 2016. (page
Adam Smith.
statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium Theory of computing, pages 813-822 2011. (page
30
Tran Tran, Matthew Reimherr, and Aleksandra Slavkovic. Differentially private quantile regression. In International Conference on Privacy in Statistical Databases, pages 18-34. Springer, 2024.
(page 22)
Junhua Zhang and Caiming Zhong. Differential privacy-based double auction for data market in
blockchain-enhanced internet of things. Wireless Communications and Mobile Computing, 2022
(1):8038846, 2022. (page 3
Xiaojin Zhang, Yan Kang, Kai Chen, Lixin Fan, and Qiang Yang. Trading off privacy, utility, and efficiency in federated learning, ACM Transactions on Intelligent Systems and Technology, 14(6): 1-32, 2023. (page 23)
Ying Zhang, Xuemin Lin, Jian Xu, Flip Korn, and Wei Wang. Space-efficient relative error order sketch over data streams. 22nd International Conference on Data Engineering (ICDE'06)
pages 51-51. IEEE, 2006. (page 22
14


Reviews:
[{"review_id": "Y5y7MPBwlf", "reviewer": "Reviewer_Ncwf", "summary": "The paper investigates the problem of designing differentially private (DP) mechanisms for single-item auctions that maximize revenue while ensuring ($\\epsilon$, 0)-pure privacy. The authors propose two auction learning frameworks for both bounded and unbounded valuation distributions that privately estimate specific quantiles to achieve near-optimal revenue. Notably, the proposed frameworks maintain computational efficiency with only polylogarithmic overhead relative to non-private versions. Extending the approach to multi-round online auctions, the paper introduces mechanisms to limit strategic behavior from non-myopic bidders, demonstrating effectiveness in both bounded and unbounded distribution settings. The authors claim the method is the first efficient DP Myerson auction model under pure privacy and applicable to unbounded distributions.", "questions": "1. Experimental Validation: While the theoretical framework and proofs are robust, the paper lacks empirical validation. Demonstrating practical performance via simulation or real-world data could strengthen the results, showing real-world applicability of the bounded and unbounded auction mechanisms.\n\n2. Complexity for Practitioners: Although theoretically sound, the use of pure DP and quantile estimation could be challenging for practitioners to implement in real auction settings. The paper might benefit from guidance on parameter selection or case studies showing how to configure the model in practical scenarios, particularly for choosing ε and handling non-i.i.d. bidder distributions.\n\n3. Can the authors clarify how sensitive the revenue guarantee is to variations in the privacy parameter $\\epsilon$? For instance, what level of revenue tradeoff might practitioners expect for specific values of $\\epsilon$?\n\n4. In the online auction application, how does the mechanism handle scenarios with highly irregular bidder participation, such as sporadic or bursty bidding behavior?\n\n5. Could the approach be adapted or extended to multi-item auctions? If so, are there foreseeable challenges specific to quantile estimation or revenue guarantees?\n\n6. What is the impact on revenue performance if the quantile estimation accuracy deviates from the bounds established in the paper? Would empirical validation potentially show scenarios where revenue significantly underperforms due to quantile estimation errors?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses a critical gap in differential privacy for revenue-maximizing auctions, especially in providing efficient algorithms that ensure pure DP, a stringent privacy model often overlooked in mechanism design. The focus on both bounded and unbounded distributions adds further novelty, and the integration with online auctions for non-myopic bidders is an innovative extension.", "weaknesses": "1. Experimental Validation: While the theoretical framework and proofs are robust, the paper lacks empirical validation. Demonstrating practical performance via simulation or real-world data could strengthen the results, showing real-world applicability of the bounded and unbounded auction mechanisms.\n\n2. Complexity for Practitioners: Although theoretically sound, the use of pure DP and quantile estimation could be challenging for practitioners to implement in real auction settings. The paper might benefit from guidance on parameter selection or case studies showing how to configure the model in practical scenarios, particularly for choosing ε and handling non-i.i.d. bidder distributions.\n\n3. Assumptions in Non-Myopic Bidder Models: The assumption of a commitment mechanism to prevent strategic bidding in online auctions may be limiting, as real-world non-myopic behavior could vary significantly. A sensitivity analysis on bidder behavior assumptions could improve robustness and applicability to broader settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jtFeQ5hWsY", "reviewer": "Reviewer_QM6b", "summary": "This paper studies how to learn the optimal single-item auction (Myerson auctions) from samples of non-iid bidders' values in a pure differentially private (pure DP) way. The authors reduce this problem to private quantile estimation of the bidders' value distributions. By doing that, they improve previous works in DP mechanism design in several aspects.  The authors also apply their results to online auction design with non-myopic bidders, obtaining a learning algorithm that is approximately truthful for the bidders and approximately revenue-optimal for the seller.", "questions": "**Question:**\n\n(Q1) Should the $V_{[i, :]}$ be $\\hat V_{[i, :]}$ in Algorithm 1?  And what does $[i, :]$ mean? \n\n\n\n**Suggestions:**\n\n- Definition 2.1: The allocation rule and payment rule notations $\\bf x$ and $\\bf p$ should be vector-valued functions, not vectors.\n\n- Typo in Definition 2.3: $exp$ $\\epsilon$. \n\n- Line 225: \"increasing the sample size n from continuous value distributions naturally leads to points that are either very close or identical\". Points sampled from a continuous distribution are identical with probability 0.\n\n- The proof sketch of Theorem 3.2 and the formal proof (the proof of Theorem F.4 in the Appendix) didn't say why the QESTIMATE oracle is DP.  I guess it is given Lemma F.3.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(S1) Previous attempts to integrate DP with prior-dependent auction design were all computationally inefficient or only guaranteed approximate DP.  This work is the first to achieve both computational efficiency and pure DP, which is a significant conceptual and technical contribution.\n\n(S2) The authors show that their approach can be applied to online auction with non-myopic bidders, ensuring that bidders are approximately truthful and the seller can obtain approximately optimal revenue.  This generalizes the iid setting of Huang et al (2018a) to the non-iid setting, answering their open question. This is a novel contribution to the online auction design literature.\n\n(S3) The private quantile estimation technique used in this work does not directly follow from previous work like Kaplan et al 2022.  The authors generalize previous techniques for distinct data points to the case with potentially identical data points.  This is an interesting contribution to the DP literature. \n\n(S4) The writing is very good. For example, the results and contributions are clearly stated in the introduction. The proof sketches nicely summarize the main proof ideas.", "weaknesses": "(W1) The high level idea is not new. Huang et al (2018) and Abernethy (2019) have applied DP techniques to the problem of learning optimal auctions from non-myopic bidders. This paper is more of a refinement and generalization of previous works. \n\n(W2) No experiments are given.  Some experimental results might strengthen the work a lot, given the practical motivation of using DP mechanism in real-world auctions. \n\nNevertheless, this work improves previous works in several aspects, like pure DP, non-identical bidders, unbounded distributions, and computational efficiency.  So I lean towards accepting this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SChWnrzvAL", "reviewer": "Reviewer_vD12", "summary": "This paper studies the problem of differentially private Myerson auction design under a Differential privacy constraint. The model is that there are k “types” of users and in each round, we get k buyers sampled from the distribution (assumed to be i.i.d.). Myerson’s foundational result defines the revenue maximizing truthful auction when the seller knows the distributions that the valuations are drawn from. In this work, the authors ask if we can privately learn enough about these distributions from samples to be able to run a near-optimal auction.\n\nThe main contribution is to show that indeed this is feasible. Using samples, one can learn the approximate quantiles of the distributions. Given the quantiles, the authors show that one can get a good approximation to the Myerson prices. In the case that the range of valuations is bounded, one can use any of the many known quantile estimation algorithms. In the case of unbounded range, one can use a recent result to estimate the range and then run quantile estimation.\n\nThe authors also show how for non-myopic bidders in a repeated game setting, one can use this private learning algorithm along with a commitment algorithm to get near optimal revenue.", "questions": "- It would be useful if the authors compared to the utility the exponential mechanism would offer in this case, ignoring computational constraints.\n- It is also likely that the sampling from the continuous exp mech distribution can be done by being a little careful in understanding the distribution, especially since the structure of Myerson should allow you to independently sample each user’s price.\n- The online mechanism designed in this work uses “greedy” by separating the explore and exploit phases. Can you do better by combining exploration and exploitation?\n\nNits:\n- “Mechanism Design in the title seems too general for what the paper is doing. I would suggest putting Myerson Auction Design or at best Auction Design in the title.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper expands the set of settings where DP can be used for mechanism design\n- It combines DP tools with an understanding of auctions to allow learning from buyer’s bids while preserving incentive compatibility even with non-myopic bidders.", "weaknesses": "- No major weaknesses, perhaps with the exception of relavance to this conference. See questions below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tAr3zxOKCd", "reviewer": "Reviewer_377R", "summary": "This paper combines differential privacy with auction theory, specifically focusing on revenue-maximizing auctions under pure DP.  The authors propose frameworks that handle independent, non-identical, and both bounded and unbounded valuation distributions.", "questions": "1. In the multiple-dimension case, it is well-known that DP community considers approximate DP since it can help improve $\\sqrt{d}$ factor in utility where $d$ is the dimension like in [1]. In this paper, the authors consider $k$-dimension but achieve pure DP. The motivation is weird. What is the advantage of pure DP compared with approximate DP in your setting? \n2. One should consider composition theorem for multiple rounds like in algorithm 3 to achieve central DP. Also, in lines 277-278, the final privacy guarantee should be $\\epsilon$-DP and then divide it to each dimension.\n3. I have some concerns about the novelty of the technical part since the paper just invokes and combines previous methods in other work.\n\n\n[1].Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and\nhigh-dimensional regression. In Conference on Learning Theory, pages 25.1–25.40, 2012.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides auctions for unbounded distributions and establishes theoretical guarantees.", "weaknesses": "1. There is no experiment.\n2. I have some concerns about motivation and novelty, see Questions part for details.\n3. The notation is confusing like different $\\epsilon$ and in Theorem 5.4 , \"the regret is upper bounded by $\\tilde{\\Theta}$\" where $\\tilde{\\Theta}$ should be $\\tilde{O}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)