Maximizing Revenue under Market Shrinkage and Market Uncertainty
Authors: Nina Balcan
Siddharth Prasad
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)
Keywords: Shrinking markets
automated mechanism design
market uncertainty
combinatorial auctions
revenue maximization
gross substitutes

Abstract: A shrinking market is a ubiquitous challenge faced by various industries. In this paper we formulate the first formal model of shrinking markets in multi-item settings, and study how mechanism design and machine learning can help preserve revenue in an uncertain, shrinking market. Via a sample-based learning mechanism, we prove the first guarantees on how much revenue can be preserved by truthful multi-item, multi-bidder auctions (for limited supply) when only a random unknown fraction of the population participates in the market. We first present a general reduction that converts any sufficiently rich auction class into a randomized auction robust to market shrinkage. Our main technique is a novel combinatorial construction called a winner diagram that concisely represents all possible executions of an auction on an uncertain set of bidders. Via a probabilistic analysis of winner diagrams, we derive a general possibility result: a sufficiently rich class of auctions always contains an auction that is robust to market shrinkage and market uncertainty. Our result has applications to important practically-constrained settings such as auctions with a limited number of winners. We then show how to efficiently learn an auction that is robust to market shrinkage by leveraging practically-efficient routines for solving the winner determination problem.

Maximizing Revenue under Market Shrinkage and Market Uncertainty
Maria-Florina Balcan
Siddharth Prasad Computer Science Department
Tuomas Sandholm
School of Computer Science
Computer Science Department Carnegie Mellon University Optimized Markets, Inc. Strategic Machine, Inc. Strategy Robot, Inc. sandholm@cs cmu edu
Carnegie Mellon University
Carnegie Mellon University sprasad28cs. cmu edu
ninamf danamf@cs..o cmu. edu
Abstract
A shrinking market is a ubiquitous challenge faced by various industrics. In this paper we formulate the first formal model of shrinking markets in multi-item set- tings, and study how mechanism design and machine learning can help preserve revenue in uncertain, shrinking market. Via sample- based learning mecha- nism, we prove the first guarantees on how much revenue can be preserved by truthful multi-item, multi-bidder auctions (for limited supply) when only random unknown fraction of the population participates in the market. We first present a general reduction that converts any sufficiently rich auction class into randomized auction robust to market shrinkage. Our main technique is novel combinatorial construction called a winner diagram that concisely represents all possible execu- tions of an auction on an uncertain set of bidders. Via a probabilistic analysis of winner diagrams, we derive general possibility result: a sufficiently rich class of auctions always contains an auction that is robust to market shrinkage and market uncertainty. Our result has applications to important pmutically-conssraane settings such as auctions with a limited number of winners. We then show how to efficiently learn an auction that robust to market shrinkage by leveraging practically-efficient routines for solving the winner determination problem.
Introduction
A shrinking market with uncertain buyer participation is natural phase of products' and services' lifecycles. Current examples of great importance include media
as cord cutters- who cancel cable-TV subscriptions in favor of streaming services (29]. thinning customer base for department stores due to online retailers like Amazon [1] [6]. and reduced capacities for restaurants during the COVID-19 pandemic 43). In this paper study how mechanism design can help preserve revenue in this ubiquitous challenge of a shrinking market, specifically for combinatorial auctions for limited supply. The seller has m indivisible items allocate a set S of bidders. The bidders can express how much they value each possible bundle b C (1,..., m) of items. Combinatorial auctions have had wide reach in practice, from strategic sourcing spectrum auctions estate auctions. Cramton et al. [10] provide a survey of various aspects combinatorial auctions. The design of revenue-maxe maximizing combinatorial auctions multi-item, multi-bidder settings an elusive and difficult problem that has spurred a long and active line of research combining techniques from economies, artificial intelligence, and theoretical computer science. This is still largely an open question and very active research area.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper we start new strand within that topic area, namely the study of shrinking markets with uncertain buyer participation. We introduce the first formal model of market shrinkage in multi-item settings, and prove the first revenue guarantees. Specifically, we show how much revenue can be preserved when only a random unknown fraction of the set S of bidders participates the market.
1.1 Summary of the contributions of this paper
We present the first formal analysis of how much revenue can be preserved in a shrinking market, for multi-item settings. More precisely, there is set S of bidders that is known to the mechanism designer. Each bidder participates in the market independently with probability p. but the valuations of the bidders who participate in the market, denoted by So C S, are unknown (what known is that they belong to S). We present learning- based method for designing a mechanism that satisfies the first known rexenue-preservation guarantees in this setting.
In Section 2 we provide a formal description of the problem setting, including formal definitions of the auction settings consider. We precisely show how to reckon with subtleties that arise when auctions are run among a shrunken market of unknown size.
In Section 3 we provide and discuss simple example of a market where reduced competition in shrinking market drives revenue to a lower threshold than one might expect. We furthermore show that if bidders's s valuation functions can depend on what items other bidders receive, there exist scenarios in which only an exponentially small (in the number of items) fraction of the revenue obtainable by even the vanilla Vickrey- Clar-e--aareseeeee (VCG) auction on S can be guaranteed random subset bidders, even if a large fraction of the market shows up. For example, 50 items for sale and each bidder shows up independently with 90% probability, our construction yields maximum expected revenue roughly 7% of the VCG revenue on S. 100 items are for sale, at most 0.52% of the VCG revenue on S can be guaranteed.
Our main theorem is the following revenue guarantee obtained via sample- learning algorithm. Delineability is a structural assumption introduced by Balcan et al. B satisfied by nearly all commonly studied auction classes. W (S) denotes the maximum welfare achievable by mechanisms in M, the number of winners in any mechanism in M, and is a constant that
is term that depends depends on S. Rev denotes the revenue function induced by M. All notation and formal definitions are in the following sections. Sections 4 and are dedicated to proving Theorem I.
Theorem 1.1. Let M be (d, di-deiinaablle class of mechanisms. A mechanism M E M such that
E|Rev (So)] 2 (ot
WM(S)
with probability at least 1 8 can be computed in NET + (Nh))(4) time, where T the time required to generate any given hyperplane witnessing delineability of any mechanism in M and N -= (dlog(ah) log(3))
In Section 4 we prove that suPMEM E Rev (So)] 2 9 (1-11111 (47)) (SM,,), which is the major technical contribution of this paper. Our main technique is the analysis of novel combinatorial structure we construct called a winner diagram, which is graph that concisely captures all possible executions of an auction on an uncertain set of bidders. Via probabilistic method argument that randomizes over a subgraph of the winner diagram, we arrive at a general possibility result: if M is sufficiently rich class of mechanisms, there always exists an M .M that is robust to umcertainty/ssrrinkage
p²
the market. This implies our bound on sup E[Rev (So)). We primarily focus on the case where bidders participate in the market independently with probability p, but show how to generalize our results to any distribution over submarkets. Our bound is a parameterized guarantee that has interesting applications to practically motivated auction constraints: (1) limiting the number of winners and (2) bundling constraints on items.
In Section 5 we present a learning algorithm to compute a mechanism such that B[ (So)) Z supar E. Re (So)] e with high probability, which proves Theorem 1.1 Our algorithm exploits geometric structure and a mnear-programmingg approach over hyperplane arrangements. We show the run-time of our procedure computationally tractable for specific auction class by leveraging rractccall-eefficce routines for solving the winner determination problem.

