1 Introduction↩︎

Combinatorial assignment is a flexible and powerful model for allocation of indivisible resources without the use of money or of explicit priorities. Combinatorial assignment captures many complex allocation problems including course allocation [1], [2], allocation of food donations to food banks [3], [4], and refugee resettlement [5], [6]. In these settings, agents typically reveal their preferences over bundles of resources and the designer hopes to pick a fair and efficient allocation.

In order to achieve fairness, mechanisms that allocate indivisible resources often use randomization. It is therefore important to ensure that the mechanism’s fairness and efficiency properties are desirable both ex ante (i.e., prior to the realization of the lotteries) and ex post. In this paper, we will focus on canonical ex-ante efficiency and fairness requirements for a random mechanism based only on ordinal preference information: ordinal efficiency and ordinal envy-freeness [7].¹ Ordinal efficiency requires that no alternative assignment exist in which every agent receives a lottery that first-order stochastically dominates (ordered by their preferences) the original one. Ordinal efficiency implies ex-post efficiency by ensuring that ex-post inefficient allocations are never assigned a positive probability. Ordinal envy-freeness requires that every agent receive a lottery that first-order stochastically dominates the lottery received by any other agent. Since we only assume that agents’ preferences over lotteries satisfy monotonicity (rather than be expected-utility maximizers)², ordinal efficiency and ordinal envy-freeness are the natural ex-ante analogues of Pareto-efficiency and ex-post envy-freeness.³

There is no existing mechanism for combinatorial assignment that simultaneously achieves desirable ex-ante and ex-post fairness and efficiency properties. Some ex-post efficient mechanisms that might appear fair, such as the Random Serial Dictatorship (RSD) and the Approximate Competitive Equilibrium from Equal Incomes (ACEEI) [1], are neither ordinally efficient nor ordinally envy-free. Other mechanisms, such as the Bundled Probabilistic Serial (BPS) [11] are ordinally efficient and ordinally envy-free, but do not provide any ex-post envy-freeness guarantees. While the RSD mechanism is strategyproof, ACEEI and BPS mechanisms are only strategyproof in the large [12]. Indeed, there is a stark tradeoff between ordinal efficiency, truthtelling incentives and minimal forms of fairness even for the simplest allocation problems [7].

The main insight of our paper is that by using a single market-clearing price vector to guide the ex-ante and ex-post allocations, the designer can simultaneously achieve ordinal efficiency, ordinal envy-freeness, approximate ex-post efficiency, approximate ex-post envy-freeness, as well as strong truthtelling incentives in large markets even in the most general combinatorial assignment settings. To achieve this, we introduce a new version of competitive equilibrium in an economy with an artificial currency (henceforth, “tokens”) in spirit of [10] and [1]. The key technical twist is that we make the budgets of tokens be exogenously random for all agents. Our Competitive Equilibrium from Random Incomes (CERI) works as follows: agents are allocated distributions of token budgets, they report their ordinal preferences over bundles, and the designer computes their expected demand by averaging over optimal bundles at each budget realization.⁴ Finally, the designer computes a linear and anonymous equilibrium price vector that equates aggregate expected demand to supply for every good. At CERI prices, an agent’s allocation is therefore a lottery (or, more generally, a distribution) over optimal bundles at different budgets. CERI prices turn out to be precisely the prices that ensure desirable properties of the ex-ante and ex-post allocations.

First, we deal with existence and implementability. For a given profile of budget distributions, it might not be possible to exactly equate aggregate expected demand with supply (e.g., when budgets are identical and deterministic). However, we show that if distributions of budgets are continuous for all agents, then a CERI always exists (Theorem 1).⁵ Since CERI only outputs an ex-ante allocation (i.e., lottery for each agent), the key concern is whether a CERI allocation is implementable as a single lottery over ex-post feasible allocations. Unlike the unit-demand setting, we cannot merely rely on the Birkhoff-von Neumann (BvN) Theorem [13], [14] to guarantee exact implementability. However, Theorem 2 shows that any CERI allocation can be implemented as a lottery over approximately feasible allocations supported by CERI prices and by appropriate realizations from correlated token budget distributions. Second, we turn to efficiency. We show that any CERI allocation is ordinally efficient (i.e., our First Welfare Theorem). We also show that any ordinally efficient allocation can be supported by a CERI with appropriate (independent) distributions of agents’ token budgets (i.e., our Second Welfare Theorem). Hence, an allocation is ordinally efficient if and only if it is a CERI allocation (Theorem 3). By connecting this characterization to approximate implementability established earlier, we show that any CERI allocation is implementable over near-feasible Pareto-efficient allocations (Theorem 4). While the economic content of our characterization—that efficient and equilibrium outcomes coincide in competitive markets—might be familiar from general equilibrium theory [15], [16], the connection between ordinal efficiency and competitive pricing that we establish is novel. Additionally, we believe that our characterization of ordinally efficient allocations opens a door towards exploring market design applications in which token budgets are deliberately set unequally by the designer in order to correct for natural asymmetries between agents. For example, food banks are allocated different amounts of token currency to account for the different sizes of their client populations [3].

Third, we discuss envy-freeness. We show that if token budget distributions are identical then CERI produces an ordinally envy-free allocation (Theorem 5). Moreover, if budget distributions are on a sufficiently small support, then any realization of CERI is ex-post envy-free up to one good (EF1) [1], [17]. Therefore, we can simultaneously ensure that the lottery allocation is ordinally envy-free and that all ex-post allocations are EF1 by setting agents’ budget distributions to be identical and by requiring that they have a sufficiently small support.

The power of the single market-clearing CERI price vector becomes especially clear when we consider truthtelling incentives of mechanisms for combinatorial assignment. As a warm-up, we combine the results above in Theorem 6 to show that, under identical budget distributions, a mechanism (CERI-S) that uses CERI as its allocation rule is ordinally (and hence ex-ante cardinally) envy-free entailing that it is strategyproof in the large [12]. However, strategyproofness in the large provides a relatively weak incentive for truthtelling when we consider the whole market. Specifically, strategyproofness in the large and even stronger notions of asymptotic strategyproofness [18] do not ensure that, in any finite economy, a positive fraction of agents have a dominant strategy to truthfully report their preferences. To address this limitation, we introduce uniform strategyproofness which is a far stronger incentive compatibility notion in large markets than those in the literature. Uniform strategyproofness requires that, as the market grows large, all agents have a dominant strategy to truthfully report their preferences with a probability arbitrarily close to 1. To this end, we develop another CERI-based mechanism, called CERI-L, which satisfies uniform strategyproofness while preserving asymptotic ordinal efficiency.

The technical idea behind CERI-Lis an exogenously random grid of the type space. After agents report their types, the mechanism selects a grid point which approximates the type distribution. In CERI-L, we compute a CERI using the grid point’s approximation of the type distribution and allocate bundles to agents using the prices from this CERI. The grid choice balances efficiency and the provision of incentives. A coarse grid reduces the likelihood that an agent’s misreport can affect the type distribution approximation, ensuring uniform strategyproofness. On the other hand, a fine grid closely reflects the original type distribution and leads to allocations that are close to efficient under truthful reporting. However, a finer grid gives the agents stronger incentives to misreport their preferences. By carefully choosing the size of the random grid, we demonstrate that CERI-L is uniformly strategyproof, asymptotically ordinally efficient, ordinally envy-free, and ex-post EF1 (Theorem 7). In “small” markets, away from the asymptotic limit, while CERI-L is not ordinally efficient, it can nevertheless be realized as a lottery over approximately feasible, Pareto-efficient allocations.

Taken together, our paper makes three key contributions. First, we introduce the idea of using a single market-clearing (CERI) price vector in order to achieve desirable ex-ante and ex-post properties of combinatorial assignment mechanisms (Table 1). Second, we offer a novel price-theoretic lens on existing mechanisms for assignment of indivisible resources. Third, we illustrate how CERI can be used to develop new mechanisms such as CERI-L  and to pinpoint the balance between efficiency, envy-freeness and incentives, both in large and small markets.

After reviewing related work, we present the combinatorial assignment model in Section 3. Then in Section 4 we define CERI, provide existence and implementability results, discuss the characterization of ordinally efficient allocations, and describe envy-freeness properties. In Section 5 we describe CERI-Sand use CERI to offer a price-theoretic foundation for other assignment mechanisms in the literature. In Section 6 we introduce CERI-Land describe its (large-market) properties. Section 7 is a conclusion.

2 Relationship to existing work↩︎

