Prior-independent Dynamic Auctions for a Value-maximizing Buyer
Authors: Yuan Deng
Hanrui Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: dynamic auctions
value-maximizing buyer
return on investment (ROI) constraint

Abstract: We study prior-independent dynamic auction design with production costs for a value-maximizing buyer, a paradigm that is becoming prevalent recently following the development of automatic bidding algorithms in advertising platforms. In contrast to a utility-maximizing buyer, who maximizes the difference between her total value and total payment, a value-maximizing buyer aims to maximize her total value subject to a return on investment (ROI) constraint. Our main result is a dynamic mechanism with regret $\tilde{O}(T^{2/3})$, where $T$ is the time horizon, against the first-best benchmark, i.e., the maximum amount of revenue the seller can extract assuming all values of the buyer are publicly known.

Prior-independent Dynamic Auctions for a Value-maximizing Buyer
Yuan Deng Google Research dengyuan@google... com
Hanrui Zhang Duke University hrzhang0cs duke. edu
Abstract
We study prior-independen dynamic auction design with production costs for a value-maximizing buyer, a paradigm that is becoming prevalent recently following the development automatic bidding algorithms advertising platforms. In contrast to a utility-aximizing buyer, who maximizes the difference between her total value and total payment, a value- maleimmaximizing buyer aims to maximize her total value subject return investment (ROI) constraint. Our main result is dynamic mechanism with regret (TT2/3), where I is the time horizon, against the first-best benchmark, i.e., the maximum amount of revenue the seller can extract assuming all values of the buyer are publicly known.
Introduction
Automatic bidding has become one of the main options for advertisers to buy advertisement op- portunities in the online advertising market (Dolan 2020]. The prevalence of automatic bidding is partly driven by the fact that it significantly simplifies the interaction between the advertisers and the advertising platform. Nowadays, millions of auctions are conducted in any given day while the competitive landscape could be evolving over time and becoming vastly different across auctions. Therefore, it is difficult for the advertisers reason about its dynamics, let alone optimizing their bids for each auction separately. Instead of soliciting for fine-grained bids for different auctions they participate in, the automatic bidding product only asks the advertisers to provide high-level objectives and constraints. With provided high-level information, the automatic bidding product bids on behalf of the advertisers to optimize the objectives while respecting the constraints. While there are many different types of automatic bidding produces, well-adopted product bids to maximize the number acquisitions subject to constraint on advertiser-speeciied return on investment (ROI) constraint, i.c., target ratio between the advertiser's 's return and her advertising spend (Facebook) 2021, Google 2021]. J. To bid on behalf of the advertiser to maximize the number of acquisitions, the automatic bidding products invoke sophisticated prediction algorithms to predict the acquisition rate. These prediction algorithms have the benefit of being trained with long periods of data to have a good generalization [Juan al. 2016, McMahan al., 2013 Zhou al. 2018). In this way, the advertiser can only focus on designing their high-level objectives and specifying their constraints, while leaving the complicated bidding part the automatic bidding products.
The emergence of automatic bidding products opens up the opportunities for novel design dynamic auction mechanisms, as classic mechanisms are heavily specialized for dillit-maaiiizing bidders, the de facto paradigm in economic theory, which maximize the difference between their total value and total payment [Edelman et al.) 2007] Myerson 1981]. In contrast, automated bidders behave very differently in a way such that the payment is not directly involved in their objectives; and instead, the payment indirectly appears in the ROI constraints while the objectives aim maximize the total value only. Therefore, classic auction design tailored for maxiittm bidders may not continue to perform well in automatic bidding environment. Furthermore, recent results demonstrate that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for single-slot auctions, neither welfare nor revenue achieved by an incentive-com compatible auction (for maximiizgg bidders. e.g., second- price auctions) at any reasonable equilibrium can be larger
than 1/2 of the optimum [Aggarwal et al. 2019 Deng et al. 2021). Recently, [alseiro et al. [021]
initiated the study of characterizing single single-stage revenue-optimal auctions for automated bidders
under various information structures. Surprisingly, they show that in Bayesian setting in which the advertiser' value is private and the target ratio in the ROI constraint is public, a payment-scaless second-price auction can achieve first-best revenue, i.e., the revenue when all information is public. For a comparison, recall that first-best revenue is in general not achievable against maxiiiima bidders demonstrated by the Myerson's 's auction [Myerson| [981]. However, the assumption on perfect knowleds ledgledge of the prior distribution on the advertiser's 's values limits the application of their payment-scales second- price auction, as the seller usually needs to learn the distribution via repeated interactions with the advertiser.
1.1 Our results
In this paper, we aim to relax such an assumption by studying the problem of designing prior- independent dynamic mechanisms against a single automated bidder. In line with the literature [Amin et al. 2013], we consider setting of repeated auctions with multiple stages against an impatient automated bidder whose valuations are drawn identically and independently across stages. Moreover, we assume the automated bidder bids in a way to satisfy her ex-ante ROI constraint per stage, consistent with the setup in [Balseiro et al. 2021]. In practice, the auction parameters are updated infrequently (e.g., once per day) and the automated bidders participate in multiple repeated auctions in stage, i.e., the period between two consecutive updates. For each stage, the ROI constraints need to be satisfied on average over many auctions that the bidders participate in.
Our main result a novel dynamic mechanism achieving 0(r2/3) regret against a strategic automated bidder, where I' is the time horizon. Our dynamic mechanism adopts the aafoore-and-xxplon scheme by first estimating the bidder's 's value distribution. We then offer a robust version of the single-stage revenue- optimal mechanism to extract the revenue. A cornerstone of our dynamic mechanism in the exploration phase is a novel prior- intepenneenn single-stage mechanism that incentive-com conttiiiel for automated bidders. This mechanism forces the bidder to make a trade-off between her future gain from misreporting her values and her immediate loss, leading to a Wasserstein distance bound on the magnitude of misreporting from the automated bidder - which is precisely the form of error that our exploitation mechanisms are robust against.
1.2 Related work
Optimal mechanism design is a central topic in economics and game theory with many successful real-world applications, such as combinatorial auctions for FCC spectrum auctions [Cramton et al., 2006) and generalized second- ponnd-picce auctions for online advertising (Edelman et al. 2007]. However, bidders. In contrast,
almost all of these classic works make the assumption of inspired by the development of automatic bidding products in online advertising industry, growing body of recent literature starts to focus on automated bidders. Aggarwal et al. [2019) initiate the study of mechanism design with automated bidders and raise the question of how the mechanism designed for utility- mixityyiaxiiizing bidders performs against automated bidders. They show that neither welfare nor revenue achieved by an incentive comptible auction can be larger than 1/2 of the optimum. Deng et al. [2021) improve the approximation ratio to (c (1/(c)//++ 2) with boosted auctions using side information that correlates with advertisers' values. The closest related work to ours is [Balseiro] et al. 200T). which studies single-stage revenue-optimal auctions for automated bidders under various information structures and bidding behavior. In particular, examines the difference in auction design landscapes between miliit-ma bidders and automated bidders and shows that first-best revenue can be achievable when either the the advertiser" value is public or the target ratio in the ROI constraint is public. However, their mechanisms are prior-dependent while our objective is to design prior-independent dynamic mechanisms.
Our work is also related to the literature on robust online pricing against strategic agents. No-regret policies have been developed for both the non-contextual environment [Amin et al., 2013 Drutsa 2017 2018 2020) and the contextual environment [Amin et al. 2014 Deng et al. 2019 2020
Golrezaei et al. 2019]. All these results concern impatient maxiiizin bidders and Amin
ct al.
2013 show that no learning algorithm can achieve sublincar revenue loss with patient
2

---

udility-mann maximiin bidder. In contrast, our work studies robust online pricing against strategic automated bidder instead of a
bidder.
2 Preliminaries
Dynamic mechanisms. Throughout this paper, we consider dynamic mechanisms that solicit single bid from the buyer each stage. Roughly speaking, in each stage I, the buyer submits their bid b,, which is generally supposed to reflect their true value in stage / in some way After receiving the buyer's bids, the mechanism computes the fraction H, of the item allocated to the buyer and the payment Pt, based on all bids that the buyer has submitted so far. Formally, let T be the time horizon, i.e., the total number of stages. A dynamic mechanism M = herr = { Pt) he is collection of allocation-payment Iy R4 - [0, 1] maps the vector of historical bids (b1.... by) to the fraction of the item in stage t allocated to the buyer. Similarly, the payment rule pt : 144 - IR+, maps historical bids to the payment from the buyer to the seller in stage t.
pairs, one for each stage t. For each t, the allocation rule
Buyer's incentives and behavior. We consider the case of automatic buyers, who are ROI con- strained value maximizers. Such buyers maximize their expected value, subject to the constraint that the ratio between the value and the payment must be at least fixed threshold in expectation. Formally, we model value-maximizing buyer in dynamic environments in the following way. There is a value distribution D E A A(0 1]) which is private to the buyer. In each stage t, the buyer's 's value vr is drawn from D independently of everything else. For simplicity, throughout the paper, assume that D is non-atomic, meaning that for any e E [o, 1), Pre = v] = 0
There is publicly known threshold Tı E [1, oc) in each stage f, which specifies the minimum ROI ratio that is acceptable to the buyer in stage t. Note that we require 7: 2 because (1) conceptually, the buyer would always want their value to be at least their payment, and (2) technically, allowing T; arbitrarily close to would enable the seller to extract unbounded revenue (because the buyer is willing to pay up to T average) in single stage, in which case it is impossible to achieve low regret. Moreover, in line with the literature [Amin et al. 2013 Deng et al. 2019. Drutsa 2017)), we assume there is public discount factor À E (0, 1), which models how impatient the buyer is.
Recall that a dynamic mechanism solicits single bid be from the buyer in each stage t. Since the mechanism decides allocation and payments based on all historical bids, the buyer may submit bids that depend on historical values in order to best respond. Thus, in general, we assume each bid be [0, 1] + R.+ is a function of all historical values ....... of the buyer. Fixing dynamic mechanism M {(xx. the buyer faces the following constrained optimization problem.
max by....rr
E (E ( DDT
Σ AEIT
It Ut
subject to
E D
Fx Ue
Te Pe
U1
U2 2 0. E [T], ......,
U...,, 0t E 10.
Here, b, by (v (vi,,...,, vt), 34 zre(bn (be ...b........ b.). and pt Peb.i....... be). We assume the buyer is rational, and always chooses some optimal solution to the above optimization problem as their bidding strategy. Note that here, similar the single-stage formulation considered in previous work [Aggarwal et al. 2019 Balseiro et al. 2021 Deng et al. 2021]. we only require ROI constraints to hold in expectation over U (as opposed to for all vt) eachh stage. Conceptually, this is because in practice, every stage corresponds to a period of time (e.g., a day), which normally consists of large number of auctions happening in the same environment. Therefore, it makes more sense to set a target ROI ratio for the entire time period, rather than individual transactions which are normally quite small. Technically, in-expectation constraints allow the buyer to have richer bidding strategies.
In the Bayesian setting (i.e., with a publicly known prior), is without loss of generality to consider incentive-compatibee mechanisms where the buyer is always incentivized to submit their true value as the bid. However, the mechanism we present, being prior- rrior-idependdent, is not incentive-come compatible. As discussed later, we only require rough correspondence between the bids and the true values, which, we prove, can in fact be guaranteed by the mechanism.
2 Alll our results still hold without this assumption. When there are mass points in 27, the buyer's optimal bidding strategy may be random, which complicates the presentation.
3

---

and therefore, they can only make the problem of designing dynamic mechanisms harder. We also remark that one can simulate the case where the buyer submits multiple bids in each period of time, by making multiple copies of a stage with the same target ROI ratio.
First-best revenue and seller's goal. Our goal is to approximate the so-called first-best revenue in the long run, which is the maximum revenue possible when the buyer's ' values are public. Formally, suppose the seller's cost for producing unit of the item in stage / is C2 E [o, 1], and the buyer's value distribution and target ROI ratios are D and 7.. Then, in each stage t, the maximum expected revenue (P) the seller can achieve is given by the following optimization formulation.
max =FP
E (p()) c. x(0)]
BND
subject to
E wDD
( -- To p(v)] 2 0.
It is known that the first-best revenue is explicitly given by
OPT,(D) E maax c,, 0}]:
and that there is a single-stage incentive-compatible (meaning that it is always in the buyer's best interest to report their true value) prior-dependent mechanism that achieves single-stage revenue (P), [Balseiro et al., 2021]. So overall, with access to the prior distribution D, the maximum total first-best revenue that the seller can achieve throughout the T stages is
OPT(D) = Σ (PT,(D).
(E[T]
In this paper, we assume that the seller does not have access to the prior distribution D, and the goal is to achieve sublinear regret against the first-best revenue OPT(D) for all D with single dynamic mechanism. Formally, we aim to find mechanism M = {( Pt) herry. subject to the condition that for all D, there exists a bidding strategy satisfying the buyer's ROI constraints 33 and moreover,
OPT(D) - Σ (pr(1pp ....., b..pP.M)
(bp
P.M
P.M ) caa o(T),
sup DEA(V)
AE(T]
where bP.M
6. P.M (VI,..., w)) is the buyer's best response to mechanism M when the value distribution is D, defined above.
3 The Mechanism
In this section, we present the overall mechanism and discuss key high-level ideas therein. The full mechanism is given in Figure [ Similar prior work (Amin et al.) 2013), our mechanism has an exploration phase (step 2) followed by an exploitation phase (step 4). The idea of the exploration phase is to obtain an estimate D of the buyer's 's value distribution D. by offering prior-independent auctions that are strictly" single-stage stage, the more the buyer misreports, the worse their value will be (but misreporting may still lead to future gain). In each of these auctions, the seller can potentially suffer significant loss. However, by keeping the exploration phase short, the total loss from this phase can be bounded. Here, we face several technical challenges introduced by maximmiixiiizzng buyers, including:
compaiie-,,,,,ible,, in the sense that restricted the current
Single-stage compaiblle mechanisms for ROI constrained buyers have substantially different structures than those for quasilinear mixiit-ma buyers that are traditionally considered. In fact, even the existence of a strictly single-stage incentive-compatibl prior- independent mechanism for ROI constrained buyers is nontrivial, let alone finding one explicitly that specifically suits our purposes.
'For example, a mechanism where (0) = 0 for all t would satisfy this condition. In particular, b. = 0 for all is always a feasible bidding strategy under such mechanisms.
which guarantees that the buyer is indifferent between truth-telling and lying, does not suffice for our purposes. In particular, the buyer may still have strict incentive to misreport in arbitrary ways in response to such mechanisms, as long as misreporting leads to any positive future gain (no matter how small it is how much it discounted).
*Note that weak

---

1. Let - = (1og))) and T₃ @
( log
where T is the time
horizon and À is the buyer's discount factor.
2. For each
,,.... Ti + T2, solicit bid be E R from the buyer, allocate st min } of the item to the buyer and charge payment 2t min(b..1)
3. Let 'D be the distribution induced by (min HEEM) i.e., for each E [0. 1).
Eeem, Mmin (b, 1) =
D(0)= = Pr Iv' o] wnaD
Ti
4. For each Ti T2 + 1, , T, let
q: E TU/To v/To 2 20 mnD
PraNDlu/ 1//T ct
Solicit a bid b. E R... If 2 ct. then allocate 3t = of the item and charge = max c... Otherwise, allocate and charge p: = 0.
Figure 1: prior-indepentent no-regret mechanism for a value-maximiza buyer.
In conjunction with the strictly single-stage coopptivecommpatible mechanism, we need to find the right way of measuring the magnitude misreport, which must be manageable given the mechanism we choose, and at the same time ensure that our estimate D is sufficiently close to DD in a way that can be exploited in the later phase.
To tackle the above challenges, we use an exploration mechanism that is Linglestage incentive- compatible in very specific way. Intuitively, single-stage prrentve-compatibiine for ROI constrained buyers roughly means the buyer cannot gain by "arbitraging" between value and ROI slackness. Our exploration mechanism is designed such that whenever the buyer tries to arbitrage by misreporting. they suffer an immediate loss in the sum of value and ROT slackness that is precisely equal to the squared magnitude of deviation from their true value. Dynamic preettie-comppttbiiii then allows us to bound the expected squared deviation in any single stage in the exploration phase.
When computing our estimate D. we only use the first Tj bids collected in the exploration phase. This is because the last T2 bids are chronologically too close the exploitation phase. As result, the buyer's interest in future gain is not sufficiently discounted when making these bids so that they are potentially more misleading than the first Ti bids in the exploration phase. For this reason, simply ignore the last Tr bids to avoid introducing error in our estimate that cannot be effectively controlled.
Finally, in the exploitation phase, switch to running nearly revenue-optimal auctions based on estimate D of the value distribution D obtained from the exploration phase. dicetive-compatioe revenue-optimal mechanisms for ROI constrained buyers have been characterized by [alssirro et al. 2021 However, such optimal mechanisms require knowing the exact value distribution 2, and is not immediately clear whether an estimate suffices for approximate optimality. So here, the main challenge is adapt previously known optimal mechanisms into robust form that tolerates the specific form error introduced the exploration phase.
We remark that the mechanism does not need to know the time horizon T beforehand: applying the standard doubling trick allows the mechanism to achieve the same regret bound for any unknown T [Deng et al. 2019 2020, Golrezaei et al. 2019]. Also, the mechanism does not need to know т and o before each stage f.
4 Analysis of the Mechanism
In this section, we present an analysis of our mechanism and establish the regret bound. We first consider the exploration phase in Section 4.1 aiming to bound the difference between the true value
5

---

distribution D and our estimate D. Then in Section 4.2 we turn to the exploitation phase, and show that the mechanisms used there are robust against the specific form of estimation error introduced in the exploration phase. Finally, we combine everything into regret bound for our mechanism.
4.1 The Exploration Phase
In this section, we show that the exploration phase yields an accurate estimate of the buyer's value distribution with high probability, whenever the buyer adopts an optimal bidding strategy. The first key step prove the strict single-stage compatbl-o of the mechanism used each stage t in the exploration phase (henceforth the exploration mechanism in stage t). In fact, each exploration mechanism belongs a larger class of nontrivial drior-independent mechanisms that are single-stage incentive-come compaaiilee for ROI constrained buyers. Before zooming into exploration mechanisms, we first prove the single-stage axcettie-cooppttion of independent interest.
of this larger class of mechanisms, which may be
Proposition 1. Fix a target ROI ratio T. For any a E R.4,, let (Ia, Pa) be such that for any b E Rt,
min 13
(b( = (min 13)" and Pa(b) = xa (b)
T
Then fixing any a E Rt,, all value distribution D. (Ia: Pa) is single-stage incentive-compatiine iee, for any bidding strategy b: [0, + RR satisfying
E (b(o))) v Pa (b(o))))] 2 0, ond
we have
Ea (b(u)) - BrD
S E 2nD
(v) e].
We defer the proof of the proposition, well as all other missing proofs, the appendix. In principle, for any a > O, (P))P)) is strictly single-stage incentive-compatile. Out of all these mechanisms, we choose the one corresponding in different stages), because it enables a way of bounding the magnitude of misreporting that couples nicely with other components of our overall mechanism. Formally, the exploration mechanism in each stage t has the following key property.
as our exploration mechanisms (instantiated with different T
Lemma 1.
Let (I+, be the exploration mechanism in stage f. For any value distribution 'D and bidding strategy b [0. 1] + [0, let
Val(D, b) = E (z<(()) v] and ROI(D, = B [=(b(()) - p(b())))
D
Moreover, let id [0, + [0, 1] be the truthful bidding strategy, where id(v) e for all 1]. Then for any bidding strategy 6 [0, 1] + [0.
Val(D, b) + ROI(D, b) = Val(D, id) - E (v - b(u))
UnD
Proof. First fix any v E [0, and v' = b(o). We have x(v') v - z(v) u = = v. (0' - v). and moreover, (x(r") v Te p(1')) - (x(z) - - 7. p(u)) = d - v'). As a result, for any D and b, (Val(D, 6) ROI(D,)) 6)) (Val(D, id) + id)
D- (z(b(v)) =(v) v) ((=(b(v)) Ti p(b()))) (z(v) To -(p)))
E
E D
( (b(v) - v) + b(v) (u (v- b(0)) = E -~ - (()))
Rearranging terms and plugging in ROI(D, id) = 0, we obtain precisely the claim to be proved.
The above lemma states that under the exploration mechanism in each stage f, any bidding strategy that deviates from truthful reporting suffers a loss in the sum of expected value (from the fraction of the item received) and ROI slackness. And moreover, this loss is equal to the expected squared magnitude of deviation. This provides way of bounding the magnitude of deviation in each stage in the exploration phase because of the following reasons. First, since the buyer ROI constrained, in each stage they must have nonnegative ROI slackness, and result, their immediate value loss

---

is at least as large as the squared magnitude of deviation in the current stage. Moreover, note that the exploration phase has completely no dependence on historical bids, so the only motivation for misreporting in the exploration phase comes from the exploitation phase, which is far away in the future as we only use the first Ti bids in the estimation. Since the buyer less patient than the seller (i.e., they have a discount factor À < 1), any potential future gain is substantially discounted. As result, the motivation for deviation becomes sufficiently small, such that the buyer only willing to sacrifice small amount of immediate value in exchange for that. Thus, by Lemma we know that the expected squared magnitude of deviation in each exploration phase auction is sufficiently small. This is captured by the following lemma.
Lemma 2. For any value distribution D, optimal bidding strategy {be}, t E [Ti). and historical values U1,.... Ut-1 before stage I,
8²
[1ve - bb)² U1 22 v Mr
E
16"
and corollary,
8 4
E 100 m
byl Ui...., Ut
where E the error parameter defined in Figure
The above lemma controls source (i.e., misreporting) of error incurred in the exploration phase. In particular, the form of error that we care about is in the second part of the lemma, which provides an upper bound the expected absolute value of deviation in any exploration mechanism. This measure of сгтоr is closely related to the notion of the L Wasserstein distance W1 (also known as the earth mover's distance) in IR, defined as follows.
Definition 1. For probability distributions Dj and D2 over TR,
( E [|x vll)
Wi (i, D2)
inf D)er(D),Ps) (a.y))
where T(D1, D2) ) is the family of distributions over IR2 with marginals Dj and D2 in the two dimensions respectively.
Intuitively, each D, E [[D1, D2) corresponds to a matching between Dj and D2, and W1 W1(D). D2) the minimum total cost of matching D, D2. In fact, is easy show that Lemma iimples the following bound.
Corollary 1. Let by (D) be the distribution of be(e)) (given v1, (t-1) where is ~ D. Then
Wi(D,bb(D) < E 1|. - (x(r))l S 4 EED
This is simply because b explicitly specifies matching between D and (D)) whose cost is upper bounded by e/4. In light of this, our goal in the rest of Section 4.1 is to upper bound Wi (D, D). We will later see in Section mechanisms need to achieve approximate optimality.
that this is precisely the kind of guarantee that our exploitation
Below we handle the other source of eтror, i.c., the discrepency between the buyer's value distribution D and the empirical value distribution (henceforth D) without misreporting, induced by he(m)) Since {vx hete, are i.i.d. samples from D. can apply standard results for the convergence of empirical processes in the W, distance to obtain the following bound.
Lemma 3. Ler be the empirical distribution induced by vi...., UT, With probability at least 1 12(2T) over Ui...., VT,, (DDD, D) < g
With Lemma proved, we can now proceed to the final step of bounding W, (D, D), i.e., combining the error from misreporting and that from W, (D, D). This may appear straightforward: the error from misreporting is on top of Wi(D, D). so we only need to add the bounds from Corollary and Lemma 3 together. However, achieve low regret, we need W, (D, D) to be small with high probability, but Corollary[oon provides an in-expectation bound. Moreover, since the buyer may use adaptive bidding strategy (i.c., b, may depend on bj bj....,b bi-1).,,b.1), cannot apply standard
7

---

concentration bounds for independent variables to obtain breobbbobybilityy bounds. Therefore, instead of applying Corollary I
we observe that the sequence
1 Ti
8 4 Σ (Ibe - vel F's
X
form a submartingale. As a result, we can apply one-sided concentration inequalities for submartin- gales to obtain high-probability upper bound
Xπ.
1 T EE(Ti
Σ
(0e ( rel 4)
The above observation gives us the following lemma.
Lemma 4, With probability at least 1/(TT) over ui,.... UT,
1
Wi(D,
bb. vol - 2
T
EE
Combining Lemmas and (D,, D), which is essentially the only property of the exploration phase that we need to establish the overall regret bound.
we immediately obtain the following high-probability bound on
Lemma 5.
With probability at least 1 - 1/T, Wi(D,D) SE.
4.2 The Exploitation Phase
In this section, we show that when the exploration phase succeeds, i.c., when Wi WI D) I E. the expected revenue by the mechanism in each stage in the exploitation phase (henceforth the explotation mechanism stage t) is at least OPT, e. Since the bid submitted in any of these decouple the exploitation
stages cannot affect the exploitation mechanism in any other stage, stages and look at each of them individually.
We first characterize the buyer's 's optimal bidding strategy in response to the exploitation mechanism in each stage I. First observe that these exploitation mechanisms have simple structure: the exploitation mechanism in stage l is essentially a take-it-or-leave- offer, where the buyer can either take the item and pay 9t. or leave and pay nothing. particular, the specific value of the bid b, does not affect how much the buyer pays when they get the item.
Under the traditional assumption that the buyer maximizes their utility, the best response to such mechanisms is extremely simple: take the item if and only if the buyer's value i at time & is at least the posted price qt- The optimal bidding strategy is less straightforward with aalue-maximizing buyers who maximize value subject to ROI constraints. However, they still have the intuitve structure that the buyer should take the item whenever their value is higher than a certain threshold. This captured by the following claim. Lemma 6. Suppose a value maximizing buyer with target ROI ratio T has value distribution D. Then the optimal bidding strategy b [0, 1] > [0, 1] against tuke-it-or-leave-it offer price q (0, 1) is given by
b(v) = [1, if
10. otherwise,
where
inf
E L 1 UnD
We remark that the above optimal bidding strategy is essentially unique, in the sense that the mappings from the value u to the allocation & induced by any two optimal bidding strategies can differ only on cero-measure set with respect to D. which makes no difference for purposes. Henceforth, in the rest of the paper, without loss of generality we assume that the bidding strategy given in Lemma 6 is the unique optimal bidding strategy.
With the optimal bidding strategy characterized, we can now bound the revenue collected in the exploitation mechanism in each stage t and compare that to OPT.(D). We first prove that when the

---

exploration phase succeeds, in each exploitation stage, the optimal revenue that can be extracted from the buyer when the value distribution is D cannot be much larger than that when the value distribution D. Formally, we have the following lemma.
Lemma 7. When W1 (D, D) e, all E {Ti + T2 + 1, ,.).
,T)
OPT,(D) & (PT,(D) +..
The next step, which captures the essence of our exploitation mechanisms, is to show that, conditioning on the success of the exploration phase, when the buyer (with actual value distribution D) uses the optimal bidding strategy in the exploitation mechanism in stage t, the revenue collected is not much smaller than OPT, (D). In other words, the exploitation mechanism in stage can tolerate an estimation error up to e the W, distance, sacrificing only e the revenue. Intuitively, this is because by the definition of the W1 distance, we can find a matching D, E [ D) between D and D. such that the following is a feasible bidding strategy for a buyer with distribution D: for (v, ö) Dy. where is the realized value of the buyer and the value that v matches to under D), buy the item and only a buyer with distribution D would buy the item when their value é in response to slightly higher price. This means the probability that buyer with distribution D buys the item is least the probability that buyer with distribution D does when the price is slightly higher. Then, one can show that under the optimal bidding strategy, a buyer with distribution 'D buys the item with least the same probability, so the revenue loss is solely from the difference between the two prices, which is by construction small. This intuition is captured by the following lemma.
Lemma 8. When W1 (D, D) E. for all t E {Ti + 1,.... ,), the expected revenue of the exploitation mechanism in stage satisfies
Rev.(D, D) := max -)),),))0 0} Pr [v 2 0,] 2 OPT,
where 0, is the threshold of the optimal bidding strategy given in Lemma o i.e.,
0. = inf (0 E [0.1]
E lv anD
2 0 qe).
Finally we combine Lemmas 7 and g to obtain the following conditional revenue bound, which is essentially the only property of exploitation mechanisms that we need.
Lemma 9. When (D, D) S e, for all t E (Ti + To + T...,,T,, the expected revenue of the exploitation mechanism in stage satisfies
Rev, OPT,(D) - 2E.
4.3 Putting Everything Together
Finally, we are ready to put everything together and prove the regret bound of our mechanism. The following theorem states that our mechanism not only guarantees low regret in expectation, but also in fact collects total revenue close to the first-best benchmark with high probability, over the the randomness in the buyer's ''s values.
Theorem 1. With probability least O1)TT), our mechanism achieves total revenue least
OPT(D) 2/3 log T").
5 Conclusion
In this paper, we develop a prior-independen dynamic mechanism achieving low regret against value-maximizing buyer. Along the way, we propose novel prior-independent single-stage mechanism that incentive-compatible for value-maximizing buyers. An intriguing question to consider in the future is to extend the results to an environment with multiple value-maximizing buyers; however, tackling the interactions between multiple buyers seems to be a non-trivial and challenging task. Another open question is whether the O(T2/3) bound (nearly) optimal - we suspect the bound cannot be significantly improved restricted to exploration-exploitai mechanisms,