---

1.2 Related work
Shrinking markets and uncertainty Shrinking markets have been studied by various researchers in the context of oil companies 47.. cable TV [T 29]. labor markets [3], telecom markets [3]], housing markets [24], and in combinatorial settings including a thinning customer base for department stores due to online retailers like Amazon [ 16 and reduced capacities for restaurants during the COVID-19 pandemic [43]. Most of this existing research is extremely domain specific, and provides advisory content based on historical observations, data, and general economic knowledge. We introduce the first formal model of market shrinkage in multi-item settings, and prove the first known guarantees for how much revenue can be preserved in a shrinking market. Our guarantee on the revenue preserved in a shrinking market provides positive contrast to recent work of Dobzinski and Uziely [12), who study the effect of market shrinkage on revenue loss. They show that even in the case of selling single item to buyers with known valuation distributions, the absence of a single buyer with a fixed "low" value can surprisingly result in a (multiplicatiie) revenue loss of e+1 (in expectation). We tackle the significantly more complex multi-item setting. Furthermore, our main results are prior-free (in that they are tailored to the specific set S of bidders and do not require bidders to come from a distribution) and thus provide a strong positive contrast to this negative result.
Our results can also be viewed from the perspective of an uncertain market, since at the point of the mechanism design the subset of bidders that participates in the market is unknown. Mechanism design with uncertainty about bidder valuations has previously studied (28 45,, but to the best of our knowledge the prior-free setting for combinatorial auctions has not been considered.
Revenue in combinatorial auctions We prove guarantees when the seller limits the number of winners and when the seller places bundling constraints on the items (for example, by enforcing that certain items must be sold together). Reasons for limiting the number of winners include: (1) avoiding the logistical hassle of having a large number of winners - this constraint is commonly used
in sourcing auctions [2] 36 37 41 and (2) increasing competition to boost revenue, as is studied by
Roughgarden et al. (34] (though in a different setting than ours). Kroer and Sandholm (25) show that the VCG auction run with bundling constraints can yield significant revenue gains.
Furthermore, catalyzed by the seminal work of Bulow and Klemperer (7]. a recent line of work studies the competition complexity of auctions, and provides results that compare the optimal (expected) revenue to the revenue of mechanisms like VCG when the number of bidders is augmented [6] g 14
15
Competition complexity results can be seen tackling the "opposite" situation of growing market. However, existing work in this area uses the very different objective of expected revenue over buyer valuation distributions, and moreover has only tackled restrictive classes of valuation functions (such as unit-demand and additive valuations). Also related is the work of Rastegari et al. [32] who study settings where revenue can counterintuitively be boosted by dropping bidders.
Learning for auction design Our algorithm for designing mechanism robust to uncertain market shrinkage is a sample-bace based learning algorithm. Such sample-bast automated mechanism design methods were introduced by Sandholm and Likhodedov [26 27 42
with the first generalization guarantees for machine learning based mechanism design appearing in Balcan et al. [2]. Machine learning for auction design has since grown into a rich field blending theory and practice 3 4 13 30)
Unlike most prior work on machine learning for auction design, our setting is prior-free and does not have access to samples. In learning algorithm, the mechanism designer produces samples himself that simulate the shrunken market, which is along the lines of the learning wwwhiw--a--iiieeeeeee paradigm of Balcan al. (5). For simplicity, we use the term sample-based as catch-all for any algorithm that uses samples, prior-free or not. Furthermore, while our algorithm is a sample-based, the techniques we use to prove our main guarantee are fundamentally new. The aforementioned literature seeks to find near-optimal mechanism from samples- in contrast our goal is to prove concrete revenue guarantees on the optimal mechanism.
2 Problem formulation
Combinatorial auctions A seller has m indivisible items to allocate among set S of bidders. Each bidder is described by her combinatorial valuation function Us : 2 + R>o. We assume
3

---

bidders' valuations satisty free-disposaa that is, (4(b) I v,(b) for all b S 8' S (1.....m) and (0) O. For an allocation a, vj(a) is bidder i's value for the bundle she receives under a.
mechanism M specifies, given a set of bidders S, an allocation a of the items and a payment p: to be collected from each bidder i S. The welfare of M when run on S is W = Eies U (a))), and its revenue S is Re increase her utility (value minus payment) by misreporting her true valuation function U; to M. M is individually rational if ea(a) Pt for all i. All mechanisms considered in this paper assumed to be incentive compatible and individually rational. The classical
Eies Pi- M is incentive compatible if no bidder i may strictly
Sefrey-Clarke-Grovee uses an efficient allocation a" (one that maximizes Lies by (o)), and charges bidder payment of maxa Ejes By (a) - Eize U/ (a")). The VCG auction is truthful and individually rational. It is well known that the VCG auction can yield low revenue in many scenarios.
(VCG) auction 2 17 48
Market-size uncertainty In our model, the mechanism designer has full knowledge of the entire population of bidders S' (described by their valuation functions). An unknown random subset of S participates in the market. We write So Pp S to denote a subset So that is sampled from S by including each bidder in Sp independently with probability p. More generally, for distribution D over 25, we write Su ~D to denote random subset of chosen according to D. We are interested in what happens to the maximum revenue achievable when only random fraction of the set S of bidders participates in the auction, that is, SuPMEM Eso-ns (So)].
Since a variable group of bidders of variable size can participate in the auction mechanisms we run, we require the important assumption that auctions in .M can be run variable-size sets of bidders in well-defined manner. Various well-studied classes of auctions satisfy this property: examples include the class of VCG auctions with reserve prices, X-auctions (22], affine-maximize
auctions [33], and various population-size -iin---iii-dddedeeenn auctions in Balcan et al. [5]. We assume that the mechanism designer knows the valuations of the bidders in S to begin with. So, each bidder can be thought of having an identity (for example, "the bidder who values apples at z and oranges at y", or "the bidder with valuation function V2 and the mechanism designer knows the identities/valuutin , Un of all bidders in S. An allocation. formally, is a mapping from items to bidder identities.
The sequence of mechanism design and revelation in our setting is the same as in the standard mechanism design setting. Specifically, the mechanism design (computation of a mechanism from M) takes place before the bidders in the shrunken market are asked to reveal their valuations. This is important for incentive compatibility, that is, for motivating the bidders to reveal their true valuations. If the design/choice of M M is allowed to be based on the revealed valuations, the auction might not be incentive compatible. (The class of second price auctions with reserve prices for a single item serves as an illustrative example. Choosing the reserve price to maximize revenue after the shrunken market is revealed clearly violates incentive compatibility.) Because the designer does not know exactly which bidders are in the shrunken market So, the designer has uncertainty about the valuations of the bidders. He only knows that they belong to S.
Assumptions on M and S For any S' S. let (S') = MaxMEM (S' and RevM((') MaxMeM Rev (S"). Let win (5") denote the set of bidders in S" that win a nonempty bundle of items per M. Let win (S") denote the set of bidders in S' that win a nonempty bundle of items per the mechanism in M achieving (s'''". The following two assumptions are the most critical ones.
Z (M (S Winner monotonicity For all S" C S' C S and all i E S win.(('))
Welfare submodularity For all S1 S2 S S, (SI)
E (i".
Suppose WM((S"= = Wyc for any S C S. that is, M is sufficiently rich to be able to allocate items efficiently (as is the case with all mechanisms in the hicrarchies discussed by Balcan et al. 3l5.). Then, welfare submodularity implies winner monotonicity [1)]. If the valuation functions of bidders in S satisfy the srbss-substitute property, then both welfare submodularity and winner monotonicity hold 18 19 49].
The final assumptions stipulate that M is a sufficiently rich class of mechanisms. We assume that (e") = (S') = Wvca(S") for all 5' C S. and further that M satisfies the following "global VCG-like" property: Rev (e")( depends only on (in)((')) and (i (i)) for each i (S') In words, these conditions stipulate the following: (1) M is sufficiently rich such that in nruntruthfuu full-information setting, M can always extract the full social surplus

---

WM(S") = (vca(S") as revenue and (2) for any S', the payments collected by the revenue- maximizing mechanism M that achieves Re (S') depend only on (M(S) and the maximum welfares W. (M((5) \ {i)) achievable when each bidder drops out.
As concrete example, if S is of bidders with gross- substitutss valuations, then the class of A-auctions and the class of affine-maximizer auctions satisfy all of the above properties (we prove this fact in Appendix and provide more details about these auction classes).
3 Revenue loss can be drastic
At first glance it might appear that the expected revenue preserved by a mechanism M when each bidder participates independently with probability p should simply be p Rev (S) (or more if one thinks of revenue as having diminishing returns in the number of bidders). This intuition indeed accurate if Rev is submodular function (which captures the diminishing returns property). However, revenue can shrink by more than this when mechanisms in M do not have submodular revenue. One reason for greater revenue loss is reduced competition among buyers. For example, suppose there are m items and 2m bidders, where bidder for < i < m has valuation 8y (b) = c i S has valuation Um+s(6) = c z/m if E b and +m++ (b) = otherwise (bidders have combinatorial valuations in this example, so valuation functions only depend on the bundle of items received). The VCG auction will allocate } to bidder i. The payment collected from bidder will be c E/m, which the second highest value for item The revenue from VCG is thus mc W(S) Now, suppose each bidder participates in the auction independently with probability The expected revenue can be computed by breaking it up across items:
i 6 and (b) = 0 otherwise, and bidder m i for 1 S
item E {1...., m)
E ca Em E Revenue from item
T E p/mm (W =).
-E).
The third equality due to the fact that VCG generates nonzero revenue from item and only both bidders i and m + participate, since if at most one of them shows up there is no competition for that item. So co = p² Revyca(S).
Furthermore, if bidders' valuations are allocational, that is, vi(ax) can depend on what items other bidders receive, revenue loss be even more dramatic.
Theorem 3.1. For any >> 0 there exists S of bidders with allocational valuations such that for So ~p S, E. R (So)] S mm2 (Revvca(S) 2λ) + e for any individually rational auction M.
The exponential revenue decay in the number of items means that even if the shrunken market large in expectation, the revenue loss can be dramatic. For example, if 50 items are for sale and each bidder shows up independently with 90% probability, our construction shows that any auction can guarantee only at most roughly 7% of the VCG revenue on S. If 100 items are for sale, most 0.52% of the VCG revenue on S can be guaranteed.
4 Main guarantee on preserved revenue
We now present our main revenue guarantee when each bidder participates in the auction indepen-
dently with probability p. For set of bidders S' S, (St) = (S")UUUU wi (S") (i)) be the set of bidders in S" whose valuations determine Rev Rev,((5) Define an equivalence relation subsets of S by S₁ S2 if and only if (S,) (S2). Let (SS")
Ei= (M \ {i)).
serves as a potential function in the proof of the following theorem and represents the average
max-welfare of S' when uniformly random bidder in S drops out.
Mechanism A
(1) Let S1, S1,..., Se be an enumeration of the equivalence classes with ((S))) > (SM(
(2) Let M,,..., Mr denote the mechanisms that achieve Rev Rev,,(S))... (ev.
(3) Choose M uniformly random from (M....., Me). and run M.
The main challenge in analyzing this mechanism is bounding f. Before we do that, we analyze the revenue guarantee it satisfies in terms of L.
5

---

(23 [22,08)
(02,04)
( (01,09)
{14)
{0i)
[0l E0s
{
Figure I: A winner diagram representing a second-price auction with a single item and four bidders with valuations = {mi 1, rg 4, v4 8). At each node, the top set 5' is the set of remaining bidders, and the bottom set the set of bidders w(S') that actually determine revenue. Boxed nodes represent heavy equivalence classes for 8/9, which is the subgraph of the winner diagram A randomizes over.
Lemma 4.1. Let |S| 2 For Su ~p S. (ERRev,(SS)) 2 260
Proof. By definition of w, if S1 S2, then (11) WM((S2), (0S2) ((S2), and (ev = (S2) (and the maximum revenue is achieved by the same M E M for both sets). Call set of bidders S" S heavy if cpS") (S). So is heavy, there is M E {M Mr] such that Rev (So) = WM(Ss). so E. R 2 1 (So) 2 pp((s) > p/ WM()). Let H denote the event that So is heavy. Then,
[A[Es, a (So)] Es. [EA (So)l] 2 Es, [E (8))11]]))((H) (())
We now derive a lower bound on Pr(H). We have
Es, [sp(S)) = Es, [ Σ WM {i}]] EiS [Es. [S (i)III 2 WWM(S)
where in the final inequality by Hartline et al. (20). Es, (So) 2 PWM(SS). By Markov's inequality on the (nonnegative)
the fact that |S| 2 2 and that WM is submodular, and
random variable W (S) (So)).
Pr(Su is heavy)
(s) WM(
p/1 1-p/4 2 -.
Substituting this into our previous bound yields (ES, Rev A 2 16E WM( as desired.
We bound the number of heavy equivalence classes E. In order do this, introduce the notion of a winner diagram, which a subgraph of the Hasse diagram of S. The winner diagram for S is the following directed graph G: each node is labeled (S', w(S)) for some subset S' S. The root node is labeled (S, (S)). The children of node (S', w(")) are given by (S' wi), \ {i})) for each e (S'). Figure I iillustrates the winner diagram corresponding
second -picc auction for single item with four bidders. Winner monotonicity will allow us to show that G contains a node that represents every equivalence class of =.
Lemma 4.2. G contains all equivalence classes of
Proof. Let S* C S be a set of bidders that arises as winner set, that is, S = w(S") for some S" S*. The set S' 3 S" S* is maximal for S* if w(')) = S and (S' (+} + S* for every i S'. We show that for a given winner set of bidders S there is unique maximal set of bidders S' 2 S* such that (SS)) = S* Initialize S' = S and greedily add bidders from to while
(S")) S* does not change. Due to winner monotonicity, if i w(S), then i w(' U (i}) for

---

5" maximal Ln (S$")=
(1}
S"
5" \ f/r
SEBYS' (EW(S"U(())
S" U1.... .r3
Figure 2: Illustration of the inductive step in Lemma 4.2 Boxed sets correspond to representative
elements of equivalence classes in G. Solid arrows represent directed edges in G from parent to child.
any bidder j. Hence, the order in which bidders are added by the greedy procedure does not matter, and therefore the final set S" is the unique maximal set for S Let the representative element of each equivalence class ((S", (S')) be the one such that S' is maximal for ((S').
We prove the lemma by backwards induction on the size of the representative set S' of any equivalence class. The base case of |S"| = n is immediate since the root (SS) is the only node for which the representative set has size n. For the inductive step suppose that G contains node for every equivalence class for which the representative set of size at least n'. Let (S', w((") be the representative of equivalence class with [S"| n' 1. Let i $ S' be bidder such that i E wSS U {t)). Such an exists due to winner monotonicity: if E w(S). then E w(S {i}), since S' U {i] C S. Let S" be the maximal set such that w(S")
w(S' U {i)). We have [S") 2 U > |S'), so by the induction hypothesis G contains a node labelled (S" w(S))) Now, there must exist bidder jn E S" SS such that j1 wS""). If not, adding all the bidders in S" 5" to S' would not introduce any new winners, that is, w (5" U (S" ((5)) = w (S") = w (S"), which contradicts the maximality of S' for w(S"). Therefore, the node (S" (S(")) has child
(S"
(S" \ (ii))
(S") {ni} is maximal due to winner monotonicity). We may now find a bidder je E S" {hi} S such that J2 w(S" {i1 \ S') for the same reason before. Continuing in this fashion yields path from (S" "("")))) to (S", ((")), so (5" w(S')) E G, as desired.
Combining Lemmas 4.1 and 4.2 yields our main guarantee. Let max (Sw(S)) (p and
(S))(
let = maxg. (w()"). ][. We have S 2m. The parameter 7y measures the smallest decrease in between any two levels G. which
use to control the depth of nodes considered by our main mechanism A. We stipulate that y < 1. In Appendix C we discuss how to remove this assumption and replace 7 with an appropriate parameter that is unconditionally strietly less than 1.
Theorem 4.3. Let [S] 2 2 and Sq <p S. We have
E Eso Rev (
WM(S).
If M consists of revenue-monotore mechanisms the slightly improved bound 9 1o01/-197 (97) (S) holds. In particular, there exist mechanisms in M achieving the above guarantees in expectation.
x²
Proof. Let G' denote the restriction of the winner diagram G to nodes representing heavy equivalence classes. Each node of G' has out out-degree at most i = maxs' (w(("),,, and the depth of G' is at most
(//1//(4pp) since decreases by factor of at least y when passing from a parent node child node (and truncated at nodes that are not heavy). Hence the number of nodes g' at most (11l01//(4/p)) If mechanisms in M are revenue monotonic, then we may modify A to randomize only over mechanisms corresponding nodes of G' with out-degree O. The
1og1/7 /
(u(T)
W (S)(S)
7

---

number of such nodes is at most (4/p1/ By Lemma 4.2 we may substitute this quantity for in Lemma which completes the proof.
We have thus shown, via an application of the probabilistic method, that M is a sufficiently rich mechanism class, there always exists M E M that is robust uncertainty in the market. Thus, SUPMEM ar (So)] 2 91 gitlony (475) (S), with a slight improvement under revenue monotonicity.
p²
In Section we showed that if bidders can have allocational valuations there exist scenarios where only an exponentially small fraction of revenue can be guaranteed. Theorem 4.3 also holds in this setting under a stronger version of winner monotonicity, which we show Appendix
4.1 Applications
The dependence of Theorem 4.3 on maxg/ (S() allows us to derive interesting families of guar- antees when the seller places practical constraints the auction setting. The first is constraint on the number of winners, and the second a bundling constraint that favors allocations that sell certain items together. Reasons for limiting the number of winners include: (I) avoiding the logistical hassle of having a large number of winners this constraint is commonly used in sourcing auc- and (2) increasing competition boost revenue, is studied in Roughgarden et al. (34] (though in different setting than ours). Kroer and Sandholm (25) show that even the vanilla VCG auction run with bundling constraints can yield significant revenue gains compared to VCG with no bundling constraints.
tions 21 36
4.1.1 Limiting the number of winners
Suppose M is class of mechanisms such that (win (S)] S no for all M .M such that WM is submodular, winner-monotonic, and satisfies the global-VCG-lice property discussed previously. The proofs of all previous theorems go through with this constraint taken into account, with parameters modified correspondingly. Let yo, y be defined as previously.
Theorem 4.4. Let |S| 2 2 and So ~- p, and let M be class of mechanisms that sell to at most no bidders. Then, there exists M MM such that
E Rev M (So) 2 Ω
WM(S).
(2ma) 141881/ (37p)
In practical settings the auction designer might limit the number of bidders that can win a nonempty bundle of items and in such no can potentially be treated constant relative to and
In Appendix C we consider VCG-like auctions that favor allocations that bundle certain items together. For such auctions, we obtain a guarantee in terms of the relevant bundling constraints.
General distribution over submarkets
So far we have stated our guarantees under the assumption that each bidder participates in the auction independently with probability p. When bidders participated independently with probability
p. welfare submodularity required to ensure that WW (So) 2 (S). In Appendix C we give more general guarantee in terms of E E(WM((S)) which only requires winner monotonicity.
How choose an auction
Computing the mechanism M e M that achieves the revenue guarantee of Theorem 4.3 can be accomplished by searching over the set (M1...., Mc} that AA randomizes over, but this would potentially be a highly-inefficient procedure. Moreover, A itself not computationally--fioiii determining the heavy sets of bidders, and determining the mechanisms M,, MI,..., MM that are revenue maximizing for the heavy sets an exhaustive procedure that would require enumerating over potentially exponential number of subsets of S.

---

A more natural way for the mechanism designer to arrive at mechanism is to learn from samples, which ensures that the mechanism designer uses the auction that (nearly) optimizes the expected preserved revenue, which could be significantly higher than what Theorem guarantees.
We give a learning algorithm that the mechanism designer can use to learn a mechanism M E .M that achieves an expected revenue of nearly Su [e[eev as [S)]]. ]. Our algorithm similar in spirit to the learning-within-ang within-an-instance paradigm of Balcan et al. [.. To describe the algorithm, we require the following structural notion of mechanism delineability introduced by Balean et al. (
Definition 5.1 (Balcan et al. BD) Let d, h E N. A mechanism M (d. h) deelineabll if (1) each mechanism M E M can be parameterized by a d-dimensional vector 0 E TRd and (2) for any set S' S S of bidder valuations, there is a set H of at most f hyperplanes in Rd such that Reva(S) is linear in over any given connected component of R H.
Theorem 1.1. Let M be (d, h) dellneele class of mechanisms. mechanism M E M such that E[Rev xy (S6)] 2 [
WM(S) -
with probability at least 1- - 8 can be computed in NhT (Nh))od) time, where T is the time required to generate any given hyperplane wimessing delineability of any mechanism in M and N = (( e²
dd logidh)) log(})))
We design a mechanism M such that E[Rev (So)] 2 sup MEM M Revv (So)] - with high probability. The theorem statement then follows from Theorem 4.3 Our algorithm is based on the framework of empirical risk minimization from machine learning. The mechanism designer samples ,I...., SN S S independently and identically according distribution on 25, (We assume for simplicity that sampling according to D can be done in computationally efficient manner. If bidders participate independently with probability p, then the mechanism designer simply needs to flip N coins of bias for each of the n bidders in S.) The auction used will be the one that maximizes empirical revenue M arM N' Σ Reva((S)) Balcan et 3 show that N = O (llogdhh) log(?)) samples suffice to guarantee that the expected revenue of M is s-close to optimal with probability at least - 8 over the draw of SN.
Proof.
We now determine the computational complexity of maximizing empirical revenue. Our algorithm exploits similar geometric intuition that was used by Balcan et al. (3) derive the above sample complexity guarantee. A similar approach has been used in other settings as well [,55..
For each St E {Si,..., S....,,,,, }. let H4 denote the of most h hyperplanes witnessing (d, h)- delineability of M, and let H. = U.H,, so |7| I Nh. The number of connected components of Rd ( 7 at most [ d < (NA)d. Each connected component is a convex polyhedron that is the intersection of at most [H] halfspaccs. Representations of these regions 0/1 constraint-vector of length H (a in entry h E H corresponds to one side of h, a corresponds to the other side) can be computed in poly([H14) time using standard techniques [46]. Empirical revenue is linear function in each connected component due to delineability, so the parameter 0 that maximizes empirical revenue within given component can be found by solving a linear program that involves d variables and at most [H| constraints, which can be done poly( , d) time.
Our algorithm has a run-time that is exponential in the number of parameters d required to describe mechanisms in M. In Appendix D we study a class of sparse X-auctions that can be described by a constant number of parameters. By leveraging practically-effici
(a generalization of the problem of computing routines for winner determi- allocations), we show how our empirical revenue maximization is computationally tractable for this setting (in particular, the run-time T of computing the hyperplanes witnessing delineability is in terms of the of run-time of winner determination).
nation 35 39 40
6 Conclusions and future research
Our work the first to formally study the problem of preserving revenue in a shrinking market. We gave sasple-based learning algorithm to design a mechanism that is robust to shrinkage

---

and uncertainty in the market. The crux of our analysis was new combinatorial construction we introduced called a wimner diagram. Our model of shrinking market simple and natural, and can serve as a testbed for many exciting mechanism design questions.
There are several open questions and new interesting research directions that stem from this study. The most immediate question is to derive tight bounds on revenue loss. There is a gap between the bound of Theorem 4.3 and the (1 p²) --raccioon revenue loss of the simple example of market with competition. Where does the true answer lie? Another interesting, and seemingly more difficult,, setting the one where the mechanism designer does not know the distribution over 2 beforehand. Can he still arrive at an auction that is robust to the shrinking market? If the mechanism designer knows that each bidder participates independently with probability p. but does not know p. still possible to design a robust auction? Finally, we believe that the combinatorial bidder structure uncovered by our notion of a winner diagram could have interesting applications to other areas in mechanism design. While our analysis required a number of assumptions on the set of bidders, it would be interesting to extend the concept of a winner diagram to prove more general results with weaker assumptions. It would be interesting to extend our techniques to understand market shrinkage in other settings including objectives beyond revenue, other auction classes, and unlimited supply.
Acknowledgments and Disclosure of Funding
This material is based on work supported by the National Science Foundation under grants CCF1733556, CCF-1910321, IIS-1901403, and SES-1919453, the Defense Advanced Research Projects Agency under cooperative agreement HR001 22020003, an AWS Machine Learning Research Award, an Amazon Research Award, Bloomberg Research Grant, and a Microsoft Research Faculty Fellowship. S. Prasad thanks Morgan McCarthy for interesting discussions about real-world shrinking (combinatorial) markets.
References
[1] Nicole P Aliloupour. The impact of technology on the entertainment distribution market: The effects of Netflix and Hulu on cable revenue. 2016.
[2] Maria-Florina Balcan, Avrim Blum, Jason D Hartline, and Yishay Mansour. Mechanism design via machine learning. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2005.
[3] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample com- plexity for multi-item profit maximization. In ACM Conference on Economics and Computation (EC), 2018.
[4] Maria-Florina Balcan, Siddharth
Prasad, and Tuomas Sandholm. Efficient algorithms for learning maximiinn two-part tariffs. In International Joint Conference on Artificial Intelligence (IJCAT), 2020.
[5] Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Learning within instance for designing high-revenue combinatorial auctions. In International Joint Conference on Artificial Intelligence (IJCAI), 2021.
[6] Hedyeh Beyhaghi and S Matthew Weinberg. Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. In ACM Symposium on Theory of Computing (STOC), 2019.
[7] Jeremy Bulow and Paul Klemperer. Auctions versus negotiations. The American Economic Review, 86(1):180, 1996.
[8] Shuchi Chawla, Jason D Hartline, David I. Malec, and Balasubramanian Sivan. Multi hulti-parameter mechanism design and sequential posted pricing. In ACM Symposium on Theory of Computing (STOC), pages 3-1-320, 2010.
[9] Ed H. Clarke. Multipart pricing of public goods. Public Choice, 11:17-33, 1971.
[10] Peter Cramton, Yoav Shoham, and Richard Steinberg. Combinatorial Auctions. MIT Press. 2006.
[11] Michael Cusumano. Amazon and Whole Foods: follow the strategy (and the money). Communications of the ACM, 60(10):24-26, 2017.
10

---

[12] Shahar Dobzinski and Nitzan Uziely. Revenue loss in shrinking markets. In ACM Conference on Economics and Computation (EC), 2018.
[13] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning
(ICML), pages 1706-1715, PMLR, 2019.
[14] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S Matthew Weinberg. The competition complexity of auctions: A Bulow-Klenn cell--reemperer result for multi-dimennional bidders. In ACM Conference on Economics and Computation (EC), 2017.
[15] Michal Feldman, Ophir Friedler, and Aviad Rubinstein. 99% revenue via enhanced competition. In ACM Conference Economics and Computation (EC), 2018.
[16] Maris Goldmanis, Ali Hortaqsu, Chad Syverson, and Önsel Emre. E-commerce and the market structure of retail industries. The Economic Journal, 1206545):651-682, 2010.
[17] Theodore Groves. Incentives in teams. Econometrica, 41:617-631, 1973.
[18] Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95-124, 1999.
[19] Mingyu Guo. VCG redistribution with gross substitutes. In AAAI Conference on Artificial Intelligence (AAAT), 2011.
[20] Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th International Conference on World Wide Web (WWW), pages 189-198, 2008
[21] Gail Hohner, John Rich, Ed Ng, Grant Reid, Andrew J. Davenport, Jayant R. Kalagnanam, Ho Soo Lee, and Chae An. Combinatorial and quantity-discount procurement auctions benefit Mars, Incorporated and its suppliers. Interfaces, 33(1):23-35, 2003.
[22] Philippe Jehiel, Moritz Meyer-Ter- Vehhen, and Benny Moldovanu. Mixed bundling auctions.
Journal of Economic Theorr, 127(1):494-5) 2007.
[23] Randall S Jones and Haruki Seitani. Labour market reform in Japan to cope with a shrinking and ageing population. OECD Economic Department Working Papers, (1568), 2019.
[24] Kohei Kawai, Masatomo Suzuki, and Chihiro Shimizu. Shrinkage in Tokyo's central business district: Lcrge-scale redevelopment in the spatially shrinking office market. Sustainability. 11
(10):2742.2019 2019.
[25] Christian Kroer and Tuomas Sandholm. Computational bundling for auctions. International Conference on Autonomous Agents and Mulfi-Agent Systems (AAMAS), 2015. Extended version: Carnegic Mellon University, Computer Science Department technical report AMU-CS-13-111) 2013.
[26] Anton Likhodedov and Tuomas Sandholm. Methods for boosting revenue in combinatorial auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 232-237, San Jose, CA, 2004.
[27] Anton Likhodedov and Tuomas Sandholm. Approximating maxiiiiim combinatorial auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Pittsburgh, PA, 2005.
[28] Giuseppe Lopomo, Luca Rigotti, and Chris Shannon. Uncertainty in mechanism design. arXiv preprins arXiv:2 /2633, 2021.
[29] Victor J Massad. Understanding the cord-cutters: An adoptioonseef--ffiicccy approach. Interna- tional Journal on Media Management, 20(3):216-237, 2018.
[30] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory (COLT), pages 1298- 1318. PMLR, 2016.
[31] Toannis Neokosmidis, Theodoros Rokkas, Dimitris Xydias, Antonino Albanese, Muham- mad Shuaib Siddiqui, Carlos and the neutral host model the solution to the shrinking telecom market. In IFIP International Conference on Artificial Intelligence Applications and Innovations, pages 70-77. Springer, 2018.
and Dimitra Simeonidou. Are 5g networks
[32] Baharak Rastegari, Anne Condon, and Kevin Leyton-Brown. Brown. Revenue monotonicity in deter- ministic, dominant-strategy combinatorial auctions. Artif. Intell., 175(2):441-455 2011.
11

---

[33] Kevin Roberts. The characterization of implementable social choice rules. J-J Laffont, editor, Aggregation and Revelation of Preferences. worth-Holland Publishing Company, 1979.
[34] Tim Roughgarden, Inbal Talgam- Cohen,, and Qiqi Yan. Robust auctions for revenue via enhanced competition. Operations Research, 2020.
[35] Tuomas Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1-54, January 2002.
[36] Tuomas Sandholm. Expressive commerce and its application to sourcing: How we conducted
$35 billion of generalized combinatorial auctions. Al Magazine, (8(3):45-58, 2007.
[37] Tuomas Sandholm. Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of soureing. In Zvika Neeman, Alvin Roth, and Nir Vulkan, editors, Handbook of Market Design. Oxford University Press, 2013.
[38] Tuomas Sandholm and Anton Likhodedov. Automated design of revenue-maximizig combina- torial auctions. Operations Research, 6305):1000-1025, 2015.
[39] Tuomas Sandholm and Subhash Suri. BOB: Improved winner determination in combinatorial auctions and generalizations. Artificial Intelligence, 145:33-58, 2003.
[40] Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. CABOB: A fast optimal algorithm for winner determination in combinatorial auctions. Management Science, 51(3): 374-390, 2005. Early version in IJCAI-01.
[41] Tuomas Sandholm, David Levine, Michael Concordia, Paul Martyn, Rick Hughes, Jim Jacobs, and Dennis Begg. Changing the game in strategic sourcing at Procter & Gamble: Expressive competition enabled by optimization. Interfaces, 36(1):55-68) 2006.
[42] Tuomas Sandholm, Anton Likhodedov, and Andrew Gilpin. Automated design of revenue- maximizing combinatorial auctions. Operations Research, 6305):1000-1025, 2015. Special issue on Computational Economics. Subsumes and extends over AAAI-05 paper and AAAI-04 paper.
[43] Hyoung Ju Song, Jihwan Yeon, and Seoki Lee. Impact of the COVID-19 pandemic: Evidence from the US restaurant industry. International Journal of Hospitality Management, 92:102702,
2021.
[44] Pingzhong Tang and Tuomas Sandholm. Mined-bundling auctions with reserve prices. In International Conference Autonomous Agents and Multi-Agent Systems (AAMAS), 2012.
[45] Taiki Todo. Mechanism design with uncertainty. In Proceedings of the Twenty-Ninth Interna- tional Joint Conference on Artificial Intelligence, (ICCAI), 2020.
[46] Csaba D Tóth, Joseph O' Rourke, and Jacob E Goodman. Handbook of Discrete and Computa- lional Geometry. Chapman and Hal//CRC, 2017.
[47] Thijs Van de Graaf. Battling for shrinking market: oil producers, the renewables revolution, and the risk of stranded assets. In The Geopolitics of Renewables, pages 97-121. Springer, 2018.
[48] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8-37, 1961.
[49] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. The effect of false-name bids in combina- torial auctions: New fraud Internet auctions. Games and Economic Behavior, 46(1):174-188 2004.
Checklist
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] We described the limitations of our work in the Conclusions and future research section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
12

---

(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 to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 'e using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "oJBLYB_R8Ck", "reviewer": "Reviewer_jXoY", "summary": "This paper studies the mechanism design problem when all the players' valuation functions are known, and each player participates with certain probability. It provides a randomized mechanism with revenue lower bound guarantee and also a sample-based mechanism which can be implemented efficiently. ", "questions": "Theorem 4.3 states there must exists a (deterministic) mechanism. Where does it prove its existence?\n", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I like the idea that each player participates with uncertainty. \n2. This paper provides a first lower bound result for the \"market shrinkage\" problem, and provides a sample-based algorithm. \n\nWeaknesses:\n1. The assumption that the valuations for all players are known is kind of restricted.\n2. This paper seems more related to market uncertainty, but less to market shrinkage. What is the formal economic definition of market shrinkage? ", "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": "CF_KMAO6_Ef", "reviewer": "Reviewer_jPw2", "summary": "This paper models shrinking markets with uncertain size in multi-item setting, and proposes a sample-based learning algorithm with provable guarantees on how much revenue can be preserved in the face of uncertain market. The major novelty is the construction of a winner diagram, which captures all possible executions of an auction on an uncertain set of bidders, and a general possibility result by analyzing the winner diagram shows the proposed bound on the revenue guarantee.", "questions": "This paper is not in my area, and I have very limited related knowledge to give technical comments.\n1. One question on bidder participation distribution: In Appendix C.5, the paper states that the proof techniques easily generalize to handle any distribution $D$ over subsets of bidders, does it imply that bidder participation probabilities can be mutually dependent? What is the impact on the revenue guarantee if the bidder participation distributions are not independent? \n2. Do we have existing revenue guarantee on markets with known size? If yes, given the proposed model of market with uncertain size, how much loss do we encounter on revenue guarantee? Does the proposed algorithm have orderly optimal performance on revenue guarantee?", "limitations": "I did not notice any.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* The paper is well-written, all the ideas are clearly discussed and properly organized.\n* The paper states that the proposed model of shrinking markets is the first formal model in multi-item setting, which seems technically non-trivial.\n\nWeaknesses: NA\n\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": "5wpGpE0N5b6", "reviewer": "Reviewer_3o7v", "summary": "This paper studies the problem of maintaining a good revenue in a shrinking market for combinatorial auctions of n bidders and m items. The shrinking market is modeled as follows: every bidder n participates in the market independently with probability p (the valuations of the bidders participating in the market are hidden). The modeling of the problem is the first contribution of the paper. The second contribution is to show that in general settings, not handling the shrinking market specifically may not just incur a revenue that is p times the optimal revenue but significantly less. This result motivates even further the need to understand how much the revenue changes in a shrinking market. The third contribution is a possibility result, showing a lower bound on the revenue that can be extracted from a shrinking market. The result’s proof is based on a new construction, the winner diagram which may be of independent interest. The last contribution is a learning-from-samples-type algorithm for nearly achieving this revenue. \n", "questions": "See my question inside the first strength above about a more learning-theoretic phrasing of the problem. My other questions are mostly related to different assumptions in the model, so I listed them under “Additional Comments”. \n", "limitations": "properly addressed by the authors", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths.\n1) The problem studied in the paper seems fundamental and to the best of my knowledge, it has not been addressed in the literature. I was also thinking that although the paper is written in a way to emphasize the inherent MD component, the problem looks like a core ML theoretical problem phrased as follows: Let S be a sample on which an algorithm is trained and obtains a model M with loss L. If instead of S, the same algorithm is used on a subset of S (say S’ \\subseteq S) then how far away are the two models M’ and M in terms of their losses? This is not precisely the question addressed in this work, but I was wondering whether there is a more ML-theoretic language to phrase the problem.\n2) The paper is very well written. I also liked the story of the paper because I found it rather “complete”; for the problem at hand not only do the paper presents how much revenue can be preserved but also how to efficiently learn an auction achieving this revenue (i.e., an auction robust to market shrinkage or general market uncertainty). \n3) The winner diagram technique (which is at the center of the construction for the possibility result) is quite neat. To be honest I was wondering whether there are certain classes of auctions where one can build and traverse these graphs fast enough so that we don’t have to learn from samples, but this is certainly not required for me to think positively about this paper.\n\nWeaknesses. \nKnowing p (or the distribution D) is restrictive. Do the current results hold even if you know p approximately? This would mean that there is a distribution D’ that is known with small distance from D. Such a result would strengthen the punchline of the paper even more. \n\nEvaluation.\nIn my opinion, the weakness that I pointed out above was not as important as the strengths of the paper. Moreover, they mostly constitute interesting directions for future work. For that, I’m leaning positive for the paper.\n\nAdditional Comments. \n* I understand that the assumption on the existence of independence in choosing the subset is done for technical reasons and I think it is okay given that this is one of the first studies of market shrinkage. But in reality shouldn’t we expect that there is some correlation between people who decide to leave the market? That is at least the case in all the examples mentioned in the introduction where there was an outside “force” pushing people out of the market.\n* In lines 56-61: I would suggest adding a short description of what delineability is.\n* In the first paragraph of Section 3, when describing v_j(b), would you mind explaining why this is correlated with i? And what is i in this case fixed to? \n* After Def 5 I would suggest adding a short paragraph about what d, h, and \\theta are for certain well-known examples, like the second price auction.\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": "0OREJsG0wzd", "reviewer": "Reviewer_2dG7", "summary": "This paper studies revenue guarantees for multi-item auctions under shrinking markets, where the participation of bidders in auctions are independent and random. The paper first presents a motivating example for VCG auctions that demonstrate only an exponentially small fraction of revenue can be guaranteed under shrinking markets when bidders’ values also depend on what others receive. The paper then develops a probabilistic argument to show for a sufficiently large class of mechanisms, there must exist a mechanism that is robust to market shrinkage, and preserves a certain level of revenue. Finally, the paper presents a sample based approach to find a mechanism that yields revenue at least the presented guarantee on revenue with high probability. \n", "questions": "See above in strengths and weaknesses.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well-written, and to the best of my knowledge, the probabilistic existence result for mechanisms that achieve certain revenue guarantees (along with the construction and analyses of the “winner diagram”) under shrinking markets is novel, and provides quite substantial contribution to the understanding of auction revenue in this particular market scenario. I find the motivating example in Section 3 that states in certain scenarios VCG can only retain an exponentially small fraction of revenue quite enlightening, and I appreciate the exemplifying numerics for revenue loss presented after Theorem 3.1. Despite being a theoretical paper, I feel the paper presents nice insights into challenges for auction design and revenue maximization in practice.  \n\nWeaknesses:\nI do not see major weaknesses in the paper. Perhaps one question/concern I have for the overall methodology of mechanism $\\mathcal{A}$ and the sample based approach to find a particular mechanism with good revenue guarantees, is that both rely on the knowledge of $p$  which is the probability that a bidder participates in an auction. If there is misspecification in this parameter (especially over estimations), it seems that certain mechanism equivalence classes may be ruled out which in the worst case may be those who correspond to the highest revenues. If this is true, is there any intuition regarding how sensitive are the revenue guarantees to misspecification of $p$? I may be missing something here, and would be great if the authors can clarify.\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": {}}]

Author rebuttal:

Decision: Accept