Our paper is related to three strands of the literature. First, we are able to illuminate the price-theoretic foundations of existing mechanisms (such as the Probabilistic Serial mechanism) for assignment with unit-demand agents. As a result, we can offer implementations of these mechanisms which have stronger incentive properties. Second, we can combine the desirable properties of existing mechanisms for combinatorial assignment (ACEEI and Bundled Probabilistic Serial) into a single mechanism. Third, our results are broadly related to a literature on pseudomarkets in which agents are assumed to be expected utility maximizers. In summary, the benefit of using a single, anonymous price vector in CERI is that it fully characterizes ordinally efficient outcomes, allows us to obtain EF1 allocations and yields uniform strategyproofness. The cost is that in our setting ex-post efficient economies are only approximately feasible. While feasibility violations could be removed by using nonlinear pricing, it might add complexity, lose incentive guarantees and create potential opportunities for arbitrage in probability shares.

Ordinal preferences: unit-demand assignment↩︎

Results from our paper shed a new light on existing assignment problems for unit-demand agents with ordinal preferences. In a celebrated paper, [7] introduced the Simultaneous Eating mechanisms that characterize all ordinally efficient allocations. A special case, the Probabilistic Serial mechanism in which all “eating speeds” are the same, delivers an ordinally envy-free outcome. Hence, for the unit-demand setting, CERI allocations (for different profiles of budget distributions) coincide with the allocations produced by Simultaneous Eating mechanisms (for different profiles of “eating speeds”). Our characterization entails that in the unit-demand setting an allocation is ordinally efficient if and only if every ex-post efficient allocation in its support can be supported by a single, anonymous equilibrium price vector. Moreover, an ordinally efficient allocation is ordinally envy-free if and only if agents face the same budget distributions in the CERI. In Section 5, we provide a mapping between the “eating speeds” and “finish times” in the Probabilistic Serial mechanism and the budgets and prices in a CERI.

[7] showed that the Probabilistic Serial mechanism is not strategyproof.⁶ However, [20] noted that the Probabilistic Serial mechanism is strategyproof in a large enough replica economy. [21] demonstrated the asymptotic equivalence of Probabilistic Serial to the Random Serial Dictatorship. [18] then established a broader equivalence between asymptotically strategyproof and asymptotically efficient mechanisms. Compared to previous work on large markets, we strengthen the notion of asymptotic strategyproofness to uniform strategyproofness. Moreover, a special case of CERI-Lis an asymptotically ordinally efficient and uniformly strategyproof implementation of the Probabilistic Serial mechanism.

Ordinal preferences: combinatorial assignment↩︎

Our work is intimately related to combinatorial assignment mechanisms with ordinal preferences [1], [2], [22]. The most celebrated such mechanism is the ACEEI introduced by [1]. Budish shows that one can find an equilibrium price vector which exactly clears a convexified market after a small budget perturbation. He then shows that one can find a budget perturbation which ensures approximate ex-post market-clearing. Moreover, ACEEI allocations are ex-post EF1.

However, the ACEEI mechanism might be neither ordinally efficient nor ordinally envy-free. In the unit-demand setting, the ACEEI mechanism coincides with RSD (see Section 5). For the multiunit-demand setting, we provide an example in Appendix 9.2 that demonstrates that there may be only one deterministic allocation—an empty one—that satisfies ACEEI’s ex-post market-clearing condition, but which is ordinally inefficient. The reason that the ACEEI mechanism is neither ordinally efficient nor ordinally envy-free is that it computes a different set of market-clearing prices for different budget perturbations, rather than, as CERI does, a single set of market-clearing prices for a given profile of budget distributions.⁷ As a consequence, CERI allocations are ordinally efficient (and ordinally envy-free with appropriate budget distributions) and, in fact, we can show that the existence of a CERI implies the existence of an ACEEI (Appendix 9.1). A final difference between the properties of ACEEI and of CERI is that the ACEEI allocation bounds depend on the market size and are expressed in terms of the \(\ell^2\)-norm whereas CERI bounds are expressed good-by-good and are independent of the market size (i.e., in the \(\ell^\infty\)-norm). The good-by-good bounds which are invariant to the market size are often more practical from a market design perspective because by adjusting the capacities of individual goods the designer can ensure that none of the bounds are exceeded ex-post [23]. Hence, our CERI-Smechanism replicates the approximate ex-post efficiency, ex-post EF1, and strategyproofness in the large properties of ACEEI while additionally ensuring ordinal efficiency and ordinal envy-freeness (Theorem 6).

[11] proposed the BPS mechanism for combinatorial assignment. The BPS mechanism extends the PS mechanism to the combinatorial setting. The BPS mechanism is ordinally efficient and ordinally envy-free. In Section 5, we provide a mapping between the “eating speeds” and “finish times” in the BPS mechanism and the budgets and prices in a CERI. But, unlike CERI, BPS neither guarantees ex-post EF1 nor characterize all ordinally efficient allocations (as shown in Example 3).

Overall, mechanisms based on CERI can combine the best features of ACEEI—i.e., ex-post efficiency after adjusting supply and EF1—with the best features of the BPS mechanism—ordinal efficiency and ordinal envy-freeness—while strengthening the incentive properties of these mechanisms in large markets [12] (see Table 1).

Cardinal preference representations↩︎

There is a substantial literature on efficient and fair allocation of indivisible goods in which agents are assumed to be expected utility maximizers.⁸ [27] explored how to combine various desirable ex-ante and ex-post properties (what they called the “best of both worlds”) and derived a number of impossibility results under the assumption of additive preferences over bundles. CERI mechanisms can also claim to satisfy the “best of both worlds” property. [28] show that for a class of partition-based utility functions one can guarantee allocations that are exactly realizable (i.e., the lottery allocation is assumed to come from the set of lotteries over ex-post feasible allocations), ex-ante cardinally efficient and ex-ante cardinally envy-free. Their notion of efficiency is stronger than ours, but their notion of envy-freeness is weaker. Moreover, imposing exact implementability means that ex-post efficient allocations are supported by different market-clearing price vectors which weakens the large-market incentive compatibility properties of their solution. Finally, a strand of work explored “pseudomarket” allocation rules (reminiscent of ours) in which expected-utility maximizing agents can select their most preferred lotteries at competitive prices using budgets of tokens [23], [29]–[32]. In this setting, [33] provide First and Second Welfare Theorems while [34] provide necessary and sufficient conditions for exact implementability in a sufficiently rich preference domain.

We only assume that agents’ preferences are monotonic in probabilities so the designer is only required to elicit an ordinal ranking over bundles. Indeed, there is evidence that relying on ordinal preferences is more robust from a practical market design perspective: Recent work suggests that market participants (e.g., in course allocation) make more mistakes when their ranking over bundles is sensitive to the cardinal representation of preferences [35].

3 Model↩︎

There is a finite set \(M\) of goods, with \(|M|=m\), and a finite set \(N\) of agents, with \(|N| = n\). Each good \(j\) has a finite integer capacity \(c^{j}\in \mathbb{N}\).

A bundle is an integral vector, \({\boldsymbol{x}}\in \mathbb{N}^m\). If \({\boldsymbol{x}}\) contains good \(j\), we use \(({\boldsymbol{x}}-{\boldsymbol{e}}^j)^+\) to denote the bundle \({\boldsymbol{x}}\) with one unit of good \(j\) removed. The bundle consumed by agent \(i\) is denoted by \({\boldsymbol{x}}_{i}\). There might be further constraints on consumption; let \(\Psi_i\subseteq \mathbb{N}^m\) denote the set of acceptable bundles for agent \(i\). We assume that \({\boldsymbol{0}}\in \Psi_i\) for all \(i\), meaning each agent has an outside option. However, we do not assume free disposal, indicating that if a bundle \({\boldsymbol{x}}_{i}\) is acceptable to agent \(i\), it is possible that \({\boldsymbol{x}}'_{i}\leq {\boldsymbol{x}}_{i}\) is not acceptable. Furthermore, we assume the maximum size of an acceptable bundle for any agent is at most \(\Delta\).⁹ An (ex-post or deterministic) allocation \(\mathbf{X}=({\boldsymbol{x}}_{1}, \ldots, {\boldsymbol{x}}_{n})\) is a list of acceptable bundles, one for each agent. Allocation \(\mathbf{X}\) is feasible with respect to capacities \(\mathbf{c^{}}\) if \(\sum_{i\in N} {\boldsymbol{x}}_{i} \leq \mathbf{c^{}}\).

Each agent \(i\) has a strict preference relation \(\succ_i\) over the set \(\Psi_i\). We assume (without loss) that \({\boldsymbol{0}}\) is the least preferred bundle for all agents. We denote the weak relation of \(\succ_i\) by \(\succeq_i\); i.e., \({\boldsymbol{x}}\succeq_i{\boldsymbol{y}}\) means either \({\boldsymbol{x}}\succ_i{\boldsymbol{y}}\) or \({\boldsymbol{x}}={\boldsymbol{y}}\), and denote the preference profile of all agents by \(\succ:= (\succ_i)_{i\in N}\). We use \(\succ_{-i}\) to denote the preference profile of agents excluding agent \(i\).

In addition to (ex-post) allocations, our paper considers (ex-ante) lottery allocations and their associated stochastic order. Let \(\mathcal{L}(\Psi_i)\) denote the set of lotteries over \(\Psi_i\). We use \(\widetilde{{\mathbf{x}}}_{i}\in \mathcal{L}(\Psi_i)\) to indicate a lottery obtained by agent \(i\) and \(\mathbb{E}\left[\widetilde{{\mathbf{x}}}_{i}\right]\) to denote expectation of this lottery.

A lottery allocation, \(\widetilde{{\mathbf{X}}}_{}=(\widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n})\in \mathcal{L}(\Psi_1)\times ..\times \mathcal{L}(\Psi_n)\), is a list of lotteries over the acceptable bundles, one for each agent. The lottery allocation \((\widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n})\) is feasible with respect to capacity \(\boldsymbol{c}\) if \(\sum_{i=1}^n \mathbb{E}\left[\widetilde{{\mathbf{x}}}_{i}\right] \le \boldsymbol{c}\). A lottery allocation \(\widetilde{{\mathbf{X}}}_{}\) is implementable over a set of ex-post allocations (which are not necessarily feasible) if it can be realized as a lottery over this set of allocations. Since our primitives are ordinal preferences rather than their cardinal representations, we will assume that agent \(i\) prefers lottery \(\widetilde{{\mathbf{x}}}_{}\) to lottery \(\widetilde{{\mathbf{y}}}_{}\) if and only if \(\widetilde{{\mathbf{x}}}_{}\) (first-order) stochastically dominates \(\widetilde{{\mathbf{y}}}_{}\) (when ordered by \(\succ_i\)).

