Credible, Sealed-bid, Optimal Repeated Auctions With Differentiable Economics
Authors: Davidson Cheng
Yang Hong
Ian Miers
John P Dickerson
Michael Curry
Venue: Submitted to ICLR 2023 (2023)
Keywords: Mechanism Design
Differentiable Economics
Deep Learning
Zero-Knowledge Proofs

Abstract: Online advertisement auctions happen billions of times per day.  Bidders in auctions strategize to improve their own utility, subject to published auctions' rules.  Yet, bidders may not know that an auction has been run as promised.  A credible auction is one in which bidders can trust the auctioneer to run its allocation and pricing mechanisms as promised.  It is known that, assuming no communication between bidders, no credible, sealed-bid, and incentive compatible (aka ``truth-telling'' or otherwise truthful-participation-incentivizing) mechanism can exist. In reality, bidders can certainly communicate, so what happens if we relax this (typically unrealistic) constraint? 

In this work, we propose a framework incorporating cryptography to allow computationally-efficient, credible, revenue-maximizing (aka ``optimal'') auctions in a repeated auction setting. Our contribution is two-fold: first, we introduce a protocol for running repeated auctions with a verification scheme, and we show such a protocol can eliminate the auctioneer's incentive to deviate while costing negligible additional computation. Secondly, we provide a method for training optimal auctions under uncertain bidder participation profiles, which generalizes our protocol to a much wider class of auctions in the online ad market. Our empirical results show strong support for both the theory and competency of the proposed method. 

Under review as a conference paper at ICLR 2023
CREDIBLE, SEALED-BID, OPTIMAL REPEATED AUC- TIONS WITH DIFFERENTIABLE ECONOMICS
Anonymous authors Paper under double-blind review
ABSTRACT
Online advertisement auctions happen billions of times per day. Bidders in auc- tions strategize to improve their own utility, subject to published auctions' rules. Yet, bidders may not know that auction has been as promised. A credible auction is one in which bidders can trust the auctioneer to run its allocation and pricing mechanisms as promised. It is known that, assuming no communication between bidders, no credible, sealed-bid, and incentive compatible (aka "truth- telling" or otherwise truthful-pare purticipation-incettvve reality, bidders can certainly communicate, so what happens if we relax this (typ- ically unrealistic) constraint?
mechanism can exist.
In this work, we propose a framework incorporating cryptography to allow computationalll--efiie.
credible, revenue-maximizing (aka "optimal") auctions in repeated auction setting. Our contribution is two-fold: first, we introduce a protocol for running repeated auctions with a verification scheme, and we show such protocol can eliminate the auctioneer's 's incentive to deviate while costing negligible additional computation. Secondly, we provide a method for training optimal auctions under uncertain bidder participation profiles, which generalizes our protocol to a much wider class of auctions. Our empirical results show strong support for both the theory and competency of the proposed method.
INTRODUCTION
The problem of designing optimal, evvenue-maximizing, auctions bears significant theoretical and practical importance in economics: every Google search involves a sponsored search auction D webpage views involve real time auctions for ads, and online platforms like Ebay and Amazon have created markets ran by auctions. This problem is non-trivial: the auctioneer's revenue is dependent on the "best response" strategy of each bidder, which can each be dependent on each other. In his bobel-prize-wimnigg work, Myerson showed the n-bidder, 1-item optimal auction can be solved by essentially computing a virtual bid for each bidder. then maximizing welfare Myerson (1981); Daskalakis (2015). What about multi-item auctions? This has been shown to be no casy task, one clear reason for this difficulty is the size of the bundling space which grows exponentially. Additionally, an auctioneer may set reserve prices or draw lotteries to earn additional revenue. In essence, the optimal auction can be weird and "defying intuition" Daskallkis (2015).
Given no analytical solution have been found in designing the optimal multi-item auction, Daskalakis et al. (2014) have turned towards the complexity of this problem. They demonstrated that, under reasonable assumptions, finding the optimal multi-item auction is #P-hard. This has mo- tivated the line of work called "diffcrentiable economics" " that focus on using machine learning to find desirable solutions to mechanism design problems Dütting et al. 2219), which includes auction design. Differentiable economics approaches consider an auction as a function that takes bids as inputs and returns what item allocated who and how much each bidder pays. This function is usually encoded as a neural network, which can be backpropagated on given a differentiable loss function. The loss function is parameterized by the revenue, incentive compatibility- which we will provide a definition and discuss in more detail in later sections or other desirable properties
A sponsored search auction is one where the website owner auctions different ad spots on the wehpage when certain keyword is searched.

---

Under review as a conference paper at ICLR 2023
of the auction Peri et al. (2021): Kuo et al. (2020). Although differentiable economics is newly- emerged field, recent progress Ditting et al. (2019); Rahme et al. (2020) 202 Curry et al. (202T)
show that it may be the most promising method for approximating optimal multi-iten auctions.
Besides optimality, credibility of the auction is another major consideration. Consider a sealed-bid, one-item, second-price auction P being run between bidder 1 and bidder 2, whereas bidder 1 has valuation of $2 and bidder has valuation of $3. Acting in their best strategy, bidder 1 and bidder 2 bid S2 and $3, and the auctioneer should then allocate the item to bidder charging them $2. However, since the auction is sealed-bid, the auctioneer can tell bidder 2 that they won the auction and bider 1 bid $2.99, which would increase the auctioneer's revenue by $0.99. An auction is said to be credible if the auctioneer has no incentive not to stick to their proposed auction. The significance of auction credibility was brought to light when Google was called out for gaming their proposed second-price online ad auction Schiff (2022).
is known that there exists no sealed- bid, incentive-compatible, and credible auction if communi- cation between bidders is precluded Akbarpour & Lij (2020). The authors of this work admit that modern cryptography along with bidder communication can potentially break the trilemma, but they consider the costs, in terms of computing resources and latency, of cryptographic constrictions too high.
In this paper, propose approach for running repeated auctions that greatly reduces the cost of credible multi-item auction when verified either by revealing bids (i.e. we greatly reduce the number of bids that must be revealed) or using a cryptographic mechanism such First, we show that in a sequence of repeated auctions, we need not run the verification mecha- nism for every round. Instead, we can punish deviations with a penalty that when high enough, can prevent the auctioneer from being untruthful even when only a random set of auctions are au- dited. The repetition of auctions naturally brings up an issue regarding bidder participation which previous works in differentiable economics did not have to deal with, as it is unrealistic to assume that the same set of bidders participates from start to end in repeated auctions. We address this issue by proposing model that takes account of bidder participation uncertainty, and we provide a method to extend previous works in differentiable economics this model, which we support with experimental results.
snoo-knoweedge proofs.
2 RELATED WORK
Neural networks. RegretNet auctions to maximize revenue using deep Tearning. RegretNet has two components: the allocation net and the payment net. Each network treats the corresponding part of the auction as a function, taking the bids from the bidders and outputting the allocation/paymeet other networks developed on the basis of RegretNet to cover specific needs. Peri et al. (202T) con- siders possible human preference in the allocation process. Kuo et al. (2020) focuses on improving the fairness of the auction mechanisms. There are also works focusing on improving the accuracy and efficiency of RegretNet. Rahme et al. (2020) proposed ALGNet as more efficient version of RegretNet, which considers auction design as a auctioneer versus bidders adversarial model.
Degttin Dütting al.] (2019) was the first work train incentive compatible
There are various version of
Verification tools. To prevent the auctioneer from deviating, we need some verification method that does not reveal additional information. Angel & Walfish (2013) proposed a cryptographic ver- ification system called VEX that can be efficiently applied to second price auctions. In VEX, the auctioneer acts as the prover and the bidders act as the queriers. Under some given algorithm, the queriers can verify what the prover proposed is correct without information leakage in a considerable amount of time. More generally, [Lu et al. (202 1) has proposed kero-knowledge proof structures that can work for neural networks, Mishra et al. (2000) has described a cryptography system which can also be applied to neural networks. With all that in mind, we can be confident that it is realistic to introduce verification tools during auction design.
There also exist concrete work on granting credibility in auction design for specific scenarios. Fer- reira & Weinberg 2020) finds a credible and optimal auction for MHR valuations with commitment,
"In second price auction, the auctioneer allocates the item to the highest bidder, and charges them the bid of the second highest bidder. The best strategy for any hidder in the second price auction is to bid exactly how much they value the item.
2

---

Under review as a conference paper at ICLR 2023
and Essaidi et al. (2022) extends that result more general distributions of valuations. What sepa- rates this paper from theirs is that sealed-bid is not a consideration in these two papers, and our work focuses more general setting for neural network-encoded auctions.
BACKGROUND
3.1 AUCTION MODEL
We design a repeated auction with a set of n. bidders N = 21, and m items M = {1,2..., ..., m. over some time horizon T" T, in which the bidders know how many bidders there are. This repeated auction does not partition one auction into several auctions that each sell a subset of the original items. Rather, each round of our repeated auction completes a multi-item auction, then the auctioneer restocks their goods and runs another stage auction. In our model, we assume each round of auction to be independent, and the bidders memoryless agents that only try maximize their utilities in the current round. So extensive-form game equilibria are not being considered, i.e. the bidders do not analyze how their actions in the current round can influence their utility future rounds. We denote such repeated auctions A.
During the f-th round, each bidder has a valuation function 'v, 2M + R20. where (v,(S) denotes how much bidder values the set of items S S M in round t. The valuation function 'v, is drawn independently from a distribution F; over possible valuation functions Vi, whereas F; is fixed in round and is public both bidders and auctioneers. To provide a realistic simplification of the bidders' input space, we can assume the bidders have additive valuation, which means (S() Eves vf (s). Therefore, we can use matrix of size n X to represent 'v. Upon receiving their valuation function round f. bidder then reports their bids the auctioncer. We will let '0 R denote bidder i's bids at round t, and let '0 C "F" denote the full bid profile at round t. We will let the set O contain all possible bids, and we say bidder is truthful in round iff '0 Lv;-
Prior to the first round of the repeated auction A, the auctioneer proposes stage auction function as tuple of an allocation function and a payment function A = (a. p) whereas R=xm + {0. 1 and p: Rnxm + R. We say A = (a. p) is feasible if for any '0 E O, Vm E M. E.EN 2n.m S 1, in other words, no item is allocated more than once. In round f, once the auctioneer receives '0, they invoke some feasible stage auction function 'A= ('a.' p) compute who gets what and how much they pay. We say the repeated auction A is truthful iff V/ E T, A===A
The auctioneer's revenue in round is then 'reu- = Σ (a,(')) 'p:(')).. whereas (z),,, (pe(x) represent the i-th row of (xx)), (a()). Traditional auction design studies ask the auctioneer to pub- lish the mechanism function prior to the auction, and follow it strictly. In the work by AAkbrrpour & Li (2020), they considered the auctioneer as millit--mxiimizin the doors to the study of auction credibility. We take a similar approach in our model. We first ask the auctioneer to publish the mechanism, however, the auctioneer is free deviate from this plan in strategic ways, which means it may be the case that the auctioneer can obtain higher revenue by running some A' + in round / T, thus define the regret of the auctioneer in round as
agent as well, which opened up
"a agRt = max[[ev(] A, (.) rev (A, '0)
*A
such that L A is feasible. Similarly, the utility of bidder is u.(' A, '0, 'v) = (':::"p<('0) (')) may be the case that bidder can obtain higher utility by misreporting, we formalize this by defining the regret of a bidder as
uRgt, max|u, ('A, ' v)] u, ('A ', u))
whereas '0_; '0-.. This is equivalent to searching for bidder i's optimal misreport assuming all other bidders are truthful in round t.
3.1.1 STATIONARY PARTICIPATION
Traditional auction design and differentiable economics studies usually define a stage auction for a fixed set bidders and fixed set of items. Our model won't 't require each bidder show up every round of Á. Rather, will g denote participation profile, which is binary string of
3

---

Under review as a conference paper at ICLR 2023
length that indicates which bidders showed up to the auction. The set G C {0, 1 will contain all possible 9:8 and the set Q will contain 9;8 that entail the probability of g. at any round E [T]. This implies the probability distribution of participation profiles is stationary, and we call this the stationary participation model. We will use fixed-bidder model to denote the special case where
|G] = 1, G (<
3.2 CRYPTOGRAPHIC BACKGROUND
Commitments A commitment scheme is cryptographic protocol that allows user to commit data by publishing the commitment without revealing the actual data. Given the data and a commit- ment, anyone can verify that the data has not been changed since the commitment Commitment schemes are said to be binding-ove -one commiteed, data cannot be changed even by the original owner-and hiding-the commitment on it's own does not reveal the data. A simple efficient commitment scheme consists of picking a 128 bit random number and hashing together with the data to be committed to.
published.
Zero-Knowledge Proof A zero- knowlenoweddge proof allows a prover to convince one or more verifiers that some statement hold without revealing how or why. [Goldricc et al. (1986) have shown that there exists zero-knowledge proof for any NP-relation thus there exists a vero-knowledg. proof for the correctness of auctions. More concretely, the last decade as seen marked advances practical zero- knowledge proof systems to the point where they efficiently handle matrix multiplications and even neural networks. [iu et al. (02TT) build a non-interactive zero- cero-knowledge proof for predication in neural networks: given model, the zero-knowledge proof shows that its output is correct for given inputs.
PROTOCOL
We define, in Algorithm]] 1 the protocol that propose. For the sake of comparison, also define (Appendix: I. default auction protocol if companies like Google were to adopt recent works in differentiable economics like Dütting al. (2019); Rahme et al. (2020): Peri al. (202I) into their sponsored search auctions.
Algorithm Proposed Repeated Auction Protocol
Bidder valuation distributions made public (a.p)
Auctioneer proposes
Initialize T E N Initialize logs T.g, Tig. Tpp E RTxx Initialize penalty E ({0) UR++
1+1
while < do :o] <²
auctioneer solicit #0 from bidders auctioneer runs auction with '8 to obtain 'a(*0), (p('))
Tul4;;; 'a('0)
T. 1,p1,, (p()
t t +-t+1
end while
bidders randomly select r E (1, T}
t ver(A, LoIr, :s], La Ir, ::,, Lp[r,::)
8 0 then
penalize auctioneer by penalty
end
whereas the verification function ver is defined below.
Thii holds for hash functions like SHA3.
4

---

Under review as a conference paper at ICLR 2023
Definition 4.1. The verification function ver(A, '0, ",,'d',' ''p)) takes in stage auction A (a,p), the bids of the bidders '0 in round t. along with a hypothesis allocation matrix 'a' E Ruxm and a hypothesis payment matrix 'p' Ruxm. It returns 1 if
'd' a 'p' g p('0),
otherwise returns O.
The log in algorithm D can be implemented with commitments and access to a broadcast channel which ensures all parties the committed bids when they are announced. Upon request, the log provides the bids and results of the auction in a specific round, which can be audited. We have abstracted the audit process as the verification function ver because it can take on various forms. The most straightforward way to accomplish ver is to bring in a trusted third party, possibly at a cost that the bidders and auctioneer pay together. This third party can simply take the bids in round and run it with the proposed auction function. Other than incorporating third-party, the bidders can ask the auctioneer publish the result of the auction in round r, which the bidders can then verify with their commitments in round r. The downside of this approach is that the allocation and payment of randomly selected round will be revealed, so bidder can possibly learn the bidding strategy of another. To address this issue, the bidders can construct zk- zk-SNARK "Zero-Knowlen Succinet Non-Interactive Argument of Knowledge) et al. (202T) out of the auction function, which would prevent the leakage of private information during verification.
Next, we will show that the verification scheme along with the penalty are sufficient to make the auction credible while preserving desirable properties of the stage auction. From now on, when write (AA,, we refer to Algorithm implemented with as its proposed stage auction.
4.1 OBTAINING CREDIBILITY
Given the proposed stage auction function A. let aRgt" be an upper bound on ' 'algt over all possi- ble reported bids A. This bound certainly exists the bidders' valuation distributions are bounded, even if they not bounded in the model, it would be reasonable to assume they are. In practice, this bound can be found by summing the highest market price of every item. Then the additional revenue that the auctioneer makes by being untruthful in out of T rounds is bounded by aRgtt.. Since in algorithm | the bidders are selecting round to verify with a uniform distribution, the probability that the auctioneer is not caught deviating is 1 additional revenue in each untruthful round is
So with the penalty considered, the expected
w penalty]
[1
T w aRg
T
w aRgt
penalty
penalty T
= aRgt*
aRgt
Notice that the above inequality is independent of w, and when penalty > T aRgt", this expression is negative. So if we can estimate aRgt", we can set penalty so that the auctioneer makes negative expected additional revenue per untruthful round. This should prevent the auctioneer from deviating in any round. We include a strategy for the auctioneer to make additional revenue by being untruthful when the penalty is not high enough in appendix
We have identified approach to obtain truthful auctioneers using verification scheme and penalty. We now turn to the problem of maximizing the auction's revenue, which is concerned with the bidders' behaviors. Since we have shown credibility be obtained independent of bid- ders' behaviors, we can assume that the auctioneer will be truthful to their proposed auction from now
4.2 BIDDER BEHAVIOR
In practice, is difficult to predict behaviors of bidders under a certain mechanism. However, using the concept of equilibrium and incentive compatibility, infer some behaviors of the bidders assuming rationality and perfect information. We provide the definition of incentive compatibility in two solution concepts below.
5

---

Under review as a conference paper at ICLR 2023
Definition 4.2. A stage auction A is Bayesian Nash Incentive Compatible (BNIC) if there is Bayesian Nash equilibrium where the bidders report their true valuation. A repeated auction A is BNIC if given every other bidder choose be truthful in every round, then bidder i achieves their optimal utility by bidding trutfully in every round.
Definition 4.3. A stage auction A is Dominant Strategy Incentive Compatible (DSIC) if being truthful weakly dominates every other strategy regardless of other bidders' strategy. A repeated auction A is DSIC if no matler what every bidder does, bidder i achieves their optimal utility by bidding truthfully in every round.
The revelation principle states that for any auction mechanism A (a, such that there exists bidding equilibrium under A, there exists mechanism A' (a' such that A' is incentive compatible (BNIC/DSIC depending on solution concept of the equilibrium) and achieves the same payoff profile as A expectation. The adoption of incentive compatibility is commonplace in mechanism design studies due to this fact, which allows to search in the smaller space of incentive compatible auctions when looking to maximize revenue.
It's not hard to see that in both stage auctions and repeated auctions, DSIC' implies BNIC. In fact, in the fixed-bidder model, the repeated auction (AA) will inherit incentive compatibility properties of the stage auction A.
Lemma 4.4. In the fixed bidder model, A(A) DSIC iff A is DSIC, similarily, A(A) is BNIC iff A is BNIC.
Corollary 4.4.1. In the fixed bidder model. if A is revenue-maximizzng DSIC/BNIC. Then if we set penalty > T aRgt" in A, ((A) is credible, DSIC/BNIC, and revenue maximizing.
The proofs of the above theorems are in appendix A.4.I
This implies find the revenue- maximizing repeated auction ((A) in the fixed bidder model, we can just use the machine learning- based techniques proposed by Dütting al. 2019) to optimize A.
Now we transition to the stationary participation model, where the same set of items are being auctioned each round, but the bidders may change according to some stationary probability distri- bution. In this model, despite the auctioneer's uncertainty about which bidder will participate in any of the future rounds, they can still observe which bidder participates in the current round, as we can emulate pon-piatiiipating bidder by assuming their valuation for each item is O. Therefore, the auctioncer can design a stage auction mechanism that depends on which bidder participates.
Let G contain all participation profiles that happen with non-zero probability, and let 'g E G be the participation profile in the t-th round. The auctioneer will proposed stage auction whereas Å is defined by mapping d('0) O - G and set agg(A) that contains an auction A, for each gs E G, which means [agg(A) |G| s 2". Specifically, the aggregated auction Á is defined by the following piecewise function:
aggregated auction Á as their
(t0))
if d('0) = 91
At()
if d(( () = 92
A( =
A A if d('0) 9
whereas the mapping d can be accomplished by rounding all non-zero entries in '0 to 1, and then find the maximum bid of each bidder. This will result in a binary vector that must correspond to its matching 9. G. It's not hard see that in the stationary participation model, any stage auction function A can be written in the form of an aggregated auction Á which consists of mapping from bids to a set of auctions. Therefore, we will say that the auctioneer selects an aggregated auction as their proposed auction function in the stationary participation model.
Lemma 4.5. In the stationary participation model, for any A₃ Agg(A), A, is DSIC/BNIC, then (A) is DSIC/BNIC.
Theorem 4.6. In the stationary participation model, the repeated auction A(A) is revenue- maximizing iff A& is revenue-maxiimzing for any A E (gg(A).
The proofs of the above statements in appendix A.4.1 From now on, use A to refer to revenue-maximizin instance of Å. Theorem 4.6 informs us that find Å it suffices find set

---

Under review as a conference paper at ICLR 2023
of auctions where each auction corresponds to participation profile and is revenue-maximinn now discuss our approach to this task.
ESTIMATING A+
We expect the size of agg( to grow quickly with respect to the number of bidders. In particu- lar, if the bidders' participation probabilities are independent from each other, the size of agg(A")) (A*) will grow exponentially. Considering the known complexity of finding a single revenue-masn maximizing multi-item auction, we can infer that the task of obtaining Á is daunting. This complexity is some- what relieved by recent works in differentiable economics, if we can settle with approximately optimal auction for each participation profile, each A E (gg((A>) can be approximated with ma- chine learning. However, we would still need to perform auction training |G] number of times, which can be exponential. This section presents an approach to circumvent this complexity, and its performance is experimenially evaluated in the subsequent section.
5.1 TWEAKED DATASET
Our insight for estimating Á is to generate a dataset according to (participation profiles) and Q (probabilities of profiles) under the stationary participation model, call this dataset the "tweaked dataset". Then we try to train an auction that performs well in the tweaked dataset expectation. To put simply, we are estimating every element of agg(AA (A* at the same time. The tweaked dataset will contain size K number frames whereas each frame will be a matrix of size m that contains the valuations of each bidder for each object. To obtain each frame, we first sample participation profile g E G S {0, 13" according to Q, then sample the untweaked valuations gnxm, then element- wise multiply the two after broadcasting g across the items' dimension.
5.2 ARCHITECTURE
We adopt the additive neural network architecture from Rahme et al. (2020), which consists of multi-layer perceptron (MLP) allocation and payment network. Similar styles of mechanism neural network architectures are used in Duetting et al.] (2019); Duan et al. (2022); Ivanov et al. allocate item, and the optimal auction can take
(2022). Since the auctioneer can choose on the form of a lottery, the allocation network is implemented as two networks. The first one (f gaxm +
[0. _]"") computes the probability that the auctioneer allocates each item; the sec- ond one (fz mm + [0, 1] 1]=xm) computes the probability that an item will be allocated to each bidder if the auctioneer allocates that item. In Rahme al. (2020) and our implementation, (0) = (MMLP(B), f2( = poftnax(MLP(B)
(allowing for ghost bidders/items representing "no allocation"). The final allocation is then obtained with a, = [B)] [/2(B]] The payment function is computed
o (ML)( ratio of the bidder's 's bid that they shall pay.
5.3 REGRET ESTIMATION
To compute the bidder's regret, we follow the approach proposed by Duetting et al. (2019) and use misreport optimization loop estimate the optimal "untruthful bid" of each bidder assuming other bidders are truthful. The misreport function is a MLP whose width and depth will be specified. The output of the misreport network is n m matrix ratios between 0 and 1, which when element- multiplied by the valuations returns the matrix of misreports. This allows the indi- vidual rationality constraint to be built into the network. When testing the misreport module, we noticed that there does not seem to be a general optimal misreport network: one misreport network can perform excellently for one auction but horribly for another. Therefore (similar to the choice of |Rahme et al. (2021b)), we reinitialize the weights of the misreport network at each iteration of the auction training loop. We also found that the efficiency of the regret estimation step is greatly improved if we allow early stopping of the misreport, which means stopping the misreport optimiza- tion loop once the regret stops increasing for a certain number of rounds. Hyperparameters for early stopping will be specified in section 6.
7

---

Under review as a conference paper at ICLR 2023
5.4 TRAINING
The training loop consists of three steps: 1) computing the auctioneer's revenue and bidders' regret 2) computing loss and gradient 3) backpropagation. A nice property of thee loss function would be providing comparison between two auctions with different revenue and regret. This is accom- plished using Proposition from Rahme al. (2020). attributed to Balcan et al. (2005) and Nisan.
Lemma 5.1. (Rahme et al. (2020)) Let rev, rgt denote the expected revenue and regret of some auction, then there must exist some other auction that achieves zero BNIC regret and revenue of (vrev - /r under the same setting.
The lemma above can be applied to DSIC auctions in 1 bidder, m item auctions. Whether also holds for general n bidder, item DSIC auctions is still an open problem Rahme et al. (2020). Regardless, for any auction with non-zero regret, it provides lower bound for the revenue of its zero-regret counterpart in BNIC solution concept. Nevertheless, |Rahme (Ramhe et al. (2020) argues convinc-
ingly that it is a reasonable single metric to compare auctions which we can estimate the competency of any non-zero regret learned auction. We will adopt the above lemma as the loss function, which is stated below.
loss (Vrrvv
/rrg') rgt'..
(The -rgt' term is for making the model slightly inclined towards auctions with low regret.)
EXPERIMENTS
We perform experiments to test the capability of our proposed training procedure recover A We first choose the n = 2, m = 2, bidder valuation uniformly distributed between [0, 1] case, because it is classic test case for automated mechanism design SSanhholm & Likhodedov (2015); Likhodedov &
Sandholm 2205), widely used by related papers in differentiable economics Duetting et al. (2019);
Duan et al. (2022); Ivanov et al.] (2022); Rahme et al.) (2021a b): Curry et al. (2020) and allows an in-depth evaluation of the results. In particular, we pick three scenarios to test on: 1. bidder participates with 0.2 probability, bidder participates with 0.8 probability,
bidder participates with 0.5 probability. bidder 2 participates with 0.7 probability, 3. bidder participates with 0.7 probability, bidder participates with 0.9 probability. Since the participation probabilities of bidders all independent, the participation profiles for each scenario are the same, namely 91 =< 1, 92 =< 1,0 >; Us =< 0, >; 94 =< 0,0 >. However, the probabilities of each profile are different across scenarios and specified below.
Scenario 1: 91 0.16, Q2 = 0.04, = 0.64, 21 0.16
Scenario 2: q1 = 0.35, Q2 = 0.15, 43 = 0.35, 94 = 0.15
Scenario 3: Q1 0.63, Q2 0.07, Q3 0.27, Q4 0.03
All of the scenarios above are trained on their corresponding tweaked dataset with K 20, 000. and the depth, width of the allocation MLP, payment MIP,, and misreport MLP are all set to 7 and 100. The learning rate of the misreport optimizer is set to x 10-5 and it is looped for 300 times with early stopping point set to 100. The auction function optimization step is looped for 300 times with learning rate of 5 10-4 for the first 100 iterations, 5 10-3 for the second 100 iterations, and 5 x 10 for the last 100 iterations. After training, we evaluate the learned auctions on a separate test set for both the aggregated auction and the individual auction performance. We first report the results on the three scenarios above when trained on tweaked datasets. Note that each scenario is trained with designated neural network, and tested on that network.
Table 1: Performance of three learned auctions in their corresponding scenario after training on the tweaked dataset
Scenario
rev' ogg
rey agg
rgl Pgyag
(Vrev' revv agg
rgV/
0.470
2s 0.513
5 x 10-3
0.375
0.580
Rs 0.579
9 x 10-3
0.444
0.765
As 0.735
0.013
0.577
8

---

Under review as a conference paper at ICLR 2023
For comparison, also train an auction function untweaked dataset, and test it the test sets the three scenarios above.
Table 2: Performance of neural network trained on untweaked dataset tested on the three scenarios
Scenario
rev's egg
rev
rgt
(Vrevaan ogg
V /rgtann
untweaked
0.854
0.87
3 x 10
0.822
0.279
Ri 0.513
9 x 10-4
0.247
0.422
2s 0.579
3 x 10-3
0.352
0.615
0.735
x 10-3
0.514
The comparison between table and table 2 show that the networks trained on the tweaked dataset perform markedly better than the benchmark. In theory, A", the optimal auction under stationary participation profile is simply a "weighted sum of its individual auctions. So we should expect the learned auctions from each of the three scenarios to perform decently in each individual participation profile. We evaluated this by testing the three neural networks trained on the tweaked datasets on the 2 x and x 2 scenarios additionally.
Table 3: Benchmark performance of learned aggregated auction on individual auctions
91 1,
92
1,0
9s
0,
NN
rev
revi
rgt/
rev
rev
rgt/
rev
rev
rgt
0.688
RJ 0.87
8 x 10
0.031
0.55
3 x 10-5
0.563
0.55
7 x 10
2
0.886
R 0.87
0.019
0.503
0.55
5 x 10-3
0.563
0.55
5 x 10-3
0.927
x 0.87
0.017
0.473
0.55
x 10
0.535
0.55
X 10-3
We see that the learned auctions perform relatively well on the individual auctions: achieving revenue close to the optimal in most cases while maintaining low regret. We see a trend that the performance on the individual auctions dependent on the probability of the participation profile associated with that auction. For example, in scenario 1, the participation profile Ø2 =< 1,0 happens with a low probability of 0.04, so for the first neural network, if it performs badly g2 won't harm the aggregated auction performance much as if it performs badly in g3 =< 1, >, which happens with probability 0.64. Therefore, although g2 and g3 are in theory the same auction, the first neural network performs better in Øs. This trend can also be found in the other two scenarios. larger scale experiment with bidders and 10 items is included in Appendix A.5
7 CONCLUSION
In this paper, we demonstrate how to run credible, incentive compatible, privacy-preserving and revenue maximizing auctions in settings where auctions take place with high frequency. Our work is inspired by the impossibility theorem proposed by Akbbrrpour & Li (202)), where a trilemma is established between credibibility, incentive compatibility, and privacy preeeerv-peeiigngg in stage auctions assuming no communication between bidders. Because cryptographic protocols are efficient these days, we relax the assumption of bidder communication, and show that by implementing a verifi cation scheme in repeated auction, we can obtain credibility while maintaining incentive compat- ibility and bidders' privacy. We also propose a stationary bidder participation model, which to our knowledge is the first in the differentiable economics community. We provide method for train- ing revenue-maximizal maximizingiiigggm auctions in the stationary participation model, whose theory and efficacy is tested with two experiments. We note that our method for training revenue maximiziin auctions in the stationary participation model can not only be applied in our repeated auctions protocol, but also any stage auction where participation of bidders is uncertain.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammad Akbarpour and Shengwu Li. Credible auctions: A trilemma. Econometrica, 88(2): 425-467, 2020.
Sebastian Angel and Michael Walfish. Verifiable auctions for online ad exchanges. In Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, pp. 195-206, 2013.
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'O5), pp. 605-614, 2005. doi: 10. 10.110000 109//F0CS2000S
Michael Curry, Ping- Ych Chiang, Tom Goldstein, and John Dickerson. Certifying strategyproof auction networks. Advances in Neural Information Processing Systems, 33:4987-49998, 2020.
Michael J Curry, Uro Lyi, Tom Goldstein, and John Dickerson. Learning revenue- maximizing auctions with differentiable matching. In International Conference Artificial Intelligence and Statistics (AISTATS), 2021.
Constantinos Daskalakis. Multi-item auctions defying intuition? SIGecom Exch., 14(1):41-75, nov 2015. doi: 04.14452284592.2845522 Ut//attee///bb..oog0001111/////3
2845928
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmss, pp. 1002-1188 SIAM, 2014.
Zhijian Duan, Jingwu Tang, Yutong Yin, Zhe Feng, Xiang Yan, Manzil Zaheer, and Xiaotie Deng. A context-integrated transformer-based neural network for auction design. arXiv preprint arXiv:2201.12480 12489, 2022.
Paul Duetting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning (ICML), 2019.
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference Machine Learning, pp- 1706-1715. PMLR, 2019.
Meryem Essaidi, Matheus V. X. Ferreira, and S. Matthew Weinberg. Credible, strategyproof, op- timal, and bounded expected-round single-item auctions for all distributions. Schloss Dagstuhl LeibnizzZenntrum für Informatik, 2022. doi: 10.4230/LIPCC.IITCS 2022.66. URL https:
7/drops. dagstuhl. htte/ppu/vvooie httpp///s/oolleeeee///222/555550
Matheus V. X. Ferreira and S. Matthew Weinberg. Credible, truthful, and two-round (optimal) auctions via cryptographic commitments. In Proceedings of the 21st ACM Conference on Eco- nomics and Computation. ACM, jul 2020. doi: 00.1145/33914433339999 URL https: (/doi.org/10.1133
Oded Goldreich, Silvio Micali, and Avi Wigderson. How to prove np-statements in zero- knowledge, and methodology of cryptographic protocol design. volume 263, pp. 171-185, 08 1986. ISBN 178-3-54001804744 doi: 10.100773-540-4772---1111
Dmitry Ivanov, Iskander Safiulin, Ksenia Balabaeva, and Igor Filippov. Optimal-er auctions through attention. arXiv preprint 2rXi:2220.1331100 2022.
Kevin Kuo, Anthony Ostuni, Elizabeth Horishny. Michael J. Curry, Samuel Dooley, Ping yeh Chi- ang, Tom Goldstein, and John P. Dickerson. ProportionNet: Balancing fairness and revenue for auction design with deep learning- arXiv preprint arXiv:2010.06399: 2020.
Anton Likhodedov and Tuomas Sandholm. Approximating revenue- maxinui-maximiiing combinatorial auc- tions. In AAA/ Conference Artificial Intelligence (AAAI), 2005.
10

---

Under review as a conference paper at ICLR 2023
Tianyi Liu, Xiang Xie, and Yupeng Zhang. zkenn: Zero knowledge proofs for convolu- tional neural network predictions and accuracy. Cryptology ePrint Archive, Paper 2021/673, 2021. URL https://epprnt.. iacr. org/2021/673 org/2021/677 6/33
https://eprint: iacr.
Alejandro M. Manelli and Daniel R. Vincent. Bundling as an optimal selling mechanism for multiple-good monopolist. J. Econ. Theory, 127(1):1-35, 2006.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Sympo- sium (USENIX Security 20), pp. 2505-2522. USENIX Association, August 2020. ISBN 978-1- 939133- 17-5. URL https:/ www. usenix org/ http:///ooaeeeeeeeeeeeeeeeeeeeaa
presentation/mi.
Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):88-7,, 1981.
Neehar Peri, Michael Curry, Samuel Dooley, and John P Dickerson. Preferencenet: Encoding hu- man preferences in auction design with deep learning. In Neural Information Processing Systems (NeurIPS), 2021.
Jad Rahme, Samy Jelassi, and S Matthew Weinberg. Auction learning as a two-player game. arXiv preprint arXiv:2006.0564 2020.
Jad Rahme, Samy Jelassi, Joan Bruna, and S Matthew Weinberg. A permutation-cquivrriant neural network architecture for auction design. In AAAI Conference on Artificial Intelligence (AAAI), 2021a.
Jad Rahme, Samy Jelassi, and S Matthew Weinberg. Auction learning as a two-player game. In International Conference on Learning Representations (ICIR), 2021b.
Tuomas Sandholm and Anton Likhodedov. Automated design revenue-maximiizng comiiiiittiioooommomomoiiia combinatorial auctions. Operations Research, 13(5):1000-102)) 2015.
Allison Schiff. More Details Revealed On Project Bernanke And Jedi Blue In Newly Unsealed January 2022.
Google Suit. sernaakwwundddddd-eeeeeeeeeeeeee

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1
BENCHMARK ALGORITIIM
The following algorithm provides a default way to implement auctions learned with diffcrentiable economics techniques Dütting et al. (2019) in high-frequency auction market such as online ad auctions.
Algorithm 2 Default Repeated Auction Protocol
Bidder valuation distributions made public Auctioneer proposes A = (a.p) p)
Initialize 7 1-1
while * do auctioneer solicit '0 from bidders
auctioneer runs auction with '0 to obtain 'a(*0), 'p('0)
t t- +
end while
Note that the running time for our proposed auction protocol described in algorithm and the default protocol algorithm 2 are both linear with respect to T assuming the auction, queries of the log, and the verification scheme ver take constant time.
A.2 SAMPLE UNTRUTHFUL STRATEGY FOR AUCTIONEER
We now illustrate strategy for the auctioncer when the penalty is not set high enough in Algorithm Recall that this means penalty T aRgt". Since the valuation distribution is fixed, then ' shall be sampled from the set all possible bids θ C R=*m Suppose there exists a set of misreports
O' = (0' 0' = O, a, 2 penalty/2 / for some feasible A', Prob(0') > 0}:
then if the auctioneer deviates whenever '0 E e' and be truthful otherwise, they obtain equal or higher revenue compared to the strategy of always being truthful.
A.3 REGRET AND REVENUE OF INDIVIDUAL AUCTIONS
Corollary A.0.1 (Corollary of Lemma 5.1 by Rahme et (220 Let be the optimal revenue for an additive auction with n bidders and m items. Then under the BNIC solution concept, for any other auction A' that achieves expected revenue reu' and expected mean regret rgt', the following inequality must hold,
rev* 2 (Vrev' vrrg')²
The above corollary allows us find an upper bound for the revenue of auction given its regret and the optimal revenue, which useful in estimating the revenue an individual auction within an aggregated auction. We will discuss this below.
In section 5.3 and 5.4, we have transformed estimating A into learning pvenue-maximizaee auction in a setting where bidders have a "tweaked" valuation distribution. By definition of the aggregated auction Á, if we obtain A' as decent estimate of Å", we should expect at least some A, E (A' to be near revenue-maxe maximiiin as well. For example, if we are given n 3, m = 2, all bidders have valuation uniformly distributed in [0, 1]. and {< 1, >, < 0, >}. and we learn a competent auction A' for this stationary participation model, then we should expect Å' to perform well in the fixed-bidder bidder item auction as well. Thankfully, this is something can check because analytical results are known for special cases of combinatorial auction including
bidder 2 item case Manelli & Vincent (2006).
12

---

Under review as a conference paper at ICLR 2023
We now let A' denote the learned aggregated auction, and let rev/, rgt; denote the expected revenue and regret of A E agg(A') which corresponds the participation profile 9i that happens with probability q.. We will let rev; denote the revenue of the optimal auction for participation profile 9h- Suppose the aggregated auction Å' achieves revenue rev' agg and regret rgyagg then we know the following about the performance of individual auctions A/s.
Lemma A.I. The regret of the individual auctions can be bounded in the following way rgl, S super
Proof of Lemmn A.I The aggregated regret rytagg is weighted sum of the regret of each of its individual auctions rghagg Liejay q: rgt,.
Lemma A.2. The revenue of the individual auctions can be upper bounded in the following way
Vreet +
Igtagg
ree; I
4
whereas rec" is the optimal revenue.
Proof of Lemma A.2 From Corollary 5.1.1, we know Vrev' S Vrev* + Vrgf'. Plugging in rgt' <
obtain the claim.
4
Thus if we know the optimal revenue of the individual auctions Å, and we know the revenue and regret of the learned auction A', we can find upper bounds of the revenue and regret of each individual learned auction. Since the aggregated revenue is of the revenue of each individual auctions weighted by their corresponding probability, we can also obtain a lower bound for the revenue of the i-th auction by subtracting away the upper bound of every other auction.
Theorem A.3. The revenue of A E agg(A')) is guaranteed in the following way
rev'
-rev
GG| -1
V /rg
reu reul
agg
agg
rg
48 reuţ
qi
qi
qi
Proof of Theorem
A.3
We can plug lemma A.2 into
rev' agg
grev
to obtain
rgt
qi reu 2 rev
(veu
341
expanding the right hand side leaves
renj + rglagg
rglagg
qi reo 2 rev
Σ
+ 2 rgl
IG
q. rev, 2 revlag (IG) - 1) rgl.
4i rrey - 2 rrgh agg
V V /
13

---

Under review as a conference paper at ICLR 2023
notice that
[G1
1G
- (qx rev, +
43 Teuj) = Σ
gyrev -rev",
j=1
131
4j ret) -reb" + 7 TEU,
3/1
plugging leaves
G7
reel 2 revlag (IG) - 1) rgglag
revagg + reu] - 2/ rgl agg
22/rgl
Vüjy reuz)
17
revl - 9i reu 2 (red'ag revagg) - (IG) - rgt 2v rgt aggg
V /
agg
reu' agg - reu agg
G| -1-1
V rrgga agg
|G
reu,
rev, 2
rgt rggagg 2
93 reos
reu3
qi
qi
qi
J
Note that theorem A.3 is quite conservative bound, because lemma A. is conservative bound for rgl,, and theorem A.3 repeatedly applies it |G] - 1 many times. Therefore as |G] increases, the bound in theorem A.3 will become loose pretty quickly. We also provide an alternative lower bound for rev' that is tighter than theorem A.3 the tradeoff is that this tighter bound contains maximization problem.
Proposition A.4. The revenue of A', E agg(A") is guaranteed in the following way
IG|
Σ 95 (Vrevf Vus - rgtt
4: rev 2 rev'agy max
under the constraint that u E [0, 1| and E U4
The maximization problem inside this bound can make it seem complex, in fact, the objective func- tion of the maximization problem is quite straightforward, thus the bound can be computed effi- ciently as well.
A.4 PROOFS
A.4.1 PROOFS IN SECTION 4
To see that A(A) is BNIC implies BNIC and A(AA DSIC implies is DSIC, observe that A is special case of A(A) where T 1. For the other direction, suppose A is BNIC and every bidder but i truthful in each of the rounds, then always being truthful weakly- dominates every other possible strategy for bidder The same argument goes for DSIC.
Proof of Lemma 4.4
I1
14

---

Under review as a conference paper at ICLR 2023
Let uijj be the expected utility of bidder i by bidding truthfully in Aj (g regardless of other bidders' strategy. By the assumption that every A, ogg(A) is DSIC, Uij must be the highest utility that bidder can obtain in Aj. Now suppose (AA) reaches round t, which means the auctioneer will run some A₁ E (gg((A) that corresponds to 'g. Despite the bidder may not know what A, is, the maximum expected utility for bidder i in this round is uij, which is
Proof of Lemma 4.5
achieved by bidding truthfully. The proof for BNIC follows similar argument where we relax the assumption to expect other bidders to be truthful.
Proof of Theorem 4.6
The expected revenue per round of ((A) can be computed as
G
Σ BG
(expected revenue of Á at gi)
q (expected revenue of A,).
It's then clear that the expected revenue per round of A(A) can be improved iff the revenue of any A; E (A) can be improved.
A.5 ADDITIONAL. EXPERIMENTS
We now slightly larger scale experiment: = 10. bidders valuations uniformly distributed between [0, 1]. We again pick three scenarios where the bidders' participation proba- bilities are independent, thus the three scenarios will share the same set of participation profiles,
which are =< 1, 2.91 =< 0,1,1 =< 1,0, 2,91 =< 1, 1,0 >, 91 =< 1,0,0 0
:9 =< 0,1,0,, 91 =< 0, 0, >, Is =< =<0,,, 0, >. However, in each of the three scenarios, the participation profiles will take place with different probability.
Table 4: Probability of participation profiles
Scenario
g1
92
93
g4
Fs
96
97
gs
1
0.032
0.128
0.128
0.008
0.032
0.032
0.512
0.128
2
0.175
0.175
0.175
0.075
0.075
0.075
0.175
0.075
3
0.441
0.189
089
0.049
0.021
0.021
0.091
0.009
We perform the same experimental procedure as we did for the 2 x 2 experiment, except the al- location MLP, payment MIP, and misreport MLP all expanded to have depth of 17 and width of 120. We also only loop the misreport module 100 times with no early stopping on each regret estimation step. The auction function optimization step is also looped for 600 times with learning rate of 5 x 10-4 for the first 200 iterations, 5 x 10 - for the next 200 iterations, and 5 x 10 for the last 200 iterations.
Table 5: Performance of three learned auctions in their corresponding scenario after training on the tweaked dataset
Scenario
rev
revagg
rgfag
(Vrev'agg / /rgg'age
3.725
3.378
0.139
2.426
2
4.285
2 4.183
0.095
3.105
4.696
4.817
0.093
3.47
15

---

Under review as a conference paper at ICLR 2023
Table 6: Performance of neural network trained untweaked dataset tested on the three scenarios
Scenario
revagg
re
rglngg
(vrev
V /rglogo
untweaked
5.172
R2 5.55
0.065
4.076
0.816
3.377
0.014
0.612
2
1.918
4.183
0.03
1,469
3.3
4.817
0.047
2.56
Table 7: Benchmark performance of learned aggregated auction on individual auctions (* implies estimated value).
Scenario 1
Scenario 2
Scenario
ree
5.334
5.392
5.427
91 =,1,,>>>>>>>
revj
Ra 5.55
= 5.55
= 5.55
rgt
0.586
0.086
0.086
rev4
5.463
5.090
5.068
92 =< 0,1,1>
rev
& 4.55
~ 4.55
2 4.55
rgt/
0.261
0.145
0.119
rev
4.754
5.122
5,095
93 1,0,1
revz
2s 4.55
s 4.55
x 4.55
rgtz
0,456
0.16
0.149
rev
4.995
5.067
5,014
91 << 1,1,0>
rev
4.55
4.55
4.55
rgt'
1.468
0.13
0.207
revl
0.002
3.651
3.287
96 =< = 1,0,0>
reug
3.47
3.47
3.47
rgt's
2 x 10-9
0.116
0.163
revg
4.428
3.517
3.625
96 =< 0,1,0
reug
Rs 3.47
3.47
3.47
rgle
x 10-5
0.087
0.14
rev,
4.06
3.676
6 10
97 - 0,0,1
reu;
z 3.47
3.47
< 3.47
rgtz
0.103
0.131
1 10 10-4
16


Reviews:
[{"review_id": "wJOltxHb0po", "reviewer": "Reviewer_eKk8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors consider the problem of a monopolist seller auctioning multiple items to many buyers, repeatedly over many time periods. They propose to learn the single-shot approximately IC mechanism using essentially off-the-shelf deep learning approaches (I guess this is why they submitted to ICLR?). Then they propose to solve the seller’s credibility issue by revisiting a random time period, revealing the bids and punishing the seller if they violated the auction terms.", "summary_of_the_review": "See numbered items above", "strength_and_weaknesses": "1.\tYou abstract the audit process, and essentially use an off-the-shelf auction learning algorithm. It feels like there isn’t much novelty left in your submission. \n2.\tI don’t think that your bid-revealing protocol resolves the seller credibility issue. An incredible seller could have a dummy buyer participating in the auction and submitting bids optimized to raise the price for the winning bidder. See e.g. https://arxiv.org/abs/2205.14758 on how to do it right.\n3.\tWhen considering repeated auctions, it is sub-optimal to use even the “optimal” single-shot auction many times. There is a rich literature on dynamic mechanisms that you should go read.\n4.\tIt is not clear from your model how do bidders choose bids. Do they also do some kind of regret minimization? What happens when the auction uses a lottery?\n\n**Typos:**\n\n•\t“Forty years of little analytical results” – what?! There are hundreds of papers on this. They don’t get fully optimal solutions for every case, but this is super well studied.\n\n•\t“Despite differentiable econ..” -> “Although…”\n\n•\tI can’t find the reference for Mor (2022)\n\n•\t“bids(i.e. “ -> “bids (i.e.~”\n\n•\t“the forgo the cost”\n\n•\tAlgo 1 pseudocode: what is t not-greater-than T?! Did you mean \\le?\n\n•\t“pay for together”\n\n•\t“and ran it” -> run\n\n•\t“the the weights”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ggig6W6YnXI", "reviewer": "Reviewer_cqog", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies how to combine cryptographic tools with neural auction design to provide credible optimal (repeated) auctions. The idea is to adding a verification step in repeated auctions to check the credibility of the auctioneer, while with properly design penalty, only excuting verification for a limited times is enough to prevent auctioneer's cheating. The repeated auction desgin through deep learning is transfered from previous work for single round auction, with an aggregation under bidders' stationary participantion. The approximate revenue maximization is supported by experiments.", "summary_of_the_review": "The paper consider an important issue on credibiliy in differentiable auctions. The designed protocol is convincing with both theoretical analysis and experiments. Overall, I would recommend acception.", "strength_and_weaknesses": "Strength:\n1. The issue of credibility is important for the field of differentiable economics. \n2. The idea of introducing cryptographic tools, although straightforward, is quite convicing. The combination of verification and repeated auctions is properly designed, with clear theoretical analysis for credibility guarentee and corresponding revenue.\n\nWeaknesses:\n1. The assumption of stationary participation may be kind of strong. Nevertheless, I am not sure whether there has been related works on this issue.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ctin4aH-YY8", "reviewer": "Reviewer_zy43", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "It is known that no credible, sealed-bid, and incentive compatible exists, assuming no communication between the bidders. In this work, the authors relax this assumption and propose a framework to run efficient, credible, and revenue-optimal repeated auctions with cryptographic tools. Their main contributions are as follows:\n1. The authors show how an auction can be made credible with just a verification scheme and a penalty. This verification scheme could simply be to bring in a trusted third party for auditing. They also show how to set a penalty that is independent of the auctioneer being untruthful.\n2. The authors also propose a stationary bidder participation model and a method for training revenue-maximizing auctions in this context. They demonstrate the efficacy of this approach through a couple of experiments.", "summary_of_the_review": "Overall this is a good paper. The use of differential economics for running credible, incentive-compatible, and revenue-maximizing auctions is a new and an exciting direction to pursue.", "strength_and_weaknesses": "**Strengths:** The proposed framework is quite novel. The authors also perform sufficient experiments to illustrate the efficiency of the training procedure. This direction of research of also quite relevant and is of significant importance especially given that a lot of tech companies generate revenue through auctions.\n\n**Weakness:** The approach is not quite scalable, although I think this is a good first step.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CkLrFKnq0Wk", "reviewer": "Reviewer_53Tu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper examines how to design credible auctions (i.e. auctions where the auctioneer is not incentivized to deviate from their proposed mechanism), with a focus on repeated auctions. The setup is that the auctioneer proposes an allocation rule and a payment function at the beginning of the game, and then they run a multi-item auction at each time step. The paper proposes using a cryptographic verification scheme and penalties at randomly chosen set of time steps to guarantee credibility. \n\nThe paper then considers the design of revenue-maximizing auctions in the repeated auction setup in the case where not all bidders necessarily participate in the auction at every time step (they change according to a stationary probability distribution). They propose a method for training revenue-maximizing auctions in this model and evaluate the method in simulations on small auction setups. ", "summary_of_the_review": "The paper studies an interesting setup of designing credible auctions in the repeated auctions setup. However, both the theoretical and empirical contributions are somewhat incremental relative to prior work. ", "strength_and_weaknesses": "Strengths:\n- The idea of using cryptographic verification schemes to guarantee commitment of the auctioneer is interesting. It provides a different approach to ensure credibility than is typically studied in market design (it is obtained by relaxing the assumption of no bidder communication). \n\nWeaknesses:\n- The theoretical contribution is limited. The proof of credibility is straightforward, since the penalty is set so high that it guarantees that the auctioneer would rather stick to the proposed mechanism than deviate. It may be more interesting to investigate tradeoffs between approximate credibility and penalties. \n- The empirical contribution—designing revenue-maximizing auctions in the repeated auction setup—seems incremental relative to existing work in the automated auction design literature (e.g. Duetting et al., 2019, Rahme et al., 2020). \n- The two contributions in this paper—proposing a scheme to guarantee credibility and training revenue-maximizing auctions in the repeated auction setup when bidders can change between rounds—are somewhat disjointed. It is perhaps confusing to combine these investigations into a single paper. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject