Prior-independent Dynamic Auctions for a Value-maximizing Buyer
Year: 2021

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 Õ(T ), 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.

heading: 1 Introduction
text: Automatic bidding has become one of the main options for advertisers to buy advertisement opportunities 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 to 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, a well-adopted product bids to maximize the number of acquisitions subject to a constraint on the advertiser-specified return on investment (ROI) constraint, i.e., a target ratio between the advertiser’s return and her advertising spend [Facebook, 2021, Google, 2021]. To bid on behalf of the advertiser to maximize the number of acquisitions, the automatic bidding products can 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 et al., 2016, McMahan et al., 2013, Zhou et 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 to the automatic bidding products.
The emergence of automatic bidding products opens up the opportunities for novel design of dynamic auction mechanisms, as classic mechanisms are heavily specialized for utility-maximizing 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 to maximize the total value only. Therefore, classic auction design tailored for utility-maximizing bidders may not continue to perform well in an automatic bidding environment. Furthermore, recent results demonstrate that
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for single-slot auctions, neither welfare nor revenue achieved by an incentive-compatible auction (for utility-maximizing 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, Balseiro et al. [2021] initiated the study of characterizing single-stage revenue-optimal auctions for automated bidders under various information structures. Surprisingly, they show that in a Bayesian setting in which the advertiser’ value is private and the target ratio in the ROI constraint is public, a payment-scaled 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 utility-maximizing bidders as demonstrated by the Myerson’s auction [Myerson, 1981]. However, the assumption on perfect knowledge of the prior distribution on the advertiser’s values limits the application of their payment-scaled second-price auction, as the seller usually needs to learn the distribution via repeated interactions with the advertiser.

heading: 1.1 Our results
text: In this paper, we aim to relax such an assumption by studying the problem of designing priorindependent dynamic mechanisms against a single automated bidder. In line with the literature [Amin et al., 2013], we consider a 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 a 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 is a novel dynamic mechanism achieving Õ(T 2/3) regret against a strategic automated bidder, where T is the time horizon. Our dynamic mechanism adopts the explore-and-exploit scheme by first estimating the bidder’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-independent single-stage mechanism that is incentive-compatible 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.

heading: 1.2 Related work
text: 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-price auctions for online advertising [Edelman et al., 2007]. However, almost all of these classic works make the assumption of utility-maximizing bidders. In contrast, inspired by the development of automatic bidding products in online advertising industry, a 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-maximizing bidders performs against automated bidders. They show that neither welfare nor revenue achieved by an incentive-compatible 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., 2021], which studies single-stage revenue-optimal auctions for automated bidders under various information structures and bidding behavior. In particular, it examines the difference in auction design landscapes between utility-maximizing 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 utility-maximizing bidders and Amin et al. [2013] show that no learning algorithm can achieve sublinear revenue loss with a patient
utility-maximizing bidder. In contrast, our work studies robust online pricing against a strategic automated bidder instead of a utility-maximizing bidder.