Note that stochastic dominance places only very weak assumptions on agents’ preferences over lotteries viz. that preferences satisfy monotonicity.¹⁰ In particular, we do not assume that agents are expected utility maximizers.¹¹

An economy is a tuple \(\mathcal{E}=(N,M,\mathbf{c^{}}{}, (\Psi_i)_{i\in N}, \succ)\). We shorten this to \(\mathcal{E}=(\mathbf{c}, \succ)\), as capacities \(\mathbf{c}\) and preferences \(\succ\) completely define the economy. A (direct) mechanism \(\Phi(\cdot)\) maps every economy to a lottery allocation, and \(\Phi_i(\cdot)\) denotes the lottery obtained by agent \(i\) in this mechanism. We say that a mechanism has an ex-ante property P if its lottery allocation has property P; we say that a mechanism has an ex-post property Q if all realizations of the mechanism’s lottery allocation have property Q.

4 Competitive Equilibrium from Random Incomes↩︎

We first describe our novel equilibrium concept. Consider a random variable \(\mathcal{B}_{}\ge 0\) which we call a random income. For any agent \(i\), price vector \({\boldsymbol{p}}\ge 0\) and random income \(\mathcal{B}_{i}\), define the following random variable \[\label{eq:xhat} {\mathcal{X}}_{i}({\boldsymbol{p}},\mathcal{B}_{i}) := \left\{\max_{\succ_{i}} \{{\boldsymbol{x}}_{}: {\boldsymbol{x}}_{} \in \Psi_{i} \text{ and } {\boldsymbol{p}}\cdot {\boldsymbol{x}}_{} \leq b_{i} \} \;\; \middle| \;\; b_{i}\sim \mathcal{B}_{i} \right\} .\tag{1}\] We call \({\mathcal{X}}_{i}({\boldsymbol{p}},\mathcal{B}_{i})\) the random demand of the agent \(i\). The realizations of \({\mathcal{X}}_{i}\) are the optimal bundles for agent \(i\) at prices \({\boldsymbol{p}}\) when \(i\)’s budget is drawn from the distribution \(\mathcal{B}_{i}\). Denote agent \(i\)’s expected demand by \(\mathbb{E}\left[{\mathcal{X}}_{i}({\boldsymbol{p}},\mathcal{B}_{i})\right]\), where the expectation is over \(\mathcal{B}_{i}\).

Using this definition, our equilibrium concept is intuitive: when each agent receives what they demand given their random incomes, the markets for all goods clear exactly in expectation.

We refer to a lottery allocation \(\widetilde{{\mathbf{X}}}_{}\) as a CERI allocation if there exists a price vector such that, together with \(\widetilde{{\mathbf{X}}}_{}\), it forms a CERI. Similarly, a price vector is called CERI prices if it corresponds to the price vector of a CERI. In Section 5, we define a CERI mechanism, which explicitly describes how the concept of CERI can be used in an allocation mechanism.

A CERI allocation is a profile of independent lotteries over acceptable bundles. In order to make such an allocation economically meaningful, we must ensure that this lottery allocation can be implemented as a lottery over ex-post allocations.

An ex-post implementation of a CERI is a joint distribution over incomes (in which the marginals coincide with the agents’ budget distributions) supported by a set of ex-post allocations in which every agent gets their most preferred bundle under CERI prices. This definition entails one of the key conceptual contributions of the paper: the allocations in the support of any ex-post implementation are governed by a single CERI price vector.

We call an ex-post implementation of a CERI feasible if all supporting allocations are feasible, i.e., \(\sum_{i=1}^n x_i^\mathbf{w} \leq \mathbf{c^{}}\); in this case, each \(\mathbf{X}^{\mathbf{w}}\) is a competitive equilibrium allocation with deterministic incomes \(\mathbf{w}\) and supported by the CERI price vector \({\boldsymbol{p}}\). When agents have unit demand, a feasible ex-post implementation of the CERI always exists by the Birkhoff–von Neumann Theorem [13], [14]. Unfortunately, due to the presence of combinatorial demand, in general it is impossible to implement a lottery allocation over feasible ex-post allocations (no matter which prices they are supported by). The reason is intuitive: the joint distribution of incomes \(\mathcal{D}\) might allow several agents to independently draw a large budget and demand the same desirable bundle that cannot be provided by the designer. We therefore allow the designer to relax the capacity of any good in any ex-post allocation by a small amount in order to achieve approximate implementability.

To illustrate the definitions of CERI, exact ex-post implementation and \(\kappa\)-near-feasible ex-post implementation, consider the following example.

Existence and Implementability↩︎

A CERI is not guaranteed to exist for all profiles of budget distributions (e.g., when budgets are deterministic). Nonetheless, we establish that a CERI always exists when the budget distributions are continuous.

The crucial observation in the proof of Theorem 1 is that with continuous income distributions, random demand is continuous in the lottery space. This allows us to apply a standard fixed-point argument.

For discrete distributions of agents’ budgets, however, a CERI might not exist. Yet, we can slightly perturb the budget profile so that a CERI exists. Specifically, for any discrete budget distribution \(\mathcal{B}_i\), we can replace each mass \(\rho\) with a uniform distribution on \([\rho, \rho + \epsilon]\) for any \(\epsilon > 0\). The resulting profile of budget distributions will have cumulative distribution functions that are continuous, and therefore, a CERI will exist under the new profile.

Next, we discuss ex-post implementation of CERI. In general, there is no exact ex-post implementation of a CERI allocation. However, if the designer can relax the supply of any good by one less than the size of the largest bundle, any CERI allocation be near-feasibly implemented.

The proof of Theorem 2 applies a generalization of the Birkhoff–von Neumann theorem due to [11] and works as follows. For each agent \(i\), given any realization of the random demand, we can construct a conditional income distribution under which the agent’s consumption matches the realization. Since the marginals of the lottery over near-feasible ex-post allocations coincide with the random demand for each agent \(i\), the marginals of the corresponding joint income distribution also coincide with \(\mathcal{B}_{i}\) for all \(i\).

Two properties of the near-feasibility bound in Theorem 2 are worth emphasizing. First, the bound is tight. For example, when \(\Delta=1\) we recover the Birkhoff–von Neumann theorem. Second, the bound is expressed as a good-by-good capacity violation that is independent of market size. This means that in order to ensure exact feasibility in any market, the designer simply has to reduce the capacities of each good by at most \(\Delta-1\).¹³

Efficiency↩︎

We now analyze the efficiency properties of CERI both from the ex-ante and ex-post perspectives. We begin with the definition of ordinal efficiency.

A key result of our paper is that CERI characterizes ordinally efficient outcomes thereby

The key insight in the proof lies in the requirement that for an allocation to be supported by a CERI, there must exist a price vector \(\mathbf{p}\) such that, for every agent \(i\), if the probability of consuming a bundle \(\mathbf{x}\) is positive, then for every bundle \(\mathbf{y} \succ_i \mathbf{x}\), the cost of \(\mathbf{y}\) must be strictly greater than the cost of \(\mathbf{x}\). Otherwise, agent \(i\) would be better off consuming \(\mathbf{y}\) instead of \(\mathbf{x}\). Conversely, if such a price vector exists, it is possible to construct random budgets for the agents so that each lottery allocation precisely corresponds to the optimal consumption under the random budget.