---

given that similar lower bounds have been established in related problems in prior work [Babaioff al., 2014, Devanur and Kakade 2009]. In principle, one could also consider the case where the target ROI ratio is also private and needs to be reported. However, people do not currently have good understanding of this case even in static environments, and as a result, it not even clear what the benchmark should be for this case in dynamic environments. Other variants of the problem, e.g.. where there a "cumulative" ROI constraint over all stages (as opposed to one target ROI ratio for each stage), may also be of potential interest. To zoom out, it is very interesting to establish better understanding about the power and the limitations of dynamic mechanisms against maximizing buyers.
Funding Transparency Statement
Hanrui Zhang was supported by NSF grant IIS-1814056.
References
Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17-30. Springer, 2019.
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1169-1177, 2013
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 622-630, 2014.
Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. Characterizing truthful multi-armed bandit mechanisms. SIAM Journal on Computing, 43(1):194-230, 2014.
Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. The landscape of auto- bidding auctions: Value versus utility maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
Peter Cramton, Yoav Shoham, and Richard Steinberg. Combinatorial Auctions. MIT Press, 2006.
Yuan Deng, Sébastien Lahaie, and Vahab Mirrokni. A robust non-clairvoyant dynamic mechanism for contextual auctions. In Advances in Neural Information Processing Systems, pages 2019.
Yuan Deng, Sébastien Lahaie, and Vahab Mirrokni. Robust pricing in dynamic mechanism design. In International Conference on Machine Learning, pages 2494-2503. PMLR, 2020.
Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Towards efficient auctions in an auto- bidding world. In Proceedings of The Web Conference 2021, 2021.
Nikhil R Devanur and Sham M Kakade. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM conference on Electronic commerce, pages 99-106, 2009.
Shelagh Dolan. Us programmatic digital display ad spending will grow despite pandemic-relater ad bud---ending-we will
recession. http::/wwwwwmakkkeee..oooooo hwwpo//ccnttnntss-ppaaaaaaaaaaea Srow-despite-pandeeee wwwdemian relaaaerreeeeedesssoooo recession, August 2020. Accessed: -05-24..
Alexey Drutsa. Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. In Proceedings of the 26th International Conference on World Wide Web, pages 33-42, International World Wide Web Conferences Steering Committee, 2017.
Alexey Drutsa. Weakly consistent optimal pricing algorithms in repeated posted-price auctions with strategic buyer. In International Conference on Machine Learning, pages 1318-1327, 2018.
Alexey Drutsa. Reserve pricing in repeated second-price auctions with strategic bidders. In Interna- tional Conference on Machine Learning, 2020.
10

