Posted Pricing and Dynamic Prior-independent Mechanisms with Value Maximizers
Authors: Yuan Deng
Vahab Mirrokni
Hanrui Zhang
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study posted price auctions and dynamic prior-independent mechanisms for (ROI-constrained) value maximizers. In contrast to classic (quasi-linear) utility maximizers, these agents aim to maximize their total value subject to a minimum ratio of value per unit of payment made. When personalized posted prices are allowed, posted price auctions for value maximizers can be reduced to posted price auctions for utility maximizers. However, for anonymous posted prices, the well-known $\frac 1 2$ approximation for utility maximizers is impossible for value maximizers and we provide a posted price mechanism with $\frac12(1 - 1/e)$ approximation. Moreover, we demonstrate how to apply our results to design prior-independent mechanisms in a dynamic environment; and to the best of our knowledge, this gives the first constant revenue approximation with multiple value maximizers. Finally, we provide an extension to combinatorial auctions with submodular / XOS agents.

Posted Pricing and Dynamic Prior-independent Mechanisms with Value Maximizers
Yuan Deng Google Research dengyuan@googJe.c com
Vahab Mirrokni Google Research mirrokni www.ooiinooooooooooooooooooooo.o com
Hanrui Zhang Carnegie Mellon University hanruiz1@es 21ccs. cmu edu
Abstract
We study posted price auctions and dynamic prior-independent mechanisms for (ROI-constrained) value maximizers. In contrast to classic (quasi-linear) utility maximizers, these agents aim maximize their total value subject to minimum ratio of value per unit of payment made. When personalized posted prices are allowed, posted price auctions for value maximizers can be reduced to posted price auctions for utility maximizers. However, for anonymous posted prices, the well-known 2 approximation for utility maximizers is impossible for value maxi- mizers and we provide posted price mechanism with (1 1/e) approximation. Moreover, demonstrate how to apply results to design prior- iifor-independentt mechanisms a dynamic environment; and to the best of our knowledge, this gives the first constant revenue approximation with multiple value maximizers. Finally, we provide an extension to combinatorial auctions with submodular / XOS agents.
Introduction
In online udvertising, the growing adoption of autobidding witnesses the emergence of value maxi- mizing bidding, which has become the prevalent behavior model for bidding agents in recent years (Aggarwal ct al. 2019 Deng et al. 2021a]. Instead of specifying their bids per auction opportunities, the advertisers only need to report their high-level objectives and/or constraints to the bidding agents and the bidding agents bid on behalf of the advertisers to maximizes their objectives subject to the constraints. A common type of value maximizing bidding is return on investment cROt)-constrained value-maximizers a.k.a.. target CPA (cost per acquisition) and target ROAS (return on ad spend) auto-bidding. For ROI-constrained value- maximizszss,,ss, their objective is to maximize their total value subject to constraint specifying minimum ratio of value per unit of payment made.
In theory, there is already a fairly complete understanding of mechanism design with ROI-constrained value-maximizens With single-purameter buyers and publicly known target ROI ratios, Balseiro et al. (20216) show that the VCG auction with properly scaled payments extracts the full optimal welfare as revenue, which is arguably the strongest guarantee one can think of. In order to apply this result, however, there are two major issues:
Firstly, the incentive-come compatiiiyy of this optimal mechanism is quite sensitive to the payment scalars, which in turn require prior knowledge to compute. Moreover, when incentive-compatiility is compromised because of (even slightly) inaccurate or misaligned prior beliefs, there is no known way predict the buyers' behavior, any guarantee of the mechanism is completely lost. In order to tackle this issue, Balseiro et al. [2021a] propose robust auction formats that are approximately optimal given "signals" that are close enough the buyers' such signal available? Another recent attempt addresses the prior dependence issues by designing prior-independee dynamic auction mechanism with single ROI-constrained value-maximizer [Deng and Zhang 2021]. Such mechanism is useful when the buyer' value distribution is unknown the seller, and must be learned over time which is the case in many important application
values. But what can we do when there no
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