Note that CERI prices can be scaled to ensure that the cost difference between bundles \(\mathbf{y}\) and \(\mathbf{x}\) is at least 1. Consequently, a lottery allocation can be sustained by a CERI if and only if there exists a price vector \(\mathbf{p} \geq 0\) such that \[{\boldsymbol{p}}\cdot ({\boldsymbol{y}}-{\boldsymbol{x}})\ge 1 \text{ for every } {\boldsymbol{y}}\succ_i {\boldsymbol{x}}\text{ and } \mathbb{P}(\tilde{\mathbf{x}}_i={\boldsymbol{x}})>0.\]

Therefore, the presence of a price vector \(\mathbf{p}\) satisfying the given conditions can be expressed as a solution to a linear program. Farkas’ lemma offers a characterization for the existence of such a solution through the dual of the linear program. We show that the dual condition precisely captures the criterion for the allocation to be ordinally efficient.

We now consider whether the allocations in the ex-post implementation of CERI are Pareto-efficient. As Theorem 2 showed ex-post implementations of CERI are only near-feasible in general. The following definition adapts Pareto efficiency to take into account the near-feasibility of allocations.

In words, \(\kappa\)-ex-post efficiency requires that when the supply of each good is relaxed by at most \(\kappa\), the allocation is Pareto-efficient. Each allocation in the CERI ex-post implementation corresponds to a competitive equilibrium under a particular realization of budgets and adjusted capacities. By the First Welfare Theorem, such a competitive equilibrium is Pareto-efficient with respect to the adjusted capacities. This logic is summarized in the following result.

If the designer wished to ensure that the capacities are never violated ex-post, she can progressively reduce capacities, find a CERI and then check whether the allocations in the ex-post implementation violate the capacities. Theorem 2 and 4 guarantee can such preliminary capacity reductions never have to exceed \(\Delta-1\) for any good.

Envy-freeness↩︎

We now examine the envy-freeness properties of CERI both from the ex-ante and ex-post perspectives.

In an ordinally envy-free lottery allocation no agent prefers the lottery of another agent. The Probabilistic Serial mechanism and the Bundled Probabilistic Serial mechanism are both ordinally envy-free, but the RSD and the ACEEI mechanism are not. Since exact ex-post envy-freeness is not achievable in our setting due to the indivisibility of goods, we introduce the following relaxation based on envy-freeness up to one good due to [17] and [1].

Note that our definition of ex-post envy-freeness is a slight generalization of [17]’s and [1]’s envy-freeness up to one good (which is satisfied by ACEEI allocations), because their definition applies to allocations rather than lottery allocations. Here, we extend envy-freeness up to one good to lottery allocations by requiring that every realization of the lottery allocation must satisfy EF1.

The envy-freeness properties of CERI are summarized in the following result.

Note that the two conditions that ensure ex-ante and ex-post envy-freeness properties in Theorem 5 are independent. If income distributions are not the same, but have a sufficiently small support, it is possible that a CERI allocation is not ordinally envy-free, but each allocation in the ex-post implementation is EF1. Conversely, if income distributions are identical but come from a large interval, then the CERI allocation will be ordinally envy-free, but some (or all) allocations in the ex-post implementation would not be EF1.

5 The CERI mechanism and relationships to existing mechanisms↩︎

The properties described in the previous section allow us to define a range of mechanisms that implement a CERI. Abstractly, a CERI mechanism maps an economy to a CERI allocation. Concretely, a CERI mechanism consists of the following steps:

• fix a profile of random incomes,

• ask every agent \(i\in N\) to report their \(\succ_i\),

• compute a CERI, and

• construct a \(\Delta-1\)-near feasible ex-post implementation of this CERI.

A key parameter in any CERI mechanism is the profile of random incomes in step (i) because its choice governs the envy-freeness and incentive compatibility properties.

5.1 CERI-Smechanism↩︎

For any economy, let CERI-Sbe a CERI mechanism in which every agent’s income distribution is \(U[1, 1+\epsilon]\) where \(\epsilon< 1/m\). The following result summarizes the main properties of CERI-S.¹⁴

The CERI-Smechanism is elementary because it simply aggregates the preferences, computes a CERI from them and outputs an ex-post implementation. CERI-Scombines all the ex-ante and ex-post efficiency and envy-freeness properties discussed in the previous section. Moreover, CERI-Sis strategyproof in the large [1], [12], i.e., every agent has an incentive to report their preferences truthfully as a best response to CERI prices which she cannot affect in a large market.¹⁵

5.2 Relationship to existing mechanisms↩︎

We discuss the relationship between CERI mechanisms and other mechanisms in the literature. Figure [fig:tradeoffs] provides an illustration.

Relationship to Serial Dictatorships↩︎

A Serial Dictatorship is ex-post efficient (and ordinally efficient), but it is not ex-post envy-free up to one good. The allocation of any given deterministic Serial Dictatorship can be implemented by a CERI mechanism in a straightforward manner. For instance, in the unit-demand case, set the \(k^\text{th}\) agent’s budget to be \(\$\frac{1}{k}\) w.p. 1. The CERI mechanism will set the price of the item that the \(k^\text{th}\) agent consumes to \(\frac{1}{k}\).

Relationship to the Random Serial Dictatorship↩︎

The Random Serial Dictatorship (RSD) selects one of Serial Dictatorship allocations uniformly at random. The RSD mechanism is ex-post efficient, but it is not ordinally efficient even in the unit-demand case, as the following example shows.

Theorem 3 implies that the RSD lottery allocation in Example 2 cannot be supported by a CERI. Intuitively, since the price of each item can vary substantially across different Serial Dictatorships, achieving coordination on the same prices across every Serial Dictatorship, as required by a CERI, is impossible. Finally, the RSD is neither ordinally envy-free [7] nor ex-post envy-free up to one good [1].

Relationship to ACEEI↩︎

The ACEEI mechanism is approximately ex-post efficient and ex-post envy-free up to one good. However, similarly to the RSD, the ACEEI mechanism might be neither ordinally efficient nor ordinally envy-free. In the unit-demand case the ACEEI mechanism coincides with the RSD. To see this, consider Example 2 again. In the ACEEI mechanism [1], agents’ budgets are uniformly perturbed within the interval \([1-\epsilon, 1]\), and a competitive equilibrium is then computed based on these adjusted budgets. In the case of unit demand, consider ordering the agents by their budgets from largest to smallest and allocating items according to a Serial Dictatorship. This allocation corresponds to a CERI where the price of each item matches the budget of the agent who receives it (see above). Because the perturbations are uniformly random, the ACEEI mechanism produces a lottery allocation identical to the one produced by the RSD. Hence, the ACEEI mechanism is not ordinally efficient. In Appendix 9.2, we give another example of the ordinal inefficiency of the ACEEI mechanism in the multiunit-demand setting and in Appendix 9.1 we show that the existence of a CERI implies the existence of an ACEEI.

Relationship to Simultaneous Eating and the Probabilistic Serial mechanisms↩︎

Simultaneous Eating mechanisms and in particular the Probabilistic Serial (PS) mechanism, were introduced and algorithmically defined by [7] for the unit-demand setting. A Simultaneous Eating mechanism involves an “eating” procedure in which agents “eat” fractional amounts of the most preferred available item at a certain “speed”. Once an entire item has been “eaten”, agents proceed to “eat” the next most preferred available item. Since Simultaneous Eating mechanisms characterize ordinally efficient allocations for the unit-demand setting, each lottery allocation produced by a Simultaneous Eating mechanism can be supported by a CERI.

There is a formal and intuitive mapping between Simultaneous Eating mechanisms and CERI mechanisms: In any Simultaneous Eating mechanism, at any time \(t\), an agent always “eats” the most preferred available item while in the corresponding CERI mechanism, the agent receives the most preferred item at a price at most \(t\). Concretely, consider the following mapping from a Simultaneous Eating mechanism to a CERI mechanism. First, normalize the “eating speeds” so that the Simultaneous Eating mechanism runs as a descending clock, starting at time 1 and finishing at time 0. Without loss of generality, we can also assume that each agent “eats” exactly 1 unit of the goods (e.g., by adding a dummy good). The first moment at which an item is fully “eaten” corresponds to the item’s price in the CERI mechanism. If an item is not fully “eaten” by the end of the mechanism, its price will be 0. The budget distribution of agents is defined on the interval \([0,1]\), and the “eating speed” of an agent at time \(t\) corresponds precisely to the density of the budget distribution at \(t\).

