Mechanism Design via the Interim Relaxation

Thank you for your review.

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.

This 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.

To 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.

We’ll add a sentence or two to Theorem 2 to make this clearer in the final version.

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)?

VH 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.

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)?

Thank 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)$.

Regarding 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.

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)?)

There 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.

Thank you for your review. We will incorporate all reviewer feedback to improve the presentation.

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.”

Yes, 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.

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"?

Allocating 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.

Matroids 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.,:

• Frugality of Truthful Mechanisms. Karlin, Kempe, Tamir. Beyond VCG: FOCS 2005
• Simple versus Optimal Mechanisms. Hartline, Roughgarden. EC 2009
• Matroids, Secretary Problems, and Online Mechanisms. Babaioff, Immorlica, Kleinberg. JACM 2018
• Matroid Prophet Inequalities. Kleinberg, Weinberg. STOC 2012.
• An Ascending Vickrey Auction for Selling Bases of a Matroid. Bikhchandani, de Vries, Schummer, Vohra. OR 2011.
• Deferred-Acceptance Clock Auctions and Radio Spectrum Reallocation. Milgrom, Segal. JPE 2017.

Thank you for your review.

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?

This 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.

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?

We 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.

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?

The 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.

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?

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.

Matroids 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.,:

• Frugality of Truthful Mechanisms. Karlin, Kempe, Tamir. Beyond VCG: FOCS 2005
• Simple versus Optimal Mechanisms. Hartline, Roughgarden. EC 2009
• Matroids, Secretary Problems, and Online Mechanisms. Babaioff, Immorlica, Kleinberg. JACM 2018
• Matroid Prophet Inequalities. Kleinberg, Weinberg. STOC 2012.
• An Ascending Vickrey Auction for Selling Bases of a Matroid. Bikhchandani, de Vries, Schummer, Vohra. OR 2011.
• Deferred-Acceptance Clock Auctions and Radio Spectrum Reallocation. Milgrom, Segal. JPE 2017.

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?

Our 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.

Thank you for your review. We comment on some of the weaknesses you point out in your review.

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?

(Markdown was having issues with $p^*_{i,j}(v_i)$, so we will be using $p$ in this response)

In 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(.)$.

Due 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.

The construction procedures of tOCRs is only illustrated for VH family or more specifically, Knapsack constraints.

We 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.

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.

This 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.

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.

Yes, 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.

It is unclear whether the approximation ratio is ratio; a comparison with the related work would be helpful.

We 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.

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.

This 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.