heading: 2 Preliminaries
text: Dynamic mechanisms. Throughout this paper, we consider dynamic mechanisms that solicit a single bid from the buyer in each stage. Roughly speaking, in each stage t, the buyer submits their bid bt, which is generally supposed to reflect their true value in stage t in some way.1 After receiving the buyer’s bids, the mechanism computes the fraction xt 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 = {Mt}t∈[T ] = {(xt, pt)}t∈[T ] is a collection of allocation-payment pairs, one for each stage t. For each t, the allocation rule xt : Rt+ → [0, 1] maps the vector of historical bids (b1, . . . , bt) to the fraction of the item in stage t allocated to the buyer. Similarly, the payment rule pt : Rt+ → R+ maps historical bids to the payment from the buyer to the seller in stage t.
Buyer’s incentives and behavior. We consider the case of automatic buyers, who are ROI constrained 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 a fixed threshold in expectation. Formally, we model a value-maximizing buyer in dynamic environments in the following way. There is a value distribution D ∈ ∆([0, 1]) which is private to the buyer. In each stage t, the buyer’s value vt is drawn fromD independently of everything else. For simplicity, throughout the paper, we assume that D is non-atomic, meaning that for any v ∈ [0, 1], Prv′∼D[v′ = v] = 0.2
There is a publicly known threshold τt ∈ [1,∞) in each stage t, which specifies the minimum ROI ratio that is acceptable to the buyer in stage t. Note that we require τt ≥ 1 because (1) conceptually, the buyer would always want their value to be at least their payment, and (2) technically, allowing τt arbitrarily close to 0 would enable the seller to extract unbounded revenue (because the buyer is willing to pay up to vt/τt on average) in a 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 a public discount factor λ ∈ (0, 1), which models how impatient the buyer is. Recall that a dynamic mechanism solicits a single bid bt 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 bt : [0, 1]
t → R+ is a function of all historical values v1, . . . , vt of the buyer. Fixing a dynamic mechanism M = {(xt, pt)}t, the buyer faces the following constrained optimization problem.
max b1,...,bT E (v1,...,vT )∼DT ∑ t∈[T ] λt · xt · vt  subject to E
vt∼D [xt · vt − τt · pt | v1, . . . , vt−1] ≥ 0, ∀t ∈ [T ], v1, . . . , vt−1 ∈ [0, 1].
Here, bt = bt(v1, . . . , vt), xt = xt(b1, . . . , bt), and pt = pt(b1, . . . , bt). 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 to 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 vt (as opposed to for all vt) in each stage. Conceptually, this is because in practice, every stage corresponds to a period of time (e.g., a day), which normally consists of a 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,
1In the Bayesian setting (i.e., with a publicly known prior), it is without loss of generality to consider incentive-compatible mechanisms where the buyer is always incentivized to submit their true value as the bid. However, the mechanism we present, being prior-independent, is not incentive-compatible. As discussed later, we only require a rough correspondence between the bids and the true values, which, as we prove, can in fact be guaranteed by the mechanism.
2All our results still hold without this assumption. When there are mass points in D, the buyer’s optimal bidding strategy may be random, which complicates the presentation.
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 a unit of the item in stage t is ct ∈ [0, 1], and the buyer’s value distribution and target ROI ratios are D and τt. Then, in each stage t, the maximum expected revenue OPTt(D) the seller can achieve is given by the following optimization formulation.
max x,p E v∼D [p(v)− ct · x(v)]
subject to E v∼D [x(v) · v − τt · p(v)] ≥ 0.
It is known that the first-best revenue is explicitly given by
OPTt(D) = E v∼D [max{v/τt − ct, 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 OPTt(D) [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) = ∑ t∈[T ] OPTt(D).
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 a single dynamic mechanism. Formally, we aim to find a mechanism M = {(xt, pt)}t∈[T ], subject to the condition that for all D, there exists a bidding strategy satisfying the buyer’s ROI constraints,3 and moreover,
sup D∈∆(V ) OPT(D)− ∑ t∈[T ] ( pt(b D,M 1 , . . . , b D,M t )− xt(b D,M 1 , . . . , b D,M t ) · ct ) = o(T ), where bD,Mt = b D,M t (v1, . . . , vt) is the buyer’s best response to mechanism M when the value distribution is D, as defined above.

heading: 3 The Mechanism
text: In this section, we present the overall mechanism and discuss key high-level ideas therein. The full mechanism is given in Figure 1. Similar to 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 value distribution D, by offering prior-independent auctions that are strictly4 single-stage incentive-compatible, in the sense that restricted to the current 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 value-maximizing buyers, including:
• Single-stage incentive-compatible mechanisms for ROI constrained buyers have substantially different structures than those for quasilinear utility-maximizing buyers that are traditionally considered. In fact, even the existence of a strictly single-stage incentive-compatible priorindependent mechanism for ROI constrained buyers is nontrivial, let alone finding one explicitly that specifically suits our purposes.
3For example, a mechanism where pt(0) = 0 for all t would satisfy this condition. In particular, bt = 0 for all t is always a feasible bidding strategy under such mechanisms.
4Note that weak incentive-compatibility, 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 or how much it is discounted).
• In conjunction with the strictly single-stage incentive-compatible mechanism, we need to find the right way of measuring the magnitude of misreport, which must be manageable given the mechanism we choose, and at the same time ensure that our estimate D̂ is sufficiently close to D in a way that can be exploited in the later phase.
To tackle the above challenges, we use an exploration mechanism that is single-stage incentivecompatible in a very specific way. Intuitively, single-stage incentive-compatibility 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 ROI slackness that is precisely equal to the squared magnitude of deviation from their true value. Dynamic incentive-compatibility 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 T1 bids collected in the exploration phase. This is because the last T2 bids are chronologically too close to the exploitation phase. As a 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 T1 bids in the exploration phase. For this reason, we simply ignore the last T2 bids to avoid introducing error in our estimate that cannot be effectively controlled.
Finally, in the exploitation phase, we switch to running nearly revenue-optimal auctions based on our estimate D̂ of the value distribution D obtained from the exploration phase. Incentive-compatible revenue-optimal mechanisms for ROI constrained buyers have been characterized by Balseiro et al. [2021]. However, such optimal mechanisms require knowing the exact value distribution D, and it is not immediately clear whether an estimate suffices for approximate optimality. So here, the main challenge is to adapt previously known optimal mechanisms into a robust form that tolerates the specific form of error introduced in 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 τt and ct before each stage t.

heading: 4 Analysis of the Mechanism
text: 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
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 a regret bound for our mechanism.

heading: 4.1 The Exploration Phase
text: 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 is to prove the strict single-stage incentive-compatibility of the mechanism used in each stage t in the exploration phase (henceforth the exploration mechanism in stage t). In fact, each exploration mechanism belongs to a larger class of nontrivial prior-independent mechanisms that are single-stage incentive-compatible for ROI constrained buyers. Before zooming into exploration mechanisms, we first prove the single-stage incentive-compatibility of this larger class of mechanisms, which may be of independent interest. Proposition 1. Fix a target ROI ratio τ . For any α ∈ R+, let (xα, pα) be such that for any b ∈ R+,
xα(b) = (min{b, 1})α and pα(b) = xα(b) · min{b, 1}
τ .
Then fixing any α ∈ R+, for all value distribution D, (xα, pα) is single-stage incentive-compatible, i.e., for any bidding strategy b : [0, 1]→ R+ satisfying
E v∼D [xα(b(v)) · v − τ · pα(b(v))] ≥ 0,
we have E v∼D [xα(b(v)) · v] ≤ E v∼D [xα(v) · v].
We defer the proof of the proposition, as well as all other missing proofs, to the appendix. In principle, for any α > 0, (xα, pα) is strictly single-stage incentive-compatible. Out of all these mechanisms, we choose the one corresponding to α = 1 as our exploration mechanisms (instantiated with different τt 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. Lemma 1. Let (xt, pt) be the exploration mechanism in stage t. For any value distribution D and bidding strategy b : [0, 1]→ [0, 1], let
Val(D, b) := E v∼D [x(b(v)) · v] and ROI(D, b) := E v∼D [x(b(v)) · v − τt · p(b(v))].
Moreover, let id : [0, 1]→ [0, 1] be the truthful bidding strategy, where id(v) = v for all v ∈ [0, 1]. Then for any bidding strategy b : [0, 1]→ [0, 1],
Val(D, b) + ROI(D, b) = Val(D, id)− E v∼D [(v − b(v))2].
Proof. First fix any v ∈ [0, 1] and v′ = b(v). We have x(v′) · v − x(v) · v = v · (v′ − v), and moreover, ( x(v′) · v − τt · p(v′) ) − ( x(v) · v − τt · p(v) ) = v′(v − v′). As a result, for any D and b,(
Val(D, b) + ROI(D, b) ) − ( Val(D, id) + ROI(D, id) ) = E
v∼D
[( x(b(v)) · v − x(v) · v ) + (( x(b(v)) · v − τt · p(b(v)) ) − ( x(v) · v − τt · p(v) ))] = E
v∼D
[ v · (b(v)− v) + b(v) · (v − b(v)) ] = E v∼D [ −(v − b(v))2 ] .
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 t, 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 a way of bounding the magnitude of deviation in each stage in the exploration phase because of the following reasons. First, since the buyer is ROI constrained, in each stage they must have nonnegative ROI slackness, and as a 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 T1 bids in the estimation. Since the buyer is less patient than the seller (i.e., they have a discount factor λ < 1), any potential future gain is substantially discounted. As a result, the motivation for deviation becomes sufficiently small, such that the buyer is only willing to sacrifice a small amount of immediate value in exchange for that. Thus, by Lemma 1, 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 {bt}, t ∈ [T1], and historical values v1, . . . , vt−1 before stage t,
E vt∼D
[(vt − bt)2 | v1, . . . , vt−1] ≤ ε2
16 ,
and as a corollary, E
vt∼D [|vt − bt| | v1, . . . , vt−1] ≤
ε 4 ,
where ε is the error parameter defined in Figure 1.
The above lemma controls one 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 on the expected absolute value of deviation in any exploration mechanism. This measure of error is closely related to the notion of the `1 Wasserstein distance W1 (also known as the earth mover’s distance) in R, defined as follows. Definition 1. For two probability distributions D1 and D2 over R,
W1(D1,D2) := inf Dj∈Γ(D1,D2)
( E
(x,y)∼Dj [|x− y|]
) ,
where Γ(D1,D2) is the family of distributions over R2 with marginals D1 and D2 in the two dimensions respectively.
Intuitively, each Dj ∈ Γ(D1,D2) corresponds to a matching between D1 and D2, and W1(D1,D2) is the minimum total cost of matching D1 to D2. In fact, it is easy to show that Lemma 2 implies the following bound.
Corollary 1. Let bt(D) be the distribution of bt(vt) (given v1, . . . , vt−1) where vt ∼ D. Then
W1(D, bt(D)) ≤ E vt∼D
[|vt − bt(vt)|] ≤ ε
4 .
This is simply because bt explicitly specifies a matching between D and bt(D), whose cost is upper bounded by ε/4. In light of this, our goal in the rest of Section 4.1 is to upper bound W1(D, D̂). We will later see in Section 4.2 that this is precisely the kind of guarantee that our exploitation mechanisms need to achieve approximate optimality.
Below we handle the other source of error, i.e., the discrepency between the buyer’s value distribution D and the empirical value distribution (henceforth D̄) without misreporting, induced by {vt}t∈[T1]. Since {vt}t∈[T1] are i.i.d. samples from D, we can apply standard results for the convergence of empirical processes in the W1 distance to obtain the following bound.
Lemma 3. Let D̄ be the empirical distribution induced by v1, . . . , vT1 . With probability at least 1− 1/(2T ) over v1, . . . , vT1 , W1(D, D̄) ≤ ε2 .
With Lemma 3 proved, we can now proceed to the final step of bounding W1(D, D̂), i.e., combining the error from misreporting and that from W1(D, D̄). This may appear straightforward: the error from misreporting is on top of W1(D, D̄), so we only need to add the bounds from Corollary 1 and Lemma 3 together. However, to achieve low regret, we need W1(D, D̂) to be small with high probability, but Corollary 1 only provides an in-expectation bound. Moreover, since the buyer may use an adaptive bidding strategy (i.e., bt may depend on b1, . . . , bt−1), we cannot apply standard
concentration bounds for independent variables to obtain high-probability bounds. Therefore, instead of applying Corollary 1, we observe that the sequence
Xt = 1
T1 ∑ t′≤t ( |bt′ − vt′ | − ε 4 ) form a submartingale. As a result, we can apply one-sided concentration inequalities for submartingales to obtain a high-probability upper bound on
XT1 = 1
T1 ∑ t∈[T1] ( |bt − vt| − ε 4 ) .
The above observation gives us the following lemma. Lemma 4. With probability at least 1− 1/(2T ) over v1, . . . , vT1 ,
W1(D̄, D̂) ≤ 1
T1 ∑ t∈[T1] |bt − vt| ≤ ε 2 .
Combining Lemmas 3 and 4 , we immediately obtain the following high-probability bound on W1(D, D̂), which is essentially the only property of the exploration phase that we need to establish the overall regret bound.
Lemma 5. With probability at least 1− 1/T , W1(D, D̂) ≤ ε.

heading: 4.2 The Exploitation Phase
text: In this section, we show that when the exploration phase succeeds, i.e., when W1(D, D̂) ≤ ε, the expected revenue by the mechanism in each stage t in the exploitation phase (henceforth the explotation mechanism in stage t) is at least OPTt(D)− ε. Since the bid submitted in any of these stages cannot affect the exploitation mechanism in any other stage, we can decouple the exploitation stages and look at each of them individually.
We first characterize the buyer’s optimal bidding strategy in response to the exploitation mechanism in each stage t. First observe that these exploitation mechanisms have a simple structure: the exploitation mechanism in stage t is essentially a take-it-or-leave-it offer, where the buyer can either take the item and pay qt, or leave and pay nothing. In particular, the specific value of the bid bt 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 vt at time t is at least the posted price qt. The optimal bidding strategy is less straightforward with value-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 is captured by the following claim. Lemma 6. Suppose a value-maximizing buyer with target ROI ratio τ has value distributionD. Then the optimal bidding strategy b : [0, 1]→ [0, 1] against a take-it-or-leave-it offer at price q ∈ (0, 1) is given by
b(v) = { 1, if v ≥ θ 0, otherwise,
where θ = inf{θ′ | E
v∼D [v | v ≥ θ′] ≥ τ · q}.
We remark that the above optimal bidding strategy is essentially unique, in the sense that the mappings from the value v to the allocation x induced by any two optimal bidding strategies can differ only on a zero-measure set with respect to D, which makes no difference for our 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 OPTt(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 isD cannot be much larger than that when the value distribution is D̂. Formally, we have the following lemma. Lemma 7. When W1(D, D̂) ≤ ε, for all t ∈ {T1 + T2 + 1, . . . , T},
OPTt(D) ≤ OPTt(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 OPTt(D̂). In other words, the exploitation mechanism in stage t can tolerate an estimation error of up to ε in the W1 distance, sacrificing only ε in the revenue. Intuitively, this is because by the definition of the W1 distance, we can find a matching Dj ∈ Γ(D, D̂) between D and D̂, such that the following is a feasible bidding strategy for a buyer with distribution D: for (v, v̂) ∼ Dj , where v is the realized value of the buyer and v̂ is the value that v matches to under Dj , buy the item if and only if a buyer with distribution D̂ would buy the item when their value is v̂ in response to a slightly higher price. This means the probability that a buyer with distribution D buys the item is at least the probability that a 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 at 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̂) ≤ ε, for all t ∈ {T1 + T2 + 1, . . . , T}, the expected revenue of the exploitation mechanism in stage t satisfies
Revt(D, D̂) := max{(qt − ct), 0} · Pr v∼D [v ≥ θt] ≥ OPTt(D̂)− ε,
where θt is the threshold of the optimal bidding strategy as given in Lemma 6, i.e.,
θt = inf{θ ∈ [0, 1] | E v∼D [v | v ≥ θ] ≥ τt · qt}.
Finally we combine Lemmas 7 and 8 to obtain the following conditional revenue bound, which is essentially the only property of exploitation mechanisms that we need.
Lemma 9. When W1(D, D̂) ≤ ε, for all t ∈ {T1 + T2 + 1, . . . , T}, the expected revenue of the exploitation mechanism in stage t satisfies
Revt(D, D̂) ≥ OPTt(D)− 2ε.

heading: 4.3 Putting Everything Together
text: 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 values. Theorem 1. With probability at least 1−O(1/T ), our mechanism achieves total revenue at least
OPT(D)−O(T 2/3 log T ).

heading: 5 Conclusion
text: In this paper, we develop a prior-independent dynamic mechanism achieving low regret against a value-maximizing buyer. Along the way, we propose a novel prior-independent single-stage mechanism that is 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̃(T 2/3) bound is (nearly) optimal — we suspect the bound cannot be significantly improved restricted to exploration-exploitation mechanisms,
given that similar lower bounds have been established in related problems in prior work [Babaioff et al., 2014, Devanur and Kakade, 2009]. In principle, one could also consider the case where the target ROI ratio τt is also private and needs to be reported. However, people do not currently have a good understanding of this case even in static environments, and as a result, it is not even clear what the benchmark should be for this case in dynamic environments. Other variants of the problem, e.g., where there is 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 a better understanding about the power and the limitations of dynamic mechanisms against value-maximizing buyers.
Funding Transparency Statement
Hanrui Zhang was supported by NSF grant IIS-1814056.

Review summaries:
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.  The 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.  

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.

The paper studies prior-independent dynamic auctions with a single value-maximizing buyer. In 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). The 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. The work is under the assumption of a patient seller and a buyer has a time discount factor $\lambda$.  The algorithm is divided into three parts:  1. Exploration phase that incentivizes the buyer to report approximately truthfully. To my understanding, this is the main new technique in the work.  2. A buffer phase.  3. Exploitation phase that extracts the revenue using a robust version of the single-stage revenue-optimal mechanism for this problem.  

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.