The PS mechanism is a special case of Simultaneous Eating mechanisms where the “eating speed” is the same for all agents. In addition to being ordinally efficient, the PS mechanism is ordinally envy-free. Hence, the PS mechanism corresponds to a CERI mechanism with uniform budget distributions \(U[0,1]\) for all agents and prices constructed as just described above. Hence, our Theorem 5 immediately implies that the PS mechanism must be ordinally envy-free.

Relationship to the Bundled Probabilistic Serial mechanism↩︎

[11] introduced and algorithmically defined a generalization of the PS mechanism for the multiunit-demand setting called the Bundled Probabilistic Serial (BPS) mechanism. Rather than “eating” their most preferred goods as in PS mechanism, in the BPS mechanism agents “eat” the most preferred available bundle of goods. [11] demonstrated that a BPS lottery allocation is ordinally efficient. We first illustrate how to map the BPS mechanism to a CERI mechanism and then show that BPS can only implement a strict subset of ordinally efficient outcomes.

The mapping from the BPS mechanism to a CERI mechanism is similar to the mapping of the Simultaneous Eating mechanism to the CERI mechanism in the unit-demand case, but with one modification in the calculation of prices. This modification ensures that, for each agent, the price of a bundle “eaten” earlier is strictly higher than that of a bundle “eaten” later. This property of bundle prices ensures that one can construct a budget distribution so that the consumption of an agent in the “eating” procedure coincides with the consumption under CERI.

To achieve the required property of bundle prices, we arrange the items based on the order in which they are fully “eaten”. For item \(i\), let \(r_i\) represent its order, where \(r_i=1\) if it is the first item and \(r_i=\infty\) if the item is still available at the end of the mechanism. Let \(K\) be the largest size of an acceptable bundle, and set the price of an item to \(\frac{1}{(K)^{r_i}}\). If a bundle is available before item \(i\) is fully “eaten”, its price is at least \(\frac{1}{(K)^{r_i}}\). On the other hand, if a bundle \(x\) remains available after item \(i\) is fully “eaten”, then the price of \(x\) is less than \(K \times \frac{1}{(K)^{r_i+1}}= \frac{1}{(K)^{r_i}}\).

Unlike CERI, Bundled Simultaneous Eating mechanisms (i.e., the BPS mechanism with heterogeneous “eating speeds”) do not characterize the set of all ordinally efficient allocations in the multiunit-demand setting. The following example illustrates that Bundled Simultaneous Eating mechanisms produce allocations that are a strict subset of CERI allocations.

6 Incentive properties↩︎

It remains to discuss the incentive properties of CERI mechanisms. To formally describe incentives in a large market, we fix the set \(M\) of goods and the size \(\Delta\) of the largest bundle, increase the number of agents, but allow capacities and agents’ preferences to be arbitrary. The CERI-Smechanism has already offered a strategyproof-in-the-large (SP-L) implementation of CERI (Theorem 6). However, SP-L only evaluates deviation incentives from an interim perspective: it merely requires that truthtelling be a best response to the empirical distribution of opponent types which must become exogenous to any given agent in a large market. Another large-market incentive guarantee introduced by [18] requires that each agent find it approximately optimal to report their type truthfully in response to any realization of other agents’ reports. Denote by \(\mathbb{P}_\mathbf{y}\left(\Phi_i(\mathbf{c},\succ)\right)\) the probability that agent \(i\) obtains (an acceptable) bundle \(\mathbf{y}\) under the mechanism \(\Phi\), when the reported preference profile is \(\succ\) and the capacities are \(\mathbf{c}\). In our setting with ordinal preferences, such a notion of asymptotic strategyproofness is defined as follows.¹⁶

In words, asymptotic strategyproofness requires that every agent’s lottery under truthtelling “almost” first-order stochastically dominates the lottery under any misreport in a large market.

Asymptotic strategyproofness is strictly stronger than SP-L and indeed many mechanisms used in practice that are SP-L (such as uniform-price auctions and stable matching mechanisms) are not asymptotically strategyproof [12]. However, all notions of incentive compatibility in large markets (including SP-L and asymptotic strategyproofness) share a fundamental limitation: they bound misreporting incentives agent by agent and merely assume that each agent is content with following an approximately optimal strategy. Such guarantees are not explicitly tied to how the mechanism is implemented and do not ensure that, with some probability, the mechanism is strategyproof. In fact, there is no guarantee that any positive fraction of the agents will find it optimal to report their preferences truthfully with any given probability. This is a significant shortcoming of existing incentive guarantees, since a mechanism’s outcomes may deviate substantially from theoretical predictions even if only a small fraction of agents misreport their preferences. To overcome this limitation of existing incentive guarantees, we will require a stronger property: we say that a mechanism is uniformly strategyproof if the event that all agents have a dominant strategy to report their types truthfully occurs with a high probability in a large market.

In order to describe a uniformly strategyproof mechanism based on CERI, we will use an additional external source of randomness in the mechanism. In particular, let \(\Omega\) be a (finite) sample space, and for every outcome \(\omega\sim \Omega\), let \(\Phi^\omega\) be a direct mechanism. Define \(\Phi^{\Omega}\) to be the random mechanism that outputs \(\Phi^\omega\) with the same probability as drawing \(\omega\) from \(\Omega\). Therefore, \(\mathbb{P}_{\omega\sim \Omega}\left(\Phi_i^\omega(\mathbf{c},\succ)\right)\) denotes the lottery that agent \(i\) obtains under the random mechanism \(\Phi^\Omega\), when the reported preference profile is \(\succ\), the capacities are \(\mathbf{c}\) and the realization of the external source of randomness is \(\omega\). The following definition formalizes our new guarantee for truthtelling incentives.

Definition 10 of uniform strategyproofness is stronger than Definition 9 of asymptotic strategyproofness in two ways. First, though less importantly, if a random mechanism is uniformly strategyproof, then for any agent \(i\) and any preference profile \(\succ_{-i}\) of the other agents, the probability that the lottery achieved by a misreport first-order stochastically dominates her lottery under truthtelling is at most \(\epsilon\). This immediately implies that the error bound \(\eta\) in Definition 9 of asymptotic strategyproofness is bounded by \(\epsilon\). Second, and more importantly, uniform strategyproofness ensures that with arbitrarily high probability the mechanism is strategyproof; that is, it is a dominant strategy for every agent to be truthful in a large market. This immediately implies that any individual agent is better off by being truthful in a large market which is all that is required by Definition 9. Thus, uniform strategyproofness strictly strengthens both asymptotic strategyproofness and, a fortiori, SP-L.

6.1 Random grid↩︎

We will now show how we can use CERI to implement a large-market mechanism that is uniformly strategyproof but nevertheless maintains the strong guarantees for efficiency and envy-freeness. The key feature that allows the mechanism to achieve its desirable properties is an external source of randomness that we call a random grid. In our next CERI implementation, we will approximate the reported type distribution by a nearby point on the grid. The intuitive reason for doing this is that with a sufficiently coarse grid, the likelihood of a single agent significantly altering the approximation to the grid is reduced, giving agents stronger incentives to report their types truthfully in a large market. On the other hand, the grid cannot be too coarse because in that case the grid point we use to approximate the type distribution might be too far from the true distribution, leading to an inefficient allocation. Let \(\tau\in \mathbb{Z}_{>0}\) denote the dimension and \(\lambda\in \mathbb{Z}_{>0}\) denote the step size.

The random grid is instantiated in the \(\tau\)-dimensional type-space, where dimension \(\tau\) is the number of agent types. Hence, a point on the grid represents the number of agents of each type. The step size \(\lambda\) of the grid is key to trading off the properties of the mechanism: larger \(\lambda\) can improve truthtelling incentives but can reduce efficiency. We note that if the grid were deterministic, certain type distributions would tend to be near the grid lines. In such cases, the choice of grid point for the approximation would become highly sensitive to the actions of a single agent. Choosing a random grid mitigates this problem and ensures that, for every type distribution, the probability of any single agent substantially altering the approximation in a large market is negligible.

6.2 CERI-Lmechanism↩︎

Our large-market mechanism, denoted CERI-L, works as follows.¹⁷ First, it instantiates a random grid. It then elicits a vector of agent types \(\boldsymbol{\psi}= (\psi^1, \psi^2, \ldots, \psi^{\tau})\), where \(\psi^t\) denotes the number of agents of type \(t\), and approximates \(\boldsymbol{\psi}\) by a grid point \(\overline{\boldsymbol{\psi}}\). The mechanism then computes a CERI on the economy defined by \(\overline{\boldsymbol{\psi}}\), by identical budget distributions with a small support, and by the true capacities, and then implements an ex-post allocation according to this CERI. For clarity, we use an alternative definition of an economy. Instead of \(\mathcal{E} = (\mathbf{c}, \succ)\), we define it using the capacities and a vector of agent types: \(\mathcal{E} = (\mathbf{c},\boldsymbol{\psi})\), where \(\boldsymbol{\psi}\in \mathbb{Z}^\tau\) is as above. Formally, the mechanism is the following.

CERI-Lspecifies two features of a CERI mechanism. First, like CERI-S, it sets agents’ budget distributions to be identical and to have a small support. Second, CERI-Lapproximates the type distribution using a random grid before calculating a CERI. Figure 2 illustrates how the random grid works in CERI-L. In this illustration, there are two types: \(\tau=2\). We elicit agents’ types \(\boldsymbol{\psi}= (\psi^1, \psi^2)\) and then compute the minimal grid point \(\overline{\boldsymbol{\psi}}\) that, for each agent type \(t\), is no smaller than the stated number of types, \(\psi^t\). We then use these approximate type vector as an input in CERI-L.

6.3 Properties↩︎

Since CERI-L  approximates agents’ preferences by the random grid, it will not in general be ordinally efficient. Nevertheless, we can guarantee efficiency properties of CERI-L  in large markets. In order to define notions of asymptotic efficiency, we will require the following two definitions of ex-ante and ex-post approximate efficiency.

Ordinal \(\epsilon\)-efficiency simply requires that an allocation be ordinally efficient in an economy with slightly relaxed capacities. Naturally, we also consider a definition of approximate ex-post efficiency.

A \((\kappa, \epsilon)\)-ex-post efficient allocation relaxes capacities in two ways: by a multiplicative factor of \(1\pm \epsilon\) and by an additive error of at most \(\kappa\). As above, we will show that the additive error \(\kappa\) is bounded by the maximum bundle size minus one. Hence, in large markets, the additive error is negligible relative to capacities and can be absorbed into the multiplicative error.

We can now define our two notions of asymptotic efficiency, one from the ex-ante perspective and the other from the ex-post perspective. Let \(\mathcal{D}\) be the (discrete) distribution of agents’ types, and let \(\mathcal{D}^n\) denote the distribution of preference profiles for \(n\) agents drawn i.i.d.from \(\mathcal{D}\).

In an asymptotically ordinally/\(\kappa\)-ex-post efficient mechanism, the ex-ante/ex-post allocation is guaranteed to be ordinally \(\epsilon\)-/(\(\kappa,\epsilon)\)-ex-post efficient with an arbitrarily high probability when the market is sufficiently large. Note that the probability bound has to hold in all outcomes of the random grid.

As the agents’ budget distributions are identical and meet the requirements of Theorem 5, CERI-L is ordinally envy-free and ex-post EF1 despite the approximation of types by the random grid. In addition, CERI-L is uniformly strategyproof and asymptotically efficient from ex-ante and ex-post perspectives as the following result shows.

The proof is in Appendix 8.5. The choice of the random grid step size \(\lambda\) is crucial as \(\lambda\) represents a trade-off between efficiency and strategyproofness. When the grid step size \(\lambda\) is set to 1, CERI-Lcoincides with CERI-Sİn this case, CERI-Lis ordinally efficient in a market of any size, but it cannot be guaranteed to be uniformly strategyproof. A larger \(\lambda\) reduces the probability of an agent having a significant influence on the grid point and, consequently, on equilibrium prices, thereby increasing truthtelling incentives. However, a larger \(\lambda\) also corresponds to a larger error in the approximation of the true type distribution, leading to a less efficient allocation. As Theorem 7 shows, in a large market, one can carefully choose a grid step size to achieve a high probability of both minimizing the influence of individual agents on the grid and ensuring an asymptotically ordinally efficient allocation.

7 Conclusion↩︎

This paper has laid price-theoretic foundations for efficient combinatorial assignment. Our characterization of ordinally efficient allocations as CERI allocations provides valuable insights for comparing existing mechanisms and for constructing new ones. Our results illuminate the relationships between efficiency, envy-freeness and incentive compatibility in combinatorial assignment settings and suggest ways to manage the tradeoffs between them in market design.

There are many possible research directions. The first direction is to theoretically explore other implementations of CERI that might strike a different balance between the objectives of market designers or to add new features to CERI. For example, one can imagine incorporating priorities into CERI [22]. The second direction would be to give formal results about the complexity of computing (an approximate) CERI and to develop algorithms for practical implementation (cf. [37], [38] and [39] for such results for the ACEEI). The third direction would be to examine how CERI performs empirically relative to other mechanisms. For example, [2] empirically examined the Harvard Business School “draft” mechanism and pointed out its properties relative to RSD. [40] also examined other combinatorial assignment mechanisms in the course allocation setting, and showed that BPS in particular outperforms first-come-first-served mechanisms. Since CERI improves on the properties of both ACEEI and BPS, these initial results suggest that CERI would perform well in practice.

8 Omitted proofs↩︎

8.1 Proof of Theorem 1↩︎

We use a standard fixed-point argument. First, note that since the cumulative distribution functions of budgets are continuous, the expected consumption \(\mathbb{E}\left[{\mathcal{X}}_{i}({\boldsymbol{p}},\mathcal{B}_{i})\right]\) is continuous with respect to \({\boldsymbol{p}}\) for each agent \(j\).

Second, as the price of a good approaches infinity, the probability of demanding a bundle containing that good tends to \(0\). Therefore, there exists a positive constant \(P\) such that if the price of good \(j\), denoted as \(p^{j}\), exceeds \(P\), then the expected demand for good \(i\) from every agent is less than \(c^{j}/n\). This implies that the aggregate consumption of good \(j\) will be strictly less than the supply when the price exceeds \(P\).

Recall that \(\Psi_i\) is the set of acceptable bundles available to agent \(i\), and \(\mathcal{L}(\Psi_i)\) is the set of lotteries over \(\Psi_i\). In the proof, we will construct a mapping \[f:[0,P]^m\times \mathcal{L}(\Psi_1)\times \ldots \times \mathcal{L}(\Psi_n)\rightarrow [0,P]^m\times \mathcal{L}(\Psi_1)\times \ldots \times \mathcal{L}(\Psi_n)\] and use Brouwer’s Fixed-Point Theorem to conclude that it has a fixed point. We will then show that this fixed point corresponds to a CERI.

To begin, given a lottery allocation \(\{\widetilde{{\mathbf{x}}}_{i}\in \mathcal{L}(\Psi_i) \}_{i=1}^n\), let \(\overline{\boldsymbol{x}}=\mathbb{E}\left[\sum_{i=1}^n \widetilde{{\mathbf{x}}}_{i}\right]\) be the aggregate expected consumption. The excess demand vector is \(\overline{\boldsymbol{x}}-\mathbf{c^{}}\). Let

\[z_j({\boldsymbol{p}}, \widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n}):= \min\{(p^{j}+ \overline{x}^j-c^{j})^+,P\} \text{ for all } j\in M,\] and denote \({\boldsymbol{z}}:= (z_1,..,z_m)\). Define the following mapping \[f({\boldsymbol{p}},\widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n}):=({\boldsymbol{z}}, {\mathcal{X}}_{1}({\boldsymbol{p}},\mathcal{B}_{1}), ...,{\mathcal{X}}_{n}({\boldsymbol{p}},\mathcal{B}_{n})).\] It is easy to see that \(f\) satisfies all the conditions (continuity and boundedness) of Brouwer’s Fixed-Point Theorem. Let \(({\boldsymbol{p}},\widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n})\) be a fixed point of the mapping.

First, at this fixed point \(\widetilde{{\mathbf{x}}}_{i}= {\mathcal{X}}_{i}({\boldsymbol{p}},\mathcal{B}_{i})\) for all \(i \in [n]\). It remains to check the market-clearing condition (ii) in Definition 2 of CERI.

Since the mapping is defined on the set of prices between \(0\) and \(P\), we have \(p^{j}\le P\). We will show that the strict inequality holds, that is, \(p^{j}<P\) for all goods \(j \in M\). If this is the case then the fixed-point condition implies that \(p^{j}=z_j=(p^{j}+\overline{x}^j-c^{j})^+\). And therefore if \(p^{j}>0\), then \(\overline{{x}}^j= c^{j}\) and if \(p^{j}=0\), then \(\overline{{x}}^j \le c^{j}\) which is the market-clearing condition (ii) in Definition 2.

Finally, assume towards a contradiction that \(p^{j} = P\) for a good \(j\), then by the way \(P\) is selected, the aggregate expected demand for good \(j\), \(\overline{x}^j\), will be strictly less than \(c^{j}\). Therefore, \[z_j({\boldsymbol{p}}, \widetilde{{\mathbf{x}}}_{1},..,\widetilde{{\mathbf{x}}}_{n})=\min\{(p^{j}+ \overline{x}^j-c^{j})^+,P\}= \min\{(P+ \overline{x}^j-c^{j})^+,P\}<P = p^{j},\] which contradicts the fixed-point condition and completes the proof. 0◻

8.2 Proof of Theorem 2↩︎

Let \(({\boldsymbol{p}}, \widetilde{{\mathbf{X}}}_{})\) be a CERI. To construct a near-feasible ex-post implementation of CERI, it suffices to express the lottery allocation \(\widetilde{{\mathbf{X}}}_{}\) as the marginal distributions of a lottery over near-feasible ex-post allocations.

Consider an agent \(i\). Let \(x_i\) be a realization of the random demand \({\mathcal{X}}_{i}({\boldsymbol{p}}, \mathcal{B}_{i})\). Define \(\mathcal{B}_{i}|_{x_i}\) as the conditional income distribution such that the optimal consumption is \(x_i\). This distribution has the density function

\[f_{\mathcal{B}_{i}|_{x_i}}(b) := \frac{f_{\mathcal{B}_{i}}(b)}{\mathbb{P}({\mathcal{X}}_{i}({\boldsymbol{p}}, \mathcal{B}_{i}) = x_i)}\] if agent \(i\) consumes \(x_i\) under income \(b\), and \(0\) otherwise.

We use the following result from [11]:

Any feasible random allocation with respect to \(\mathbf{c^{}}\) can be realized through deterministic allocations that are feasible with respect to \(\mathbf{c^{}}+ (\Delta - 1) \cdot {\boldsymbol{1}}\).

As a consequence, there exists a lottery \(\tilde{A}\) over \(\Delta - 1\)-near-feasible deterministic allocations such that its \(i\)-th marginal distribution is \(\widetilde{{\mathbf{X}}}_{i}\). The joint distribution of income is then constructed as follows: for each \((x_1, \dots, x_n)\) drawn from \(\tilde{A}\), we generate \((\mathcal{B}_{i}|_{x_1}, \dots, \mathcal{B}_{i}|_{x_n})\), where the coordinates are independent distributions. This construction of the joint income distribution, together with \(\tilde{A}\), provides a \(\Delta - 1\)-near-feasible ex-post implementation of the CERI. 0◻

8.3 Proof of Theorem 3.↩︎

If a feasible allocation \(\widetilde{{\mathbf{X}}}_{}=(\widetilde{{\mathbf{x}}}_{1},\ldots,\widetilde{{\mathbf{x}}}_{n})\) is CERI, then there exists a price vector \({\boldsymbol{p}}\) that satisfies the following two conditions.

The first condition is the market-clearing condition: \[\label{eq:c1} p_j \ge 0; \quad p_j = 0 \text{ if good j is not fully allocated, i.e., } (\sum_i \mathbb{E}\left[\widetilde{{\mathbf{x}}}_{i}\right])_j < c_j.\tag{2}\]

The second condition is that, for every agent \(i\) and a pair of deterministic bundles \({\boldsymbol{y}}'\succ_i {\boldsymbol{y}}\), where \({\boldsymbol{y}}\) is assigned with positive probability in \(\widetilde{{\mathbf{x}}}_{i}\), we have \[\label{eq:c2} {\boldsymbol{p}}\cdot ({\boldsymbol{y}}'-{\boldsymbol{y}}) \ge 1.\tag{3}\]

The second condition holds because if an agent consumes a bundle with a positive probability, it implies that there exists a realization of the budget such that it is the optimal bundle within that budget constraint. Consequently, the cost of any more preferred bundle must be strictly higher. By scaling prices, we can assume that it is at least 1.

Conversely, if there exists a set of prices, denoted as \({\boldsymbol{p}}\), satisfying Eqs. 2 and 3 , then \(((\widetilde{{\mathbf{x}}}_{1},\ldots,\widetilde{{\mathbf{x}}}_{n}),{\boldsymbol{p}})\) forms a CERI under the budget distribution \(\mathcal{B}_{i}:= {\boldsymbol{p}}\cdot {\boldsymbol{x}}\) with a probability distribution of \(\mathbb{P}(\widetilde{{\mathbf{x}}}_{i}={\boldsymbol{x}})\) for each agent \(i\).

Thus, when provided with a feasible allocation \(\widetilde{{\mathbf{X}}}_{} =(\widetilde{{\mathbf{x}}}_{1},\ldots,\widetilde{{\mathbf{x}}}_{n})\), we can determine whether it is a CERI by using a linear program that identifies prices \({\boldsymbol{p}}\) satisfying both Eqs. 2 and 3 .

Let \(\{\mathcal{A}{\boldsymbol{p}}\ge \boldsymbol{1}, {\boldsymbol{p}}\ge 0\}\) be the description of this linear program. By Farkas’ lemma, such \({\boldsymbol{p}}\) exists if and only if \(\{\mathcal{A}^T \lambda \le 0, \lambda \ge 0; {\boldsymbol{1}}^T \lambda >0\}\) does not have a solution.

We will show that the dual has a solution if and only if \(\widetilde{{\mathbf{X}}}_{} =(\widetilde{{\mathbf{x}}}_{1},\ldots,\widetilde{{\mathbf{x}}}_{n})\) is not ordinally efficient. To show it, we first observe that an equivalent expression for stochastic dominance \(\widetilde{{\mathbf{y}}}_{} \succeq^{sd}_i \widetilde{{\mathbf{x}}}_{}\) is that if \(\widetilde{{\mathbf{y}}}_{}\) can be derived from \(\widetilde{{\mathbf{x}}}_{}\) through a sequence of moves involving the reallocation of probabilities from less preferred to more preferred bundles.

The dual variable \(\lambda\) has a clear interpretation. Each coordinate corresponds to a tuple \(i,{\boldsymbol{y}}',{\boldsymbol{y}}\), where \({\boldsymbol{y}}'\succ {\boldsymbol{y}}\) and \(\mathbb{P}(\widetilde{{\mathbf{x}}}_{i}={\boldsymbol{y}})>0\). \(\mathcal{A}^T \lambda \le 0\) implies that for every good \(j\) that is fully allocated, \[\label{eq:dual} \sum_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}}\cdot y'_j - \sum_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \cdot y_j \le 0\tag{4}\]

Due to the positive probability \(\mathbb{P}(\widetilde{{\mathbf{x}}}_{i}={\boldsymbol{y}})\), we can normalize \(\lambda\) such that each \(\lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}}\) is at most \(\mathbb{P}(\widetilde{{\mathbf{x}}}_{i}={\boldsymbol{y}})\).

Interpret \(\lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}}\) as the probability mass indicating the extent to which agent \(i\) shifts from bundle \({\boldsymbol{y}}\) to a superior bundle \({\boldsymbol{y}}'\). Eq. 4 asserts that agents can make such shifts without violating the resource constraint of goods that are fully allocated.

For goods that are under-allocated in the allocation \(\widetilde{{\mathbf{X}}}_{}\), Eq. 4 may not hold. However, it is possible to additionally scale down \(\lambda\) by a constant factor, ensuring that the difference is within the limits of the remaining resources for that particular good:

\[\label{eq:dual1} \sum_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}}\cdot y'_j - \sum_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \lambda_{i,{\boldsymbol{y}}',{\boldsymbol{y}}} \cdot y_j \le c_j- (\sum_i \mathbb{E}\left[\widetilde{{\mathbf{x}}}_{i}\right])_j.\tag{5}\]

Let \(\widetilde{{\mathbf{z}}}_{i}\) represent the resulting lottery for agent \(i\) after the probability shift according to \(\lambda\). Because all agents have shifted probability to more preferred bundles, \(\widetilde{{\mathbf{z}}}_{i}\succeq_i^{sd}\widetilde{{\mathbf{x}}}_{i}\). Moreover, \({\boldsymbol{1}}^T \lambda >0\) indicates that there is at least one move of probability that is strictly positive, thereby implying that at least one agent is strictly better off.

Eqs. 4 and 5 together imply that the allocation \(({\widetilde{{\mathbf{z}}}_{1}},\ldots,{\widetilde{{\mathbf{z}}}_{n}})\) is feasible with respect to \(\mathbf{c^{}}\). This means that the allocation \(\widetilde{{\mathbf{X}}}_{}\) is not ordinally efficient. 0◻

8.4 Proof of Theorem 5↩︎

8.4.0.1 Part (i)

