Though prior-dependent auctions, which adjust parameters based on samples of value distributions, often yield better revenue than prior-independent auctions, they risk leaking information about the bids they were trained upon. To address this issue, differential privacy (DP) offers a promising solution (Dwork, 2006;2008;McSherry and Talwar, 2007;Pai and Roth, 2013), ensuring that a single data point minimally affects the algorithm's output, thus preventing inference of a 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.e., prior-dependent), achieves optimal revenue. However, releasing the learned Myerson'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 to integrate pure DP into the learning process of such auction.
Pure Differential Privacy. Given two datasets that differ in one data point, i.e., D, D → , we say an algorithm A satisfies (ω, ε)-approximate DP if for any given output s: Pr[A(D) = s] → e ω [A(D → ) = s] + ε. We say A satisfies pure DP if ε = 0. Pure DP allows no slack in privacy protection, and hence is more challenging to achieve than approximate DP. Previous attempts (McSherry and Talwar, 2007;Nissim et al., 2012) to integrate DP with prior-dependent auctions have been computationally inefficient or guaranteed approximate rather than pure DP. To our knowledge, no algorithm guarantees pure DP for Myerson'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). This issue has been observed in similar contexts, such as online learning (Jain et al., 2012), federated learning (Zhang et al., 2023) and deep learning (Abadi et al., 2016). In our context, to achieve pure DP, implementing exponential mechanism (McSherry and Talwar, 2007) over 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 running time increases by only polylog factors compared to the non-private version.
Under review as a conference paper at ICLR 2025 Notations We use M A to denote the optimal mechanism of 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, M A denotes the Myerson auction fitted on distribution A, and we denote OPT(A) := Rev(M A , A) as the optimal revenue one could get from a distribution A. We use 1 k to denote a k-dimensional vector with all entries equal to 1. We use O and ! to hide polylog factors.
Formally, we define the problem of learning a near-optimal auction with a pure DP: Problem 1.1 (Optimal Auction with (ω p , 0)-DP). Given n samples of k-dimensional distribution D, the goal is to learn a single item auction M with (ω p , 0)-DP, whose expected revenue on D is close to the optimal revenue, i.e., with prob.
Insight. To address this problem, we leverage the insight that, the expected optimal revenue from value distribution is insensitive to 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 is to ensure that the values (hence distribution) returned by DP Quantile Estimation (QE) possess meaningful and provable accuracy guarantees. To obtain such accuracy, our algorithm (Alg. 1) first additively discretize the empirical distribution in the value space to distribution D ω , then estimate the pre-specificed quantiles with DPQE. We improved the accuracy bound of DPQE (DPQUANT, Kaplan et al. (2022)) to accommodate cases with duplicate values. This improved bound allows us to upper bound the statistical distance between the output distribution and D ω , 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 k since the output of mechanism M is of dimension 2k. We present complete details in Section 3 and the complete theorem statement in Theorems 3.2 and 3.3.
Theorem 1.2 (Revenue Guarantee of Private Myerson, Bounded). Given n = !(ω ↑2 ) samples V of the joint distribution D ↓ [0, h] k , there exist a mechanism M that is 2kω p differentially private with running time !(kn) and takes !(1) pass of the distribution. With probability 1 ↑ ε, this mechanism
The prior algorithm does not work for unbounded distributions. Our second algorithm (Alg. 9) addresses the case for ϑ-strongly regular value distributions by efficiently truncating them to bounded distributions with small expected revenue loss. This approach enables the application of our previous mechanism (Alg. 1) 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 on 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 I.13. Theorem 1.3 (Revenue Guarantee of Private Myerson, Unbounded). Given n = !(ω ↑2 ) samples V of ϑ-strongly regular joint distribution D ↓ R k , there exist a mechanism M for unbounded distribution that is 2kω p differentially private with running time !(kn) and takes O(n) passes. With probability
Application: Online auction with nonmyopic bidders. We now describe how our mechanisms incentivize truthful bidding from nonmyopic bidders under practical online auction settings. 2 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. 1, Alg. 9) with a 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 probability by privacy parameter ω p . 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 a 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 5 and Theorem 5.4 for further details. Theorem 1.4 (Revenue Guarantee of Online Mechanism). Given ω ↓ [0, 1/4], under the online auction setting described in Section 5.1), there exists an algorithm (Alg. 3) run with parameter T = !(ω ↑2 ) that, with probability 1 ↑ ε, achieves diminishing regret, i.e.,
where ϑ is a constant specific to bidders' utility model.
DP Mechanism Design. Emerging from McSherry and Talwar (2007), there has been interest in delivering mechanisms with DP guarantees (Nissim et al., 2012;Huang et al., 2018a;Zhang and Zhong, 2022;Huh and Kandasamy, 2024). These mechanism are either no longer optimal in our setting, or doen't generalize to 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 metrics 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 a detailed, complete list of related work topics, please see Appendix C.
Revenue Maximizing Auctions with Pure Privacy Guarantee. Our work is the first to develop a 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 ϑ-strongly regular distributions. For bounded distributions, our mechanism achieves optimal time complexity within polylog factors.
Application to Online Auction Setting. We apply our 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 a small neighbor around the corresponding value. Consequently, these approximately truthful bids enables our solution to generate revenue guarantee that converges to the optimal revenue over time, for time-discounted, or large market bidders. We generalize the i.i.d bidder setting in Huang et al. (2018a) and solve the open problem they proposed.
Extended Analysis 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 focus on empirical performance.
In this section, we outline the preliminaries on mechanism design, differential privacy, and quantile estimation. Additional information can be found in Appendix E.
We now formally define the allocation rule and payment rule of a single item auction.
, where x j denotes the probability that the j-th bidder gets the item, and p j denotes her payment.
Under truthful sample access, the Myerson's auction maximizes the expected revenue. Definition 2.2 (Myerson's Single Item Auction (Myerson, 1981)). For a discrete product distribution (Elkind, 2007), the virtual value for D j at value v j i with support
, where v j i s are ordered in increasing order of i,
and
For these distributions D with nondecreasing virtual value, Myerson's allocation rule A key property we leverage from differential privacy is its immunity to post-processing. Postprocessing 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 auction to a 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 : R n + ≃ R be an (ω, ε)-DP algorithm, and let f : R ≃ R be a random function. Then, f ⇐ A : R n + ≃ R is also (ω, ε)-DP.
Quantile estimation (QE) is used for estimating a 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 a range of the data as H, a dataset X ⇒ H n containing n points from range H, and a set of m quantiles 0 → q 1 , . . . , q m < 1, identify quantile estimations v 1 , . . . v m such that for every j ↓
We now present the definition of statistical dominance and KS-distance below. (2) For some x, F D(x) < F D → (x).
The KS distance between D and
In this section, we introduce the algorithm for fitting a Myerson's auction with a pure privacy guarantee. To ensure pure privacy, since DP is immune to postprocessing, it is sufficient to input a 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 to achieve the desired guarantee. However, the standard guarantees of DPQE collapse when the dataset contains points that are extremely close. This is a critical issue in our setting, as increasing the sample size n 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.
Next, we present DPMYER algorithm (Alg. 1). The algorithm first value-discretize the samples of the distribution additively by ω a , then quantile-discretize these samples by ω q with pure privacy guarantee. Specifically, the quantile discretization estimates the values of the quantile set [ω q , 2ω q , . . . , 1] with pure privacy. Next, DPMYER use the estimated quantile values and the quantile set to construct a distribution, then perturb it to a 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, ω q , ω a , h, ω p )
Input: n samples V ↓ R k↗n + , discretization parameter ω q , ω a , upper bound h, privacy parameter ω p 1: Discretize all values into multiples of ω a ; let the resulting samples be V . 2: Prepare the quantile to be estimated: Q ⇔ {ω q , 2ω q , . . . , . . . , ↖(1/ω q )↙ • ω q , 1}. 3: For each dimension i ↓ [k], decide the prices S [i,:] ⇔ QESTIMATE(Q, V [i,:] , ω p ).
ϱ Estimate the quantiles by DPQUANT (Alg. 4) 5: Construct distribution D based on S, treating the valuations in S as if each has probability ω q . 6: For each i ↓ [k], shift the top ω q quantile of D i to the bottom, fit Myerson on this distribution.
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 ⇓ D → whose valuations are bounded by h, with d ks (D i , D → i ) → ς i for any bidder i, the optimal revenue of these distribution satisfies:
We apply this theorem to upper bound the revenue loss between 1) the quantile-discretized distribution and its pre-quantized 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 to control the KS-distance between the estimation and the ground truth.
We now present the accuracy guarantee of the private Myerson algorithm. Provided the privacy parameter is not too small (i.e, ω p = "(ω ↑1 )), our guarantee implies that the optimal revenue of the distribution does not exceed the revenue of our algorithm on its samples by more than !(ωkh).
Theorem 3.2 (Revenue Guarantee of Private Myerson (Alg. 1)). Given n samples V ↓ [0, h] k↗n of the joint distribution D, DPMYER (Alg. 1) is (2kω p , 0)-DP, and the expected revenue of this mechanism is close to the optimal revenue of distribution D, i.e., with probability 1 ↑ ε:
under parameter ω a = ω q = ω and n = !(ω ↑2 ), where we hide the polylog factors in ! and O .
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 D p and the additively discretized distribution D ω . 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, ε, ω a , ω p , ω q for a clear presentation. Further details are provided in Appendix H.2.
Privacy Guarantee. We know that the quantile estimates from DPQE is (ω p , 0) private (Lem. H.2). Since DP is 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 (2kω p , 0)-DP.
Upper Bounding the Statistical Distance The distribution D p is obtained by changing from distribution D through distribution D, the distribution D ω and D q (Figure 1). 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/ ↔ n) for each coordinate i (with probability 1 ↑ ε/2). 2) By definition, we upper bound the KS-distance between D ω and D q by kω q . 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 D q and D p by k ω for ω := !(1/(ω p n)) (with probability 1 ↑ ε/2).
Upper Bounding the Revenue Loss. We then upper bound optimal revenue loss from D to D p . This upper bound can be obtained by combining the revenue loss from the aforementioned distributions (by revenue shift theorem), with an additive ω a revenue loss from discretization (by Lem. F.1). The revenue loss from statistical shift aggregates to !((1/ ↔ n + ω q + ω)kh) with probability 1 ↑ ε.
Putting it all together. Finally, condition on the DPQUANT proceeds successfully and the samples are close to the underlying distribution (with probability 1 ↑ ε), we get that the expected revenue of DPQUANT on the underlying distribution is at least the optimal revenue from this distribution minus the revenue difference between D and D p by the following inequality:
where the first inequality follows from the optimality of M D on D and the second inequality follows from adding OPT( D p ). By our construction of D p , this distribution is stochastically dominated by D, thus from the strong revenue monotonicity (Lem. F.3), we get that E[Rev(M D p , D)↑OPT( D p )] ↘ 0. Thus, we concluded that the revenue gap is upper bounded by !((1/ ↔ n + ω q + ω)kh + ω a ). We set ε in the statement as 1/k of the ε we used in this proof to generate the final revenue guarantee. We establish connections between the accuracy/revenue guarantee of the original distribution D with the empirical distribution D, the valuediscretized D ω , the quantile-discretized D q and the distribution D p returned by DPQUANT(Alg. 4).
Next, we demonstrate the efficiency of our algorithm, which is achieved through a organized implementation 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 m quantile estimates (of a single quantile). For more details, we refer readers to Appendix H.1. Theorem 3.3 (Time Complexity for Private Myerson, Bounded). Given the same parameters as stated in Theorem 3.2, DPMYER (Alg.1) runs in !(kn) time and requires !(1) passes of the samples.
Proof Sketch. The time dominant step is quantile estimation, which requires log(↖1/ω q ↙ + 1) passes of the dataset. It takes O(k log(↖1/ω q ↙ + 1)/(ω a ω q )) = !(kn) time, since n = !(ω ↑2 ). This step calculates the utility of k↖h/ω a ↙ over ↖1/ω q ↙ quantiles for at most !(1) time. For full version of this proof, please refer to Appendix H.3
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 ϑ-strongly regular distributions, which decays at least as fast as exponential distributions. A key element of our approach is appropriately truncating the distribution, which enables us to extend the discretize-then-DP-quantile method to the unbounded setting. Specifically, we apply the property of the regular distribution that (Devanur et al., 2016), truncating the distribution by 1 ω OPT(D) costs at most 2ω fraction of the optimal revenue (Lem. I.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 a k-approximation of the optimal revenue with pure DP for ϑ-strongly regular product distributions. Our DPKOPT (Alg. 2) algorithm approximates the optimal revenue by running a empirical reserve(ER) over each bidder's distribution truncated at the top ϑ 1/(1↑ε) /4 quantile. 5 Summing up these estimates gives us a !(k)-approximation of the optimal revenue, by the fact that kOPT(D)
Algorithm 2 DP Estimation for Optimal Revenue DPKOPT(V, ω q , ω a , ω p , ϑ) Input: n samples V = {v 1 , . . . , v n }, quantile discretization ω q , additive discetization ω a , privacy parameter ω p , regularity parameter ϑ.
ϱ Estimate the truncation point of D d . 5:
Prepare the quantile to be estimated,
ϱ Apply DP quantile estimate (Alg. 4).
Let F d be the distribution generated by value profile S [d,:] and quantile set Q.
8:
ϱ Estimate the optimal revenue from F d (Alg. 6). 9: end for 10: KREV ⇔ d↔[k] SREV 11: return KREV To guarantee pure privacy, our algorithm estimates the optimal revenue using a DP-estimated proxy F [k] derived from the sample data. This proxy is obtained from truncating the distribution by DPQUANTU (Alg. 7) and quantile-discretizing 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 ωpn k + ω a ). Aggregating these revenue loss concludes that the output is a !(k)-approximation of the optimal revenue. See Appendix I.4 for more details.
Our private Myerson algorithm for the unbounded distribution (Alg. 9) integrate DPKOPT and yields the following accuracy bound. See Appendix I.5 for formal statements and more details. Theorem 4.1 (Revenue Guarantee of Private Myerson, Unbounded). Given ω ↓ [0, 1/4], n samples V of the joint distribution D ↓ [0, h] k , the output of Myerson fitted under DPMYERU (Alg. 9) is (2kω p , 0)-DP, and under
Under review as a conference paper at ICLR 2025
We now study how to integrate our 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-myopic bidders, and have incentives to bid strategically in the current round to increase their utilities over future auctions.
Before presenting our algorithm, we first provide the formal problem definition of the online auction setting. We study online mechanism design over a time horizon of T , where an 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 2. We defer to Appendix J.2 for more details how bidder generates the samples.
For each time t ↓ [T ]:
• The learner/auctioneer sells a fresh copy of the item.
• The learner collects the bids in the form of (b j , a j ), where b j and a j denote the bid and the attribute of the j ↓ [d t ]-th bidder, respectively.
• The learner decides the allocation rule x t and payment p t accordingly. Each item the auctioneer sells is identical, and each bidder has an additive (discounted) utility of the items across rounds. We consider the bidders either have discounted utility or are in a large market. Definition 5.1 (Bidder's Utility). Each bidder j has a quasi-linear utility function at time t: u t j = x t j (v t j ↑ p t j ), where x t j , v t j , p t j are the allocation, value, price for bidder j at time t, 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 φ. At the t-th iteration, the discounted utility is u t j = T r=t u r j φ r↑t . Large Market: (Anari et al., 2014;Jalaly Khalilabadi and Tardos, 2018;Chen et al., 2016): The bidder only participates in a subset S j of auctions, i.e., for each u 1:T = t↔Sj u t , with subset |S j | < l.
Ideally, the learner'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 ε, the learner's objective is to decide an allocation x 1:T and a payment p 1:T that achieves sublinear regret, i.e., with probability 1 ↑ ε,
with the expectation taken over the value 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 h. The algorithm first collects the samples for the first T 1 rounds, by running a commitment algorithm (Alg. 10) that punishes nontruthful bids. Then, the algorithm deploys our previously developed DP Myerson's Algorithm (Alg. 1, Alg. 9) for the remaining rounds to obtain near optimal revenue. In addition to these two steps, our algorithm includes a step where all samples are reduced by ↼ (line 4 of Alg. 3) and projected onto nonnegative value spaces. This step is designed to offset the impact of strategic bidding.
Under review as a conference paper at ICLR 2025
Algorithm 3 Two-Stage Algorithm A BOUNDED Input: Rounds T , learning rounds T 1 , parameter ω a , ω q , ω p , ↼, upper bound h. 1: for t ⇔ 1, . . . T 1 do ϱ Collection Stage 2: Receive bids b t , and attributes a t . 3: Return (x t , p t ) ⇔ COMMIT(b t ). ϱ Commitment Algorithm(Alg. 10) 4:
b t ⇔ P [0,h] [b t ↑ ↼1 k ] 5: end for 6: ( x(•), p(•)) ⇔ DPMYER( b 1:T1 , a 1:T1 , ω q , ω a , h, ω p ) ϱ Fit Myerson's auction (Alg. 1, or Alg. 9) 7: for t ⇔ T 1 + 1, . . . T do ϱ Revenue Stage 8:
Receive bids b t , and attributes a t . 9:
(x t , p t ) ⇔ MYERSON( x(•), p(•)); 10: end for Specifically, the parameter ↼ 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 lie within a small, controllable neighborhood of the true values. The range of this neighborhood is determined by the privacy parameter ω p (hence is controlled by our algorithm), and the bidders' utility functions. By setting ↼ to match the range of this neighborhood, the resulting distribution is dominated by the empirical distribution.
Before presenting the revenue guarantee of our main algorithm, we first introduce a lemma that upper bounds how a bidder's bid deviates from its true value during the collection stage. Intuitively, by the design of our commitment algorithm the bidder will incurs a loss that scales (positively) with the bid deviation, compared to 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 a certain range of their true values to optimize their overall utility. More details in Appendix J.4. Lemma 5.3 (Bid Deviation). For any t ↓ [0, T 1 ], the bidder will bid only b t such that |b t ↑ v t | → 2ς, where ς = 2(l ↑ 1)ω p hk for bidders in a large market; and ς = 2ϑωp 1↑ϑ kh for discounting bidder.
From this lemma, we get that selecting a small ω p would incentivize bid distributions that are close to the ground-truth. Let ↼ = 2ς in our algorithm (line 4, Alg. 3) would yield a distribution that is stochatically dominated by, yet close in revenue guarantee to, the true distribution. Run our DP Myerson algorithm on this distribution would give us sublinear regret, as stated below. Theorem 5.4 (Accuracy Guarantee of Two-stage Mechanism). Given ω ↓ [0, 1/4], n samples of the joint distribution D ↓ [0, h] k , and T 1 = !(ω ↑2 log(k/ε)), T = "(T 1 ), ω a = ω q = ω p = ω, with probability 1 ↑ ε, Alg. need not be optimal over D, we have that:
where in the last inequality we apply revenue shift theorem (Thm. 3.1) to upper bound the first term and apply Lemma J.9 to upper bound the second term. Please refer to Appendix J.3 for more details.
In this section, we 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 is designed to achieve near-optimal revenue for a given value distribution, whereas the latter, while strategy-proof, 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 domains. The lognormal distribution is widely considered a representative or "groundtruth" model in many auction settings, thanks to its capacity to capture a broad spectrum of value distributions commonly observed in economic and market contexts (Gorbenko and Malenko, 2014). A random variable V is said to be lognormal distributed with parameter (µ, ↽), if ln(V ) follows normal distribution N (µ, ↽).
For each value profile, we test various hyperparameters-additive discretization (ω a ), quantile discretization (ω q ), and the privacy parameter (ω p )-and select the configuration with the best performance. For details on DP Myerson's sensitivity to hyperparameters, see Appendix A.
Bidder Profile DP Myerson Second Price Myerson Ref. Normal N (0.3, 0.5) 0.25272 0.15154 (66.7 %) 0.32598 Table 2 Lognormal (µ, ↽) = (↑1.87, 1.15) Normal N (0.3, 0.5) 0.37691 0.33741 (11.7 %) 0.50204 Table 3 Normal N (0.5, 0.7) Lognormal (µ, ↽) = (↑1.87, 1.15) 0.13912 0.11578 (20.2 %) 0.21292 Table 4 Lognormal (µ, ↽) = (↑1.24, 1.04) Table 1: Empirical Revenue of DPMyerson (Alg. 1) under 2-dimensional non-identical value distributions. 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 1, under non i.i.d distribution settings where there is a 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.
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 are independent, non-identical, and can either be bounded or unbounded. By recognizing that the optimal auction mechanism exhibits robustness to 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 a 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 are fitted on bids from previous auctions. In this setting, non-myopic bidders reasons about their utility accross 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 (i.e., time discounting bidder and/or non-discounting bidders in a large market). This result highlights the robustness of our approach in both protecting privacy and maintaining near optimal expected revenue in dynamic, strategic environments.
This failure probability ω is inevitable due to the inherent uncertainty in learning from a finite sample set, see Chapter 1Kearns and Vazirani (1994)
In practice, recognizable non-i.i.d. value distributions are common, e.g., Meta Ad platform (met) requires that each advertiser selects one of six objectives, corresponding to different distributions based on the industry or advertisement topic.
We define the virtual value inverse ε →1 i (ε) as arg minv↑V εi(v) → ε.
More formally, vj ↑ X is the minimum value such that this quantity exceeds qjn.
Without privacy constraints, truncating at the top ϑ 1/(1→ω) -suffices by Lem. I.4. Our algorithm adopt a looser truncation since the DPQUANTU algorithm only return the value of given quantiles approximately.