scenarios, such as online ad auctions. Despite significant interest in designing prior-independe dynamic auctions, it remains unknown whether one can even extract constant fraction of the optimal welfare as revenue in the long run.
Secondly, perhaps an equalty important consideration is the cognitive complexity of the mechanism. Despite strong theoretical guarantees it provides, the format of the optimal mechanism (and in particular, the payment scalars) may appear quite mysterious to buyers. As result, buyers may act suboptimally, and therefore unpredictably. based on their misunderstanding of the mechanism. This can be further exacerbated incentive-comee compatiblll is compromised, in which case buyers must come up with their own bidding strategies. All these reasons motivate us to investigate robust and simple solutions for mechanism design with ROI constraints. In terms of robustness in particular, we are also interested in designing prior-independen mechanisms that do not rely on any kind of predictions.
Sequential posted price mechanisms. In traditional environments, among simple auction formats, the one that receives the most attention is posted price mechanisms [Chawla et al.) 2010]. Sequential posted price mechanisms are arguably the simplest format of auction protocols (among nontrivial ones): the seller approaches the buyers one by one in arbitrary order. For each buyer, the seller offers a take-it-or-leave-i price. If the buyer takes the offer, then the buyer gets the item and pays the price, and the auction ends. Otherwise, the seller proceeds the next buyer and repeats the procedure. In addition to simplicity, posted price mechanisms are also intrinsically robust: with appropriately chosen prices, the guarantees of the mechanism remains approximately valid, even with inaccurate or misaligned prior belief's. Technically, posted pricing is connected to prophet inequalities [Krengel and Sucheston 1977 1978), in the sense that the two can be viewed as the same technical problem interpreted in different ways.
From utility-maximizerr to ROL-constrained maximimaximizess. In traditional settings with miliiiimmxiiizers, it is known that in terms of welfare, one can achieve a (1/2)-aaproxiimttion using posted pricing, and this ratio is the best possible 1 The mechanism used extremely simple: the seller offers an anonymous price (i.e., same price for all buyers) that is equal to 1/2 of the expected maximum value across buyers. This guarantee generalizes to multi-unit unit auctions [Alaei 2014
Hajiaghayi al. 2007], and even combinatorial auctions (Dutting et al. 2020 Feldman et al. 2014 The huge success of posted pricing with utility-maximizens as well as its simplicity and
robustness, brings us to the following natural question: is it possible to achieve similar guarantees using posted pricing, hopefully with similar pricing strategies, when buyers are ROI-constrained value-maximizers?
1.1 Our Results
In this paper, we initiate the study of posted pricing and prophet inequalities with ROI-constrained value maximizers. The main focus of the paper is on the single-item setting, where n buyers compete for single indivisible item. We first consider the case of personalized prices, where the seller is allowed to offer a different price for each buyer. We show that with personalized prices, selling to value-maximizers is no harder than selling to traditional dility-maximizzer
Proposition (Informal Version of Proposition 4. When personalized prices are allowed, any approximation guarantee in terms of welfare with milittymaximizers implies the same approximation guarantee in terms of revenue against welfare with value-maximizers.
We then proceed to the more interesting case, where the seller must offer the same, anonymous price to all buyers. Our first result is an upper bound (i.e., impossibility result), which says the usual ratio of 1/2 is unachievable with an anonymous price, even in terms of welfare, when buyers are ROI-constrained value-maximizers.
Theorem 1 (Informal Version of Theorem 3.. There exists a problem instance where no anonymous price achieves an approximation ratio better than 0.479 in terms of welfare.
Interestingly, the hard instances we present are found by computer-aided search over structured problem instances where the optimal anonymous price can be computed efficiently. Given the upper bound, we move on to the search for a price that achieves good approximation guarantee, hopefully
'Essentially the same guarantees can be established for revenue by considering the virtual values.

---

close to the above upper bound. The most natural candidate is the usual price, 2 E/max; U/] (where o is buyer i's value), that has been extensively studied in posted pricing and prophet inequalities with cillity-maximizert natural settings with utility-mxxiiizes. While this is no longer possible give the upper bound, we show this price still achieves a decent approximation ratio even with value- maximizzesss,ss And in fact, the ratio given by our analysis is the best possible for this price.
This price and its generalizations achieve the optimal ratio of 1/2 in most
Theorem 2 (Informal Version of Theorem 4 and Proposition For any problem instance, offering the price of 2 M[max, Vi}, where vs is buyer i's value, to all buyers extracts a 2(1 1/e) ss 0.316 fraction of the optimal welfare as revenue. Moreover, our analysis tight for this price.
Finally, we demonstrate the wide applicability of our techniques by showing how they can be useful in two related problems: crior-independem. dynamic auctions and combinatorial auctions with maximiesxs. For prior- iroeeidndeennent dynamic auctions, we prove the following result.
Proposition 2 (Informal Version of Proposition (]. There is a prior-independer dynamic auction mechanism that extracts 2 (1 1/c) fraction of the optimal welfare as revenue in the long run.
To our knowledge, this is the first nontrivial revenue guarantee for prior-independent dynamic mechanism with multiple value-maximizers (the case with single buyer has been studied very recently [Deng and Zhang (202T). )) For combinatorial auctions, through an alternative analysis of the usual price, we prove the following result.
Proposition 3 (Informal Version of Proposition 7. In combinatorial auctions with malue-maximszers there are anonymous item prices that achieve an approximation ratio 1/4 in terms of welfare.
To our knowledge, this is the first nontrivial result for combinatorial auctions with value-maximizers.
1.2 Further Related Work
Mechanism design with value-maximizers. Aggarwal et al. (2019) initiate the study of ROI- constrained value maximizers and show that VCG mechanism can achieve at most 1/2 of the optimal social welfare in the worst case, which inspire a series of follow loplow-up works to find ways to improve the approximation ratio. [Balseiro et al. 20] and Deng et al. [2021a] demonstrate that with machine learning advice that approximates the advertisers' values well, the mechanism design can use boosts and/or reserves based on the advice to improve the efficiency guarantees. [alseiro et al. [202 lb) design revenue-optimal mechanisms under various information structures in the Bayesian setting. Deng and Zhang [202]] design prior-in inderiddeeendent mechanisms in an online environment by leveraging the structure of the optimal mechanism from Balsciro et al. [2021b).
Posted pricing and prophet inequalities. Prophet inequalities were initially introduced in the context of optimal stopping theory [Krengel and Sucheston| 1977 1978), and later re-introduced to the CS community by HHajiaghayi et al. [2007]. Since then, its connection to posted pricing has been extensively studied and exploited. For a detailed exposition on the connection between prophet inequalities and posted pricing, see the survey by Lucier (0017). In the past two decades, posted pricing and prophet inequalities have proved useful in an extremely wide range of settings, from simple kinle-paramete settings [ al.
2014 Correa al., 2019a b Dütting and Kesselheim 2019 Hajiaghayi et al., 2007] Rubinstein et al. 2020), to matroid and knapsack constraints [Caramanis et al.
2022 Chawla al. 2010 Dutting et al. [2200] Ehsani al. 2018 Kleinberg and Weinberg|
to general feasibility constraints [Rubinstein] 2016]. to combinatorial objective functions [Rubinstein and Singla 2017]. simple multi-parameter settings [Chawla et al. 2010), combinatorial auctions with submodular/XOS [Dutting et al. 2020 [Esani et al.] |eldman et al., (2014) and subadditive valuations (Dütting et al.] 2020 Zhang 2002). J. Similar techniques have also proved useful in online settings [Cohen et al. 2214 Deng et al. 2021b). All these results are under the traditional assumption of muxitt--maimiizing agents. In contrast, we consider posted pricing with maxilm-exxiizzrs.. which, as we will see, creates significant differences and new challenges, both conceptuallyy and technically.
objectivv
2 Preliminaries
Basic setup. We consider selling a single indivisible item to n buyers. Each buyer has value i drawn independently from distribution D.. For simplicity, unless otherwise specified, we always
3

---

assume each D, is non non-atomic, i.e., the CDF of D; is continuous, although all our results still apply without the assumption. We focus on posted price mechanisms in this paper, where the seller chooses price p; for each buyer i based on the value distributions {Di}:- The buyers then arrive in an adversarial order. Upon the arrival of buyer i, i decides to accept the price, then the seller's 's revenue is Pts and the auction ends. Otherwise, the next buyer arrives, and decides whether to accept the price, etc. If no buyer accepts their price, then the seller's revenue is O.
ROI-constrained maximieeasisiesss. Now we describe how ROI-constraince maximiinn buyers decide whether to accept a price. Without loss of generality, we assume each buyer's 's target ROI ratio is 1. Each buyer's 's goal is to maximize their expected value, subject to the constraint that the expected payment cannot exceed the expected value. This is captured by the following program.
maximize
E [x((v) v] v~D
subject to
(x(v) 2 xxu) p]. w~D
E
where D is the buyer's value distribution, p is the price, and the variable 1R - (0. is the buyer's 's strategy mapping the realized value e to "accept" (i.e., 1) or "reject" (i.e., 0). Conceptually, this
corresponds to settings where auctions happen repeatedly, and the buyer about the cumulative value and payment in the long run. It is not hard to show that the optimal solution to the above program is
[1, if 2
((D.)(D.)) ((D.))
x(v) = (0.
otherwise
where
O(D. = infff0 E
v 22/0202200 2p.
aND
For consistency we say inf 0 cc. So, buyer with value distribution D facing price p accepts the price, iff the realized value is greater than or equal to ((D.p).
Seller's objectíve: revenue maximization. Following conventions in mechanism design with ROI-constrained value-maximizers, we assume the seller's objective is to maximize expected revenue. Moreover, the benchmark that we compare to the maximum expected welfare, i.e., [(v,)~(D.) [max; vz]. Our goal is to maximize the ratio between the seller's expected revenue and the maximum expected welfare. Note that since buyers are ROL-constrained, any revenue guarantee immediately implies welfare guarantee of the same factor.
3 Warm-up: Posted Pricing with Personalized Prices
We first consider the case where personalized prices are allowed, i.e., for two buyers é and ig. the prices offered by the seller, Pi, and Piz, not necessarily the same. We show that with personalized prices, any guarantee that is achievable in traditional settings with utility-maximizen is also achievable with ROI-constrained key connections and differences between which will be instrumental in our later discussion. Formally, we prove the following claim.
The proof is fairly simple, but reveals and ROI-constrained maximizsxss
Proposition 4. For any number of buyers n and value distributions Di..... Dn, there exist person alized prices Pi.....Pry Pu. such that the seller's 's expected revenue is at least 1 2 (vv.)-(D.) [max, 0z}.
Proof. We present a reduction to posted pricing with maximizmaximszess... That is, given prices that guarantee a-approximation in terms of welfare with villit--maiimieen construct prices that extract an a fraction of the maximum welfare as revenue with ROI-constrained maximizees..... The proposition follows immediately since there are known 1 1/2-approximation prices with utility- maximizers.
Consider any prices .1..... Ir for utility- maximizers with value distributions DI...., D,,. Without loss of generality, we also assume each qi is in the support of D,. We construct prices pı.... Pv that induce exactly the same allocation with ROI-constrained value-maximizers for every combination of realized values, as that induced by ..,..... In with mtaiitysm For each i, let pt be such that 0(D (D p.) q, (this is always possible since gi is in the support of D.). Observe that the behavior of

---

a utility-mman maximizer facing price qi is the same as that of an ROI-constrained maltmmmmx facing price pt. In the former case, the buyer accepts the price iff the value o 2 9:- the latter case, the buyer accepts the price iff the value vi 2 ((Di, p:), which is equal to dj-
Given the above, we immediately see that the welfare guaranteed by Pl.....Pr Pr with ROI-constrained calue-maximizers is the same as that guaranteed by Q1..... On with utility-mxximizers. We only need to argue that the revenue guaranteed by P1...... Ps is the same as the welfare. To this end, observe that the ROI constraint is binding for every buyer i. That is, the expected value of each buyer is equal to the expected payment the buyer makes. This may appear trivial given the definition of 8 (D, p). but actually it is not: consider a buyer whose value is constantly 10. When facing a price of 1, the buyer always accepts the price, but clearly the value is much higher than the payment. Nevertheless, the two are always equal if the price is at least the expected value of the buyer, i.e., when 2 Ev--pu] This is because such cases, there exists f such that E (1 V 2 0] = p. which by definition implies (D v 2 0 ((D,)) = p. Our construction does satisfy this condition Now summing over the binding ROI constraints, we immediately see that the revenue is equal to the welfare, which concludes the proof.
Another way to interpret Proposition i the following: one can consider the Lagrangified version of each buyer's decision problem. Suppose the optimal Lagrange multiplier is X*. Observe that q = T+x= then the problem of a value-maximizer facing price is the same as the problem of a muxlity-maiimizer facing price q. This also gives a way of constructing prices :I. for value-maximizen based on existing prices Q1..... 2n for maiiityss
We make two remarks regarding the above reasoning.
The new prices .......Pr Pr. in general are different even if the old ones .1,.... In are the same. This because each p; also depends on D,, in addition to q:- So, the existence of an anonymous price that guarantees 1/2 of the optimal welfare with utility- maximizsa does not imply the same guarantee with ROl-constrained galue-maximizers using an anonymous price. In fact, as we will show later, with ROI-constrained malum-naximizers, it is impossible to achieve the ratio of 1/2 using an anonymous price.
With ROI-constrained utility maximizers, the "interesting" case when all ROI constraints are binding. This is because if some buyer's ROI constraint is not binding, then that buyer must always accept the price, which means the revenue of the seller is at most the price for that buyer (when that buyer arrives first). Restricted to the case where all ROI constraints are binding, the revenue of the seller is always equal to the welfare, and it may sometimes help to reason about the latter, as we will see.
4 Posted Pricing with an Anonymous Price
As P shows, posted pricing with ROI-constrained value-maximizers is easy with person- alized prices, but for various practical reasons we may want single anonymous price for all buyers. In that case, the reduction approach of Proposition 4 fails completely. In this section, we present our results on posted pricing with an anonymous price, which also involve some intriguing technical ingredients.
4.1 An Upper Bound Strictly below 0.5
Our first result an upper bound on the approximation ratio, which says is impossible achieve the familiar ratio of 1/2 using an anonymous price when buyers are ROI-constrained value-man maximizerx........
Theorem 3. With n = 4 buyers, there exist value distributions Di...., price extracts more than 0.483 of the optimal welfare as revenue. With n 5 buyers, the ratio further degrades to 0.479. Moreover, the same lower bounds apply even if we optimize for the welfare.
D....,,A, D4. such that no anonymous
'Recall that we require qi to be in the support of D; in (this is without loss of generality, because if qu not in the support, we can increase it in way that the probability that the buyer accepts q stays the same, until qi is back in the support). Then we can choose p: such that (DD, p.) = q.. and p. must be unique since
we also assume D; is non-atomin which also means E[v; 2 qi] = Pt. On the other hand, we know that Eles |
x) increases monotonically in æ. and gi 2 0. so Pi E/es N gi] > Elex vs 2 0j E(es).
5

---

The proof of the theorem, well as all other missing proofs, is deferred to the appendix. Interestingly. the hard instances we present are found by computer-aided search over structured problem instances. To be more specific, we consider "binary" value distributions, where the value of each buyer i is either some positive number y/ or The optimal welfare for such instances is easy to compute: we simply sort all buyers in decreasing order of Yr and allocate to the first buyer whose value realizes into y: (rather than 0). On the other hand, the optimal anonymous price can also efficiently computed: in fact, we show that the price is (without loss of generality) equal to yi for some buyer i, so compute the optimal price we only need to try all yi s. We then obtain the upper bound by generating random instances with binary value distributions and computing the optimal welfare and the optimal revenue from an anonymous price, respectively.
4.2 Approximation Guarantee of the Usual Price
Now we present the main technical result of the paper, which states that the usual price of 1 E[mmx; ey] extracts least 1 1/e) of the optimal welfare revenue. Formally, we prove the following result.
Theorem
Fix any number of buyers n and value distributions Di...., Dn. With ROI-constrained vaxie-naximizing buyers, when the seller offers an anonymous price of p (u:)>>(D)) [max; vi to every buyer, the resulting revenue is at least
2 1 -1-2)
max
(oe)~(D))
To prove Theorem 4 we only need to show that with probability at least 1 1/e, at least one buyer accepts the price p. We do this by constructing another price p' satisfying (1) p' ' p. and (2) with probability at least - /e, at least one buyer accepts p/. Formally, the proof of Theorem 4 relies on the following lemma.
Lemma 1. Fix any number of buyers and value distributions DI.... Dn- Let p' be the largest real number such that
Σ <E(m)
11 Pr u>D,
2 0(D;,p')1= 1.
Then p' satisfies
E 1/ 2 2 (m.)a(D))
max mz)
And moreover, with probability at least 1 - l/e, at least buyer accepts p', i.e.
II
Pr [u, 2 w.D.
Here we give a sketch of the proof of the lemma. First observe that by the choice of p', the sum of the probabilities that each buyer accepts the price p' is 1. By independence and concavity, the probability that at least one buyer accepts y/ must be at least 1 1/e. The harder part is to lower bound p' by 1/2 E|max v.]. To this end, we compare against an "ex-ante relaxation" of E [max vg]: for each i, we let a; be the probability that 2 is the largest among all realized values, and let 3, be the top a quantile of D; (i.c.. the probability that U, B, precisely a²). Then one can show that the sum (over i) of the contribution to E[[; above B3 (i.c., ag times the conditional expectation of v; given 2/2 2 (.) an upper bound for Tfmmax vz]. So we only need to compare p' against this sum. Here, we partition the sum into two parts: the contribution of buyers where 8 2 B(D,.p) p'), and the contribution of buyers where B, < ((D.,p') We argue that is at least as large as the larger one between the two parts, which gives the factor of z. We then give two different arguments for comparison against the two parts respectively, which rely on combination of properties of 0(,, ()) p'. and the ex ex-ante relaxation.
Once we have Lemma] I it is not hard to prove Theorem
Proof of Theorem 4 Observe that the probability that at least. one buyer accepts the price is non- increasing in the price. Now by Lemma I our price p in Theorem 4 is no larger than p' in Lemmal

---

So the probability that at least one buyer accepts our price p is no smaller than the probability that at least one buyer accepts p', and again by Lemma I the latter probability is at least 1 1/e. So the revenue extracted by offering p is at least
(1-')
/ (1-11-1 (1-)) P 2
I {ws)>-D.)
max Us
Tightness of analysis. Given the seemingly unnatural factor of 21 1/e), one may wonder if our analysis of the price p is tight. The following result shows it in fact is.
Proposition 5. For any с > O, there exists n and Di....y Dn. such that offering the price p [fmax; vi] extracts revenue at most
11 2 (1-2 E max 0i
Here we sketch the problem instances used to prove tightness. There is a single "safe" buyer, whose value always some fixed number (say k). In addtion, there are about k "risky" buyers, each of which has value 1/2 with probability E, where is small positive number. The expected optimal welfare is about 2k, so the price we post is about We can perturb the numbers so that the price is bit higher than the value of the safe buyer, and that buyer never accepts the price. Now the only source of revenue the risky buyers. Since the expected value of each risky buyer about 1, each of them accepts the price of about k with probability about 1/k, and the probability that at least one of them accepts the price is about 1 - l/e. So, the revenue (and welfare) from posting E|max vy] in this instance is about (1 - -1/e)k, whereas the optimal welfare is about 2k. The ratio matches the bound we prove in Theorem
Remark on robustness. Finally, we remark that posted pricing can in fact be robust even with ROI-constrained value-maximizers. One simple way to guarantee robustness is to slightly lower the price offered, by an amount proportional to how inaccurate or misaligned the prior beliefs can be (which of course requires an appropriate measure of inaccuracy). Then, it is not hard to argue that the probability that at least one buyer accepts the price is expected, even with inaccurate misaligned prior beliefs. Any possible loss in revenue therefore only from slightly lowering the price.
Prior-Independent Dynamic Auctions with Value-Maximizers
In this and the following section, we discuss further implications and generalizations of our re- sults, which demonstrate the power of the posted pricing framework with ROL-constrained value- maximizers.
One important question in auction design with autobidders is whether there exists no-regret prior- independent dynamic auction mechanism with ROI-constrained aalue-maximizers. In many practical applications such as online ad auctions, the buyers' value distributions are unknown to the seller, and must be learned over time. Deng and Zhang [021] give such mechanism when there is only one buyer, but the case with multiple buyers remain open, Below we show how our results imply a partial answer to this question: there exists prior-independent dynamic auction mechanism that in the long run, extracts a constant fraction of the optimal welfare as revenue.
Setup. The dynamic environment we consider is similar to that studied in [eng and Zhang 2021 Below we only give an informal description of the environment (see [Deng and Zhang [021] for more details). Compared to the static setting considered above, in the dynamic setting, auctions happen repeatedly over time. Each buyer's value distribution remains the same throughout the entire procedure. In each time period, each buyer draws new value independently from their own value distribution, and each time period has its own ROI constraints. We require the mechanism to be prior-independent, which means it cannot depend on the value distributions (but can depend on historical observations of the buyers' behavior). We also assume the value distributions are supported on [0, 1), which is common assumption in prior-indepence auctions.
bi-criteria mechanism via posted pricing. We present a dynamic mechanism that extracts a (1 - 1/e) fraction of the optimal welfare in the long run. We do this by reducing the problem to
7

---

no-regret learning the optimal anonymous price: in each time period, we run a sequential posted price auction with an anonymous price, which is chosen using any off-thheshelf algorithm for finite-armed stochastic bandit after discretization. Formally, we prove the following.
Proposition 6. With ROl-constrained value- maximizing buyers, there is proor-idepennent dynamic mechanism that, for any number of ROl-constrained value maxemimaaiiiing buyers n. value distributions DI...., Dn and time horizon T, extracts revenue at least
(1
1 -1-1) ))
E {w.)<(DD))
max
- O(T2i)).
We remark that if buyers care about the future (i.e., they have a positive discount factor, as studied in [Amin et al.) 2014 [Babaioff et al.) 2009 [eng and Zhang 2021 Nedelec et al., 2022]. )) then they may still have incentives to lie response to the above mechanism. However, as long as buyers are less patient than the seller, it is not hard to design dynamic mechanism based on our posted-price mechanism, where even patient buyers have no incentive to lie. For example, one can adapt the apploration-epploitaioon framework in (Deng and Zhang [02T] in the following way: we first run the exploration mechanism in [Deng and Zhang, 2021] for each buyer for sufficiently many time periods to learn the approximate value distributions of all buyers. Then we run our posted- price mechanism with the price slightly lowered to account for potential inaccuracy in the value distributions learned earlier. By trading off between the lengths of the exploration phase and the exploitation phase, one can achieve regret ((T2/3) against (1 1/c)/2 fraction of the optimal revenue.
6 Combinatorial Auctions with Value-Maximizers
With mulity-maximizers posted pricing schemes generalize elegantly to combinatorial auctions, where multiple heterogeneous, possibly mutually substituting, items sold. One may naturally wonder if similar generalizations exist with ROI-constrained one way to generalize our results to combinatorial auctions with submodular or XOS valuations. In exchange for generality, we get a worse approx improximation factor of 1/4, which applies to welfare but not revenue. To knowledge, this is the first mechanism that achieves nontrivial guarantees in combinatorial auctions with ROI-constrained value-maximizers.
We demonstrate
Setup. The setup we consider is similar to that studied in (Feldman al. 2014]. except that consider ROI-constrained maximiaaxsss instead of
There are m heterogeneous items, and each buyer has a valuation function v; [[m] + IR., drawn independently from i's valuation distribution D;. Following prior research on combinatorial auctions, we assume each buyer i's valuation function v; is submodular XOS (we only use certain properties of these classes in blackbox way; for formal definitions see, e.g., [Feldman et al.) 2014). Such functions model items that are potentially substitutes, but never complements, to each other. We consider posted price mechanisms, in which each item E [m]] is associated with an anonymous price p,. Buyers arrive in an adversarial order. Upon arrival, each buyer i can choose to buy any subset of the items that are still available, and the total payment i pays is the sum of the prices of the items bought. Once sold to a buyer, an item immediately becomes unavailable.
Buyer's problem. Here, we deviate from the setup introduced in Section 2 and instead consider ROI constraints over different items. Each buyer i's ROI constraint is over all items that receives and the total payment that i makes. That is, when receives items S S [m²] and pays p in total, the ROI constraint requires that (S) 2 p. So, when buyer has valuation function v. the set of available items is A, and the prices are {p,) iee, the buyer's 's problem is captured by the following program.
maximize
v(S)
subject to v(S)
N
Σp Pj.
JES
where the variable S C A is the set of items that the buyer buys We let BUY A) C A denote the optimal solution to the above program. We allow the buyer to break ties arbitrarily, We also note that
To achieve the claimed regret bound, one may run Thompson Sampling Bubeck and Liu 2013 Thompson
1933
or certain versions of UCB [Auer et al. 2002 Lattimore and Szepesvári 2020 )
8

---

when each buyer's in the limit, this setup generalizes the single-item setup introduced in Section 2 valuation function is additive, and the value of each item is iid, we effectively recover the single-item setup by letting
oo.
The mechanism. The mechanism we analyze is exactly the same as the one proposed in [ellman al. 2014). Let OPT,(tt..... Un)) ) be the set of items that buyer receives in the welfare-maximizing allocation, when the valuation functions are Ui....., Un- We use the following property (see, e.g..
[Dutting al. 2020 Feldman et al.] 2014)) of submodular and XOS valuations.
Lemma 2. Fix any XOS valuation v and set of items S C [m]] There exist nonnegative numbers {aylees = (v, Hes such that (1) Ejesaj a = U(S), and (2) for any T C S, EjEr aj S (T)).
We also remark that these numbers can be computed efficiently with oracle access to the valuation function (see [Dutting et al. 2020)) Given this property, for each item j, the price we pick is
E Pj 2 (m))
Σ Eay(u, OPT, ..... vn))
where we let (v, S) jf & Intuitively, this is setting each item's price to half of its expected contribution to the maximum welfare. These prices generalize the one in the single-item setting. We prove the following guarantee of these prices.
Proposition 7. For any n, m, and valuation distributions Dı,..., Dro there exist anonymous prices Pi...., pm which guarantee expected welfare at least
1
Σ (OPT.. v.))
E 4 (D.)
The proof of Proposition 7 similar to the analysis of the same mechanism for maximzersss (see, e.g., [Feldman al. 2014)). The key difference is that with value-maximizers, the welfare is no longer equal to the sum of the revenue and buyers' utility. Instead, we only have the weaker guarantee that the welfare is at least as large as the larger one between the revenue and buyers' utility, which is at least as large as 1/2 of the sum of the two. Here we lose a factor of 2.
7 Conclusion and Future Work
In this paper, we initiate the study of posted pricing and prophet inequalities with ROI-constrained malue-maximizers. We show that with personalized prices, posted pricing with aalue-mximizzer is no harder than with traditional dulitt-maximizers. For the more interesting case of pricing with an anonymous price, we give nontrivial upper and lower bounds. In particular, our lower bound is through a tight analysis of the usual threshold of 2 [[max Uz.. and our upper bound is strictly below 1/2. The most natural open question is determine the optimal ratio with an anonymous price. We also show how our techniques can be applied to two related problems: prio--ndeppendet dynamic auctions and combinatorial auctions with value-mant maximizers. To this end, future directions also include improving the approximation guarantees for these problems, as well as further generalizing to other related problems.
Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for their helpful feedback.
References
Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mchta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17-30. Springer, 2019.
Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972. 2014.

---

Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers, Advances Neural Information Processing Systems, 27, 2014.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22) 256, 2002.
Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg. Prophet inequalities with limited infor- mation. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithms, pages 1358-1377. SIAM, 2014.
Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. Characterizing truthful multi-armed bandit mechanisms. In Proceedings of the 10th ACM conference Electronic commerce, pages 79-88, 2009.
Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34, 2021a.
Santiago R Balseiro, Yuan Deng, Jieming Mao, Vahab S 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, pages 132-133, 2021b.
Sébastien Bubeck and Che- Yu Liu. free and prponddependent regret bounds for thompson sampling. Advances in neural information processing systems, 26, 2013.
Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenoopolos,, Emmanouil Pountourakis, and Rebecca Reiffenhäuser. Single-sample prophet inequalities via greedy selection. Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1298-1325. SIAM, 2022.
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM sympo- sium on Theory of computing, pages 31 1-320, 2010.
Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Lukasz Jež. Pricing online decisions: Beyond auctions. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, pages 73-91. SIAM, 2014.
José Correa, Paul Dütting, Felix Fischer, and Kevin Schewior. Prophet inequalities for iid random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 3-17, 2019a.
José Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo. From pricing to prophets, and back! Operations Research Letters, 47(1):25-29, 2019b.
Yuan Deng and Hanrui Zhang. Prior-independent dynamic auctions for a value-maximizing buyer. Advances in Neural Information Processing Systems, 34, 2021.
Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song 7uo. Towards efficient auctions in an auto- bidding world. In Proceedings The Web Conference 2021, 2021a.
Yuan Deng, Debmalya Panigrahi, and Hanrui Zhang. Online combinatorial auctions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131-1149. SIAM, 2021b.
Paul Dütting and Thomas Kesselheim. Posted pricing and prophet inequalities with inaccurate priors. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 11 1119, 2019.
Paul Dutting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made casy: Stochastic optimization by pricing nonstochastic inputs. SIAM Journal on Computing, 49(3): 540-582, 2020.
Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o (log log m) prophet inequality for subadditive combinatorial auctions. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 306-317. IEEE, 2020.
10

---

Soheil Ehsani, MohammadTTaght Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms, pages 700-714. SIAM, 2018.
Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the twenty-sixit sixth annual ACM-SIAM symposium on Discrete algorithms,, pages 123-135. SIAM, 2014.
Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mecha- nism design and prophet inequalities. In AAAI, volume pages 58-65, 2007.
Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium Theory of computing, pages 123-136, 2012.
Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745-744) 747, 1977.
UIrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces, 4:197-266, 1978.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Brendan Lucier. An economic view of prophet inequalities. ACM SIGecom Exchanges, 16(1):24 47, 2017.
Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui, Vianney Perchet, et al. Learning in repeated auctions. Foundations and Trends@ in Machine Learning. 15(3):176 334, 2022.
Aviad Rubinstein. Beyond matroids: Secretary problem and prophet inequality with general con- straints. In Proceedings of the firth- annual ACM symposium on Theory of Computing. pages 324-332, 2016.
Aviad Rubinstein and Sahil Singla. Combinatorial prophet inequalities. In Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1671-1687. SIAM, 2017.
Aviad Rubinstein, Jack Z Wang, and S Matthew Weinberg. Optimal single-choice prophet inequalities from samples. 1 Ith Innovations Theoretical Computer Science Conference, 2020.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22 2994, 1933.
Hanrui Zhang. Improved prophet inequalities for combinatorial welfare maximization with (approxi-
mately) subadditive agents. Journal of Computer and System Sciences, 123:143-156, 2022.
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 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 reproduce the main experimental results (cither in the supplemental material or a URL)? [N/A]
11