Let \(\mathbf{p}^*\) denote the equilibrium price. Consider the random bundles \((\widetilde{{\mathbf{x}}}_{i}, \widetilde{{\mathbf{x}}}_{i'}\)) consumed by individuals \(i\) and \(i'\) when they share a common income distribution \(\mathcal{B}\). Let \(u_i\) represent a cardinal valuation consistent with the preference relation \(\succ_i\).

For a given budget \(b\), let \({\boldsymbol{x}}_{(\mathbf{p}, b, \succ_i)}\) denote the best affordable bundle at price \(\mathbf{p}\) under the preference relation \(\succ_i\). Clearly, \({\boldsymbol{x}}_{(\mathbf{p}^*, b, \succ_i)} \succeq_i {\boldsymbol{x}}_{(\mathbf{p}^*, b, \succ_{i'})}.\) Since the budget distributions \(\mathcal{B}\) are identical, it must hold that for any bundle \(z \in \Psi_i\) \[\sum_{{\boldsymbol{x}}\succeq_i {\boldsymbol{z}}} \mathbb{P}_{{\boldsymbol{x}}}(\widetilde{{\mathbf{x}}}_{i}) \;\;\ge\;\; \sum_{{\boldsymbol{y}}\succeq_i {\boldsymbol{z}}} \mathbb{P}_{{\boldsymbol{x}}}(\widetilde{{\mathbf{x}}}_{i'}).\] Hence, \(\widetilde{{\mathbf{x}}}_{i} \succeq_i^{sd} \widetilde{{\mathbf{x}}}_{i'}\) as required.

8.4.0.2 Part (ii)

We omit the proof of the second part of the theorem as it follows directly from Theorem 3 in [1]. 0◻

8.5 Proof of Theorem 7↩︎

We need an additional definition for the proofs. Let \(\mathcal{D}\) be a discrete type distribution. Define \(\tau = | \text{supp}(\mathcal{D}) |\). For every \(t \in \text{supp}(\mathcal{D})\), denote by \(p_t\) the probability that \(t\) is sampled from \(\mathcal{D}\); \(p_t = \mathbb{P}_{\succ \sim \mathcal{D}}(\succ = t)\), and set \(p_{\min}(\mathcal{D})= \min_{t \in \text{supp}(\mathcal{D})}\{p_t\}\). For simplicity, we assume that \(\tau \sqrt{n}\) is an integer.

The following three lemmata will be used to derive the efficiency and incentive properties of CERI-L. Lemma 1 and Lemma 2 derive statistical properties of the random grid. Lemma 3 shows that an allocation that is efficient with respect to one type vector is almost efficient with respect to another type vector, assuming they are sufficiently close.

To complete the proof of Theorem 7, for any \(\epsilon>0\), set \(\bar{n}= \frac{(8\tau)^2}{\epsilon^2p_{\min}(\mathcal{D})^2}\).

8.5.0.1 Part (i): uniform strategyproofness

: From Lemma 1, the coordinate-wise distance between the vector \(\overline{\boldsymbol{\psi}}\) generated by Mechanism CERI-L and \(\boldsymbol{\psi}\) is at least \(1\), with probability at least \(1-\epsilon\). If this is the case, no agent can affect the choice of the grid point used for the generation of the prices.

8.5.0.2 Part (ii): asymptotic ordinal efficiency

Plugging \(\lambda= \tau\sqrt{n}\) into Lemma 2, gives that \(\boldsymbol{\psi}\geq \left(1-\epsilon\right) \overline{\boldsymbol{\psi}}\) with probability at least \(1-\frac{\epsilon}{2}\). Lemma 3 shows that when this is the case, the allocation is asymptotically ordinally efficient. Note that Lemma 2 does not require that the grid be random. As the only source of randomness in Mechanism CERI-Lis the choice of the random grid, we have that the allocation is asymptotically efficient for every realization of the mechanism; hence it is asymptotically efficient.

8.5.0.3 Part (iii): asymptotic ex-post efficiency

This property follows directly from the asymptotic ordinal efficiency of the mechanism and from applying Theorem 2 to CERI-Lallocation. Specifically, CERI-Limplements a CERI as a lottery that deviates from the expected aggregate allocation of the CERI by at most \(\Delta-1\) units for each good.

8.5.0.4 Parts (iv) and (v): Ordinal envy-freeness and ex-post EF1

Since the allocation is a CERI with respect to the economy \(\mathcal{E}' = (\overline{\boldsymbol{\psi}}, \mathbf{c})\), then using Theorem 5 we can conclude that it is ordinally envy-free and ex-post EF1.

0◻

9 CERI vs. ACEEI↩︎

9.1 Existence of a CERI implies existence of an ACEEI↩︎

We first show that the existence of a CERI implies the existence of an approximate competitive equilibrium from equal incomes (ACEEI) with the same bound on the excess demand as in [1]. In particular we show the following result.

To show this, we use the following improved bound for the Shapley–Folkman theorem [41] in order to obtain an ACEEI.

9.2 The ACEEI mechanism is not ordinally efficient↩︎

In Section 5.2, we argued that in the unit-demand setting the ACEEI mechanism coincides with the RSD. An example from [7] described in that section showed that RSD allocations might not be ordinally efficient. Here, we provide an example of the ordinal inefficiency of the ACEEI in multiunit-demand setting. In this example, the unique ACEEI allocation (for any budget perturbation) is one that allocates the empty bundle w.p. 1 to all agents. This allocation turns out to be ordinally inefficient.

References↩︎

---

1. Perhaps better terms for these concepts would be “ex-ante ordinal efficiency” and “ex-ante ordinal envy-freeness” to contrast with “ex-ante cardinal efficiency” and “ex-ante cardinal envy-freeness” both of which fix a von Neumann-Morgenstern utility representation of preferences over lotteries. Note that ex-ante cardinal efficiency is stronger than ex-ante ordinal efficiency while ex-ante cardinal envy-freeness is weaker than ex-ante ordinal envy-freeness.↩︎

2. Our reasons are practical rather than axiomatic. First, it is difficult to elicit preferences over lotteries over many consumption bundles. Second, in many market design applications it is preferable to make as few assumptions about agents’ behaviour as possible to ensure that outcomes are robust to various forms of errors and misspecifications (this might be reminiscent of the “Wilson’s doctrine” that criticizes the reliance on the common knowledge assumption in mechanism design). While the monotonicity assumption might appear weak, there is nevertheless some recent experimental evidence of its violation [8].↩︎

3. Of course, with indivisible goods, the set of ex-post envy-free outcomes can be empty even with two agents and one good, therefore, envy-freeness in the divisible-goods setting is the more reasonable analogue [9], [10].↩︎

4. We will use “budget” and “income” interchangeably.↩︎

5. The result is substantial since any discrete distribution of budgets can be made continuous by arbitrarily small perturbations.↩︎

6. Moreover, they showed that there are no ordinally efficient and strategyproof mechanisms that satisfy the equal treatment of equals property when the numbers of agent/good is greater than four.↩︎

7. Our construction of a CERI is similar to [1]’s construction of his convexified equilibrium, however, by using a different rounding procedure we can avoid [1]’s initial budget perturbation step that compromises ordinal efficiency and ordinal envy-freeness of the ACEEI mechanism.↩︎

8. There is a well known connection between models with ordinal and vNM preferences. [24] showed that any ordinally efficient lottery allocation maximizes the sum of expected utilities for some vector of vNM utility functions that are consistent with the ordinal preferences. See also [25] and [26].↩︎

9. Formally, \(\Delta:=\max _{i \in N} \max _{x \in \Psi_i} \sum_{j \in M} x_j\). In applications, such as course allocation or refugee resettlement, \(\Delta\) is around 6.↩︎

10. Most decision-theoretic models assume monotonicity although some recent models of preferences for randomization allow for violations of monotonicity [8].↩︎

11. In the special case when agents are expected utility maximizers, the condition says that agent \(i\) prefers \(\widetilde{{\mathbf{x}}}_{}\) to \(\widetilde{{\mathbf{y}}}_{}\) if the agent obtains higher expected utility from \(\widetilde{{\mathbf{x}}}_{}\) than from \(\widetilde{{\mathbf{y}}}_{}\) for any von Neumann-Morgenstern (cardinal) representation of his ordinal preferences \(\succ_i\).↩︎

12. Using methods from [23], it is straightforward to show that if a symmetric lower bound were introduced in Definition 4 of \(\kappa\)-near-feasibility then the feasibility error on both bounds of the ex-post implementation would double.↩︎

13. By contrast, the \(\ell^2\)-norm near-feasibility bound for ACEEI depends on the market size [1]. Moreover, expressing possible capacity violations in the market-size-dependent \(\ell^2\)-norm makes it less practical for the designer to preemptively adjust capacity to ensure exact ex-post feasibility.↩︎

14. Pronounced “serious” where “S” is for “same and small income distributions”.↩︎

15. We avoid a full technical definition of SP-L which can be found in [12].↩︎

16. Other existing notions of asymptotic strategyproofness are weaker as they are expressed in terms of von Neumann–Morgenstern utilities [12], [20], [36].↩︎

17. Pronounced “cereal” where “L” is for “large market”.↩︎