---

Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the gener- alized second second-price auction: Selling billions dollars worth of keywords. American Economic Review, 97(1):242-259 2007.
Facebook. Your guide facebook bid strategies. one wat-ssseetrssffacbboooe bid- strategy- guide, 2021. Accessed: 2021-05-24.
Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. In Advances in Neural Information Processing Systems, pages 9756-9766, 2019.
Google. Google ads help center: About automated bidding. https::/support-googl httpgleeadaaaaaeee//999///////// ?hl=en, 2021. Accessed: 2021-05-24.
Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. Field-aware factorization machines for ctr prediction. In Proceedings of the 10th ACM conference on recommender systems, pages 43-50, 2016.
H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, al. Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222-1230, 2013.
Roger B Myerson. Optimal auction design. Mathematics of Operations Research, (1):58873,, 1981.
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma. Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1059-1068, 2018
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
11

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "xjsbDF4xZ-k", "reviewer": "Reviewer_giSA", "summary": "This paper studies how a seller should design its auctions to maximize her revenue when facing an impatient buyer optimizing his value under a ROI constraint. It mostly consists in plugging together two previous works, Balseiro 2021 and Amin 2013 to extend Balseiro 2021 to the setting where the value distribution is unknown a priori and needs to be learnt. Following Amin 2013, the proposed algorithm has two phases (an explore then commit schema) and the first phase is designed to make him reveal his value distribution, which allows to implement an optimal mechanism in the second phase. Provided that the buyer is impatient enough, the first phase length can be tuned to incur an overall sub-linear regret.", "questions": "", "limitations": "", "rating": 6, "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": "**Originality**\n* The algorithm, the result and the main line of proof are a well-executed but not surprising combination of results from Balseiro 2021 and Amin 2013\n  * The mechanism used in exploration phase is an instantiation of a mechanism satisfying Balseiro 2021 Lemma 3.2\n  * The one used in exploitation phase is a small variation of the optimal mechanism from Balseiro 2021 Mechanism 4.3\n  * The design and line of proof of the phased algorithm follows Amin 2013.\n* The technical contributions consist in \n  * the way to measure the drift between the true empirical distribution and the observed bids with the Wasserstein distance, which allows to use literature on Wassertein concentration and martingale tail-inequalities,\n  * modifying the optimal mechanism in phase 2 to account for the (small) misreporting coming from the first phase.\n\n**Quality and clarity**\nThe algorithm is well presented and explained. The paper is clear, and easy to read. I checked most of the proofs.\n\n**Significance**\n* I have some concern about the ROI constraint as presented in the paper. In Balseiro 2021, they use a ROI constraint in expectation as they are studying a single-shot auction. This paper studies a repeated setting and thus it would make more sense for the ROI constraint to be cumulative over time. Indeed, by only enforcing a ROI constraint in expectation at each time step, cumulatively, the ROI constraint could be violated by as much as $\\sqrt(T)$ I think. This paper makes the argument that each $t$ corresponds to a period of time (a day), but it would mean the buyer provides a single bid each day, which is not always very realistic.\n* I think it should be clear from the title and the abstract that the paper only looks at \"impatient\" buyers, as for instance, there is no lower bound to characterize what happens is $\\gamma$ is close to 1 while $\\tau$ is known.\n\n**Minor details**\n* line 136 (end of line), I think you meant \"buyer\" rather than \"seller\"\n* In the appendix, you could use another notation for derivatives of univariate functions, as using \"prime\" for both derivatives and indexing several variables like $v$ and $v'$ is kind of confusing. Maybe, you could use the \"dot\" notation for derivative, e.g. $\\dot{x}(v')$ rather than $x'(v')$ which is kind of confusing at first.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see main review", "review_text": "", "extra_scores": {"ethical_concerns": "Nothing comes to my mind.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "G6b4MFhYe7M", "reviewer": "Reviewer_JHak", "summary": "The paper studies prior-independent dynamic auctions with a single value-maximizing buyer.\nIn this setting, the buyer's objective is to maximize her obtained value (rather than utility) under ROI constraint (i.e., the value is at least $\\tao$ times higher than the price paid).\nThe authors show a dynamic auction mechanism that without having no prior information on the buyer’s value distribution (except from being bound in [0,1]), can extract a near-optimal revenue, i.e., sublinear regret for time horizon T.\nThe work is under the assumption of a patient seller and a buyer has a time discount factor $\\lambda$.\n\nThe algorithm is divided into three parts:\n\n1. Exploration phase that incentivizes the buyer to report approximately truthfully. To my understanding, this is the main new technique in the work.\n\n2. A buffer phase.\n\n3. Exploitation phase that extracts the revenue using a robust version of the single-stage revenue-optimal mechanism for this problem.\n\n", "questions": "", "limitations": "", "rating": 6, "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": "Learning to maximize revenue without knowing the prior is well motivated and was studied in the standard context of a utility-maximizing buyer.\nExtending those results to the framework of a value-maximizing buyer (under ROI or any other constraint) is a natural research goal.\n\nI am not completely sure about the results’ significance, since the algorithm and proof techniques seem rather standard. The framework of a value-maximizing buyer under ROI constraint was introduced in previous work, so the conceptual contribution also seems limited.\n\nComments and questions:\nWhat is the known lower bound for regret in this model?\n\nThe work assumes the values are drawn from a distribution bounded in [0,1].\nDo you have results for distributions bound in [0,d] for $d$ unknown to the seller?\nDo you have results for unbounded distributions?\n\nLine 136: the second seller in the line should be a buyer? \n\nIn the definition of the buyer optimization problem (line 123 and in general), the buyer’s objective depends on the future (with a discount) while the constraint only depends on the current step. Shouldn’t the ROI constraint consider future decisions as well? Especially since the constraint only cares about the expectation and not the realization at this specific time.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since the focus of this work is primarily theoretical, any societal impact depends on the application.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5m75bPAwtW", "reviewer": "Reviewer_FsWG", "summary": "This paper considers the dynamic mechanism design problem to maximize total expected revenue against a single bidder, who aims to maximize time-discounted cumulative expected value, while subject to an interim ROI constraint each period. The work proposes a dynamic mechanism consisting of an exploration phase during which the seller runs an incentive-compatible mechanism to estimate the bidder’s value distribution; and also an exploitation phase that approximates the single-stage optimal mechanism against an ROI bidder w.r.t. the distributional estimates. The paper shows that the design limits the magnitude of the bidder’s misreporting, and proves that the proposed dynamic mechanism achieves a $T$-period regret in the order of $T^{2/3}$ against the optimal revenue of a clairvoyant seller who knows the bidder’s value realizations.", "questions": "", "limitations": "", "rating": 7, "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": "I enjoyed reading the paper, as the idea of “exploring” through incentive compatible mechanisms to learn the bidder’s value distribution, and then “exploiting” via incentive-compatible revenue-optimal mechanisms for ROI constrained bidders using such distributional estimates, is interesting. Although previous works established the technique of leveraging bidder time discounted utilities to bound the deviation from truthful bidding, to the best of my knowledge adopting this methodology in a dynamic mechanism design context is novel. In addition, the paper is well-written and the key results are presented in a succinct, yet informative, fashion.\n\nMy only concern for this submission is that it does not comment on the optimality of the $T^{2/3}$ regret achieved. For comprehensiveness, it would be nice to include some statement on, or at least some intuition into, the regret lower bound. Along this line regarding bidder discount factors, Amine et al.,2013 demonstrated that in the repeated posted price setting, if the discount factor is 1 (i.e. no discount), sublinear regret is impossible. I am curious if a similar argument is directly applicable to the dynamic mechanism design setting of interest. It would be nice if the authors can include relevant discussions in the paper.\n\nIn my opinion, there are two limitations in terms of modelling choices:\n\n1.The paper studies per-period ROI constraints, which I think greatly simplifies the problem since it decouples the mechanisms from period to period, and only requires the seller approximate the single-period optimal mechanism for ROI constrained bidders (which is an established result in previous work). Moreover, I think in practice ROI is typically measured using the total value divided by total expenditure across an entire ad campaign. Hence, from both a theoretical and practical perspective, perhaps a more interesting model would be to impose a single ROI constraint for the entire time horizon. \n\n2.The paper assumes the bidder knows her value distribution, which may be an unrealistic\nassumption from a practical viewpoint. On the other hand, if the bidder is also learning her distribution, then the seller may possibly exploit the bidder's learning algorithm and achieve higher revenue compared to the clairvoyant benchmark.\n\nNevertheless, I do not think these limitations of the model undermine the contributions/key insights of this paper, and perhaps the authors can comment on relevant aspects in a “future directions” section (if space permits). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper did not adequately address limitations in terms of the model choice and proposed mechanisms. For detailed suggestions see main review above.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "43FzCB4xzp", "reviewer": "Reviewer_5rjq", "summary": "This paper studies the problem of a seller who interacts repeatedly with a buyer.  In each round an item is up for sale, and the buyer draws a value from an unknown (to the seller) distribution.  The buyer is assumed to be less patient than the seller, and the seller's goal is to maximize revenue.  Prior work had established low-regret sales strategies for the seller when the buyer is a utility maximizer.  This paper considers a value-maximizing bidder, who wants to maximize value obtained subject to an interim ROI constraint.\n\nThe authors construct a dynamic mechanism with regret O(T^{2/3}), versus the best revenue attainable if the value distribution were known.  At a high level the approach is similar to the utility-maximizing case: run an explore phase that obtains low revenue but learns about the buyer's value distribution, then deploy a mechanism aimed at extracting near-optimal revenue from what was learned.  The key here is to incentivize the buyer not to misreport in the explore phase, which is done by using a strictly truthful per-round auction (and leveraging the assumption that the buyer is less patient).  For a value-maximizing buyer, what is needed for strict truthfulness is different.  So a main technical contribution of the work is to propose a new single-round auction format that is strictly single-stage incentive compatible.\n\n", "questions": "", "limitations": "", "rating": 7, "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": "The authors do a nice job of explaining the barriers to extending prior work on prior-free dynamic mechanisms to the setting of value maximization.  The new construction is clever and natural.  There are quite a few subtleties to the analysis and the paper covers them quite thoroughly.  Overall I found the presentation quite clear.\n\nOne downside to the result is that the mechanism requires knowledge of the buyer's target ROI ratio tau in each round, which by assumption can change over time.  So it is assumed that while an agent's value is part of her private type, the ROI constraint is not.  I found this a little hard to motivate, since both value and ROI-constraint both form the underlying preferences of the buyer.  Previous work on value-maximizing bidders have also assumed public ROI constraints, so this assumption has precedence, but even so I would have liked to see some discussion about how necessary it is.\n\nConceptually, the approach taken by this paper shares a lot in common with prior work.  There are certainly details to work out, and I appreciated the care taken to show how to extend the construction to this more general setting.  But nevertheless the marginal contribution does not feel especially exciting, and even the new single-round mechanism (Proposition 1) is not very far from known methods for utility-maximizing agents, given that the ROI parameter tau is known and can be used explicitly.\n\nOverall, this feels like a solid advance in the development of dynamic prior-independent auctions for an interesting set of bidders.  The marginal contribution is a bit slight, but I feel the work is above the bar for NeurIPS and can be accepted if there is room.\n\n===\n\nPost author response: I've read the response, and I am still favorable toward acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would recommend more discussion motivating the choice to have tau publicly revealed in each round.  The paper currently just cites previous works that make the same choice, but further discussion on this point would be very helpful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews are generally positive, although not enthusiastic. There are some pros and cons. My reading of the main issues in the reviews and the discussion is as follows:

[+] The explore-then-exploit mechanism is quite technical. This is somewhat unusual: many explore-then-exploit algorithms or mechanisms in the literature are often "the easy part" of the paper, followed either by a more complicated approach based on "adaptive exploration" (and $\sqrt{T}$ regret), or a lower bound which rules it out. 

[+] As the authors suggest, $T^{2/3}$ regret appears optimal among all explore-then-exploit mechanisms. Such lower bound seems within reach, via a standard lower-bounding technique for bandits (*), and would be a natural complement to the main result. I encourage the authors to try to prove it. 

[-]  Long-term incentives are reduced to short-term incentives in a simple, brute-force way: a $O(\log T)$-sized "padding" is inserted between exploration and exploitation, to make the entire exploitation worth very little to the buyer.   

[-] This brute-force approach is feasible because the seller is assumed to be infinitely patient. This approach would probably fail if the seller had a  larger but comparable time-discount factor. Which is arguably closer to reality: e.g., advertiser's time scale is week or even a month, whereas the platform's time scale is a year. 

[+/-] The novelty lies in the design of the single-shot mechanism for exploration (which needs to be incentive compatible in a very strong sense: large deviation should cause a large loss in buyer's utility), and perhaps also the single-shot mechanism  for exploitation (which needs to be robust to uncertainty in the value distribution $D$). However, one reviewer suggests that both single-shot mechanisms are similar to those in Balseiro et al (2021). 

[-] Some of the other simplifications are not that well-justified: that ROI constraint is per-round rather than aggregate, and that target ROI is public. Probably not a big flaw, though.

(*) It may be possible to "reduce" directly to the respective lower bound for bandits. Else, it would be a slightly more involved problem-specific argument. A similar argument (for explore-then-exploit mechanisms in a technically different auction design setting) can be found in (Moshe Babaioff, Yogeshwer Sharma, Aleksandrs Slivkins: Characterizing Truthful Multi-armed Bandit Mechanisms, EC 2009, SICOMP 2014) and (Nikhil R. Devanur, Sham M. Kakade: The price of truthfulness for pay-per-click auctions. EC 2009).

Decision: Accept (Poster)