---

(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 to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releusing new assets...
(a) 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]
(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, if applicaalle?
[N/A]
(b) Did you describe any potential participant risks, with links 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 participant compensation? [N/A]
12


Reviews:
[{"review_id": "JWYLke0KTJb", "reviewer": "Reviewer_Kp2a", "summary": "The paper studies the posted price auctions for ROI constrianed value maximizers. Personalized posted prices are shown to be equivalent to posted price auctions for utility maximizers. For anonymous posted prices, a mechanism is provided, proving to be $\\frac12(1-1/e)$ approximation. The mechanism is further a to applied prior-independent mechanism with constant approximation, and extended to combinatorial auctions with submodular / XOS agents.", "questions": "In the proof of Proposition 4 (Line 193), why the construction satisfy the condition $p\\geq \\mathbb{E}_{v\\sim D}[v]$?", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The studied problem, auction designs for value maximizers, is important and attracts much attention in the field of auctions recently. The paper is probably one of the first few papers on posted price auctions for value maximizers. \n2. Concrete theoretical results are provided. Most proofs, as far as I checked, are corrected. \n3. The paper is clearly written and well organized.\n\nWeaknesses:\nOne proof is not fully justified. See questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DcmopXNHkc", "reviewer": "Reviewer_nCDy", "summary": "The paper studies posted-price auctions for ROI-constrained value\nmaximizing bidders, who seek to maximize their total value subject to\nthe condition that the return-on-investment (ROI) on their spend is at\nleast some prespecified ratio. This is in contrast to\nutility-maximizing bidders who seek to maximize their total utility\n(value - spend). Past results have shown that in the\nutility-maximizing case, using an anonymous posted price mechanism can\nachieve a (1/2) approximation of the welfare (or revenue). The current\npaper shows that if personalized prices are allowed, the same (1/2)\napproximation continues to hold. However, the paper presents instances\nwhere the no anonymous posted price mechanism can achieve an\napproximation ratio on welfare greater than 0.483. Furthermore, the\nauthors show that the using the optimal anonymous posted price\nmechanism for the utility-maximizing case obtains a (1/2) (1- 1/e)\napproximation of the optimal welfare. The authors also relate their\nresults to prior-independent dynamic auctions and combinatorial\nauctions.\n", "questions": " For the combinatorial auctions setting, the proof of Proposition~7\nuses the factthat the welfare is at least as large as the max of\nrevenue and buyers' utility. For the welfare to be at least as large\nas the revenue, the implicit assumption that the ROI is equal to 1 is\nrequired. Does the same (1/4) guarantee hold for general ROI, or does\nthe guarantee deteriorate?\n", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper extends the results for utility-maximizing bidders to\nvalue-maximizing bidders with ROI constraints, an approach common in\nonline advertizing. The results are obtained by directly reducing the\nanalysis to that in the utility-maximizing case using personalized\nprices.\n\nThe authors construct explicit instances where anonymous posted-prices\nachieve strictly less than (1/2) approximation to welfare, though a\ntight characterization for this setting is missing.\n\nThe authors also provide a tight characterization in the\nvalue-maximizing setting for the usual anonymous posted price\nmechanism used in the utility-maximizing setting.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-1sY6yTYjK", "reviewer": "Reviewer_LRn3", "summary": "The paper studies the price of anarchy / efficiency in auctions for ROI-constrained value-maximizing bidders. More specifically it studies posted-price types of auctions. First, it states that an approximation ratio of $\\frac{1}{2}$ when non-anonymized posted-prices are possible as it can be reduced to finding posted-prices for utility-maximizing buyers, which is a solve problem. Then, it shows that when using an anonymized posted-price, the approximation ratio is upper-bounded by 0.479. After, it shows that an approximation ratio of $\\frac{1}{2}(1-1/e)$ can be obtained with the same allocation as for utility-maximizing buyers. Finally, it provides a $\\frac{1}{4}$ approx ratio guarantee when valuations are non-additive.", "questions": "I know the paper I'm going to refer to has been published right before NeurIPS submission deadline, so I only put this as a question. Recent results showed that approximation ratios better than $\\frac{1}{2}$ can be attained with randomized VCG [4]. Do you think similar ideas could help improve the efficiency of posted-price auctions ?\n\n[4] Auction Design in an Auto-bidding Setting: Randomization Improves Efficiency Beyond VCG. Mehta 2022.", "limitations": "I don't have many suggestions on the form of the paper as I find it particularly well-written and easy to read. \n\nI'd say if authors want to \"thicken\" the content, they can look towards randomized posted-prices as it seems to be the promising direction for such problems.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. I find Prop. 1 (or 4) is strait-forward: one can write the lagrangian version of the buyer optimization problem between lines 147-148 and observe that choosing $q = \\frac{p \\lambda^*}{1+\\lambda^*}$ where $\\lambda^*$ is the optimal lagrange multiplier leads to the optimization problem of a utility-maximizing buyers faced with price $q$. It does not feel like a hugely novel result.\n\n2. I'm not a big fan of Sec. 5. The mechanism has a prior-dependent / non-measurable parameter $p^*$ and the section shows it can be tracked using an adapted sequence of parameters $p_t$ by discretizing its support and running a multi-armed bandit. In my mind, the real challenge about removing prior-dependence is to do so without introducing incentives for the buyers to lie. It's not clear to me that buyers wouldn't be incentivized to lie here, as accepting a price at time $t$ influences the price they get in the future (see [1,2] or [3] for a survey).\n\n3. My main concern about the paper is the strength of the claims. The main results are Th. 3 and 4 in my opinion, but the gap between the upper and the lower bound is large.\n\n[1] Repeated contextual auctions with strategic buyers, Amin et al 2014\n[2] Characterizing Truthful Multi-armed Ban- dit Mechanisms, Babaioff et al 2014\n[3] Learning in repeated auctions, Nedelec et al 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept