Mechanism Design via the Interim Relaxation
Authors: Kshipra Bhawalkar
Marios Mertzanidis
Divyarthi Mohan
Alexandros Psomas
Venue: NeurIPS 2025 poster ()
Keywords: mechanism design
auctions
OCRS
CRS
revenue maximization
Bernoulli factories
Primary area: theory

Abstract: We study revenue maximization for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. In seminal work,~\citet{alaei2014bayesian} introduced a powerful multi-to-single agent reduction based on an ex-ante relaxation of the multi-agent problem. This reduction employs a rounding procedure which is an online contention resolution scheme (OCRS) in disguise, a now widely-used method for rounding fractional solutions in online Bayesian and stochastic optimization problems. In this paper, we leverage our vantage point, 10 years after the work of Alaei, with a rich OCRS toolkit and modern approaches to analyzing multi-agent mechanisms; we introduce a general framework for designing non-sequential and sequential multi-agent, revenue-maximizing mechanisms, capturing a wide variety of problems Alaei's framework could not address. Our framework uses an \emph{interim} relaxation, that is rounded to a feasible mechanism using what we call a two-level OCRS, which allows for some structured dependence between the activation of its input elements. For a wide family of constraints, we can construct such schemes using existing OCRSs as a black box; for other constraints, such as knapsack, we construct such schemes from scratch. We demonstrate numerous applications of our framework, including a sequential mechanism that guarantees a $\frac{2e}{e-1} \approx 3.16$ approximation to the optimal revenue for the case of additive agents subject to matroid feasibility constraints. Finally, we show how our framework can be easily extended to multi-parameter procurement auctions, where we provide an OCRS for Stochastic Knapsack that might be of independent interest.

Mechanism Design via the Interim Relaxation
Kshipra Bhawalkar Google Research kshipra@google. com
Marios Mertzanidis Purdue University meertzan@uurdue edu
Divyarthi Mohan Tel Aviv University divyarthim@tan. ac ac.il
Alexandros Psomas Purdue University apsomas@cs purdue edu
Abstract
We study revenue maximization for agents with additive preferences, subject downward-closee constraints on the set of feasible allocations. seminal work, Alaci [Ala14] introduced powerful multi-to-single agent reduction based on ex-ante relaxation of the multi-agent problem. This reduction employs a rounding procedure which is online contention resolution scheme (OCRS) in disguise, now widely-used method for rounding fractional solutions in online Bayesian and stochastic optimization problems. In this paper, leverage years after the work of Alaei, with rich OCRS toolkit and modern approaches to analyzing multi-agent mechanisms; ing non-sequential and sequential multi-agent, revenue-maxinine capturing a wide variety of problems Alaci's framework could not address. Our framework uses an interim relaxation, that is rounded to a feasible mechanism using what we call two-level OCRS, which allows for some structured dependence between the activation of its input elements. For wide family of constraints, we can construct such schemes using existing OCRSs as black box; for other constraints, such as knapsack, we construct such schemes from scratch. We demon- strate numerous applications of our framework, including a sequential mechanism that guarantees e-I 3.16 approximation to the optimal revenue for the case of additive agents subject to matroid fcasibility constraints. The simplicity of our developed two-level CRSs and OCRSs highlights the strength of our framework: even with simple analysis, it yields state-of-the-ar approximation guarantees across a wide range of settings. Finally, we show how naturally extends multi-paran parameter procurement auctions.
vantage point, 10
introduce general framework for design-
mechanisms,
2c
Introduction
We consider the problem of revenue- maximiiii seller with heterogeneous items for sale to n strategic agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. Revenue maximization for multi-agent environments is a central problem in Computer Science and Economics. Beyond Myerson's 's [Mye81] single-item mechanism, char- acterizing the revenue optimal mechanism in multi-item settings is notoriously hard problem. Revenue-optimal mechanisms are hard to compute even in basic settings, and exhibit various counter- intuitive properties [MV07, DDT13, DDT15, BCKW 15, HR15, Das HN19, PSCW22]. An active research area strives to understand optimal and approximately optimal mechanisms from various perspectives, e.g., their computational complexity (CDW124 CDWI3a. CDW12b. CDW13b), sam- ple complexity [CR14 14, 1MR15, DHP16, MR16, CD17, GHZ19, GW21], robustness [BS11, CD17, DK19, LLY19, PSW19, BCD20, MMPT24), and the tradeoffs between simplicity and optimal-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

ity [CHK07, CHMS10, CMS15, Yao15, RW15, CM16, CZ17, KW19, CDW19, BILW20, BGN17, KMS* 19].
Influential work by Alaei [Ala14] provides a framework for constructing multi-agent mechanisms with ex-post supply constraints via reduction to single-agent mechanism design with ex-ante supply constraints. On a high level, Alaei's framework first finds a feasible in expectation ex-ante allocation rule: a vector x E [0, 1 where zi,j is the probability of allocating item j to agent i, over the randomness in the mechanism and all agents' valuations. Given this ex-ante relaxation, the framework needs a single agent mechanism for each agent i, such that item j is allocated to agent i with probability at most 24,-- Alaci shows that running such single-agen mechanisms independently can be combined with a rounding procedure (in order to satisfy the supply constraints ex- ex-post) to give an overall approximately optimal multi- agent mechanism. This rounding step. Alaei's 's solution to his "magician's 's problem," " an online contention resolution scheme (henceforth, OCRS), in disguise. OCRSs, later defined by Feldman et al. [FSZ21], ]. are a widely applicable tool for rounding fractional solutions in Bayesian and stochastic online optimization problems.
In this paper, we leverage our vantage point, 10 years after the work of Alaei Ala14], with a rich OCRS toolkit and modern approaches analyzing multi-agent mechanisms, to introduce novel, general framework for designing both non-sequential and sequential multi-agent, revenue-maximizing nownward-closed constraints on the
mechanisms for agents with additive preferences, subject set of feasible allocations. Our framework uses an interim relaxation, that is rounded to feasible mechanism, using what we call two-level OCRS, allowing for some structured dependence between the activation of its input elements. For a wide family of constraints, we can construct such schemes using OCRSs as a black box; for other constraints, e.g., knapsack, we construct such schemes from scratch. We demonstrate numerous applications of our framework, including a sequential mechanism that guarantees a e-1 23 3.16 approximation to the optimal revenue for the case of additive agents subject to matroid feasibility constraints. We also show how our framework can be easily extended to multi-parameter parameter procurement auctions, where we provide an OCRS for Stochastic Knapsack that might be of independent interest.
2e
1.1 Our Contributions
Our framework relies on an interim relaxation. Intuitively, an interim form (or reduced form) of a mechanism .M has variables Th (2)), which indicate the probability that agent i receives item j when reporting valuation U, to M (over the randomness in M, as well as the randomness in other agents' valuations), and variables qf (v:). which indicate the expected payment of agent i when reporting valuation U; to M (over the same randomness). Writing a linear program that optimizes revenue over the space of all feasible interim rules has proven to be useful endeavor when computing optimal and approximately optimal mechanisms [CDW NeW11a, 12a, CDW 13a, CDW121 12b, CDW13b], as well as for deriving upper bounds (via duality) to the revenue optimal mechanism [CDW19] While the number of variables in this program (corresponding to interim rules) is polynomial, the number of constraints needed to ensure that an interim rule is feasible (i.e., that there exists a mechanism M that induces it) is typically exponential (even for, e.g., the simple case of selling a single item to n agents). Our starting point is consider a relaxation of these feasibility constraints, resulting interim rules that are feasible in expectation.
Given (optimal or approximately optimal) interim rules that are feasible in expectation the first natural step for rounding to an actual mechanism is to use a CRS/OCRS. Contention resolution tool for rounding fractional solutions
schemes, or CRSs, were defined by Chekuri et al. [CVZ14] in (submodular) optimization problems. In this framework, there is a finite ground set of elements N (ei,...,,ss ). downward-closed family F of subsets of N, and fractionally feasible point r E [0, 1| The main idea is to obtain (possibly infeasible) random set R(x*) from x², by treating x as a product distribution: element i is included in R(x*) with probability x; Given R(=*), a c-sclectable CRS selects set / C R(x*) that is feasible (i.e., 1 E F), in way that each element is selected with probability at least e it is in R(x*). A refined definition, (b, -elsetect CRSs, for b E [0. 1). extends the concept of c-selectable CRSs (which are simply (1, seleettabll and provides the same guarantee per element when given as input a set R(bx*). Feldman et al. [FSZ21] extended this framework to online settings and defined OCRSs.
Back to our problem, a first blueprint for a mechanism, given interim rules that are feasible in expectation, would be to elicit reports ri,..., Tn from the agents, and then construct set of active
2

---

Plugging the aforementioned ICRSs/IOCRSs into our framework gives numerous interesting applications. As first application, consider the problem of auctioning off m items to agents with additive preferences, such that the set of agents that each item j is allocated to must be an independent set of matroid, and the items allocated to each agent must be independent set of a matroid. Our results give a sequential, BIC and BIR mechanism that guarantees a e-1 Rs 3.16 elements (the input to the CRS/OCRS) according to Ti.r(Ta), for every agent i and item j. A technical complication is that CRSs/OCRSs receive input elements that become active independently. In our blueprint, the event that element "(i, J, r3)" becomes active is correlated with the event that element "(i.j',ra rz)"" becomes active. To bypass this obstacle, we define variants of CRSs and OCRSs which we call two-level contention resolution schemes, or iCRS, and two-level online contention resolution schemes, or tOCRS. Intuitively, a (CRS/LORS receives an n by m matrix of elements, such that elements in the same row are independent, conditioned on the value of row-specific random variable (and these row-specific random variables are independent).
Our framework. Informally, our overall framework takes as input feasible in expectation interim rules and a iCRS/OCRS and outputs a mechanism; for the case of tOCRS the mechanism sequential. i..., it sequentially approaches each agent i, elicits a report ri and decides on the outcome of agent i (her allocation and payment) before proceeding to the next agent. We require that valuations are independent across agents, but the value of agent for item j can be correlated with her value for item j'. Our mechanisms are Bayesian incentive compatible (BIC) and Bayesian individually rational (BIR). Given an approximately optimal interim form, and (b, -e-settcebble (CRS/OCRS, our mechanism is be approximately optimal (Theorem 1). See Figure 1.
LP (Interim Relaxation
Division Bernoulli Factory
17
R
Xi.PP
tCRS/tOCRS
Framework
z
Figure 1: Given an interim form (T, 9) our framework (sequentially in the case of tOCRSs) elicits agents' valuations. Given the report 0ú of agent i, executes the iCRS/OCRS on a set of active elements R, and returns a set Z. The allocation of is constructed from Z; when given only black-box access to the ICRS/OCRS this construction can done efficiently via a division Bernoulli factory.
Towards constructing (CRSs/OORRs,, we first give a general reduction for constructing ICRS/OCRS, that uses CRSs/OCRS as black-box (Theorem 2). Informally, if CRSs/OCRSs for certain feasibility sets Fi..... F& exist, can provide iCRS/OCRS for certain combinations of the Fjs. Combining with known CRS/OCRS results we get iCRSs/tORRSs for various settings of interest. Next, we give 1/ 1/10-selectable 1OCRS for Knapsack constraints and 1 1/9-selectable tOCRS for Multi-Choice Knapsack constraints (Theorems 3 and 4). Notably, our tOCRS for knapsack implies a 1/10-selectable OCRS for knapsack, which is better than the 0.0e5-selectable OCRS given by Feldman et al. [FS221], but not as good as the state-of-the-art 1/(3 + e ( sellectbbee (es 0.319-selectable) OCRS of Jiang al. [JM722]]
Applications.
'2e
approximation to the optimal revenue (Application 1). The previously best-known approximation possible by sequential mechanism was 70 (for the special case where every item can be allocated at most once, and where items' values are independent), due to Cai and Zhao [CZ17], whose mechanism has additional desirable simplicity properties (that we do not guarantee here, and are in fact impossible to guarantee for correlated items 115K HN19]). Beyond its simplicity, their mechanism applies to broader class of valuation functions.
As a next application, consider the problem of auctioning off m items to a agents with additive preferences, where each item [m] has some weight ky and the total weight of items sold cannot exceed K. Our results imply that there exists an efficiently computable, sequential, BIC and BIR mechanism that guarantees 10 approximation to the optimal revenue. Additionally, if each agent i
3

---

can get at most one item, there exists an efficiently computable, sequential, BIC and BIR mechanism that guarantees a 9 approximation to the optimal revenue (Application 2). Finally, consider the problem of auctioning off m items to agents with arbitrary valuation functions, where each item j E [m]] has some weight k- and the total weight of items sold cannot exceed K. Then, our results imply that there exists (computationally inefficient) sequential, BIC and BIR mechanism that guarantees a 9 approximation to the optimal revenue (Application 3).
Extensions. Our framework can be easily extended to other mechanism design problems, beyond auctioning off items to agents. In Appendix we give an extension to procurement auctions, where a value- maximizini buyer is interested in buying services from strategic sellers, subject to a budget constraint. In this case, we show how, given an OCRS for Stochastic Knapsack (see Appendix F for definitions) it is possible to design an approximately optimal sequential multi parameter procurement auction. Combining with a result of Jiang et al. [JM7.22]. we then have a (3 + e-2) -ap--pproximmatlll optimal sequential procurement auction (Application 4). As an aside, we also give an OCRS for the stochastic knapsack setting that might be of independent interest (Theorem 6). Feldman et al. [FSZ21] give a greedy and monotone' (3/2 v2) seleecabe OCRS (= 0.0838) for Knapsack, while Jiang et al. [JMZ22] give -+c- - selectable OCRS (>< 0.319) for Stochastic Knapsack (this OCRS induces a grondgr and non-monotone OCRS for Knapsack). We give c-selectable OCRS for Stochastic Knapsack (that induces a greedy and monotone OCRS for Knapsack), where c = m 1/6), and ks is a parameter that depends on the maximum possible weight (in the support of the distributions from which the stochastic weights are drawn); our OCRS is therefore always better than the OCRS of Feldman et. al., and better than the OCRS of Jiang et, al. when k* is small.
2 Preliminaries
We consider the problem of a seller with indivisible, heterogeneous items for sale to strategic agents. Each agent has a private valuation vector i; that is drawn independently from an m- dimensional distribution D. (that is known to the seller). We write V. supp(D;) for the set of possible valuations for agent i. Agent has a value Ug for item j. We write Dr,, for the marginal distribution for item j, noting that Dr, is not necessarily independent of Dayy- We assume that agents have additive preferences, ie.. the value of agent with valuation e; for a subset of items S S [m]] is Ejes Vi.j- Agents are quasi-linear: the utility of agent is her value minus her payment. An (integral) allocation x E {0, 1 indicates which item was received by which agent, i..., æij E =00, } is the indicator for whether agent i received item j. There are constraints on the set of feasible allocations represented by a set F S {0, 13mmm, that is, an allocation x feasible if E F (therefore, one can equivalently think of the agents as constrained additive). Let Py be the convex hull of all characteristic vectors of F, i.e. Py conv(1r E F}. We write P for the polytope that corresponds to agent i, i.e., the polytope P5 when we only consider the m dimensions that correspond to the allocation of agent i.
2.1 Mechanism Design Preliminaries
A mechanism M takes as input a reported valuation from each agent and selects a (possibly random) allocation in F, and payments to charge the agents. An agent's objective is to maximize her expected utility. A mechanism M is Bayesian Incentive Compatible (BIC) if every agent E [n] maximizes her expected utility by reporting her true valuation v. assuming other agents do so as well, where this expectation is over the randomness of other agents' valuations, as well as the randomness of the mechanism. A mechanism is Bayesian Individually Rational (BIR) if every agent E [r]] has non-negative expected utility when reporting her true valuation (assuming other agents do so as well). The (expected) revenue of BIC mechanism is the expected sum of payments made when agents draw their valuations from D (and report their true valuations to the mechanism). We say that a mechanism is BIC-IR if it is both BIC and BIR.
'An OCRS is greedy if it fixes downward-closed family of feasible sets before the (online) process starts, and greedily accepts any active element e that will not violate feasibility if included. An OCRS μ is monotone for all e E A C B, the probability that μ selects e when A is the set of active elements is at most the probability that selects when B is the set of active elements. These properties are important for applications in submodular optimization [CVZ14].

---

The optimal mechanism for given distribution D, whose revenue is denoted by Rev(D), maximizes expected revenue over all BIC-IR mechanisms. For a given mechanism M, we slightly abuse notation and write Rev (D) to denote its revenue under a distribution 'D. mechanism guarantees an a approximation to the optimal revenue if Rev (D) 2 Rev(D), Finally, we say that a mechanism is sequential if it sequentially approaches agent i, elicits a report r;, and allocates items to i before proceeding to the next agent.
Interim allocations and payments. The interim allocation of a mechanism M, n-M, indicates, for M. (r:) that agent i receives item j when she reports valuation (over the randomness in M and the randomness in other agents' reported valuations V-i, drawn from D_;). The interim paymen! of agent i, (r:), is the expected payment she makes when she reports valuation ri (again, over the randomness in M and the randomness in other agents' reported valuations). It is easy to see that the expected utility of agent i with valuation v when reporting r; to mechanism M, is [m T (r.)) (ra) (M (rx). We will drop the superseript M when the mechanism is clear from the context.
each agent and item j the probability Ti
Given interim allocations and payments, it is not straightforward task determine whether they are ex- ex-post feasible, i.e., whether there exists a mechanism M that induces the exact probabilities promised by the interim allocations. In fact, doing this task efficiently is at the core of the frame- work of Cai et al. [CDW122 12a, CDW13a 13a, CDW12b, CDW13b for computing approximately optimal mechanisms. However, is typically straightforward to find interim allocations that are feasible in expectation.
Definition (Feasibility in expectation). An interim allocation rule n is feasible in expectation (i) Vi [m], vy E V4, (1, E Pj. and (ii) Ev,,, Pr[vs] (e.((t))(
E Ps.
We say that an interim allocation, payment pair (T, g) is BIC Vi E [n], vi, of E V; it holds that ue (v)) - (v()))
Σ SELm]
( - qi(v)) N
Σ jE(m]
An interim allocation, payment pair (T,, q) is BIR Vi [m]. n/ E V. Eje(mn Ve. (i)(()))))))))) (v(s)) 2 An interim allocation, payment pair (M, q) is BIC-IR if it is both BIC and BIR. Finally, an interim allocation, payment pair (),9) guarantees an a-approximation to the optimal revenue if
[Ee(n)) Σ,,y,, Pr[es] q(v))) 2 Rev(D).
2.2 OCRS and tOCRS Preliminaries
Consider finite ground set N {ei. ) and a family of feasible subsets F 2 Let Py = cone [1 I E F}) be the convex hull of all characteristic vectors of feasible sets. Let x E Pz. and let R(xx) C N be a random set obtained by including each element i N independently with probability z4. The set R(x) is feasible in expectation (with respect to F) but not necessarily ex-post feasible. Given R(x), a contention resolution scheme (CRS) selects a subset S R(x) such that I F. If elements of R(x) are given in an online manner, the corresponding scheme is called an online contention resolution scheme (OCRS). To avoid trivial solutions (e.g.. I 0). we would additionally like to have the property that each element i E N appears in I with probability at least cr, for some c. We call such schemes c-selectable. Some schemes only work if elements come from R(bx); such schemes are called (b, -ssslectabe Formally:
Definition 2 (Online Contention Resolution Scheme(OCRS) (FS721J). Let e E [0, 1). For every Py. let R(br) be random subset of active elements, where element E N is active with probability b si, independently. A (b, c)-selectable Online Contention Resolution scheme (OCRS) for Ps is a (possibly randomized) online procedure that, given active elements one by one, decides whether to select an active element irrevocably before the next element is revealed. The OCRS returns a set 1 C R(bx), x)), such that (i) F, and (ii) Pr E 1li E R(bx)] 2 c, vi N.
We introduce a variant of the previous OCRS model that allows for dependencies between the activation of different elements. This slightly changes the setup, as well as the definition of "scheme." Consider the ground set N = fea, hej)).jmm) where |N| = n m, and a family of feasible subsets F S 2N. Let Py= conv((1, e FF) be the convex hull of all characteristic vectors
5

---

of feasible sets. Let Ps be the restriction of Ps to the m dimensions that correspond to elements (i.j). j E [m]. Elements will become active certain, dependent way, as induced by a hwo-level stochastic process (D.z), defined as follows:
Definition 3 (Two-Level stochastic process). We say that (D,x) is a two-level stochastic process over {0, 1jmm, m, where D D is a product distribution and a E 1 IV.,, if it is induced by the following procedure: (i) we first sample di from Da independently, and for each (i.5) E [n] x [m], element Ei,j becomes active with probability (di), independently.
For the case of OCRSs, since elements became active independently, (expected) feasibility for product distribution x boiled down to x being fractionally feasible for F, i.e. x Py. Here, since elements are active in a dependent way, our notion of feasibility needs to be further refined:
Definition 4 (Feasibility). Let F S 2/n]x(mm) [m]] be a feasibility set and Py be its relaxation. We say that a two-level stochastic process (D, x)) is feasible with respect to F if:
1. For each E [m] and each d, E supp(D;), (I.,1 ... mm (4)) ()))EP Pj-
2. w E Py,, where wa,5 = Esppppp)D..) Pr (D, = di] x..s(:;)
Let (D,z) be a two-level stochastic process that is feasible with respect to F, and let R(D,,) S N be random set of elements obtained by sampling from (D, Our goal is select subset I C R(D,a æ²) (possibly online) such that / E F and the probability that an active element is selected lower bounded by constant c. Formally, our definitions of two-level Online Contention Resolution Schemes (IOCRSs) is as follows.
Definition 5 (Two-level OCRS (IOCRS)). Let b E [0, 1]. Let (D, x)) be two-level stochastic process that is feasible with respect to F, and let R(D, bx) S N be random set of elements obtained by sampling from (D.bx). Elements of R(D, bx), and the corresponding samples from the first level of ID,z), appear online, in batches of size m. the process selects some i E [n] and reveals di (sampled from Di) and all elements (i.m))mmm) before selecting a new E [m]. A (b, c) -eseeccceb two-level OCRS (1OCRS) for F is a (possibly randomized) online procedure that, given active elements that satisfy the aforementioned ordering, decides whether to select an active element irrevocably before the next element is revealed, ie., returns a set I C R(D,ba brr), such that (i)
I E F, and (ii) Pr li E Tli E R(D,ba) 2 c. E N.
The existence of (b, -eslecttbe tOCRS implies the existence of (b, selecttabe OCRS, by a simple simulation argument (for m = 1).
Due to space constraints, preliminaries CRSs and (CRSs are deferred to Appendix B.1, and preliminaries on Bernoulli factories are deferred to Appendix B.2.
3 Mechanisms from two-level OCRSs
We give two frameworks for constructing mechanisms. Due to space limitations the framework for ICRSs can be found in Appendix C. The input to a framework is (i) a BIC-IR interim allocation, payment rule pair (x, that is feasible in expectation and is an approximation to the optimal revenue, (ii) a (b, c)-selectable tCRSAOCRS for F, and (iii) a parameter e 2 O. Our frameworks produce BIC-IR, (c-e) approximately optimal (and sequential, for tOCRSs) mechanisms for agents with constrained (with respect to F) additive valuations.
Given a tOCRS, our framework, Algorithm 1, works as follows. We approach each agent i sequentially. Agent reports r² E V; and pays (c - <) (:(r.)) ). We consider each item sequentially. We make element (I. active with probability b Tr,(("") and then ask the tOCRS if this element should be selected (assuming it was active). If the tOCRS selects the element (i.j), we again flip an additional coin to decide whether agent i should get item j. This last coin essentially balances the randomness of the tOCRS and ensures that the probability that agent i gets item j when they report r is exactly b(c ),.),((?), which, combined with the chosen payment, ensures that BIC and BIR are satisfied. Theorem Given (i) BIC-IR interim allocation, payment rule pair (T, 9) that is feasible in expectation and is an a 2 1 approximation to the optimal revenue (ii) a (b, seleectaab tOCRS (resp. (CRS) for F, and (üii) parameter 6 2 0, Algorithm 3 and Algorithm 1 give BIC-IR, [(-ee approximaaely optimal (and sequential for the case of Algorithu 1) mechanisms for F.

---

ALGORITHM I: Our framework for (OCRSs
Input: allocation, payment rule pair (x, q). (b, c) selectable (OCRS 14, parameter
for each agent E [n]] do Agent reports r
and pays (c (r?).. for each item E [m]] do
R - 1 with probability b ma. (r.)-
7..j μo{ (.....)))) // 74, S Ri.j indicates if the tOCRS selects element (i,j)
when active
Z., =
ccc Allocate item j to agent with probability (r)) where (rf) is the probability that selects (i.j) conditioned on report rī and Ra, being equal to 1.
end
end
end
we only have query access the iCRS/OCRS, our mechanisms can be implemented using (ppoly(E; [Vll, m, {)) number of queries in expectation.
The proof is deferred Appendix D.
3.1 Implementation Considerations
Here, we highlight some implementation details for our framework. First, we give a simple LP that computes optimal (a 1). feasible expectation, BIC-IR interim allocation and payment rules (π, g). Second, we flesh out implementation details of Line 3 of Algorithm and Line of Algorithm 1, flipping coin with probability (c c)ppt,((1) when given only black-box access to a iCRS/OCRS. This not a straightforward task, since p.. (u;) might be unknown, and approximating this probability (e.g., via sampling), instead of computing it exactly, results in violation of the BIC constraint.
Finding feasible in expectation, optimal interim rules. The following linear program, (LP1)
computes an interim relaxation of the revenue-optimal BIC-IR mechanism.
maximize
Σ
Σ
Pr(vila(ve))
EE/m mEV.
s.t.
Σjeim) Ti (:())) 2 Eyemm) (1) (x())
vi [m], 2 of V.
Ejem
Ci Ti (v()) 20
Wie (n), E V
T((1)) E Pj
Vi E [n], E V.
Eneev, Pr[us] Tis (en E Pr
(LP1)
This linear program has O(m Eiejn Vil) variables and O(Ee())) (4 constraints, excluding the constraints necessary to represent P and Ps. Therefore, the overall computational complexity of solving this LP depends on whether Py and P have an efficient representation.
We note that, in series of papers, Cai et al. [CDW12a, CDW13a, CDW12b, CDW13b) propose similar linear program for finding approximately optimal mechanisms. The variables their are the same: the interim allocations and payments. In their framework, however, finding interim allocation rules that can be induced by ex-po ex-post feasible allocation rules is crucial. To do so, their constraints, even for simple feasibility sets, are exponential; see Border [Bor07]. To solve their LP efficiently they show how to construct (efficient) separation oracles. Once interim allocation and
For single item settings, [AFH* 19] gave polynomial-sine sized LP describing Border's inequalities. For general matroids, such succinct representation not possible [GNR18].
7

---

payment rules are found, they use complicated techniques - techniques that are not amenable to online arrivals of agents exactly the same variables, only needs to ensure feasibility in expectation. For many settings of interest, our LP has a polynomial-size description, and thus can be solved by any LPP solver, making our approach more convenient in practice. Furthermore, our techniques are designed to accommodate for online arrivals agents.
construct final mechanism. In contrast, our LP, even though it uses
Flipping coin with probability (v.). To implement Line 3 of Algorithm 3 and Line of Algo- rithm 1 we can use Bernoulli factory for division, which, given (c e)-coin and a Pī, (2))(()))ooo) (oo)- exactly, the (c e)-coin can be implemented trivially. One can implement Pī. (r:))ri)ciin as follows: For each i' o sample fy ~ Diy and let R + 1 with probability b m ( Also let Ra, with probability b (1)). Querying the ICRS/OCRS on the active set R returns set of selected elements; output Zi.5 as the coin flip for the pi, (v: -coin.
outputs Pi.g (mc)* We know
Constructing tCRS and tOCRS
In this section, construct tCRSs and tOCRSs for various feasibility constraints; missing proofs are deferred to Appendix E. First, we prove that for a general family of constraints we call Vertical- Horizontal (VH) constraints, it is possible to construct tOCRSs (resp. (CRSs) given OCRSs (resp. CRSs) in a black-box manner.
Pertical-Horizonte (VH) constraint with respect to ground set N = ((i)))i(m))jE(m)) if there exist sets of constraints (Fi)keln). (F) ())mm))))))) such that E if (i) vi E [n], I I5Em) E Fe (ii) Vj E [m], I (eishem E FF.
Definition 6 (VH Constraints). We call
Theorem Given (b, c)-selcctable CRSs (resp. OCRSs) for constraints {Filie(m) and (b, d')- selectable CRSs (resp. OCRSs) for constraints {F²) J5emm there exists a (b, e. sselectabee ICRS (resp. 1OCRS) for the induced
constraint F.
By combining Theorem with known results (e.g., [HKS07, LS18, KS23J) we can get tCRSs and 1OCRSs for various settings of interest; show these applications in Theorem in Section 5,
Next, we construct 1OCRSs for knapsack constraints.
Definition 7 (Knapsack Constraints). Consider ground set of elements N (ei))ie(m)jjEmm) where, for each i, [n] x [m], element ei, has weight ka.j. and there is maximum weight K. We say that FF is a Knapsack constraint when 1 E FF if and only if C N, and ((-j)oo Kiss S K.
Definition 8 (Multi-Cu Choiie Knapsack). Consider ground set of elements N {er, he(m))ielm) where, for each i, [m]] x (ml, element eij has weight hi and there is a maximum weight K. We say that is a Multi-Choic Knapsack constraint when E F if and only if T S N, Co.ivers Kig S K, and, for all E [n)). n fess 1.
The following theorem gives a (b, 1 --electabbee tOCRS for Knapsack Constraints, for b E [o, 1]. 248h
Interestingly, since tOCRSs are OCRSs, our result implies (1, 0. 1.0.11) -seeecbceee OCRS for knapsack; this better than the (1, (0.085)-selectaal good as the state-of-the-art (1, 1/(3 + -seeleccte (Rs (1, selecceelll OCRS of Jiang et al. [JMZ22].
OCRS given by Feldman et al. [FSZ21]. but not as
Theorem 3. For all b [0, 1], there exists (b, 24 2455 sellettabe 1OCRS for Knapsack.
Next, we give a (b, 2+76 sellectable tOCRS for Multi-Choice constraints, for all b E [o, 1]. The proof of the following theorem is deferred to Appendix E.
Theorem 4. For all b [0, 1). there exists a (b, 2 selectabllee 1OCRS for Multi-Choice Knapsack.
4.1 Efficient Implementation Considerations
Theorem 3 and Theorem 4 show that "Knapsack" and "Multi-Choice Knapsack" tOCRSs exist, Both 1OCRSs have non- constructive coin-flippig steps (e.g., selecting an active light element with probability (1446) (d..] where (c, is the event that, at the time step when element ex is
8

---

considered, the total weight of elements in I so far is strictly less than K/2, when d, was sampled from the two-level stochastic process (D, bz)). The following propositions show how to efficiently implement these steps, albeit with small loss in the performance guarantee.
selectable tOCRS for Knapsack in time Proposition 1. We can implement a (b, 2-56 ( (1 poly(1/e² log(1/6), m.n). n).
1-4 Proposition 2. We can implement a 2476 in time (oly(1/e,, /log///////////////// (1)))))),0 m. m)
sslectable 1OCRS for Multi-Choice Knapsack
118c
5 Applications
In this section, we combine results from Sections and 4 to get mechanisms for various problems.
2e_ First, our framework can give a sequential mechanism with a e-I (= 3.16) approximation guarantee for the problem of auctioning off m items n agents with additive preferences, under "matroid Vertical-Horizontal constraints F: (i) the set of agents that each item j is allocated to must form a matroid, and (ii) the set of items allocated to each agent must form a matroid. Observe that, F is a VH constraint (Definition 6), induced by the aforementioned constraints (i) and (ii). Both (i) and (ii) are matroid constraints, [CVZ14] give a (1, - 1 -selectable CRS and [LS18] give a (1, 1/2) -eelecccae OCRS for matroid constraints. Therefore, Theorem 2 (where use the CRS for the constraints over items and the OCRS for the constraints over agents) implies a (1, e-1 selectable 1OCRS for F:
2e
Corollary 1 (Theorem and [LSS1]]. There exists (1, - )-selectable 1OCRS for matroid Vertical- Horizontal constraints.
Corollary and Theorem readily give the following result.
Application 1 (Corollary and Theorem 1). Consider the problem of auutiooing off m items agents with additive preferences, such that the set of agents that each item j is allocated to must form a matroid, and the items allocated to each agent must form matroid. There exists sequential, 2e BIC-IR mechanism that guarantees c (=z 3.16) approximation to the optimal revenue.
Notably, the previously best-known approximation guarantee for a sequential mechanism for even special case of this problem (agents with preferences that are constrained additive with a matroid constraint, and each item can be allocated most one agent) was 70 [CZ17].
CRSs and OCRSs with approximation factors better than (i.e. better than the result of [LS18] for general matroids) are possible for some special cases. E.g., for k-uniform matroids, [HKS07]
give a 1 1-0 (1-0(V log
-selectable OCRS, and [KS23] give a (1, -x)
A m &
k K
selectable CRS, where n is the number of elements (for a fixed k; this approaches Combining with Theorem we can get tOCRSsACRS$ for these cases, and applying Theorem gives an overall (sequential for tOCRSs) mechanism with slightly improved guarantee.
(1,
k
We note that, depending on the choice of matroids, (LP1) might not be efficiently computable. For example, the representation of P= might require an exponential (in n, m and >xe(n) (Vi)) number of inequalities; in such cases, our approach does not give an end-to-en efficient procedure for finding mechanism. However, if one is given feasible in expectation, BIC-IR and approximately optimal interim rules, all remaining steps of our framework can be efficiently computed.
Finally, we combine Theorem with our tOCRSs for Knapsack and Multi-Choice Knapsack.
Application 2 (Theorem 3, Theorem 4, and Theorem 1). Consider the problem of auctioning off m items to agents with additive preferences, where each item [m] has some weight k; and the total weight of items sold cannot exceed K. There exists an efficiently computable, sequential, BIC-IR mechanism that guarantees a 10 approximation to the optimal revenue. Additionally, if each agent i can get at most one item, there exists an efficiently computable, sequential, BIC-IR mechanism that guarantees 9 approximation to the optimal revenue.

---

Recently, [ABM* 22] gave simple and approximately optimal, with respect to welfare. mechanism for the Rich-Ads problem. Application 2 readily gives a sequential, approximately optimal, with respect to revenue, mechanism for the same problem.
Finally, by creating meta-item for each possible subset of items (where the weight of the meta-item is simply the sum of weights from the corresponding subset), our approach gives an approximately optimal, sequential, BIC-IR mechanism for arbitrary valuation functions (subject knapsack constraint). For logarithmic (in n) number of items, this approach gives a computationally efficient procedure as well (but, of course, this is not true general).
Application 3 (Theorem 4 and Theorem 1). Consider the problem of auctioning off m items agents with arbitrary valuation functions, where each item E [m]] has some weight k, and the total weight of items sold cannot exceed K. There exists a sequential, BIC-IR mechanism that guarantees a 9 approximation to the optimal revenue.
Acknowledgments
Marios Mertzanidis and Alexandros Psomas are supported in part by an NSF CAREER award CCF-2144208, and research award from the Herbert Simon Family Foundation.
References
[ABM*22] Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, and Alexan- dros Psomas. Simple mechanisms for welfare maximization in rich advertising auctions. Advances in Neural Information Processing Systems, 35:28280-2888 282292, 2022.
[AFH+ 19] Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian. Effi cient computation of optimal auctions via reduced forms. Mathematcs of Operations Research, 44(3):1058
2019.
[AFHH13] Saeed Alaei, Hu Fu, Nima Haghpanah, and Jason Hartline. The simple economics of approximately optimal auctions. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 628 237-637.22 IEEE, 2013.
[AGN18] Nima Anari, Gagan Goel, and Afshin Nikzad. Budget feasible procurement auctions. Operations Reseurch, 66(3):637-652, 2018.
[Ala14] Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972, 2014.
[AW18] Marek Adamezyk and Michat Włodarczyk. Random order contention resolution schemes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 790-801. IEEE, 2018
[BCD20] Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item-independence: Learnability via robustness. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 715-761, 2020.
[BCKW15] Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. Pricing lotteries. Journal of Economic Theory, 156: 144:1444174, 2015.
[BGN17] Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan. The menu-size complexity of revenue approximation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 869-877, 2017.
[BILW20] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Mattew Weinberg. A simple and approximately optimal mechanism for an additive buyer. Journal of the ACM (JACM), 6744))4440 2020.
[Bor07] Kim C Border. Reduced form auctions revisited. Economic Theory, 31(1):167-181, 2007.
10

---

[BS11] Dirk Bergemann and Karl Schlag. Robust monopoly pricing. Journal of Economic Theory, 146(6):2527-2543, 2011.
[CCD*22] Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang, Gregory Kehne, and Rojin Rezvan. A mullti-dimensional online contention resolution scheme for revenue maximization. arXiv preprint 7rXiv:2404.14677 2024.
[CD17] Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pages 516-527. IEEE, 2017.
[CDW12a] Yang Cai, Constantinos Daskalakis, and Matthew Weinberg. An algorithmic charac- terization of multi-dimennsonnl mechanisms. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 459-478, 2012.
[CDW12b] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi- dimensional mechanism design: Reducing revenue to welfare maximization. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 130-139. IEEE, 2012.
[CDW13a] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations. Proceed- ings of the Twenty-Fourth Annual ACM-SIAN Symposium on Discrete Algorithms, pages 578-595, SIAM, 2013.
[CDW13b] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Understanding incentives: Mechanism design becomes algorithm design. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 618-627. IEEE, 2013.
[CDW19] Yang Cai, Nikhil R Devanur, and S Matthew Weinberg. A duality-based unified approach to bayesian mechanism design. SIAM Journal on Computing, 50(3): 160, 2019.
[CGLII] Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms. In Proceedings of the Seeent--Second Annual ACM-SIAM Symposium Discrete Algorithms, SODA '11, page 685, USA, 2011. Society for Industrial and Applied Mathematics.
[CHK07] Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference Electronic Commerce, EC '07, pages 243-251, New York, NY, USA, 2007. ACM.
[CHMS10] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311-320. ACM, 2010.
[CM16] Shuchi Chawla and J. Benjamin Miller. Mechanism design for subadditive agents via ante relaxation. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, page 579-596, New York, NY, USA, 2016. Association for Computing Machinery.
[CMS15] Shuchi Chawla, David Malec, and Balasubramanian Sivan. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior, 91:297-317, 2015.
[COVZ21] Yang Cai, Argyris Oikonomou, Grigoris Velegkas, and Mingfei Zhao. An efficient e-bic to bic transformation and its application to black-box reduction in revenue maximization. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1337-1356. SIAM, 2021.
[CR14] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the sixty-sixth annual ACM symposium on Theory of computing, pages 243-252, 2014.
11

---

[CRTT23]
Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos. Buy-many mecha- nisms for many unit-demand buyers. In International Conference on Web and Internet Economics, pages 21-38. Springer, 2023.
[CVZ14] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6): 1831-1879, 2014.
[CZ17] Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017, page 170-183, New York, NY, USA, 2017. Association for Computing Machinery.
[Das15] Constantinos Daskalakis. Multi-item auctions defying intuition? ACM SIGecom Exchanges, 14(1):41-75, 2015.
[DDTI3] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Mechanism design via optimal transport. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 269-286, 2013.
[DDTI5] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple-good monopolist. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 449-450, 2015.
[DHKN21] Shaddin Dughmi, Jason Hartline, Robert D Kleinberg, and Rad Niazadeh. Bernoulli factories and black-box reductions in mechanism design. Journal of the ACM (JACM), 68(2):1-30, 2021.
[DHP16] Nikhil R Devanur, Zhiyi Huang, and plexity of auctions with side information. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 426-439, 2016.
Psomas. The sample com-
[DK19] 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, EC '19, page 111-129, New York, NY, USA, 2019, Association for Computing Machinery.
[DKI.20] Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o (log log m) prophet inequality for subadditive combinatorial auctions. ACM SIGecom Exchanges, 18(2):32- 37, 2020.
[DKP23] Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. Limitations of stochastic selection with pairwise independent priors. arXiv preprint arXiv:2310.05240. 2023.
[Dug19] Shaddin Dughmi. The outer limits of contention resolution on matroids and connections to the secretary problem. arXiv preprint 1rXiv:1909.04268. 2019.
[EFGT20] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In Pro- ceedings of the 2 ACM Conference on Economics and Computation, pages 769-787, 2020.
[FSZ21] Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes with applications to bayesian selection problems. SIAM Journal on Computing. 50(2):255-308 2021.
[FT Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random order vertex arrival contention resolution schemes for matching, with applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss-
Zentrum für Informatik, 2021.
[GHKL24] Anupam Gupta, Jinqiao Hu, Gregory Kehne, and Roie Levin. Pairvise-independen contention resolution. In International Conference on Integer Programming and Combi- natorial Optimization, pages 196-209. Springer, 2024.
12

---

[GHZ19] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the S1st Annual ACM SIGACT Symposium Theory of Computing, pages 662-673, 2019.
[GJLZZ0] Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang. Optimal budget-feasible mechanisms for additive valuations. ACM Trans. Econ. Comput., 8(4), oct 2020.
[GN13] Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applica- tions. In Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013. Valparaíso, Chile, March 18- 28-20, 2013. Proceedings 16, pages 205-216. Springer, 2013.
[GNR18] Parikshit Gopalan, Noam Nisan, and Tim Roughgarden. Public projects, boolean functions, and the borders of border's theorem. ACM Transactions on Economics and Computation (TEAC), 6(3-4): 2018.
[GW21] Yannai A Gonczarowski and S Matthew Weinberg. The sample complexity of up-to-e multi-dimensional revenue maximization. Journal of the ACM (JACM), 68(3):1-28, 2021.
[HKS07] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007.
[HMR15] Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 45 45,60, 2015.
[HN19] Sergiu Hart and Noam Nisan. Selling multiple correlated goods: Revenue maximization and menu-size size complexity. Journal of Economic Theory, 183:991-1029, 2019.
[Hoe94] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426, 1994.
[HR15] Sergiu Hart and Philip Reny. Maximal revenue with multiple goods: Nonmonotonicity and other observations. Theoretical Economics, 10(3):93-9922, 2015.
[MZ22]] Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In Proceedings of the 2022 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 1221-1246. SIAM, 2022.
[KMS+ 19] Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, and S. Matthew Weinberg. Approximation schemes for a unit-demand buyer with independent items via symmetries. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Nov 2019.
[KO94] MS Keane and George L O' Brien. A bernoulli factory. ACM Transactions on Modeling and Computer Simulation (TOMACS), 4(2):213-219, 1994.
[KS22] Sophie Klumper and Guido Schäfer. Budget feasible mechanisms for procurement auctions with divisible agents. In International Symposium on Algorithmic Game Theory, pages 78-93. Springer, 2022.
[KS23] Danish Kashaev and Richard Santiago. A simple optimal contention resolution scheme for uniform matroids. Theoretical Computer Science, 940:81-96, 2023.
[KW19] Robert Kleinberg and S Matthew Weinberg. Matroid prophet inequalities and ap- plications to multi-dimennional mechanism design. Games and Economic Behavior, 113:97-115, 2019.
[LLY19] Yingkai Li, Pinyan Lu, and Haoran Ye. Revenue maximization with imprecise distribu- tion. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 1582-1590, 2019.
13

---

[LS18] Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibnin eibnii-7/eninnnnn fuer Informatik, 2018.
[MMPT24] Anuran Makur, Marios Mertzanidis, Alexandros Psomas, and Athina Terzoglou. On the robustness of mechanism design under total variation distance. Advances Neural Information Processing Systems, 36, 2024.
[MMZ24] Will Ma, Calum MacRury, and Jingwei Zhang. Online contention resolution schemes for network revenue management and combinatorial auctions. arXiv preprint arXiv:2403.05378, 2024.
[Mor21] Giulio Morina. Extending the bernoulli factory dice enterprise, January 2021.
[MR16] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory, pages 1298-1318. PMLR, 2016.
[MV07] Alejandro M Manelli and Daniel R Vincent. Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. Journal of Economic theory, 137(1):153-185, 2007.
[Mye81] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
[NPO5] Serban Nacu and Yuval Peres. Fast simulation of new coins from old. The Annals of Applied Probability, 15(1A):93-115 2005.
[NSW23] Joseph (Seffi) Naor, Aravind Srinivasan, and David Wajc. Online dependent rounding schemes. arXiv preprint arXiv:2301.08636 2023.
[PRSW22] Tristan Pollner, Mohammad Roghani, Amin Saberi, and David Wajc. Improved online contention resolution for matchings and applications to the gig economy. In Proceedings of the 23rd ACM Conference Economics and Computation, pages 321-322, 2022.
[PSCW22] Alexandros Psomas, Ariel Schvartzman Cohenca, and S Weinberg. On infinite sep- arations between simple and optimal mechanisms. Advances in Neural Information Processing Systems, 35:4818 15:4818-4822 4--829, 2022.
[PSW19] Alexandros Psomas, Ariel Schvartzman, and S Matthew Weinberg. Smoothed analysis of multi-item auctions with correlated values. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 417-418, 2019.
[QS22] Frederick Qiu and Sahil Singla. Submodular dominance and applications. arXiv preprint SCKV::2200.04957, 2022.
[RW15] Aviad Rubinstein and S Matthew Weinberg. Simple mechanisms for subadditive buyer and applications to revenue monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 377-394. ACM, 2015.
[Sin10] Yaron Singer. Budget feasible mechanisms. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, page 765-774, USA, 2010. IEEE Computer Society.
[Yao15] Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 92-109. Society for Industrial and Applied Mathematics, 2015.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims made in the abstract are backed by mathematically proven theorems.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All assumptions used to prove the theorems are clearly outlined throughout the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

All theorems are accompanied by proof either in the main paper or the Appendix. All assumptions are either defined in the preliminaries or in each theorem statement.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.coom cttpss.ccppbblcc///// htte//ublcc/ggudeeeee guides/ /CodeSubmi ssi ssionPolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https : http///eerrrp.eeeee cc cc/publicc/thicsuiieeeeeeeeeeeee
Answer: [Yes]
Justification: The reserach conducted in this paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We discuss the scope of our work in the introduction. We are interested in foundational aspects of mechanism design and machine learning. We believe direct (positive or negative) societal impact is implausible.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in wwwoodeethhoee....o
package should be provided. For popular datasets, paperswi thcode. com conddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : //tt://is....//e / for what should or should be described.
21

---

A Further Related Work
Approximations in Bayesian Mechanism Design. There is a rich body of literature on approxi- mately optimal mechanism design, as discussed in the introduction. The work most related to ours is [Ala14] which provides a framework for designing multi-agent mechanisms by a reduction to single agent mechanisms via an ex-ante relaxation and using an online rounding procedure or OCRS. This framework yielded approximately optimal non-sequential and sequential mechanisms for several fundamental settings including selling kt identical items to additive buyers, who may be subject to additional constraints such as budget constraints, although does not support any inter-buyer constraints (except for per item supply constraints). In particular, a sequential posted price mechanism
obtain O(1/V( /i)) to the optimal revenue. In the special case of unit-demand buyers with independent values for heterogeneous items (where each item can be allocated to at most one bidder), [Ala 44] establishes a sequential posted price mechanism that obtains 4-approximation- recoverrnn a prior result of [CHMS10] 10]. Sequential mechanisms have been of particular interest due to their simplicity in implementation. The [Ala14] 14 framework (along with other influential techniques like (CDW19) duality) has enabled the design of approximately optimal and simple sequential mechanisms in vari- ous follow-up works. [AFHHH3] show that revenue maximization in nulti-dimensional multi-agent setting reduces (exactly or approximately) to a single-agent problem in a variety of settings, including risk-averse agents. [AW18] use random order OCRS to design a (k + -ppppooxinattoon mechanism for unit demand bidders under k-matroid feasibility constraints. [CM16] consider more general case where agents have constrained additive valuations (aka matroid rank valuations) and provide a simple sequential two-part tariff mechanism that obtains a constant approximation. This constant was then improved to 70 by [CZ17], who also extend their results to the setting where agents have XOS (and subadditive) valuations over m. heterogeneous, independent items, and [DKL220] provide improved approximation ratio of Olog log m) for subadditive valuations. Crucially, these works assume that the agents' valuations are independent over the item. For the setting of correlated items and constrained additive buyers (with matroid constraints), [Ala14] provides a sequential mechanism that is a 2- 2-approximation to the optimal revenue. However, this mechanism is not "simple" (unlike posted price or two-tariff). Indeed when the item distributions are correlated no "simple" mechanism can obtain any non-trivial approximation [HN19, BCKW15]. A recent line of work circumvents these impossibilities by studying approximation guarantees of simple mechanisms with respect to a weaker benchmark called buy-many mechanisms [BCKW15, CRTT23, CCD*24]
CRSs, OCRSs, and their applications. Contention resolution schemes were defined by [CVZ14], and extended by [FSZ21] online settings. CRSs and OCRSs have since found numerous applica- tions in Bayesian and stochastic online optimization, such as stochastic probing [FTW#21, GN13] (with applications to posted price mechanisms), prophet inequalities [EFGT20] (in fact, OCRSs are equivalent to ex ex-ante prophet inequalities [LS 18]), pricing problems [PRSW22, CCD* and network revenue management [MMZ24]. In this paper, we define a type of dependent CRSs and OCRSs, which we call two-level CRSs/OCRSS. Online dependent rounding schemes, under the name of ODRS, were introduced by [NSW23] in the context of rounding fractional bipartite b-matchings online; here we give a different name to our schemes to highlight the specific dependence we can handle. There has also been a recent work studying OCRSs with limited correlation or pairwise inde- pendence [GHKL24, DKP23J. A special case of (OCRS called random-element OCRS, where at most one element from {eis Jy becomes active for each i, is studied in [MMZ24] for constraints induced by "L-bounded products". Other works study OCRSs under negative correlations [Dug19, QS22].
B Additional Preliminaries
B.1 CRS and tCRS Preliminaries
Definition 9 (Contention Resolution Scheme (CRS) [CVZ14D. Let e E [0, 1). For every x E Pr. let R(bx) be a random subset of active elements, where element i E N is active with probability b x4 independently. A (b, c)-seecctable Contention Resolution scheme (CRS) for Py is a (possibly randomized) procedure that, given set of active elements R(bz) returns set ((R(bx)) = R(bz), such that (i) I E F, and (ii) Pr E 1]i E R(bx)] 2 c, Vi N.
Definition 10 (Two-level CRS (ICRS)). Let b, e E [0, 1). Let (D, x)) be a two-level stochastic process that is feasible with respect to F, and let R(D, bx) C N be random set of elements obtained by
22

---

sampling from (D,bx). A (b. c)- -esseecctbble two-level CRS (rCRS) for F is a (possibly randomized) procedure that, given a set of active elements R(D, bz) S N and realizations (d),..., d,,) that were sampled in the first level of (D, x.), returns set μ R(D, bx), = 1 = R(D, ba), such that (i)
E and (i) Pr (i E Tli ((D,br) 2 e, Vi E N.
B.2 Bernoulli Factories
Berouuli factories were introduced by Keane and O' Brien [KO94], where they are defined as follows.
Definition 11 (Bernoulli Factory). Given function f : (0,1) (0, 1), Bernoulli factory for oupput a sample of a Bernoulli variable with bias f(p) (i.e. an f(p) given black-box access to independent samples Bernoulli distribution with bias p (0, (i.e. p-coin).
As an illustrative example, imagine that we are given a p-coin, a coin that outputs with probability p and 0 otherwise. Our goal is to create new coin that outputs 1 with probability f(p) p². The complication here that we do not know the value of p. f(p) = p² can be implemented as follows: flip the p-coin twice. If both are 1 then output (otherwise output 0). We include additional examples of Bernoulli factories Appendix B.2. Bernoulli factories have recently been used in mechanism design in the context of black-box reductions [DHKN21, COVZ21]. In this paper, we make of a Bernoulli factory for division: given one po-coin and one p1 coin, implement f(o. P1) = po/ /o/pi for P1 Po 2 5. This problem was considered by [NPO5] but their construction is rather involved. Instead, consider Algorithm 2, the Bernoulii Division factory of [Mor21].
ALGORITHM 2: Bernoulii Division [Mor21]
while tre do
X Bern[1/2]]
if then
W Bern|po].
if W = then
return
end
end
else
W ~ Bern(p: - po].
if w = 1 then
return 0
end
end
end
Lemma 1 ([Mor21]). Given a Po-coin and a p1 Pi-coin, assume P1 Po 2 5, and let N be the number of tosses required. Then, Algorithm 2 is Bernoulli factory for (po/Pi) which satisfies [[N] S 22.12 811.
Although the process and its correctness fully described by [Mor21], the end-to-end expected number of tosses is not explicitly calculated. For completeness, we show these calculations, and also argue that Algorithm 2 Bernoulli factory for (Po/PL
Proof of Lemma 1, Consider the following distribution:
P1 (PI
if yk
Pr = yll
po)
if y/: =
Po
if yk
Then it is not difficult to that:
k-1
1
1
Pr|Y = 1] II
Pr[y -11
1
P1
2
2
p1
k=0
2=0
k=0
and thus Algorithm 2 is valid Bernoulli factory for po/P1.
23

---

Let N₁ be the random variable that represents the number of tosses at round t. and let X, be random variable that if the experiment lasts at least rounds and otherwise. Then N - N, X,, Linearity of expectation implies that I [N] _t=1 L [N, Xr). however X, and N, are independent
and thus E [N] Σ E [N.]
E
{ From [Mor21] (Proposition 2.27) know that E [N₂] Σ
11.06(1 + )) On the other hand concludes the proof.
>x t=1 IE [Xe] = > t= (1 pp: " 2.4 Combining the above
Finally, outline few Bernoulli factories and their construction to help the reader gain some intuition:
1. Bernoulli Negation: Given a p-coin, implement f(p) = This can be implemented with one sample from the p-coin:
P ~ Bern(p).
If = output (otherwise output 0).
2. Bernoulli Down Scaling: Given p-coin, implement ((p) = X p for a constant À E [0, This can be implemented with one sample from the p-coin:
Draw A ~ Bern[X] and P ~ Bern(p].
Output A
3. Bernoulli Averaging: Given one po-coin and one pi-coin, implement f(po, PI) = 2o-t
This be implemented with one sample from the po-coin one sample from the p pcoin: Bern(po), and Pi Bernlpi].
Draw Z ~ Bern[1/2]
Output Pz.
4. Bernoulli Doubling: Given a p-coin, implement f(p) 2p for p E (0, 1/2 - 6). This can be implemented with ((1/5) samples in expectation from the p-coin. The algorithm was introduced by [NPO5].
5. Bernoulli Addition: Given one Pu-coin and one p1 coin, implement f(po. P1) = po + P1 for Po + Pi E [0, 1 5]. This can be implemented with O(1/8) samples in expectation from the po-coin and pi-co:::
Use Bernoulli Averaging to create a Past"
Use Bernouli Doubling on the potri-coin.
6. Bernoulli Subtraction [Mor21]: Given one Po-coin and one pi-coin, implement ((po, Pi) =
P1 Po for P1 Po 8. This can be implemented with (1/88) samples in expectation from the coin and p1 coin:
Use Bernoulli Negation on the P1 P1-coin to create 1 P1 Pi-coin.
Use Bernoulli Addition on the 1 P1 -oin and Po-coin create 1 P1 + Pu-coin.
Use Bernoulli Negation on the - P1 + Po-coin.
C
Mechanisms from two-level CRSs
The input to the tCRS framework (i) a BIC-IR interim allocation, payment rule pair (æ, q) that feasible in expectation and is an a approximation to the optimal revenue, (ii) a (b, c)-selectable 1CRS for F, and (iii) a parameter e 2 0. Our frameworks produce BIC-IR, πi-ce approximately optimal mechanisms for agents with constrained (with respect to F) additive valuations.
Given iCRS, our framework, Algorithm 3, works as follows. First, each agent i reports rf E Vi and pays 6 (c (cc-e) (r()). We then construct a set Rt = (el of n m elements, one for every agent, item pair, where Zı,j (i.e., element (i. is active) with probability b Try(r?) We query the 1CRS on input R, to get back a subset Z of selected elements (which is in F, by definition). We flip an additional coin to decide whether to keep an element (). i.e. whether we should allocate item j to agent i. Recall that this last coin essentially balances the randomness of the iCRS and ensures that the probability that agent gets item when they report rf is exactly - () which, combined with the chosen payment, ensures that BIC and BIR are satisfied.
24

---

ALGORITHM 3: Our framework for (CRSs
Input: allocation, payment rule pair (x, q). (b, c) selectable (CRS μ., parameter é 2
for each E [r]] do
Agent reports ri E Vi and pays (c <) q: (r.).
end
Construct Ht = ( nl mm] where i <- 1 with probability b (ri)) and rı,j + 0 otherwise.
Z = [Zr,, [m < 1u R. r-) 1/ 7 C R is the set of elements that the tCRS picks for each element (1 m] [m] with Z,. = do
Allocate item j to agent with probability
c-e (r))
where (r() is the probability that μ selects (i.j)
conditioned on i's report rf and Fij being equal
end
D Missing Proofs from Section
Proof of Theorem 1. First, we argue that our frameworks output allocations in F. By definition, and assuming truthful reports, the interim allocation π defines feasible (for F) two-level stochastic process, where we first sample u;s independently, and then Tz, Let E R(b x) be the input to the (b, c>-seccctabl tCRS (resp. for tOCRS); by definition, the set of selected elements Z satisfies Z F. We allocate a subset of Z. thus our allocations are feasible, since F is downward closed. Furthermore, for any element zi.j. Pr[zs.j | = = Pi, 2 c, and thus [e.] is probability. Second, we argue that our mechanisms are BIC. From the perspective of agent i, report E V; costs 6 (c-c) (13))--6 (rrs) and allocates item j with probability b (rv) (r.)) (r.) c-e = b (cc-c) Ti, (rs). (r.)
and therefore translates an expected utility of costs b (c-e)) e) Σye(m) VigTi - bb (rt):: since (T, q) is BIC, so is the mechanism we output. Near-identical arguments imply the BIR guarantee and revenue guarantees.
When given only black-box access to a ICRS/OCRS,
not immediately clear how one can flip coin with probability exactly (c- c)/p;, (u;) (efficiently or otherwise). as needed in Line 3 (u;) Using a Bernoulli factory for division (such as the result of [Mor21] discussed in Section 2), this step can be implemented using 22.12 (r.) (1 + 1 e
of Algorithm 3 and Line of Algorithm
O(1/e) calls in expectation (Lemma 1), assuming that S (v;) is a constant. Overall, we have (p | m, 1)) queries in expectation for the entire execution of a framework; diseuss implementation details in Section 3.1.
E Missing Proofs from Section
Proof of Theorem 2. Let (D, br) be the two-level stochastic process through which elements become active. Let μ4; be the (b, c)sseccctb CRS/OCRS for constraint F, for i E [ni], and let μd² be the (b, sellectabe CRS/OCRS for constraint Fi, for j E [m]. Given a set of active elements R(D, bx) sampled from (D, bar), our iCRSROCRS selects element e,j R(D,bx) if (i) μ² on input R(D, bx) n {ei. [vin] selects e.j. and (ii) on input R(D, bx) n {eis) Jemm) selects eij (noting that this is process does make decisions online when μº¹ and μr are OCRSs and are queried in an online fashion).
Let Aj,j be the event that Ci,j E R(D,br). By the definition of a two-level stochastic process, event Ai,5 is independent from event Av for all j [mi and /' [n] such that * Y'. Therefore, the CRSs/OCRSs μº, [m], are queried about elements that become active independently (as required by the definition of CRS/OCRS). Now, overloading notation, let (d,) be the event that ei, R(D bz)) given that d, was sampled from D,. By the definition of two-level stochastic process, event (dk)(d)) Therefore, the CRSs/OCRSs 14, E [n]. are queried about elements that become active independently (as required by the definition of a CRS/OCRS). Let Br,j be the event that jr selects an active element ei, E R(D, bz) on input R(D, bz) n [ersheees) and note that, since μ² is a (b, seleectbeee CRS/OCRS, we have that then Pr Pr[BaslAss an active element eij R(D, b)) input R(D, bx) n (ELm) Pr[Ct,]Ah, 2 c. Finally,
(4)+ is independent from event (d.), for all j * j' E [m] and all E [m].
2 é. Similarly, let Ci. be the event that μu selects
25

---

conditioned on A events Br, and Ct are conditionally independent due to the definition of two-level stochastic process. Thus, Pr[B..j C.glA.,) 2 cc', which concludes the proof.
Proof of Theorem 3. Let (D, bx) be the two-level stochastic process through which elements become active. Let j be the weight of element Gi and K bet the total weight. Let S, {er, [n].j E [m]]k,, > K/2] be the set of elements whose weight is at least K/2, the "heavy elements," and let St = {er. E [n]]. j E [m I K/2} be the of "light elements." Our tOCRS is randomized: with probability 1/2 we run scheme that considers only heavy elements, the "heavy scheme," and with probability 1/2 we run scheme that considers only light elements, the "light scheme." In both cases, we use to indicate the set of elements we output. Without loss of generality (from the definition of a (OCRS) we assume that clements arrive in the order 61,1, 21,2, Cn,m-
For the case of the heavy scheme, it is obvious that we can only take one heavy element. We initialize and consider elements sequentially. Let A,, be the event that I is empty until element Ci is considered when we run the heavy scheme and d, was sampled from the two-level stochastic process (D, bxr). If element ç is active, Ct, Sh and I 0, then with probability (1448) [d.] we set I {e otherwise we move on the next element. Assuming that (1448) (d.) is valid probability, each heavy element is selected with probability exactly [1+11] when we run the heavy scheme. Towards proving that
Pr[A.,(d)) [1+10)
Pr[A:,(d:]] 2 [1+16] we have
Pr[Ais+1(d:) =1
Σ P' Si
Σ
Prlee.y picked] +
Σ
Prfeiy picked]
1
Σ
Σ
Prler,y active] Pr(ev,y picked oy active]
P'S UES
Pr(eay active] Pr(er, picked euy active]
j'cjtlee,
1
Σ
Σ
Pr/er active) +
Σ
Pr(ei,y active]
1 + 4b
8 je ESa.
1
Σ
Σ
(di)
1+ 4b
f
4b
1 4b
1 4b'
where Wayy = Ed,v, Pr(D, d.l (d.). is the probability that Ci,y is active in (D,bz).
For the case of the light scheme, we again initialize / = 0. Let (d.) be the event that, at the time step when element Gi.j is considered, the total weight of elements in I so far is strietly less than K/2, when d, was sampled from the two-level stochastic process (D, bz). We consider each (light) element ei,j at time, and if ez, is active and the weight of elements in I is less than K/2, we set I +- IU {er,) with probability (T+446 (4]] otherwise move on to the next element. Again, if (I+-4b) Pi[B., is valid probability, each light element is selected with probability exactly Pr(Ba,(de) (1100)
(1+10] when we run the light scheme. It therefore remains to prove that Pr(Bis(d)) Z (1 Let (d.) the random variable that represents the total weight of elements in I at the time when we consider elements et,j when d; was the sample from (D, bx). We have that:
(d+) - - Pr[D, dpl
Σ
1
Pr(Br, y (bay, (dy kee
j' ES (1 46) Pr By y (dv))
PRidpEV,
Contribution from agents before
26

---

+ Σ
(1 + 4b) Pr(Bay Pr(Ba.j (dr))ars,y (d
Contribation from i's items before.
b
Σ
wy wysckes +
Σ (d.y(dd))k
1 + 46
Vec yei
8' E
2b
K.
(Feasibility of (D, ba))
1 4b
Therefore, we have
Pr[Bay(d:) Pr(WW,s(d) < K/2]
(r(W),(dd) 2 K/21
2b K
1+46
(Markov's Inequality)
K/2
1 46'
Since we rum each scheme with probability 1/2, for an element Ct,j E Sy. that is active we have:
1
Pr(ec, [] = Pr["heavy Pr(e," Ilehea scheme"]
21+ 4b
8b"
Similarly, for an active element Ci.j E St. Pr(ecs I] 1/(2 8b), concluding the proof.
Proof of Theorem 4. Let (D, lur) be the two-level stochastic process through which elements become active. Let ja.j be the weight of element eijj and K bet the total weight. Our overall approach is similar Theorem 3.
Let S₁ = {ei E [n].j j E [m]]ki. > K/2} be the set of "heavy elements" and S = {ei :
[n]..j E [mn] K/2} } be the set of "light elements." " Our (OCRS is randomized: with probability 24-76 we run a scheme that considers only heavy elements, the "heavy scheme," and with probability
1+-10
2+776 we run a scheme that considers only light elements, the "light scheme." In both cases, we use to indicate the set of elements we output. Without loss of generality (from the definition of a tOCRS)
14:36
we assume that elements arrive the order e1,1; c m,
For the heavy scheme, initialize = and consider elements sequentially. Let (r,;(d) be the event that I 0 when element Cijj is considered when we run the heavy scheme and d, was sampled from the two-level stochastic process (D, br). If element Gi is active, heavy, and / = 0, then with probability (1+-1b) (d()) we set I + {er,}; otherwise we move on to the next element. The analysis in Theorem 3 proves that (1+4b) (d.). is a valid probability. Notice that each heavy element is selected with probability exactly Pr Pr[A,, (d,) (1+4)) ( PT]A [1+46] given that run the heavy scheme.
Now consider the light case. We initialize / - 0. Let B, be the event that Σv jeee,, EI,r' kys < K/2. Also let C,,, (d,) be the event that, when de sampled from the two-level stochastic process (D, br), Vj' E Se.j' < ;:: ex, & I. We consider each light element e,,; E S₁ sequentially and, if is active, and the weight of elements in I is less than K/2, and no other element of has been selected, we set I + IU {er,} with probability
(1+33)) Pr(A, Pr(B,rCC [4,] otherwise we move on to 2 T (i.c., if (1=3h) Pr[B, [d,] is a valid probability), each light element is selected with probability exactly 1#35 when we run the light scheme. Towards proving that Pr[B, (c,, 2 (1436) let W, elements in I when we consider the first element of i. We have:
the next element. If n
27

---

B[ = E Σ
Pr[D, - Cr, (3b+) + 1) Pr[B, Cv (dx)
b
boo s (de k
EV JES:
b
wy ky.ky
1 36
b
<
K.
(Knapsack feasibility of (D, bx))
1 36
Therefore:
1 + b
Pr[B:] = Pr[W; < K/2] 1 Pr[,, 2 K/2]
(Markov's Incquality)
1+36
K/2
3b
On the other hand,
Pr(Ce5+1(4)) = Pr(Ca,(d))1B)) (1-
bii (db)
(1 36) Pr(B; n (c,(dd))
1
-Pr(Cs (1+ 36) Pr[B.]
brii (d.)
=1 (1 + 3b) Pr[
Σ
bri (d:)
j'Sid'ESt
2 1
(multi-choice feasibility of (D, bx))
(1 + 36) Pr[B.]
Combining the above we have that:
Pr[B, =t(l:(/))pppp(])eCCcpa PrC.) Pr[B.]
(1 + 3b)
1 1 36"
We run the heavy scheme with probability
1+ thus, for an active element ei. 2478
E Sh we have:
1 1+ 46
1
1
Prfeis I] Pr["hevvy scheme") Prfei.j E I heeav scheme"]
2 7b 46
2 7b"
We can similarly show that active light elements are also selected with probability at least 2476 This concludes the proof of Theorem
Proof of Proposition 1. In the proof of Theorem 3 we give an exact formula for the probability that As.j (d.) occurs; therefore, the only step cannot directly implement from the procedure outlined in the proof of Theorem 3 is the toss of the P1 coin. Even when given Pr[Ba,g (d.,) -coin,
using Bernoulli factory for division to produce [1+-46) Pr(B,, coin results in exponential ulow-up in computation, since the factory for the k-th coin would need also simulate the factory for the (k - 1) st coin, and so on. Instead, we approximate these probabilities, sequentially, using multiple experiments and bounding the error using Chernoff bounds.
In order to decide whether to select some element ei,j E Se, we repeatedly simulate our algorithm 1 log 2um repetitions, where the choice of running the "light scheme" until element Cijj for T = 2.2 and d; are fixed. In this simulation, the coins needed make decisions until element 6a, are replaced with estimated coins (described shortly). Let X, be the indicator random variable for the event that Bi5 occurred simulation & [7'. We select element ei,j (when it is active) with probability Standard Snderoff-Hooffdile bounds [Hoe94] imply that
8
(1448)(+ Evem X
Σ X. (d.): > < 2exp (-2 2exp (22e²
1
log
2nm
T
2g
nmm
EE[T]
Assuming that (d]),,
E 2e].
X, - Pr(Ba (d)))
5
6
(+ X, +c+
28

---

When bounding E [W, (. (in the proof of Theorem 3), the term (1+16) Pr [d.) Pr Pr(B,,,(d))
1
replaced with (1+111 + 2 eem Xx+e)" which is at most 1+45 Thus (.)) S I+ K, which
Pr (r),),(
I+7 2 1/5 using the same arguments presented in the proof of Theorem 3. Thus, the probability that an active, light element ei,; is selected is
gives us Pr[B..j(d::)
Pr(
2 1 4b (
1
Pr[B.,,(d:). (P([B:,(d4) 2
2 + 46
(1 4b)
7 EiEry X, +
+ 10c
Using a union bound we have that
Pr ((1,)) E [n] x [m]
Σ Xx - Pr[Bi, > 5 =E(T]
T
Thus, we overall have that with probability at least - 6, when we run the light scheme, each active
element will be selected with probability at least 1-445 1+10c
Proof of Proposition 2. Notice again that, similarly to Proposition the only step we cannot directly implement from the procedure outlined in the proof of Theorem 4 is the toss of a Pr|C..+1 (d:)) B.J- coin. Specifically, in the proof of Theorem 4 do not caleulate the following probability exactly:
Pr(Ci.++1(d) B:] = Pr[B.] Pr(Cs = Pr(B:] 1 30
E
(d:(
J'
Our procedure will again sequentially approximate these probabilities using multiple experiments, bounds.
and bounding the error using
In order to decide whether to select some element eij repeatedly simulate our algorithm until element ei.j. for T = 2zz log 2nm 8 repetitions, where the choice of running the "light scheme" and d; are fixed. Let X, be the random variable that indicates if B, occurred at simulation E (T]; from ف__
Chernoff-Hoeffding bounds [Hoe94] we have that Pr [| + Evemry X, Pr[B., (d:)
e
Instead of selecting element eiyj (when is active) with probability (1+36) (c, we select it with probability (1+36)(+te) -coin where e Eie(T) Xt- - 1+35 E3 Es (d.)
Assuming that 1 EEEm X, Pr[B.] S then (E (e+ E [Pr(Cis+1(dd) n B.J. Pr Pr(Ce++1 n
T
B:] + 2e]. Thus and thus Pr[Ci.j+1 (d:) B:] 2 I-35 2 1/4 using the same arguments presented in the proof of Theorem 4.
(d))n
S I436 Thus [W:] S न K which gives us Pr[B.]
1+h
(1+3b)(Etc)
3+36
Thus,
(+CC)++(d)))) Bi] (1 3b) (E cc
( Pr(Cis+((d)) B.]
2
2
1 + 4b
(r(C.. (d)) n B,] +.1+2 2c
1 1 4b
1 + 8E
Union bounding we have that
1 -Σx, x. Pr(B,]
Pr
B(i,)) E (n) [m]:
> 20.
T
1E|21
Thus with probability at least - 5 when we run the light scheme, each active element will be selected with probability at least 1=46 1+86
F Extensions to procurement auctions
In this section, we show how to extend our framework for the case of procurement auctions. We only show how our framework works for sequential procurement auctions, where construct an
29

---

auction using an OCRS (and interim allocations/paymentt)) our results can be extended to give non-sequential auctions using a CRS, similarly to our results in Section 3.
Budget feasible procurement auctions were introduced by the seminal work of [Sin10]. Following this, there has been line of work studying deterministic and randomized budget feasible mechanisms that obtain approximately optimal welfare, where a major focus has been on single dimensional and prior-free settings [CGLI1, GJLZ20, AGNI8, KS22J. We start by defining the procurement problem we study.
Procurement Preliminaries There a single buyer and a set of n sellers. Each seller has a total of m services they can provide. The buyer has publicly known value d1, for getting the j-th service that seller offers. An (integral) allocation x E {0. 1 yim indicates which services the buyer received: Fii E {0, } is the indicator for whether the buyer received the j-th service of seller i. The buyer's s value for an allocation x is [ie(n]jj(() Vi.j The buyer will pay the sellers for their services; the buyer's is objective is to maximize her value without paying more than a (publicly known) budget B. Each seller E [7x] has some cost for providing service
[m]] depicted as Ca.- We will assume that a is drawn from a known distribution C₁; we allow for correlation between the cost for different services for a fixed seller, but require independence between sellers.
procurement auction elicits reported costs (c1, (cI,...,,al Ca). and determines which services are procured from which seller, as well as the payments to the sellers Our goal is to design BIC-IR, budget-feasible procurement auctions that maximize the buyer's expected value. The definition of BIC-IR, approx- imate optimality, sequentiality, and interim allocations/payments are similar to the corresponding definitions from Section
A procurement auction elicits reported costs (cI...., c.). and determines which services are procured from which seller, as well as the payments to the sellers. seller's objective is to maximize her expected utility, which is the total payment to her, minus the total cost she has to pay. A procurement auction Bayesian Incentive Comparible (BIC) if every seller E [n] maximizes her expected utility by reporting her true costs C,, assuming other sellers do so as well, where this expectation is over the randomness of other sellers' valuations, as well as the randomness of the mechanism. A mechanism is Bayesian Individually Rational (BIR) if every seller E [n]] has non-negative expected utility when reporting her true cost (assuming other sellers do so as well). The (expected) value procurement auction is the expected value the buyer makes when sellers draw their costs from C (and report their true costs to the auction). We say that a procurement auction is BIC-IR if it is both BIC and BIR. A procurement auction is sequential if it sequentially approaches each seller i, clicits report, determines payments to seller i, and which services to procure from i, before proceeding to the next bidder. The optimal procurement auction for a given distribution C, maximizes expected value over all BIC-IR procurement auctions. A procurement auction guarantees an a 2 1 approximation to the optimal value if its expected value is at least the expected value of the optimal procurement auction times d-
BIC
The interim allocation of a procurement auction M,, π M indicates, for each seller i and service j the probability T (r:) that seller receives service j when she reports cost r. (over the randomness in M and the randomness in other sellers' reported costs c-j, drawn from C_z). The interim payment of the buyer to seller i, (,M(r.). is the expected payment she gets when she reports cost ra (again, over the randomness in M and the randomness in other sellers' reported costs). The expected utility of seller i with cost 6; when reporting r; procurement auction M, is EEjEm Ci (ri) + gf (r:). An interim allocation rule æ is feasible in expectation if (i) Vi E [n). q E supp(C.), n. (c)) E [0, 1]. and (ii Vi E [n], E [m/] Ee:esup(cc.) Pr[c:]- (c,( < 1.
For case of exposition, we will assume that there are no constraints on the services we can acquire, other than the buyer's budget constraint. If additional constraints exist, our framework can be extended using the ideas analyzed in the previous sections.
F11 Procurement Framework
Our procurement framework uses OCRSs for Stochastic Knapsack. A c-selectable OCRS for Stochastic Knapsack μ* is parameterized by knapsack size K and distributions from which elements' weight are drawn. The OCRS given, in an online manner, elements and their weight (which is drawn from the aforementioned distributions), one at a time, and it needs to decide.
30

---

immediately and irrevocably, whether to include an element in the knapsack, in way that every element selected with (ex-ante probability least e; see Appendix F.3 for more details.
The input to our framework is (i) feasible in expectation, BIC-IR interim allocation, payment rule pair (T,, q) that is an 2 approximation, (ii) c-selectable OCRS for Stochastic Knapsack, and (iii) parameter 2 O. Our framework, Algorithm 4, outputs a BIC-IR procurement auction that is a/ a/(c- - approximately optimal.
Algorithm 4 works as follows. We approach each seller sequentially. Seller reports r; E supp(C.). and we query the OCRS input (r.).. If the OCRS selects element with weight (r(r),, pay seller an amount equal to q: (r.)). with a certain probability (this step ensures that the expected payment to seller is exactly (c e)g.(1g) Finally, for each service [ma], we receive the service from seller i with probability (c <)
ALGORITHM 4: Our sequential procurement auction when given an OCRS
Input: interim allocation, payment rule pair (r, 4), e-selectable OCRS μи for Stochastic Knapsack, a parameter 2 0.
for each seller i E [xi] do Seller reports r E supp(C.).
Zi + [B(g:(r)))
Z then
Pay seller i, (x())) with probability (c c)/p (rt), where pf (xt) be the probability that the OCRS selects an element with weight q: (ri).
end
for each service j E [m]] do
Receive service j from seller with probability (c (c)
end
end
Theorem 5. Given (i) feasible in expectation, BIC-IR interim allocation and payment rules (x, q) that are an a 2 1 approximation, (ii) a e-selectable OCRS for Stochastic Knapsack, and (iii) parameter e Z Algorithm 4 gives BIC-IR sequential procurement auction that is a/(c- e)- approximately optimal. we have query access to the OCRS, our mechanism can be implemented using a (poly(E, (supp(C.)), m, 2)) number of queries in expectation.
Proof of Theorem 5. First, we argue that Algorithm 4 is budget feasible with probability By definition, and assuming truthful reports, the interim payment q defines a feasible distribution of "weights" for each seller. The OCRS always selects a set of elements whose weight is at most the knapsack size (in our case B), and our total payments are at most the total weight that the OCRS packs in the knapsack; therefore, our total payments are at most B.
Second, we argue that Algorithm 4 is BIC-IR. From the perspective of seller i, report r; E V; costs e-c PT Therefore, her expected utility is (c <) (9((r)) - Eje(m C.yTe (ri)) since (T, q) is BIC, so is Algorithm 4. Near-identical arguments imply the BIR guarantee.
= (c (r:). The expected cost of services is EiE(m) Cij e)TT.((
The expected value of the buyer is Exe(n) Eesec, Pr[c]] Eje(m) Pay (c (c- ()Tss)) which is a/(c-é E) approximation, since (TT, q) is a approximation.
If we are given only black-box access to an OCRS for Stochastic Knapsack, it is not immediately straightforward how to flip coin with probability (c-c)/pt (r²) (efficiently otherwise), needed in Algorithm 4. Using a Bernoulli factory for division (such as the result of [Mor21] discussed in Section 2), we implement this step with O calls in expectation; we discuss efficient implementation considerations in Appendix F22
[JMZ22] give a 3+ selectable OCRS for Stochastic Knapsack, Combining with Theorem 5 we readily get the following application.
Application 4 (Theorem and [JM722]]. Consider the problem of purchasing m services from n. strategic sellers, subject to a budget constraint. There exists sequential, budget-feasible, BIC-IR
31

---

procurement auction that guarantees a 3 + e optimal BIC-IR auction.
2 (=z 3.13) approximation to the expected value of the
In Appendix F.3 we give a new OCRS for Stochastic Knapsack that is max 2- - -selectaabe where k = K maj Esupp(K.) k; and K2 is the distribution of weights for the i-th element. Our OCRS outperforms the OCRS of [JMZ22] when k* is small (specifically, ks < 1/3). Furthermore, OCRS induces greedy and monotone OCRS for the non-stochastic knapsack problem, which not true for the OCRS of [JMZ22]]. Note that, our OCRS also implies that better approximation guarantees are possible for sequential procurement auctions if the payment to seller is more than third of the total budget.
F.2 Implementation Considerations
Here, we highlight some implementation details. First, we give simple IPP that computes optimal (a = 1), feasible in expectation, BIC-IR interim allocation and payment rule (T, q) Second, we flesh out implementation details regarding flipping (c - e)/p3 p (c))(((c)))) -coin, when given only black-box access to an OCRS.
Finding feasible in expectation, optimal interim rules Consider the following linear pro- gram, (F.2), which computes an interim relaxation of the revenue optimal BIC-IR mechanism.
maximize
ΣΣ Pr[c]] Σ Tais [rs(C))o
KE(M]C:EC.
jE/m]
s.t.
a(()) - Ejelm CL ( q(() Eje(m] G.y
Vi e [n], supp(C.)
(LP2)
a(c)) EjEmm) Ti (c)2
e [n], e supp(C.)
Eie(n) ELEc, Pr(c]la(c)) B
((G))
< B
vi [n], es e supp(C,)
This LP has (nn Eie (supp(C.)) variables, and O(n Eiem)))) (supp(C.)) constraints, and is therefore efficiently computable by standard LP solvers.
Flipping a coin. We again use Bernoulli factory for division to produce a (c-e)/pr (cs -coin. e-e is known. And, identically to our approach in Section 3.1, we can flip p (c,)-coin by simulating the entire procedure, conditioning c; being the report of seller i.
F.3 A new OCRS for Stochastic Knapsack
In the Stochastic Knapsack problem, there is ground of elements N (ei]ve(() and knapsack size K. Each element arrives sequentially and reveals random weight E [0, K] drawn from known prior distribution IG; (where a draw of k; = O is analogous to element e; being inactive/not arriving). The input distribution satisfies Σie(n) Σx, Expepttt...) Pr[K, k.] h S K. Once an element arrives and reveals its weight we need to immediately and irrevocably decide whether this element is included in the knapsack. A c-selectable OCRS for this problem is procedure that selects elements (online), such that the knapsack constraint never violated (i.e., Σie(n) ky < K in all outcomes), and every element is selected with probability least c.
Theorem 6. There exists a max 1-k" 2- -selecttabe OCRS for Stochastic Knapsack, where k
I K keuppp))) kü-
Proof of Theorem 6.
1-k" We present two OCRSs: a 7-selectable OCRS, where 7 2- and a 8-
selectable OCRS. Our overall OCRS computes k* K maxie[n) EsEsupp(KK) h; If y 2 6 it
exccutes the following 7-selectable OCRS; otherwise, it executes a _ --selcctable OCRS.
32

---

First, we give the 7-selectable OCRS. Initialize I = 0. and let (k,), be the event that Eyer by S K k; when element 6; arrives, and given that its weight is kū When element e, N with weight k arrives, if Ever by I K k; we include e, in with probability P.CC) where 7 k- The probability with which an element e; selected is then:
Σ
Pr[K; = kj Pr (C](
E
Pr[K, k2) =y.
Pr[C,(k:)]
A (Ku
((Esup((K..)
remains to prove that [+]] a valid coin (i.c., (r(C 2 7) Let W, be the random variable that represents the total weight of elements in I (i.e. Ever kir) when element i arrives.
[W]] Σ Σ Pci Veikky Eaupp()))
Pr(Cr((k))
7
Pr[K kelkip S SyK.
(r())((s))
Therefore, have
Pr(C,(k:)] Pr(E; K k.]
=1 - Pr(W; > - ks]
2 1 K ki
(Markov's Inequality)
2
k*
7
This concludes the proof for the 7-selectable OCRS.
Next, we give & -eelectable OCRS. With probability 1/2 we run a "heavy scheme," that only considers elements e; such that k; > K. 2
otherwise, we run "light scheme," that only considers
elements e; such that K; S K 2
Suppose the heavy scheme. Initialize I = 0, and let A, be the event that / = 0 when element & arrives. For each element e; such that h; > 2 if I = 0, we select e; with probability Pr[A.] Assuming that 3Pi[A.] is valid coin (i.e., Pr[A,] 2 1/3), the probability with which each element selected, given that it is heavy and that the heavy scheme, is Pr[A.] PP(A. 1/3. To prove
that 3PT[4 is a valid coin we have:
Pr|Ai+1] = Pr[Ad]
1
Σ k
Pr[K; = ki]
PP
=Pr[Ad
Σ
Pr[K; k.]
k K/
=1- - Σ Σ
Pr|KG = ky]
2: K2/2
2 1 2/3 = 1/3.
Now, suppose the light scheme. Notice that in this regime, where ignore elements whose weight is larger than K/2, the previous 7-selectable OCRS 1/3-selectable (since ks k2). Since each scheme (heavy and light) is chosen with probability 1/2,
R A this OCRS is 1/6-sclectable.
This concludes the proof for the j-selectable OCRS.
We can implement ( -selcctbble OCRS for the Stochastic Knap- sack setting in time logg(//) where c = max 1-k" स maxig[n], (Eupp((..) ki-
Proposition 3.
2- 1/6), and k* =
33

---

Proof of Proposition 3. The only step we cannot directly implement from the procedure outlined 2 in the proof of Theorem 6 is the toss of the P.[C.[]:]] coin. The use of a Bernoulli factory would exponentially blow up the complexity of the procedure. Instead, we approximate these probabilities, sequentially, using multiple experiments and bounding the error using Chernoff bounds.
In order decide whether select some element 6; N, we repeatedly simulate our algorithm until 2| repetitions. In this simulation, the coins needed to make decisions element 6,, for = 222 log g until element e; replaced with estimated coins (described shortly). Let X, be the indicator random variable for the event that (kk) occurred at simulation & E [7'. Instead of selecting element e; (when it active) with probability P[[C)(K]] select it with probability
Standard
( Evemy Xx+c)
Chernoff Hoeffding bounds [Hoe94] imply that
Pr
Σ X. - Pr(C.(k)) E
2exp (-2e2T) 2exp
-2e log
1
N|
20
|N
1E|T
+ Eieny X, Pr(Ci(kk))] S (+ Eie Xt +c) [PC(C((
Assuming that 2c].
When bounding E [W:] (in the proof Proposition 3), the term 7
(k.) Pr[C;(k:)] is replaced
with 7 (r(C(((k))
Eetr X,-+)* which is at most y. Thus E [W:] S K, which gives us (r]C;(k;) 2 using
the same arguments presented in the proof of Proposition 3. Thus, the probability that active, element e; is selected is
(k()) 27 EierT X, x++c)
Pr[C (Pr[C](k)] + 2e
27 (1+22/7) 1 22/7
Using a union bound we have that
Pr e
Σ X, Pr(C)(k:)] > 56. NE[T]
T
Thus, overall have that with probability at least 6, when we run the light scheme, each active
element will be selected with probability at least (1+2//7)
34


Reviews:
[{"review_id": "sjSYgfSBpu", "reviewer": "Reviewer_y7Bn", "summary": "The paper studies the online allocation problem, where agents report valuations for multiple heterogeneous products and make payments if a product is successfully allocated to them. The objective is to design a mechanism that guarantees Bayesian Incentive Compatibility and Individual Rationality (BIC-IR), while achieving approximate optimality up to a constant ratio. This extends existing work that simplifies the problem using single-agent reduction.\n\nThe key idea is to introduce a two-level interim relaxation that incorporates additional randomness into the selection of allocation rules, leading to the concepts of tOCRS and tCRS. Treating the relaxation (tOCRS or tCRS) as an offline oracle, the algorithm proceeds by querying the oracle to ensure that the selected allocation is feasible. It then decides whether to allocate or not using a second layer of Bernoulli sampling.\n\nThe paper establishes theoretical guarantees for the proposed algorithm by proving both the approximation ratio and the validity of the BIC and BIR properties. Finally, the paper concludes by interpreting these theoretical results in the context of the three motivating applications discussed earlier, demonstrating the practical relevance of the framework.", "questions": "Please see the above weakness section.", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength \n\n- The paper is clearly written and enjoyable to read; a quite complicated problem is very well laid out \n\n- The algorithm is elegant and easy to interpret\n\n- The paper theoretically establishes the feasibility, and the approximation ratio of the algorithm \n\n- The application in Section 5 is very clear in supporting the insights of the theoretical results \n\nWeakness \n\n- I would appreciate highlighting the novelty more in the first few pages of the paper; the paper has not elaborated on the novel sections until page 6. I understand that it is for clarity, and it might be great if these two could be balanced. For example, the framework for\ntCRSs could be kept in the main body rather than in the appendix, since this is something new. \n\n- The description about flipping a coin with probability $p^{*}_{i,j}(v_i)$ without knowledge of this probability term might need further justification. In particular, why could this way get rid of the dependency on the knowledge of this probability?\n\n- The construction procedures of tOCRs is only illustrated for VH family or more specifically, Knapsack constraints. \n\n- Proposition 1 and 2 does not tell us how to implement such tOCRs given the constraints, which is of great importance to the algorithm, since part of the key factors of Algorithm 1 is the existence of such tOCRs. \n\n- I guess the main concern Is whether one can really implement this algorithm from scratch down to earth, based on the pseudo code. It would be very helpful if there is a case study containing certain numerical results to validate the practical use case of the proposed algorithm. \n\n- It is unclear whether the approximation ratio is ratio; a comparison with the related work would be helpful. \n\n- Would it be possible to remove the assumption that the valuations of different agents are independent of one another? Given the era of digitalization, it is possible that agents can communicate or gather information about one another. \n\n- It would be helpful to include a conclusion and future work section, summarizing the paper and inspiring subsequent study along this direction.", "was_revised": true, "final_justification": "I thank the authors for the responses. I think the implementation of the algorithm requires more careful thoughts and efforts. Maybe a concrete experimental plan or even a very simple toy example would be helpful. As a result, I will keep my score as it is.", "rebuttal": "Thank you for your review. We comment on some of the weaknesses you point out in your review. \n\n>  The description about flipping a coin with probability $p^*_{i,j}(v_i)$  without knowledge of this probability term might need further justification. In particular, why could this way get rid of the dependency on the knowledge of this probability?\n\n(Markdown was having issues with $p^*_{i,j}(v_i)$, so we will be using $p$ in this response)\n\nIn order for the incentive constraints to be satisfied, we cannot afford approximations when using randomness --- we need to have a perfect handle on all the randomness we use. What we need is to output 1 with probability $f(p)$, for some function $f(.)$. \n\nDue to the nature of our setup, we do not have exact knowledge of $p$, in the sense that it is not explicitly written down in memory. We do, however, have access to a Bernoulli oracle that outputs 1 with probability $p$ and 0 otherwise. While one could sample repeatedly from this oracle to approximate $p$ up to any desired accuracy, this would still not be good enough: we would only get approximate incentive compatibility. The Bernoulli factory problem studies precisely the question we need: is it possible to implement a coin with bias $f(q)$ given black-box access to independent samples from a Bernoulli distribution with bias $q$? To efficiently implement our mechanisms while preserving exact truthfulness, we use Bernoulli factories for division.\n\n> The construction procedures of tOCRs is only illustrated for VH family or more specifically, Knapsack constraints.\n\nWe believe that this question stems from a misunderstanding. First, Knapsack constraints are not in the VH family. Our tOCRSs for Knapsack and Multi-Choice Knapsack are new. Second, Theorem 2 allows us to efficiently construct numerous tCRSs and tOCRSs from existing CRSs and OCRSs, including matchings, matroids, and so on. These constructions are also computationally efficient.\n\n> Proposition 1 and 2 does not tell us how to implement such tOCRs given the constraints, which is of great importance to the algorithm, since part of the key factors of Algorithm 1 is the existence of such tOCRs.\n\nThis also appears to be a misunderstanding. Theorems 3 and 4 show that certain tOCRSs (for Knapsack and Multi-Choice Knapsack) *exist*. Propositions 1 and 2, respectively, give efficient implementations for these tOCRSs (with only a tiny loss in the guarantee). So, using Propositions 1 and 2, we can get an efficient implementation of Algorithm 1.\n\n>  I guess the main concern is whether one can really implement this algorithm from scratch down to earth, based on the pseudo code. It would be very helpful if there is a case study containing certain numerical results to validate the practical use case of the proposed algorithm.\n\nYes, all our algorithms can be efficiently implemented from scratch. The input is a feasible in expectation interim rule, and the output is a mechanism (and even a sequential mechanism in most cases). We show how to efficiently implement every step; see Section 5 for the detailed steps for each application (we can also revise Application 2 to explicitly point to Propositions 1 and 2 if that avoids confusion). If the designer does not already have the interim rule, but only the agent distributions and feasibility constraints, the interim rule we need can be computed using LP1. LP1 can be solved efficiently for many feasibility constraints using the framework of Cai et al.; we note that our LP1 is, in fact, a lot simpler than the LPs Cai et al. need to solve, since we only need feasibility in expectation, not ex-post.\n\n> It is unclear whether the approximation ratio is ratio; a comparison with the related work would be helpful.\n\nWe are unsure what this question is asking. If the reviewer is asking how our approximation ratios compare to existing work, the framework of Cai et al. can be used to *compute* the optimal mechanism exactly. In contrast, the literature on *simple* approximately optimal mechanisms has considered much more restricted feasibility constraints (e.g., each item can be allocated to at most one agent), and typically non-sequential mechanisms. Our mechanisms are more complex than the mechanisms championed in this literature; in exchange, we give sequential mechanisms, and our work can facilitate much more general constraints, previously out of reach for this line of work.\n\n> Would it be possible to remove the assumption that the valuations of different agents are independent of one another? Given the era of digitalization, it is possible that agents can communicate or gather information about one another.\n\nThis is a great question. Unfortunately, in mechanism design, broadly speaking, we only know how to get revenue-optimal, or even approximately optimal, mechanisms under the independence assumption. There are known barriers (e.g., computational barriers) for the case of correlated types. That said, there are some important exceptions (and “twists” to the standard model) where correlation can be handled; adapting our framework to work here is an interesting direction for future work."}, {"review_id": "ul5T3k5YlM", "reviewer": "Reviewer_PWNn", "summary": "Based on the influential work of Alaei, the authors introduce a novel, general framework for designing both non-sequential and sequential multi-agent, (approximately-optimal) revenue-maximizing mechanisms for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. The framework relies on an interim relaxation, i.e., relaxation of the feasibility constraints, resulting in interim rules that are feasible in expectation. It also features two-level (online) contention resolution schemes (termed tOCRSs), which are variants of the classic (O)CRSs, and allow for dependencies between the activation of different elements. The framework takes as input such a BIC-IR interim allocation and a tCRS/tOCRS and outputs an approximately optimal mechanism for agents with constrained additive valuations. To find interim rules that are optimal and feasible in expectation, solving a (large) linear program is required. tCRSs and tOCRSs can be constructed in a black-box manner using existing CRSs/OCRSs for a general family of constraints (termed vertical-horizontal constraints). The authors also independently give a tOCRS for Knapsack constraints and a tOCRS for Multi-Choice Knapsack constraints. \n\nThey demonstrate how their framework can construct improved or new (sequential) mechanisms in three applications, which are natural and general enough, with one of them even allowing for arbitrary valuation functions for the agents (albeit computationally inefficient). For two of the applications, they use the novel tOCRS they construct for knapsack constraints. In the appendix, they also give an extension to procurement auctions.", "questions": "See questions under weaknesses and some smaller ones mentioned below.\n\nAre these constant-factor approximations for applications 2 and 3 the first for such settings in the literature? For application 2, it is mentioned that it has been studied only for the welfare objective. Are there lower bounds for these two settings? \n\nThe result for the arbitrary valuation functions is positive (despite not being computationally efficient); what makes it go beyond additive valuations and, apart from the tOCRS for knapsack, could the framework be used as a base, with new techniques on top, to go beyond additive valuations? \n\nI’m trying to understand what VH constraints exactly express. Is there some intuition behind the definition or is the definition mostly tailored to the specific application that the authors associate with the framework? What else do they capture in terms of known settings with combinatorial constraints?\n\nAs mentioned before, the computational efficiency also depends on whether the polytopes have efficient representations for solving the LP efficiently. From well-established mechanisms in the literature or other practical examples, when is this the case?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper makes for a nice read; the contributions (and limitations) are clearly stated and placed in the current OCRS and mechanism design literature, and the proofs are well-written.\n\nThe framework contains several nice components (finding the interim rules, defining and constructing the tCRS/tOCRS, the Bernoulli factory for the probabilities); it’s non-trivial to handle each of them separately and then bring them together. Also, the new tOCRS for knapsack constraints, can also handle mechanisms with arbitrary valuation functions, as demonstrated in Application 3, so it seems to have some nice generalization properties. \n\nWeaknesses:\n\nThe authors provide different results and applications, but I feel without a single point standing out. For instance, the framework is nice and presented as the main contribution of the paper, but then applied only to one of the three applications, which is an interesting enough one to improve upon the constant factor from the paper of Cai and Zhao. However, as mentioned in the submission, this was a subcase in their work, so they designed a broad enough framework that captured also this setting as a special case, and it probably not their main goal to optimize for the constant factor. Could you expand a bit on the importance of the framework and other well-known settings that it improves or provides first approximation guarantees? Or how the techniques used can provide new insights for either the construction of OCRSs or the design of (sequential) allocation mechanisms for other settings that are difficult to tackle? The other two applications are built on the specialized tOCRSs, which are a nice contribution, but maybe mainly of interest for the community working on CRS/OCRS problems for mechanism design. For these reasons, maybe the scope of the paper is a bit limited for NeurIPS and would fit better in either an EconCS or TCS conference.\n\nComputational concerns and applicability: As the authors state in 3.1, the LP is big (already the number of constraints is polynomial in the sum of the support sizes for BIC-IR + rest of polyhedral constraints). How can you deploy such schemes in practice? When all support sizes are small and there is an efficient representation of polytopes the LP step could be fast, does that occur often in practice? Could you expand a bit on how such a framework can be deployed in practice, in which situations, and if/how it can scale on its various parameters for large instances? Also, the construction of the tOCRS depends on the existence of the relevant OCRSs, which should also be easily implementable. The coin flipping processes for the non-constructive steps in the tOCRSs for knapsack might also be computationally demanding.In general, the principle is that when you go for approximately optimal mechanisms, you trade simplicity for approximation, which am not sure is happening here. For demonstrating some of the applicability of the framework and/or the tOCRSs built from scratch, it would be interesting to have some experimental results, e.g., for application 1, for the mechanism in this paper and that of Cai and Zhao (or other heuristics), to compare approximations and computational efficiency in real-world scenarios.", "was_revised": true, "final_justification": "The authors have answered my questions. The paper is well-written and makes a nice theoretical contribution at the intersection of the mechanism design and OCRS literature. I have some concerns about the practical implementation and it would be good to already have some indication whether the framework can be efficiently implemented in some scenarios.", "rebuttal": "Thank you for your review.\n\n> Are these constant-factor approximations for applications 2 and 3 the first for such settings in the literature? For application 2, it is mentioned that it has been studied only for the welfare objective. Are there lower bounds for these two settings?\n\nThis question is also related to the first weakness in your review (“...applied only to one of the three applications…”). First, we note that all three applications use the framework. The procurement setting is also, morally, a fourth application. Second, yes, Applications 2 and 3 give the first known *sequential* mechanisms with constant-factor approximations for such general settings. For Application 1, the result closest in generality is the 70 approximation of Cai and Zhao. To avoid overstating our contribution, we would also like to note that non-sequential optimal mechanisms can be efficiently computed using the framework of Cai et al.; however, these mechanisms are neither simple nor sequential.\n\n>Or how the techniques used can provide new insights for either the construction of OCRSs or the design of (sequential) allocation mechanisms for other settings that are difficult to tackle?\n\nWe agree that new techniques for constructing OCRSs are of broad interest. However, we view this as somewhat beyond the scope of our paper. Our main contribution is not a new general technique for constructing OCRSs, but rather a framework that integrates existing OCRSs into approximately optimal mechanism design, particularly in the sequential setting. That said, our tOCRSs for Knapsack and Multi-Choice Knapsack are new, and we believe this contributes meaningfully to the broader OCRS literature.\n\n>The result for the arbitrary valuation functions is positive (despite not being computationally efficient); what makes it go beyond additive valuations and, apart from the tOCRS for knapsack, could the framework be used as a base, with new techniques on top, to go beyond additive valuations?\n\nThe extension to arbitrary valuations comes from creating a meta-item for each subset of items, and adding the appropriate constraint (each agent can get at most one meta-item); our framework provides enough flexibility to give a sequential mechanism in this setting. To your broader question, our framework could plausibly serve as a base for moving beyond additive valuations more generally; the bottleneck would be getting the appropriate tCRSs and tOCRSs.\n\n>I’m trying to understand what VH constraints exactly express. Is there some intuition behind the definition or is the definition mostly tailored to the specific application that the authors associate with the framework? What else do they capture in terms of known settings with combinatorial constraints?\n\nVH constraints are feasibility constraints for each item (across agents) and **separately** for each agent (across items).  For example, a cardinality constraint that allows for at most $k$ items to be allocated to an agent (e.g., if the agent is $k$-demand) is a per-agent component of a VH constraint. Many settings also require per-item constraints. For example, in limited supply markets, an item might be assigned to at most one agent, or more generally, to at most $k$ agents when $k$ copies are available. Note also that this is an example of a matroid constraint ($k$-uniform matroids). VH constraints can express a wide variety of combinatorial structures, including matroid constraints.\n\nMatroids offer a natural abstraction for various feasibility constraints. For example, transversal matroids: consider allocating houses to $n$ agents, where each agent has a set of acceptable houses; the feasible set of agents that can be allocated forms an independent set of a transversal matroid. Another example is partition and laminar matroids: consider allocating resources fairly when agents belong to different subgroups and want to avoid overallocating to a single subgroup. Resource allocation under matroid constraints is fundamental and well-studied in the literature, e.g.,: \n- Frugality of Truthful Mechanisms. Karlin, Kempe, Tamir. Beyond VCG: FOCS 2005\n- Simple versus Optimal Mechanisms. Hartline, Roughgarden. EC 2009\n- Matroids, Secretary Problems, and Online Mechanisms. Babaioff, Immorlica, Kleinberg. JACM 2018\n- Matroid Prophet Inequalities. Kleinberg, Weinberg. STOC 2012.\n- An Ascending Vickrey Auction for Selling Bases of a Matroid. Bikhchandani, de Vries, Schummer, Vohra. OR 2011.\n- Deferred-Acceptance Clock Auctions and Radio Spectrum Reallocation. Milgrom, Segal. JPE 2017.\n\n>As mentioned before, the computational efficiency also depends on whether the polytopes have efficient representations for solving the LP efficiently. From well-established mechanisms in the literature or other practical examples, when is this the case?\n\nOur LP (LP1) is significantly simpler than the LPs in the Cai et al. framework. In particular, we only require feasibility in expectation, which avoids the more complex ex-post constraints handled in their work. Is our framework simple enough to be practical as a black-box tool in practice? That depends on the application at hand. As with much of algorithmic mechanism design (including, e.g., the framework of Cai et al.), there is a tension between theoretical generality and real-world deployability. That said, many real-world mechanisms (e.g., see the recent work on autobidding) are governed less by formal polytime guarantees and more by having “clean knobs” to tune or reason about. Our framework separates the interim form of the mechanism (solution of the LP) from its ex-post implementation (tOCRSs), so our work does contribute to this agenda."}, {"review_id": "pISwUESXtv", "reviewer": "Reviewer_9suo", "summary": "This paper studies the problem of designing revenue-maximizing mechanisms for selling m heterogeneous items to \nn additive agents, subject to downward-closed feasibility constraints. The authors propose a framework based on the following three steps:\n\n- Relaxing the feasibility constraints to allow interim allocation/payment rules that only satisfy the constraints in expectation.\n\n- Solving a linear program to compute an optimal Bayesian incentive-compatible (BIC) and individually rational (IR) interim solution.\n\n- Rounding the fractional solution using an extension of contention resolution scheme (OCRS) techniques.\n\nThe main contribution is the introduction of a new variant of OCRS that allows dependencies between the activations of elements, broadening the applicability of the framework. They also apply their framework to obtain approximation guarantees, including:\n\n- A 3.16-approximation sequential mechanism under “matroid Vertical-Horizontal” constraints (although the exact setting is not clearly defined—see comments).\n\n- A sequential, efficiently computable 10-approximation mechanism for additive agents under knapsack constraints.\n\n- A 9-approximation mechanism for agents with \"arbitrary\" valuations under knapsack constraints (this needs clarification—see comments).", "questions": "In the Applications section, when you say agents have arbitrary valuation functions, does that mean monotonicity, subadditivity, or other standard assumptions can be violated? Please clarify the assumptions.\n\nIn the first application (matroid VH constraints), can an item be allocated to multiple agents? Also, what does it mean for agents to \"form a matroid\"?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I think the extension of the (O)CRS framework to handle dependencies among elements is technically nontrivial and represents an important contribution. The framework is flexible, applies to multiple constraint types, and in some cases improves over prior results. \n\nThe presentation of the paper can be significantly improved. Key definitions, intuition, and algorithmic descriptions are often compressed or interleaved, which can make the material hard to follow, especially for readers less familiar with the area. I understand that some of these issues are due to the lack of space, but the paper as it is now is hard to follow.", "was_revised": true, "final_justification": "The authors have answered my questions. I think my concerns about presentation can be resolved if the paper is accepted. The paper has merits, and I am positive about its acceptance. However, I am not fully convinced that the novelty of the results and the framework is sufficient to strongly support acceptance. Therefore, my evaluation remains weak accept.", "rebuttal": "Thank you for your review. We will incorporate all reviewer feedback to improve the presentation.\n\n> In the Applications section, when you say agents have arbitrary valuation functions, does that mean monotonicity, subadditivity, or other standard assumptions can be violated? Please clarify the assumptions.”\n\nYes, the valuation functions in this application can be arbitrary: non-monotone, subadditive, superadditive, anything works. The only constraint is that the value is non-negative for every subset of items. We will clarify this.\n\n> In the first application (matroid VH constraints), can an item be allocated to multiple agents? Also, what does it mean for agents to \"form a matroid\"?\n\nAllocating an item to multiple agents is allowed, if desired. It can also be disallowed, if desired. More generally, VH constraints are feasibility constraints for each item (across agents) and **separately** for each agent (across items).  For example, a cardinality constraint that allows for at most $k$ items to be allocated to an agent (e.g., if the agent is $k$-demand) is a per-agent component of a VH constraint. Many settings also require per-item constraints. For example, in limited supply markets, an item might be assigned to at most one agent, or more generally, to at most $k$ agents when $k$ copies are available. Note also that this is an example of a matroid constraint ($k$-uniform matroids). VH constraints can express a wide variety of combinatorial structures, including matroid constraints.\n\nMatroids offer a natural abstraction for various feasibility constraints. For example, transversal matroids: consider allocating houses to $n$ agents, where each agent has a set of acceptable houses; the feasible set of agents that can be allocated forms an independent set of a transversal matroid. Another example is partition and laminar matroids: consider allocating resources fairly when agents belong to different subgroups and want to avoid overallocating to a single subgroup. Resource allocation under matroid constraints is fundamental and well-studied in the literature, e.g.,: \n- Frugality of Truthful Mechanisms. Karlin, Kempe, Tamir. Beyond VCG: FOCS 2005\n- Simple versus Optimal Mechanisms. Hartline, Roughgarden. EC 2009\n- Matroids, Secretary Problems, and Online Mechanisms. Babaioff, Immorlica, Kleinberg. JACM 2018\n- Matroid Prophet Inequalities. Kleinberg, Weinberg. STOC 2012.\n- An Ascending Vickrey Auction for Selling Bases of a Matroid. Bikhchandani, de Vries, Schummer, Vohra. OR 2011.\n- Deferred-Acceptance Clock Auctions and Radio Spectrum Reallocation. Milgrom, Segal. JPE 2017."}, {"review_id": "NfnIWNwan4", "reviewer": "Reviewer_hY62", "summary": "The paper suggests a new method, called two-level (O)CRS, that allows for \"Vertical-horizontal\" constraints (i.e., matroid constraints over both which items each agent gets, and which agents an item is allocated to). The paper shows how existing (O)CRSs can be combined into a t(O)CRS, and apply it to some settings, most notably improving [Cai & Zhao '17]'s approximation of 70 for the optimal revenue of an auction for constrained additive bidders, to around 3.16.", "questions": "Q1: I didn’t manage to understand the motivation for the vertical-horizontal constraints. I understand why the items allocated to an agent will have matroid constraints. But what does it mean that the agents that get item j satisfy matroid constraints? Isn’t it always Ex-post allocated to a single agent? Please explain the settings, and also references to works that previously discussed it before could be helpful. \nI see later that you mention [14] that restrict each item to be allocated to at most one agent: So maybe another way to ask my question is, so isn’t this guarantee already built into the CRS framework as the feasibility constraint (I guess not)? \n\nQ2: What is the argument for the last inequality in 1112? Why is the sum of probabilities for these elements to be active less than 4b (I can understand where the b is coming from, but why 4)? Same question for the last inequality of 1123, where it seems you use the fact that the sum of all preceding k_{i,j} are less than K/2, and again show a bound of 4 for the same sum of probabilities (but somehow here b is already outside the parantheses? so shouldn’t it be 2b^2/(1+4b)?)", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- The technical contribution is significant, and in some cases the results improve over the state of the art.\n\n- The paper is well-written\n\n- Personally I found Section B very helpful, as it provided a good introduction to the topic of Bernoulli factories. \n\nWeaknesses:\n\n- Since the topic is quite heavy and I'm not familiar with it, even though the paper is clearly written, there were still some things I couldn't figure out, which I detail here and in the questions:\n\nCorollary 1: It’s not clear from the statement of Theorem 2 that if you combine a CRS over items constraints with an OCRS over agent constraints you get a tOCRS (rather than tCRS). By the statement it seems like if you combine two CRSs, you get a tCRS, and if you combine two OCRSs, you get a tOCRS. \n\nNotice that in the proof of Theorem 1 you didn’t explicitly discuss the revenue approximation guarantee, but it’s pretty clear given the proof.", "was_revised": true, "final_justification": "I was in support of accepting the paper and remain so. I had two minor questions and the rebuttal addressed them promptly. The other reviewers seem to lean towards acceptance as well, though they raise an issue of whether the algorithms are complicated for practical application.", "rebuttal": "Thank you for your review.\n\n>Corollary 1: It’s not clear from the statement of Theorem 2 that if you combine a CRS over items constraints with an OCRS over agent constraints you get a tOCRS (rather than tCRS). By the statement it seems like if you combine two CRSs, you get a tCRS, and if you combine two OCRSs, you get a tOCRS.\n\nThis is a fair question. Indeed, combining a CRS over item constraints with an OCRS over agent constraints *does* yield a valid tOCRS. We agree that this may not be completely transparent from the high-level statement, and we’ll clarify this.\n\nTo explain, it’s simple to present the argument from a mechanism design perspective. Each agent arrives online and declares their $d_i$ ($d_i$ from Definition 4). The mechanism needs to decide which items to give them so that the final allocation is *always* feasible. We can run a CRS on the ``agent constraint,’’ since all the elements for that constraint correspond to items that will be allocated to that agent, and are all items already present. At the same time, we can independently run an OCRS per item with the agent constraints. We allocate the item to this agent only if **both** the OCRS and CRS agree to this allocation. Since for a particular element/item $e_{i,j}$ the $i$-th CRS and the $j$-th OCRS are oblivious of each other, with separate randomness, the probability that both are active is simply the product of the probabilities of being active in each process. The resulting procedure is a valid tOCRS by definition. \n\nWe’ll add a sentence or two to Theorem 2 to make this clearer in the final version.\n\n>I didn’t manage to understand the motivation for the vertical-horizontal constraints. I understand why the items allocated to an agent will have matroid constraints. But what does it mean that the agents that get item j satisfy matroid constraints? Isn’t it always Ex-post allocated to a single agent? Please explain the settings, and also references to works that previously discussed it before could be helpful. I see later that you mention [14] that restrict each item to be allocated to at most one agent: So maybe another way to ask my question is, so isn’t this guarantee already built into the CRS framework as the feasibility constraint (I guess not)?\n\n\nVH constraints are feasibility constraints for each item (across agents) and **separately** for each agent (across items). So, we have constrains on which items can go to a single agent $i$ --- e.g., “agent $i$ can get at most $k$ items” --- and constraints on how a single item $j$ can be allocated across agents --- e.g., “there are $k$ copies of item $j$, so item $j$ can be allocated to at most $k$ agents” (so, indeed, we allow for an item to be allocated to multiple agents). Perhaps the phrasing of our setup (line 150 “...$m$ indivisible, heterogeneous items…”) is what caused the confusing regarding the second point; we can rephrase.\n\n\n>What is the argument for the last inequality in 1112? Why is the sum of probabilities for these elements to be active less than 4b (I can understand where the b is coming from, but why 4)? \n\nThank you for catching this! In the second to last equality there is a $b$ missing outside the parenthesis, which we will update. Intuitively, from the perspective of any given agent $i$, an element $e_{i’, j’}$ is active with probability $b w_{i’,j’}$ (they do not know $d_{i’}$), and an element $e_{i,j’}$ is active with probability $b x_{i,j’}(d_i)$. \n\nRegarding the “4” factor: from the first condition in Definition 4, and since heavy items cannot weigh less than $K/2$, we have that the sum of $x_{i,j}(d_i)$ cannot be more than $2$. Similarly, from the second condition of Definition 4, and since the heavy items cannot weigh less than $K/2$, we have that the sum of $w_{i,j}$s cannot be more than $2$ as well. Combining we get the $4$. This is tight: there might have two items that weigh $K/2 + \\epsilon$ each and the agent almost always receives both. \n\n>Same question for the last inequality of 1123, where it seems you use the fact that the sum of all preceding k_{i,j} are less than K/2, and again show a bound of 4 for the same sum of probabilities (but somehow here b is already outside the parantheses? so shouldn’t it be 2b^2/(1+4b)?)\n\nThere is no extra $b$ term (the omission was the mistake earlier). As for the $4$ bound, the argument is similar: from Definition 4 we have that the expected weight of elements that are active before agent $i$’s turn cannot be more than $K$, and the expected weight of elements that are active in $i$’s round cannot be more than $K$ as well. Combining the two inequalities we get the desired 2K bound."}]

Author rebuttal:

Meta-review: This theoretical paper introduced a framework to design revenue maximizing mechanisms under feasibility constraints. The paper presented a few applications of their framework in various special cases. Reviewers found the problem important, the theoretical results solid, nontrivial, and useful from a theoretical point of view. The main reservation is the hardness to implement in practice. Some reviewers found the paper hard to read while other found it well-written, especially the proofs. The overall sentiment slightly went up after the discussions and rebuttal.
Decision: Accept (poster)