1 Introduction↩︎

When designing mechanisms without transfers, it is often natural to evaluate them using criteria that avoid interpersonal utility comparisons. This approach is especially appealing when the policymaker has explicitly non-welfarist goals (such as fairness) or when participants’ valuations for the allocated goods are plausibly similar. Indeed, the literature on mechanisms without money has largely focused on notions based on Pareto efficiency and ordinal welfare rankings.² Nevertheless, criteria agnostic to cardinal values are less fitting for settings like social programs, where policymakers view applicants as differing sharply in terms of need and aim to target those for whom receiving the goods has the greatest social value. For instance, affordable housing programs in many European countries serve a broad population, including families facing eviction as well as middle-class households with stable employment [5]. In the U.S. context, [6] find that affordable housing recipients differ substantially in various measures of need, and that this heterogeneity persists even after conditioning on observables.

Motivated by such settings, I consider a mechanism design problem without transfers where the designer allocates heterogeneous goods to maximize cardinal welfare. Importantly, agents’ valuations are their private information; this prevents the designer from simply giving the available supply to those who need it most. I make two main points. The first is that, under reasonably permissive conditions on value distributions, the optimal mechanism gives every agent some amount of one good and none of the others. In my model, this allocation rule can be implemented in several natural ways, including as a competitive equilibrium with equal incomes—a mechanism that has often been proposed in the literature because of its desirable fairness and efficiency properties [1], [7]–[9]. Second, I show that the designer can sometimes improve upon this simple mechanism by letting agents choose large, mixed bundles alongside smaller pure options. Intuitively, this is the case when agents with higher values for the goods tend to be less picky: they value the available goods similarly, and so care less about which particular good they receive. These agents are then willing to give up choice in exchange for a larger total allocation, while more selective agents, whose values are lower on average, choose the smaller pure options.

Thus, the optimal mechanism depends on the statistical relationship between agents’ absolute level of need and the strength of their relative preferences across goods. When higher-value agents tend to be more picky, mechanisms offering only pure options are likely to be optimal. In the reverse case, the designer can use mixed bundles to reward agents with narrower preference margins. Both correlation patterns are plausible in different settings. For instance, [6] find that lower-income households are less selective when applying for affordable housing: they are more willing to trade off assignment to a preferred unit for a higher probability of receiving an offer somewhere. In other settings, however, the correlation may go in the opposite direction. For example, consider school choice environments with specialized curricula, such as dual-language immersion programs. Families who place disproportionate weight on admission to such programs may do so because of a child’s idiosyncratic needs, aptitudes, or interests. In such cases, an intense relative preference for a particular option may instead signal a higher absolute value for receiving it.

I prove two main results. First, I fully characterize the welfare-maximizing mechanism in the case of two kinds of goods: the mechanism always offers two pure options, and sometimes also includes a single mixed bundle that gives agents some of each good and delivers a larger total quantity. In the symmetric case, I show that introducing the mixed bundle is welfare-improving precisely when weak relative preferences are sufficiently predictive of higher total value, so that the informational gain from targeting outweighs the allocative inefficiency from mixing. I then turn to the general \(N\)-good case and characterize when the mechanism offering only pure options is optimal. The condition is stated in terms of monotone transports on an appropriately constructed signed measure, which captures the designer’s marginal value of increasing different types’ allocations. I then derive a simpler sufficient condition in the special case of symmetric goods: there, the pure option mechanism is optimal if agents whose cardinal values for their favorite goods are higher tend to be more selective, in a precise stochastic sense. Intuitively, this is because any distortion away from the pure option mechanism—which is the unique incentive-compatible Pareto-efficient allocation—must reallocate resources toward less selective types. The condition ensures, however, that the higher-value types are precisely the more selective ones, so such distortions move resources in the wrong direction.

I also discuss the implications of my results for market design in settings such as allocating donations to food banks and affordable housing. In these settings, existing mechanisms can be improved when the agents the designer wants to prioritize are also those willing to accept less tailored allocations. For food banks, the results suggest a natural modification of the CEEI mechanism currently used to allocate donations: the system could offer discounts for bundles of food, allowing food banks that receive little support from their local donors to choose larger allocations. In the case of affordable housing, the model speaks to the design of waitlists and repeated lotteries. Indeed, I show in Appendix 10 that the baseline model can be interpreted as a reduced-form description of such mechanisms, once allocations are redefined appropriately. There, one could let applicants choose between a priority waitlist where they must accept any suitable unit offered to them, and longer waitlists that let them select specific units or locations. Finally, I discuss how my framework could be extended to incorporate observable characteristics, such as income or household size.

My paper contributes to the literature on allocating heterogeneous goods without transfers, and connects most directly to work on pseudomarkets and competitive equilibrium with equal incomes (CEEI). [1] introduce CEEI in an assignment setting by giving agents equal budgets of artificial currency and letting them purchase probability shares of different goods; the resulting lotteries are ex ante Pareto-efficient. Subsequent work has developed pseudomarket mechanisms for richer assignment environments, including approximate CEEI for combinatorial assignment [8] and pseudomarkets with priorities and other constraints [10]. The literature also studies mechanisms based only on agents’ rankings over objects. Random serial dictatorship lets agents choose sequentially in random order [2], while probabilistic serial assigns agents fractional shares by letting them continuously claim their most-preferred available objects, yielding ordinally efficient outcomes [3]. Other papers analyze the large-market properties of these mechanisms: [9] formalize a notion of strategy-proofness in the large for assignment and related mechanisms, while [11] show that random serial dictatorship and probabilistic serial become asymptotically equivalent.

While the study of allocating heterogeneous goods without transfers has focused mainly on criteria that avoid interpersonal utility comparisons, a smaller body of work allows for cardinal objectives and studies mechanisms that maximize them [12]–[16]. My paper is closest to [12], who studies welfare-maximizing mechanisms with cardinal utilities in a symmetric, two-good setting with finitely many agents. He shows that although the welfare optimum may differ from CEEI in finite markets, CEEI becomes optimal in a large-market limit. This, however, is because the problem is solved under a condition that turns out to exclude precisely the kind of relationship between relative preference intensity and cardinal need that makes screening with bundles useful.

A related literature studies eliciting preference intensities—information about how strongly agents prefer some options over others. In school choice, [17] observe that the Boston mechanism can elicit the extent to which families prefer certain schools—a property that deferred acceptance does not have. In a paper closely related to mine, [18] consider optimal mechanisms in a setting without transfers where agents have a common ranking over goods but differ in their sensitivity to quality. My paper, by contrast, does not impose such structure and considers heterogeneously differentiated goods. This leads to different and complementary results. Indeed, the authors show that the first-best allocations may offer lotteries between qualities, and that second-best allocations always involve lotteries and may involve free disposal; neither of these results holds in my setting. Similarly to my work, they show that CEEI allocations, despite being Pareto-efficient, do not always maximize weighted welfare.

Finally, my work builds on methods developed in the multidimensional screening literature. To obtain a characterization of the optimality of the pure option mechanism, I invoke ideas used in the study of the multi-product monopoly problem [19]–[22]. In particular, my optimality conditions rely on stochastic dominance and transport arguments related to those in [23], [24].

The rest of the paper is structured as follows. Section 2 presents the model, and Section 3 illustrates the core intuitions through simple two-good examples. Section 4 then formally separates absolute and relative values and reformulates the designer’s problem in terms of relative-value profiles. Section 5 introduces the pure option mechanism, describes the induced partition of types, and shows how the mechanism can be implemented through a CEEI, a representative endowment economy, or a choice-based lottery. Section 6 specializes the model to two goods and fully characterizes the welfare-maximizing mechanism. Section 7 turns to the general \(N\)-good case and characterizes when the pure option mechanism is optimal. Section 8 outlines the proof of this characterization. Finally, Section 9 discusses implications for market design.

2 Model↩︎

The designer has \(N\) different kinds of goods indexed by \(i\in \{1,\dots,N\}\) with \(N\geq 2\). She possesses a fixed mass of each, with the supplies given by \(s=(s_1,s_2,\dots,s_N)> 0\). There is a unit mass of agents, each of whom has a profile of values \(v= (v_1,v_2,\dots,v_N)\) for the goods; the values are private information and are distributed according to \(F\) with support on a bounded set \(\mathcal{V}\subset \mathbb{R}^N_{+}\). This distribution puts no mass on \(\mathbf{0}\) and assigns positive mass to agents with \(v_i>0\) for every good \(i\). The designer chooses an allocation rule for the goods, \(y=(y_1,y_2,\dots,y_N):\mathcal{V}\to \mathbb{R}_+^N\), to maximize utilitarian welfare: \[\label{eq:obj} \int_{\mathcal{V}} v\cdot y(v) d F(v). \tag{1}\] She faces incentive compatibility and supply constraints: \[\label{eq:IC} v\cdot y(v) \geq v\cdot y(v') \quad \text{for all }v, v', \tag{2}\] \[\label{eq:S} \int y(v) d F(v) \leq s. \tag{3}\] An allocation rule \(y:\mathcal{V}\to \mathbb{R}_+^N\) is feasible if it satisfies 2 and 3 .

2.1 Discussion of the model↩︎

I briefly discuss the interpretation of the model. First, it assumes that the designer’s preferences align with those of agents: if an agent chooses one allocation over another, the designer also considers giving her that allocation more socially valuable.

Second, the model allows for multiple interpretations of agents’ values \(v\); for instance, one can identify \(v_i\) with an agent’s (latent) willingness to pay for a unit of good \(i\). While these values are not directly elicitable without money, they remain meaningful for the designer’s welfare objective. Alternatively, and more generally, one can view them as the designer’s subjective conviction about the social value of giving goods to different agents. She may, for example, place higher weights on individuals with certain characteristics (need, vulnerability, family size, etc.), and believe that these characteristics are correlated with the pattern of preferences agents reveal over the available goods.

Finally, note that at baseline we interpret \(y_i(v)\) as the amount of good \(i\) given to type \(v\). However, some settings of interest feature unit demand, so applying the model to them requires interpreting allocations as probabilities of receiving a certain good. This in turn requires imposing an additional constraint that \(\sum_i y_i(v)\le 1\) for all \(v\). While this restriction changes the problem in general, the following result shows that imposing it is without loss when supply is sufficiently scarce relative to the population.

Intuitively, this is because when overall supply is sufficiently small, the designer cannot afford to offer any option that delivers some good with certainty. If she did, the mass of agents requesting such an option would be so large that supply constraints would be violated. This kind of extreme mismatch between demand and supply is plausible in settings like public-housing lotteries, where units are exceptionally scarce relative to the number of applicants.³

Proposition 1 also implies that the set of feasible allocation rules is uniformly bounded for any supply \(s\). A standard compactness argument then shows that an optimal mechanism exists.

3 Examples↩︎

To preview the paper’s core intuitions, I begin with illustrative examples featuring just two goods; I verify them in Appendix 13.

Under this mechanism, agents for whom \(q_1 \;v_1 > q_2 \;v_2\) select the former option, while those for whom \(q_1 \;v_1< q_2 \;v_2\) select the latter. As shown in Figure 1, these two sets of types are separated by a ray from the origin defined by \[\label{eq:rayexample1} \frac{v_1}{v_2} = \frac{q_2}{q_1}.\tag{4}\] Let us note two things about this allocation. First, it is Pareto-efficient among all allocation rules satisfying the supply constraint 3 . Second, it depends only on the ratio of agents’ values for goods \(1\) and \(2\), but not on how large \(v_1\) and \(v_2\) are in absolute terms. Indeed, while the designer would like to allocate the goods only to agents whose \(v_1\) and \(v_2\) are high, she cannot do so in an incentive-compatible way. She is therefore restricted to conditioning the allocation on how much agents like one good relative to the other. This highlights a useful distinction: an agent’s absolute values, \((v_1,v_2)\), capture the overall intensity of need for the goods, while her relative values, which I define as \((\tfrac{v_1}{v_1+v_2} ,\tfrac{v_2}{v_1+v_2})\), capture the strength of her preference between the goods. Since all agents with the same relative values always rank all offered options the same way, no incentive-compatible mechanism can meaningfully elicit absolute values among agents with the same profile of relative values.

The simple mechanism in Example 1 is not always optimal, however. For other value distributions, the designer may want to offer a richer menu.

Under this mechanism, each agent can pick between a low amount of her favorite good and a bundle of the two goods that offers a larger total amount. Agents with strong relative preferences between the two goods pick the pure allocations while those with narrow preference margins choose the bundle.

To see why this menu is optimal, note that the value distribution, illustrated in Figure 2, concentrates its mass on two kinds of agents. The first are common-need agents, who are close to indifferent about which good they get but have high values for both. The second kind are specialized-need agents, who tend to value one good substantially more than the other. However, their highest values tend to be lower than those of the common-need agents. Here too, all agents with the same relative values \((\tfrac{v_1}{v_1+v_2},\tfrac{v_2}{v_1+v_2})\) receive the same allocation. However, agents whose relative values are close together choose the bundle and thus receive higher total allocations. Since these agents also tend to have higher absolute values \((v_1,v_2)\), offering a bundle gives the designer an incentive-compatible way of directing more goods to agents in greater need. More generally, doing so can help the designer if relative and absolute values are statistically related. In such cases, she can sometimes proxy for high absolute values by offering more attractive options to agents with certain relative preferences.

Note, however, that the optimal allocation in Example 2 is not Pareto-efficient among all allocation rules satisfying the supply constraint 3 . Indeed, agents who receive the bundle could profitably trade among themselves so that types above and below the 45-degree line in Figure [fg:betterexample] each receive only the good they prefer.⁴ This illustrates the designer’s tradeoff: bundling reduces allocative efficiency, but helps screen agents by the strength of their relative preferences, allowing scarce resources to be targeted toward those with greater need.

4 Absolute and relative values↩︎

Motivated by the preceding examples, I now formally separate absolute and relative values. Since the designer cannot elicit absolute values of agents who share the same profile of relative values, we can, without loss, identify types with the latter. Let \(\Gamma\) be the \((N-1)\)-simplex of relative-value profiles: \[\Gamma \;:=\; \bigl\{\theta\in\mathbb{R}^N_{+}:\;\sum \theta_i=1\bigr\}.\] Define \(V\) as the random variable describing the value vector \(v\) of an agent drawn from \(F\) and let \(\Theta\) be the following \(\Gamma\)-valued random variable⁵ \[\Theta \;:=\;\frac{V}{\sum_j V_j}.\]

The renormalization thus maps all types that are identical up to scaling to the same renormalized type \(\theta\in \Gamma\) (Figure 3). Let \(G\) denote the distribution of \(\Theta\), which is the push-forward of \(F\) under the map \(v\mapsto v/\sum_j v_j\). Throughout, we impose the following assumption on \(G\):

While the designer cannot elicit absolute values, they are still important for her objective. We therefore let \(\lambda:\Gamma\to\mathbb{R}_+\) be the conditional expectation of total value given the renormalized type: \[\lambda(\Theta) = \mathbb{E} \Big[\sum_j V_j \,\Big|\, \Theta\Big].\] Intuitively, \(\lambda(\theta)\) is the expected total value associated with agents whose types \(v\) were mapped to \(\theta\).⁶ Since \(\mathcal{V}\) is bounded, we can fix a version of this conditional expectation that is bounded on all of \(\Gamma\). We then rewrite the designer’s problem as follows:

Indeed, Problem 1 is equivalent to the designer’s original problem in the following sense:

This renormalization has a clear economic interpretation. The type \(\theta\) contains the minimal information needed to describe behavior and is the object that can be empirically identified from choices. By contrast, \(\lambda(\theta)\) captures the expected scale of values conditional on \(\theta\), and therefore affects the problem only through the designer’s objective. Economically, \(\lambda\) encodes the designer’s prior about how need (i.e., absolute value) varies across preference profiles, and is relevant only for the normative ranking of feasible allocations.

5 The pure option mechanism↩︎

As Example 1 shows, the optimal mechanism sometimes takes a particularly simple form: it offers one pure option for each good, and each agent chooses her favorite. In this section, I formally define this kind of mechanism.

That is, agents face a menu with \(N\) options, \[\left\{\text{q_1 of good 1}\right\}, \;\;\;\left\{\text{q_2 of good 2}\right\}, \;\;\;\dots, \;\;\; \left\{\text{q_N of good N}\right\},\] where the quantities \(q_i\) are chosen so that all the supply constraints bind when all agents choose their favorite one. In the appendix, I show that such a market-clearing menu is unique:

The pure option mechanism admits several equivalent implementations.

Intuitively, the CEEI and representative-endowment implementations give all agents identical budgets to spend on goods: in the former, this budget is assigned directly, while in the latter it is the market value of their endowment \(s\). Since utilities are linear and total allocations are not capped, almost every type spends her whole budget on the good with the highest “bang per buck,” \(\theta_i/p_i\), and so the induced allocation is pure. The allocations are also pure in any pure equilibrium of the choice-based lottery. Thus, in all three implementations, almost every type receives a pure allocation. Moreover, no type prefers another type’s allocation to her own: in the first two implementations this follows because all agents face the same budget set, while in the lottery implementation it follows from equilibrium. Since the induced pure allocations also clear the market, Fact 1 implies that they must coincide with the pure option mechanism.

I now describe the allocation induced by the pure option mechanism, that is, I characterize which types choose which pure option. To do so, I first introduce a partial order comparing how strongly different types favor a particular good relative to the other goods.

Intuitively, \(\theta \succ_i \theta'\) means that \(\theta\) values good \(i\) relatively more than does \(\theta'\), compared to every other good (Figure 4).

That is, the mechanism’s allocation can be described as follows. Let \(q\) be the unique market-clearing vector of pure-option quantities. These quantities determine a unique type \(\theta^0\) that is indifferent among all options. Up to tie-breaking on a null set, option \(i\) is then chosen exactly by the types who like good \(i\) more than \(\theta^0\), in the sense that they lie in the direction of vertex \(e_i\) from \(\theta^0\) according to the partial order defined above. Denote this region by \(\Gamma_i\). Since every type lies in the direction of some vertex from \(\theta^0\), the regions \(\{\Gamma_i\}_{i=1}^N\) then form a partition of \(\Gamma\), up to the null set of types who are indifferent between two or more pure options (Figure 5).

6 Two kinds of goods↩︎

I now characterize the optimal mechanism when there are only two types of goods. In this case, the reparametrization from Section 4 effectively makes types one-dimensional, removing the difficulties of multidimensional screening. For each \(z\in[0,1]\), define \[\varphi(z) := \left( z\,\mathbb{P}(\Theta_2\le z), \; (1-z)\,\mathbb{P}(\Theta_2\ge z) \right), \qquad w(z) := \mathbb{E}\bigl[\lambda(\Theta)\max\{z\Theta_1,(1-z)\Theta_2\}\bigr].\] We then get the following result:

Thus, the optimal mechanism can take one of two forms: it is either the pure option mechanism, or it offers two smaller pure options together with a larger mixed bundle, as in Example 2.

While the proof is in the appendix, I explain its core logic as well as the reason for the simple structure of the optimum. The key observation is that every allocation rule satisfying ?? can be written as a positive combination of binary threshold rules of the form \[\label{eq:thresholdrulee} x^z(1-t,t)= \begin{cases} (z,0), & t< z,\\[3pt] (0,1-z), & t\ge z. \end{cases}\tag{5}\] This rule is induced by a two-option menu offering either \(z\) units of good \(1\) or \(1-z\) units of good \(2\); the cutoff type \(\theta=(1-z,z)\) is indifferent between the two. Indeed, \(\varphi(z)\) denotes the vector of supplies used by the threshold rule \(x^z\) and \(w(z)\) denotes the welfare it generates.

This representation turns the designer’s problem into a linear program over positive measures on such threshold rules. Each threshold rule uses up a certain amount of good \(1\) and a certain amount of good \(2\), so the supply constraints impose two linear inequalities on the measure. Since this linear program has only two resource constraints, a standard argument implies that an optimal solution places weight on at most two thresholds, say \(a\le b\). These two thresholds partition the type interval into three regions, \[t<a,\qquad a\le t<b,\qquad t\ge b,\] and therefore generate at most three allocation levels: a pure good-1 option, a bundle, and a pure good-2 option. When the optimal measure is supported on a single threshold, the construction collapses to the pure option mechanism.

Let us now discuss when the pure option mechanism is optimal. Recall that \(\theta^0 = (\theta^0_1,\theta^0_2)\) is the unique type that is indifferent between the two options in the pure option mechanism. Types to the left of \(\theta^0\) in Figure 6 choose \((q_1,0)\), while those to the right choose \((0,q_2)\). In the threshold-rule representation, the pure option mechanism corresponds to an atom on the binary threshold rule \(x^{\theta^0_2}\). Both supply constraints bind when the mass on this atom equals \(s_1/\varphi_1(\theta^0_2)\). Consequently, the welfare generated by the pure option mechanism is exactly the right-hand side of condition ?? .

Furthermore, it turns out that every menu of the form ?? is pinned down by a pair of types \((1-a,a), (1-b,b)\) that lie on either side of \(\theta^0\) (Figure [fg:2dbundle]); these types are then indifferent between the bundle and one of the pure options. Thus, in the threshold-rule representation, such a mechanism combines binary threshold rules \(x^a,x^b\) with weights \(m_a,m_b\) defined in ?? , and gives welfare \(m_aw(a)+m_bw(b).\)⁷ Condition ?? therefore ensures that no such menu dominates the pure option mechanism. In Appendix 11, I provide an explicit construction of the optimal three-option menu in the case where the pure option mechanism is not optimal.

The optimality condition for the pure option mechanism simplifies further in the symmetric case. Suppose that \(s_1=s_2\), and that \(g\) and \(\lambda\) are exchangeable. It is then without loss to consider symmetric bundling mechanisms whose two cutoffs are mirror images of one another.

To understand the condition, consider the symmetric pure option mechanism in Figure [fig:2dsymmpure] and choose two symmetric cutoff types, \((1-z,z)\) and \((z,1-z)\), on both sides of \(\theta^0=(1/2,1/2)\). Consider a modification of this pure option mechanism where all types between them receive a bundle containing \(2s(1-z)\) of each good (Figure [fig:2dsymmbundle]).

Indeed, the cutoff types are indifferent between this bundle and the corresponding pure options. Note, however, that this perturbation violates the supply constraint. We can nevertheless account for this by penalizing the extra supply it uses at the shadow value of supply under the symmetric pure option mechanism. This shadow value of one extra unit of either good is \[\mathbb{E}\!\left[\lambda(\Theta)\max_i\Theta_i\right].\] Indeed, an extra unit of good \(1\) can be used to raise the good-\(1\) option for the agents who choose good \(1\), and symmetrically for good \(2\).

Now, the perturbation in Figure [fig:2dsymmbundle] gives each middle type \(2s(1-z)\) units of each good. Relative to the pure option mechanism, where each type receives \(2s\) units of her favorite good, this is an extra total quantity of \[4s(1-z)-2s = 2s(1-2z).\] Thus, the average shadow cost of the extra supply, per type in the middle region, equals the right-hand side of ?? , up to the factor \(2s\).

Let us now consider the benefit of the perturbation, which comes only from the middle types. Such a type receives utility \(2s(1-z)\) from the bundle, instead of \(2s\max_i\Theta_i\) from her pure favorite-good option. Hence her utility gain is \[2s\bigl(1-z-\max_i\Theta_i\bigr) = 2s(\min_i\Theta_i-z).\] Therefore the average benefit per type in the middle region equals the left-hand side of ?? , again up to the same common factor \(2s\). Consequently, ?? says exactly that, for every symmetric choice of cutoffs, the average benefit from giving the middle types the bundle is no larger than the shadow cost of the extra supply it requires.

It is then intuitive that introducing such a bundle would not be beneficial under the monotonicity condition in Corollary 1. Echoing the intuition from Example 2, offering the bundle serves to direct rewards toward agents with less extreme relative preferences. If such agents tend to have lower values for their favorite good, as measured by \(t\lambda(1-t,t)\), doing so is counterproductive. Importantly, however, the opposite monotonicity of \(t\,\lambda(1-t,t)\) is not sufficient to conclude that the designer should introduce the bundle. This is because mixing goods is an intrinsically distortionary screening device: to direct rents toward less extreme types, the mechanism must give them some of the good they value less, and must finance this by reducing other agents’ allocations of their preferred good to satisfy the supply constraint. Thus, even if agents with less extreme relative preferences tend to have higher expected total values, this correlation must be strong enough to compensate for the resulting inefficiency.

7 \(N\) kinds of goods↩︎

I now characterize when the pure option mechanism is welfare-maximizing in the case with \(N\) types of goods; I focus on presenting the result and its high-level intuitions; the technical details underlying the proof are discussed in Section 8. To state the result, I first introduce several objects.

7.0.0.1 Shadow costs of supply.

These values capture the marginal welfare gain of relaxing each supply constraint at the pure option allocation. To construct them, define \[M_i:=\int_{\Gamma_i} g(\theta)\, d\theta, \quad A_i:=\int_{\Gamma_i} \theta_i g(\theta)\lambda(\theta)\, d\theta,\] so that \(M_i\) is the mass of agents choosing option \(i\) and \(A_i\) is the designer’s total value of giving each of them a unit of good \(i\). For \(i\neq j\), define: \[T_{ij}:=\int_{\Gamma_i\cap\Gamma_j} g(\theta)\,\theta_i\, d\sigma(\theta) \Big/ \sqrt{q_i^2+q_j^2-\tfrac1N(q_i-q_j)^2},\] where \(d\sigma\) denotes \((N-2)\)-dimensional Hausdorff measure on \(\Gamma_i\cap\Gamma_j\). Note that for all \(i\) and \(j\neq i\) we have \(M_i, A_i, T_{ij} >0\).⁸ We use these objects to construct the following matrix \(J\in\mathbb{R}^{N\times N}\): \[J_{ii}=M_i+q_i\sum_{j\neq i}T_{ij}, \qquad J_{ij}=-\,q_j\,T_{ij}\;\;(i\neq j).\]

I discuss the intuition for this shadow cost construction in Section 8. Note, however, that \(c\) is pinned down entirely by primitives—the distribution \(G\), the weight function \(\lambda\), and the market-clearing pure options \(q\)—and does not depend on any endogenous objects.

7.0.0.2 Chosen-good component.

For every type \(\theta\), we define the chosen-good component \(\theta_*(\theta)\) as the coordinate of \(\theta\) corresponding to this type’s preferred option in the pure option mechanism.⁹ \[\theta_*(\theta):=\theta_i \quad\text{for }\theta\in \Gamma_i^\circ\]

7.0.0.3 Rent measure.

Define the following signed measure on the type space \(\Gamma\): \[\label{eq:signedmeas} \mu(A) = \int_{A\cap \Gamma} \theta_*\;\Bigl[ (\lambda-\textstyle\sum_j c_j) \, g + \operatorname{div}\Bigl(\bigl( c-\theta \textstyle\sum_j c_j \bigr)\, g \Bigr) \Bigr]\,d\theta -\int_{A\cap \partial\Gamma}\theta_* \, \bigl( c-\theta \textstyle\sum_j c_j \bigr)\, g \cdot\nu \,d\sigma,\tag{6}\]

where \(\nu\) is the outward unit conormal to \(\partial\Gamma\) in the hyperplane containing \(\Gamma\); the divergence is also taken within this hyperplane.

Intuitively, \(\mu\) captures the marginal welfare gain from increasing the size of a type’s preferred option by a unit. It incorporates several effects: the direct utility to the recipient weighted by \(\lambda\), the shadow cost of the additional supply required, and the incentive effects arising from tightening local incentive-compatibility constraints. Thus, \(\mu\) places negative mass on types whose allocations the designer would want to decrease after accounting for all these effects, and positive mass on those whose allocations she would want to increase. In this sense, the rent measure plays a role analogous to virtual values in one-dimensional screening.

7.0.0.4 Monotone transport plan.

The optimality conditions will be stated in terms of the shape of this rent measure \(\mu\). To formalize them, we use the following concept:

Intuitively, a transport plan specifies how one measure can be moved onto another, while allowing mass to move only upward according to the partial order \(\succeq\).

We can now state the main result of this section:

Thus, the pure option mechanism is optimal if and only if, after a certain transformation, the positive and negative parts of the rent measure are suitably positioned relative to each other. This transformation of \(\mu\) into an auxiliary measure \(\tilde{\mu}\) is described by the preprocessing step which corresponds to ironing in one-dimensional mechanism design.¹⁰ Once the measure has been preprocessed into \(\tilde{\mu}\), the second condition requires that, on each region \(\Gamma_i\), the negative part of \(\tilde{\mu}_i\) can be transported onto its positive part by moving mass only in the direction toward vertex \(e_i\), in the sense of the partial order \(\succ_i\).¹¹

Figure 8 illustrates the transport condition for a three-good example. Within each region \(\Gamma_i\), the support of the positive part of \(\tilde{\mu}_i\) (lighter shading) lies closer to the corresponding vertex \(e_i\) than the support of the negative part (darker shading). In other words, the types the designer would like to reward more under the pure option mechanism are precisely the more selective ones—those with stronger relative preferences for their chosen good. This foreshadows the sufficient conditions in Section 7.1: when higher total values \(\lambda(\theta)\) are associated with more extreme relative preferences, the transport condition is easier to satisfy, and the pure option mechanism is more likely to be optimal.

7.1 Sufficient conditions for optimality↩︎

We now derive a sufficient condition from Theorem 2 for the case of equal supplies and exchangeable distributions. To state it, we first introduce a stochastic monotonicity notion.

That is, conditional on \(E\), higher values of \(Y\) are associated with conditional distributions of \(X\) that are lower in the sense of first-order stochastic dominance with respect to \(\succeq\).

Intuitively, the condition says that the pure option mechanism is optimal when agents with higher values for their favorite good tend to be more selective: conditional on good \(i\) being their favorite, higher realizations of the weighted value \(\lambda(\Theta)\Theta_i\) are associated with smaller ratios \((\Theta_j/\Theta_i)_{j\neq i}\) in the sense of stochastic dominance. This echoes the intuition from Example 2. There, distorting the pure option menu by introducing mixtures was beneficial precisely because less selective agents had higher cardinal values. Under the condition in Proposition 2, the opposite is true, and such distortions are counterproductive.

Proposition 2 also yields the following corollary, which provides a simple, closed-form condition that can be verified directly from the marginal distribution of values:

The condition is satisfied for several standard distribution families:

We end this section with an example in which the pure option mechanism is not optimal.

This is an \(N\)-good analogue of Example 2. A fraction \(p\) of agents have common need: they value all goods highly and nearly equally. The remaining agents have specialized need: such agents are associated with one good \(j\) which they tend to strongly prefer. Since common-need agents tend to have higher values, directing rents to them by introducing a bundle is welfare-improving.

7.2 Why is the pure option mechanism often optimal?↩︎

The preceding results show that the pure option mechanism is optimal for a non-trivial set of primitives. In the symmetric i.i.d. case, for example, the reverse-hazard-rate condition in Corollary 2 is relatively permissive. While it is harder to state equally simple sufficient conditions in the general asymmetric case, the next result shows that the optimality of the pure option mechanism is not a knife-edge implication of symmetry. It shows that if optimality conditions hold with an appropriately-defined strict slack, then they continue to hold after small, possibly asymmetric, perturbations of the primitives. To formulate this notion of slack, we introduce the following definition:

This upper-set formulation arises from Strassen’s theorem, which links the existence of monotone transports to positivity on all upper sets. We then get the following result:

I use the exponential parametrization to ensure that \(\lambda\) and \(g\) remain positive after the perturbation. Note also that, as the primitives are perturbed, the market-clearing pure options \(q_i\) and the regions \(\Gamma_i\) generally change. The result then says that the corresponding pure option mechanism, with its perturbed quantities and regions, is optimal.

It is also worth noting that the upper-set slack condition is not excessively demanding. For example, it holds in the uniform symmetric environment:

These results raise a question: why is such a simple mechanism optimal in a rich class of cases? To see this, we first observe that the pure option mechanism is essentially the only one that is both Pareto-efficient (given the available supply) and incentive compatible.

Intuitively, any such mechanism coincides with the pure option mechanism up to how zero-mass indifferences are resolved. To understand why this is the case, note first that the supply constraint must bind at any Pareto-efficient allocation: if some supply were left over, distributing it uniformly across everyone would strictly raise welfare while preserving incentives. Moreover, note that Pareto efficiency is inconsistent with assigning bundles to a positive mass of types. This is because the recipients of bundles could then profitably trade among themselves so that each good in the mixture would go to those who value it relatively more. Such trades would be supply-preserving and Pareto-improving. Therefore, any Pareto-efficient allocation must be pure for almost all types. However, Fact 1 shows that there is only one pure allocation that exhausts the whole supply and satisfies ?? .

Consequently, any welfare improvement over the pure option mechanism must come from Pareto-inefficient distortions. These produce mixed allocations which are relatively more attractive to agents whose values for the bundled goods are close together.¹² Hence, any departure from Pareto efficiency necessarily rewards agents who are less picky, at least with respect to the goods being mixed. This clarifies why the pure option mechanism is optimal for one special class of distributions: those under which being less picky is always a signal of lower values. When this is the case, any such distortion shifts rents toward lower-value types, so the designer does better by adhering to the Pareto-efficient outcome. Thus, broadly speaking, the pure option mechanism is often optimal because it is associated with an entire “direction” of the designer’s Pareto weights \(\lambda\) (Figure 10).

The next result formalizes this directional intuition. Suppose the pure option mechanism is already optimal for primitives \((s,g,\lambda)\). Now, hold \(s\) and \(g\) fixed and change the designer’s Pareto weights from \(\lambda\) to \(\tilde{\lambda}\). If, within each pure-option region, the new weights place relatively more value on more selective types, then the pure option mechanism remains optimal.

The above results can be interpreted as saying that, in this environment, the designer has very limited instruments for reallocating rents across agents. This distinguishes my model from environments with transfers: in the optimal taxation model of [30], for example, a Pareto-efficient allocation is optimal only under knife-edge social preferences. This is because the designer almost always has some way of distorting this allocation in a way that directs rents her preferred way: if she wants to help low-productivity agents, she taxes labor and redistributes; if she wants to help high-productivity agents, she taxes lump-sum and subsidizes labor. Here, the designer has no such freedom. Since transfers are unavailable, she can only create indirect redistribution devices, such as offering large, mixed bundles to target flexible types. However, there is no such device the designer can construct that would redistribute rents in the opposite direction.

To conclude this section, one should note that while the discussion above has focused on targeting agents based on the strength of their relative preferences, the designer could also screen them based on which specific goods they like. Nevertheless, any potentially productive distortion of the pure option mechanism will still produce mixed bundles, so the forces discussed above will remain relevant. Consequently, if the association between the strength of relative preference and cardinal values is strong, the pure option mechanism is likely to remain optimal even when strong preferences for some goods correlate with high cardinal values.

8 Proof of Theorem 2↩︎

I now present the key steps in the proof of Theorem 2 along with additional technical intuitions; supporting facts and lemmas are shown in the appendix.

8.0.0.1 Characterizing incentive compatibility.

We first characterize incentive-compatible allocation rules in the renormalized problem using the partial order introduced in Definition 3.

It is not surprising that incentive-compatible allocation rules must produce convex indirect utility functions \(U\), as they are maxima of affine functions of \(\theta\): \[U(\theta)=\max_{\theta'\in\Gamma}\;\theta\cdot x(\theta').\] Condition ?? additionally restricts how fast indirect utility \(U(\theta)\) can grow as \(\theta\) moves towards the vertex \(e_i\). To understand why ?? is necessary for incentive compatibility, fix any good \(i\) and two types such that \(\theta \succ_i \theta'\). Note that normalizing \(U(\theta)\) by \(\theta_i\) gives: \[\frac{U(\theta)}{\theta_i} \;= \;\sum_{k\neq i} \frac{\theta_k}{\theta_i} \;x_k(\theta) \;+ \;x_i(\theta).\] We can then equivalently think of type-\(\theta\) agents as maximizing their scaled utilities \(U(\theta)/\theta_i\). Recall also that by the definition of the \(\succ_i\)-order, all the ratios \(\theta_k'/\theta_i'\) are higher for \(\theta'\) than for \(\theta\). This implies that type \(\theta'\) can always guarantee a higher scaled indirect utility than type \(\theta\): \[\frac{U(\theta')}{\theta_i'} = \sum_{k\neq i} \frac{\theta_k'}{\theta_i'} \;x_k(\theta') \;+ \;x_i(\theta') \geq \sum_{k\neq i} \frac{\theta_k}{\theta_i} \;x_k(\theta) \;+ \;x_i(\theta) = \frac{U(\theta)}{\theta_i} .\] Indeed, since \(\theta_k'/\theta_i'\geq \theta_k/\theta_i\) for all \(k\neq i\), type \(\theta'\) could guarantee \(U(\theta')/\theta_i'\) above \(U(\theta)/\theta_i\) by simply reporting \(\theta\) and taking this type’s allocation. As it turns out, convexity of \(U(\theta)\) and ?? are also sufficient for incentive compatibility.¹³

8.0.0.2 Expressing the problem in utility space.

It will be useful to reformulate the designer’s problem in terms of indirect utility functions because, as shown in Proposition 5, incentive compatibility can be characterized in terms of their shape. Indeed, writing the objective as an integral over weighted indirect utilities, rather than weighted allocations, is standard in the multidimensional screening literature.¹⁴ The reformulation relies on the following result, which follows from Proposition 5 and Lemma 8, established in its proof:

Thus, every allocation rule \(x:\Gamma\to\mathbb{R}_+^N\) that implements \(U\) is equal to \(x_U\) almost everywhere.¹⁵ Consequently, Problem 1 can be written as \[\label{eq:U-objective} \sup_{U\in\mathcal{U}} \int_\Gamma \lambda(\theta)U(\theta)g(\theta)d\theta \quad \text{subject to} \quad \int_\Gamma x_U(\theta)g(\theta)d\theta\le s,\tag{7}\] where \[\label{eq:UL} \mathcal{U}:=\{U \in C(\Gamma):\;U \text{ is convex and satisfies }\eqref{eq:pseudomono}\}.\tag{8}\]

Next, I incorporate the supply constraint in 7 into the objective using the shadow costs from Definition 4, and explain the economic intuition behind their construction.

8.0.0.3 Shadow costs: construction and intuition.

Consider an exercise in which the designer can allocate any amount of the \(N\) goods, but must pay per-unit costs \(c=(c_1,\dots,c_N)\) for them. Starting from the pure option mechanism with quantities \(q=(q_1,\dots,q_N)\), ask: what cost vector would make the designer indifferent about marginally perturbing these quantities? To pin down those costs, choose any good \(k\) and consider increasing \(q_k\) by \(\epsilon\), holding the other quantities fixed. To first order, this perturbation has two effects, illustrated in Figure 11. First, agents in \(\Gamma_k\) who chose option \(k\) before continue to do so, but now receive a higher quantity. This raises their utility and incurs an additional cost of \(c_k\,\epsilon\) per agent. Second, the perturbation induces some agents who previously chose \(q_j\), \(j\neq k\), to switch to \(q_k\). For each such agent, the designer pays \(c_k q_k\) instead of \(c_j q_j\). The direct welfare effects of these switchers are not first-order: both their mass and their welfare change are of order \(\epsilon\). As \(\epsilon\) becomes small, the sum of these effects, divided by \(\epsilon\), converges to: \[A_k - c_k M_k + \sum_{j\neq k} T_{kj}\,(c_j q_j - c_k q_k).\] Thus, the system \(Jc = A\) defining the shadow costs captures precisely the first-order conditions ensuring that such perturbations are not beneficial.

I now write \(U_{\mathrm{pure}}\) for the indirect utility from the pure option mechanism. The following result shows that we can verify the optimality of \(U_{\mathrm{pure}}\) using the Lagrangian relaxation of 7 , with the multipliers on the supply constraints set to \(c=J^{-1}A\).

8.0.0.4 Measure representation of the objective.

We now rewrite the objective in ?? using a signed measure. Moreover, we show that the measure nets to zero on each option-specific region \(\Gamma_i\). Since \(U_{\mathrm{pure}}(\theta)/\theta_*(\theta)\) is constant on each \(\Gamma_i\), this zero-mass property implies that the pure option mechanism has value zero in this representation.

Notice that, on each region \(\Gamma_i\), we have \(\theta_*(\theta)=\theta_i\). Thus \(U(\theta)/\theta_*(\theta)\) is the amount of good \(i\) that would give type \(\theta\) the same utility as \(U(\theta)\). In particular, under the pure option mechanism, \[\frac{U_{\mathrm{pure}}(\theta)}{\theta_*(\theta)}=q_i \qquad \text{for } \theta\in\Gamma_i.\] Thus, at the pure option mechanism, the rent measure multiplies the chosen pure allocation. For a general feasible mechanism, however, \(U(\theta)/\theta_i\) is not the amount of good \(i\) assigned to type \(\theta\), but the amount of good \(i\) that would give type \(\theta\) the same indirect utility. In this sense, the rent measure does not multiply the allocation directly; instead, it evaluates indirect utility expressed in units of the good chosen by that region under the pure option mechanism.¹⁶

Consequently, the positive part of the preprocessed measure, \(\tilde{\mu}^+\), places weight on types whose utilities the designer would like to raise, after accounting for how such changes propagate through the local IC constraints. Conversely, \(\tilde{\mu}^-\) places weight on types whose utilities the designer would like to reduce. The designer cannot, however, choose \(U\) freely. Proposition 5 shows that feasible allocation rules must generate indirect utilities satisfying certain shape restrictions. In particular, ?? limits how quickly \(U(\theta)\) can increase as \(\theta\) moves toward the vertices of \(\Gamma\). The pure option indirect utility \(U_{\mathrm{pure}}\) is exactly the extremal profile that makes these constraints bind on each region \(\Gamma_i\). The transport condition in Theorem 2 formalizes this idea. Intuitively, the pure option mechanism is optimal if, after possibly “ironing” the rent measure, each positive part \(\tilde{\mu}_i^+\) lies closer to the vertex \(e_i\) than the negative part \(\tilde{\mu}_i^-\). When this holds, the designer wants to raise utility most for the types closer to \(e_i\), and the best feasible way to do so is to make \(U(\theta)\) increase as rapidly as ?? permits as one moves toward that vertex. This is precisely what the pure option utility does.

Throughout the remainder of the proof, we formalize this intuition. We have already established that the pure option mechanism is optimal if and only if \(U_{\mathrm{pure}}\) solves \[\max_{U\in K} \int_\Gamma \frac{U}{\theta_*}\,d\mu \quad \text{subject to}\quad \eqref{eq:pseudomono}, \quad \text{where}\quad K := \left\{ U\in C(\Gamma): U\ge 0 \text{ and } U\text{ is convex} \right\}.\]

To establish the transport-based optimality conditions, I formulate the problem as an infinite-dimensional linear program and use a duality approach related to those previously applied by [22] and [33] to multi-product monopoly pricing and delegation, respectively. The argument shows that \(U_{\mathrm{pure}}\) is optimal if and only if there exist dual multipliers for the constraints ?? .

8.0.0.5 The designer’s problem as a linear program.

Note \(K\) is a convex cone and for each \(i\) define \[R_i := \left\{ (\theta,\theta')\in\Gamma\times\Gamma: \theta_k\theta_i'\ge \theta_k'\theta_i \text{ for every } k\neq i \right\}.\] This is the closed, cross-multiplied version of the order \(\theta\prec_i\theta'\). Since \(R_i\) is a closed subset of the compact set \(\Gamma\times\Gamma\), it is compact. Now, for \(U\in C(\Gamma)\), define \[(B_iU)(\theta,\theta') := \theta_i U(\theta')-\theta_i' U(\theta), \qquad (\theta,\theta')\in R_i.\] The constraint \(B_iU\le0\) on \(R_i\) is exactly the cross-multiplied version of ?? ; unlike the ratio form, it remains well-defined on the boundary of the simplex. This lets us write our problem as: \[\label{eq:primal} \sup_{U\in K} \left\{ \int_\Gamma \frac{U}{\theta_*}\,d\mu: B_iU\le0\text{ on }R_i \text{ for every }i \right\}.\tag{9}\] Then, the optimality of \(U_{\mathrm{pure}}\) in problem 9 is equivalent to the existence of a dual certificate:

We will soon relate these dual certificates to the transports in Theorem 2. Note, however, that while these transports happen only within some region \(\Gamma_i\), the dual certificates from Proposition 7 may place weight on pairs of types drawn from different regions \(\Gamma_i\) and \(\Gamma_j\). The next lemma shows that such cross-region constraints are redundant: any dual certificate can be replaced by one that operates entirely within each region.

That is, if a dual certificate exists at all, one can always find another that enforces the constraint ?? for good \(i\) only among pairs of types that both lie in \(\Gamma_i\).

In the final step of the proof, I rewrite the certificate condition in the form of transports on a (possibly preprocessed) rent measure.

8.0.0.6 Deriving preprocessing and transport conditions.

We first show that the conditions of Theorem 2 are sufficient. Suppose that there exists a finite signed measure \(\tilde{\mu}\) satisfying both of them. Let \(U\in K\) be feasible, so \(B_iU\le0\) on \(R_i\) for every \(i\). Fix \(i\) and let \(\pi_i\) be a \(\succ_i\)-monotone transport plan from \(\tilde{\mu}_i^-\) to \(\tilde{\mu}_i^+\). If \(\theta\prec_i\theta'\), then feasibility gives \[\frac{U(\theta')}{\theta_i'} \le \frac{U(\theta)}{\theta_i}.\] Since \(\pi_i\) is supported on such pairs, \[\int_{\Gamma_i}\frac{U(\theta)}{\theta_i}\,d\tilde{\mu}_i^+(\theta) = \int_{\Gamma_i\times\Gamma_i} \frac{U(\theta')}{\theta_i'}\,d\pi_i(\theta,\theta') \le \int_{\Gamma_i\times\Gamma_i} \frac{U(\theta)}{\theta_i}\,d\pi_i(\theta,\theta') = \int_{\Gamma_i}\frac{U(\theta)}{\theta_i}\,d\tilde{\mu}_i^-(\theta).\] Therefore \[\int_{\Gamma_i}\frac{U(\theta)}{\theta_i}\,d\tilde{\mu}_i(\theta) \le 0.\] By summing over \(i\), gluing the regionwise measures and using the fact that \(\theta_*(\theta)=\theta_i\) on \(\Gamma_i\): \[\int_{\Gamma}\frac{U(\theta)}{\theta_*(\theta)}\,d\tilde{\mu}(\theta) \le0, \quad \text{so preprocessing gives} \quad \int_{\Gamma}\frac{U(\theta)}{\theta_*(\theta)}\,d\mu(\theta)\le0.\] Thus every feasible \(U\) has value at most zero. However, we know from ?? that \(U_{\mathrm{pure}}\) attains the value zero, and so the pure option mechanism is optimal.

Conversely, suppose the pure option mechanism is optimal. By Proposition 7, there exists a dual certificate. By Lemma 3, the certificate can be chosen regionwise: for every \(i\), there exists \[\gamma_i\in\mathcal{M}_+( R_i), \qquad \operatorname{supp}(\gamma_i) \subseteq R_i\cap(\Gamma_i\times\Gamma_i),\] such that, for every \(U\in K\), \[\int_{\Gamma}\frac{U(\theta)}{\theta_*(\theta)}\,d\mu(\theta) \le \sum_{i=1}^N \int_{ R_i} B_iU(\theta,\theta')\,d\gamma_i(\theta,\theta').\] For each \(i\), let \(\pi_i\) be the measure on \(\Gamma_i\times\Gamma_i\) defined by \(d\pi_i(\theta,\theta') := \theta_i\theta_i'\,d\gamma_i(\theta,\theta').\) Since \(\gamma_i\) is supported on \(R_i\cap(\Gamma_i\times\Gamma_i)\), the measure \(\pi_i\) is supported on pairs \((\theta,\theta')\) satisfying \(\theta\prec_i\theta'\). Let \(\rho_i\) and \(\tau_i\) be the first and second marginals of \(\pi_i\) and define \(\tilde{\mu}_i:=\tau_i-\rho_i\). Then, for every \(U\in K\), \[\int_{\Gamma_i}\frac{U(\theta)}{\theta_i}\,d\tilde{\mu}_i(\theta) = \int_{\Gamma_i\times\Gamma_i} \left( \frac{U(\theta')}{\theta_i'} - \frac{U(\theta)}{\theta_i} \right) d\pi_i(\theta,\theta').\] By the definition of \(\pi_i\), this equals \[\int_{ R_i} \left( \frac{U(\theta')}{\theta_i'} - \frac{U(\theta)}{\theta_i} \right) \theta_i\theta_i'\,d\gamma_i(\theta,\theta') = \int_{ R_i} B_iU(\theta,\theta')\,d\gamma_i(\theta,\theta').\] Hence, gluing the regionwise measures and using the fact that \(\theta_*(\theta)=\theta_i\) on \(\Gamma_i\), we get: \[\int_{\Gamma}\frac{U(\theta)}{\theta_*(\theta)}\,d\mu(\theta) \le \int_{\Gamma}\frac{U(\theta)}{\theta_*(\theta)}\,d\tilde{\mu}(\theta) \qquad \text{for all }U\in K.\] In particular, the preprocessing condition holds for every continuous, convex \(U:\Gamma\to\mathbb{R}_+\).

It remains to verify the regionwise transport condition. For each \(i\), \(\pi_i\) is a \(\succ_i\)-monotone transport plan from \(\rho_i\) to \(\tau_i\). Let \(\alpha_i:=\rho_i\wedge\tau_i\) be the common part of \(\rho_i\) and \(\tau_i\). Since \(\tilde{\mu}_i=\tau_i-\rho_i\), we have \(\tilde{\mu}_i^+=\tau_i-\alpha_i\) and \(\tilde{\mu}_i^-=\rho_i-\alpha_i.\) Cancelling common mass from the two marginals preserves the existence of a \(\succ_i\)-monotone transport plan. Therefore there exists a \(\succ_i\)-monotone transport plan from \(\tilde{\mu}_i^-\) to \(\tilde{\mu}_i^+\), as required.

9 Implications for market design↩︎

The main lesson of the paper is that in settings without transfers, the welfare-maximizing mechanism depends on how agents’ absolute and relative values covary. When high-value agents tend to be more selective, the optimal mechanism should let agents choose one kind of good and only give them that one. When high-value agents tend to be less selective, the designer can sometimes do better by offering larger bundles to agents who are willing to give up choice.

This force appears in many market-design settings. Consider, for instance, the problem of allocating food donations across food banks, studied by [34], [35] and [36]. In 2005, Feeding America introduced a system under which food banks bid for donations using an artificial currency. While this currency is distributed according to a formula based on the population each food bank serves, this measure of need is imperfect because food banks also differ in the generosity of local donors operating outside the system. My results suggest that if food banks in areas with fewer local donations also have significantly weaker preferences over which food items they receive, the pseudomarket mechanism can be improved by pricing broad, pre-packaged assortments at a discount. If this relationship is weaker or reversed, however, then the pseudomarket is likely to be optimal.

A related consideration appears in affordable housing. Housing authorities often use dynamic mechanisms, such as waitlists or repeated lotteries, that allow applicants to express preferences over units. For example, in a choice-based lottery, applicants periodically list the developments they are willing to accept, and vacant units are allocated by lottery among those who listed them.¹⁷ Similarly, waitlist systems often let applicants reject offers, though sometimes at the cost of losing priority or leaving the list. As I show in Appendix 10, the baseline model can be interpreted as a reduced-form description of these dynamic mechanisms, after appropriately defining \(y_i(v)\) as the expected allocation of good \(i\) over an applicant’s time in the system. Thus, the main lessons from my model also apply to these dynamic settings. While the literature on housing allocation has noted the trade-off between choice and targeting, it has focused on extreme mechanisms giving agents no choice, or letting them choose a specific development [37], [38]. My results suggest that an intermediate design, which in my baseline model corresponds to including a large bundle, may be optimal. In such a mechanism, applicants could either choose a specific development or give up choice in exchange for priority. This could be implemented in several ways. In a waitlist setting, applicants could choose between waiting for a particular development and joining a priority queue in which they cannot reject units offered to them. Alternatively, in a repeated lottery, they could choose between applying to a unit-specific lottery and entering a pooled lottery that assigns them randomly across several units. The evidence in [6]—that lower-income households are less selective when applying for affordable housing—suggests that including such mixed options may be welfare-improving.

Finally, it is worth noting that my baseline model abstracts from observable characteristics that are important in many applications. For instance, social programs often condition priorities or eligibility on variables such as income or household size. While I do not model these explicitly, my framework could be extended to allow for such observable labels. Then, conditional on each observable label, the designer would face a screening problem of the kind studied here; across labels, these problems would be linked by the common supply constraints (see e.g. [39]). Although I do not pursue this extension here, a natural question is whether, under suitable distributional conditions, the optimal mechanism could then be implemented as a competitive equilibrium with unequal incomes, where agents receive observable-dependent budgets but participate in a common market. Alternatively, the mechanism could partition the available supply across observable groups and run separate markets within each group.

10 Waitlist interpretation↩︎

I now show that the baseline model from Section 2 can be interpreted as a reduced-form description of a steady-state waitlist setting.

10.0.0.1 Waitlist model.

Consider a stationary waitlist environment in discrete time. There are \(N\) different kinds of goods indexed by \(i\in \{1,\dots,N\}\) with \(N\geq 2\). The designer possesses a fixed mass of each, with the supplies given by \(s=(s_1,s_2,\dots,s_N)> 0\). In each period, a unit mass of new agents arrives; each of them has a profile of values \(v= (v_1,v_2,\dots,v_N)\) for the goods. The values are private information and, in each arriving cohort, are distributed according to \(F\) with support on a bounded set \(\mathcal{V}\subset \mathbb{R}^N_{+}\). This distribution puts no mass on \(\mathbf{0}\) and assigns positive mass to agents with \(v_i>0\) for every good \(i\). Agents remain in the system from one period to the next with probability \(\delta\in[0,1)\). The departure process is exogenous and independent of the agent’s type, report and allocation history.

Agents may be assigned objects in every period after they arrive in the system. Let \(\mathcal{A}:=\{\varnothing,1,\dots,N\}\) denote the set of feasible one-period assignments for an individual agent, where \(\varnothing\) denotes receiving no good. A lifetime assignment path is an element \(a=(a_0,a_1,a_2,\dots)\in\mathcal{A}^{\mathbb{N}_0}\), where \(a_t\) is the assignment made to the agent in the \(t\)-th period after entry, conditional on the agent still being in the system.

The utility of type \(v\) from a realized lifetime assignment path \(a\in \mathcal{A}^{\mathbb{N}_0}\) is then \(\sum_{t=0}^{\infty}\delta^t v_{a_t}\), with the convention \(v_{\varnothing}:=0.\) If the assignment path is random, with distribution \(Z\in\Delta(\mathcal{A}^{\mathbb{N}_0})\), the agent’s expected utility from it is \[\mathbb{E}_{a\sim Z}\Big[ \sum_{t=0}^{\infty}\delta^t v_{a_t} \Big].\]

10.0.0.2 Mechanisms.

We restrict attention to stationary mechanisms that admit a steady state. That is, the same mechanism is applied to every entering cohort, and the induced cross-sectional distribution of active agents, assignment histories, and occupied goods is constant over time. Using stationarity and the Revelation Principle, we can assume that the designer selects a stationary allocation rule \(z:\mathcal{V}\to \Delta(\mathcal{A}^{\mathbb{N}_0})\). She chooses it to maximize steady-state welfare \[\label{eq:SSwelf} \max_z \int \mathbb{E}_{a\sim z(v)}\left[ \sum_{t=0}^{\infty}\delta^t v_{a_t} \right] dF(v)\tag{10}\] subject to incentive compatibility and supply constraints: \[\label{eq:ICww} \mathbb{E}_{a\sim z(v)}\left[ \sum_{t=0}^{\infty}\delta^t v_{a_t} \right] \geq \mathbb{E}_{a\sim z(v')}\left[ \sum_{t=0}^{\infty}\delta^t v_{a_t} \right] \quad \text{for all }v,v',\tag{11}\] \[\label{eq:Sww} \sum_{t=0}^{\infty} \delta^t \int \mathbb{E}_{a\sim z(v)}\left[ \mathbf{1}\{a_t=i\} \right] dF(v) \leq s_i \quad \text{for every }i.\tag{12}\] The supply constraint says that, in the steady-state period, the total mass of agents assigned good \(i\) cannot exceed the stock \(s_i\). To see why it takes this form, note that in any calendar period there is a unit mass of newly arrived agents, a mass \(\delta\) of agents who entered one period earlier, a mass \(\delta^2\) of agents who entered two periods earlier, and so on. The sum therefore represents the steady-state use of good \(i\).¹⁸

10.0.0.3 Reduction to the static model.

We now show that this dynamic problem reduces to the static model in Section 2. Given any stationary direct allocation rule \(z:\mathcal{V}\to\Delta(\mathcal{A}^{\mathbb{N}_0})\), define the reduced-form allocation \(y:\mathcal{V}\to\mathbb{R}_+^N\) by \[y_i(v) := \mathbb{E}_{a\sim z(v)}\left[ \sum_{t=0}^{\infty}\delta^t \mathbf{1}\{a_t=i\} \right].\] Thus \(y_i(v)\) is the expected survival-weighted number of periods in which an agent reporting \(v\) receives good \(i\). By the convention \(v_{\varnothing}=0\), we have \[\mathbb{E}_{a\sim z(v')}\left[ \sum_{t=0}^{\infty}\delta^t v_{a_t} \right] = \sum_{i=1}^N v_i y_i(v') = v\cdot y(v').\] Under this notation, 10 , 11 and 12 reduce to 1 , 2 , and 3 . This also implies the following bound on the reduced-form allocation: \[\sum_{i=1}^N y_i(v) \leq \frac{1}{1-\delta} \quad \text{for every }v,\] because an agent can receive at most one good in any period. Thus the waitlist model maps directly into the baseline model with this additional individual feasibility constraint. This constraint, however, is analogous to the probability constraint discussed in Subsection 2.1 and therefore, by Proposition 1, imposing it is without loss when supply \(s\) is sufficiently scarce.

11 Optimal bundling with two kinds of goods↩︎

The construction is summarized in the following corollary. I defer the proof to the next section.

When \(a<\theta_2^0<b\), the weights are strictly positive and the menu has the three-option form in ?? . If one of the inequalities binds, both weights are equal or one of the weights is zero, and the construction reduces to the pure option mechanism.

To understand the construction, consider the shadow costs associated with the two goods’ supplies. Let us normalize the shadow cost of good \(2\) to unity and use \(\rho>0\) to denote the shadow cost of good \(1\). Under these costs, threshold rule \(z\) has total resource cost \(\rho\,\varphi_1(z)+\varphi_2(z),\) and therefore generates welfare per unit of cost equal to \[\frac{w(z)}{\rho\,\varphi_1(z)+\varphi_2(z)}.\] Note that for any fixed \(\rho\), the best such ratio gives an upper bound on what any feasible combination of threshold rules can achieve. Indeed, the total cost of the available supply is \(\rho s_1+s_2\), and each unit of cost can generate at most \[\max_{z\in[0,1]} \frac{w(z)}{\rho\,\varphi_1(z)+\varphi_2(z)}\] units of welfare, and thus every feasible mechanism gives welfare of at most \[(\rho s_1+s_2) \max_{z\in[0,1]} \frac{w(z)}{\rho\,\varphi_1(z)+\varphi_2(z)}.\] The value \(\rho^*\) is chosen to make this dual upper bound as tight as possible. Hence an optimal mechanism can put positive weight only on threshold rules that maximize the welfare-cost ratio under \(\rho^*\), namely the thresholds in \(\mathcal{Z}^*\). As explained in the main text, at most two such thresholds are needed, and they must straddle the pure-option cutoff: \(a\le \theta_2^0\le b\).

12 Omitted proofs↩︎

12.1 Technical preliminaries↩︎

12.1.1 Strassen’s theorem↩︎

The following is a special case of Strassen’s theorem stated in [40]:

12.1.2 Differential geometry facts↩︎

Let \(H\) denote the \((N-1)\)-dimensional hyperplane containing the simplex \(\Gamma\): \[H := \big\{ \theta \in \mathbb{R}^N: \;\sum \theta_i =1 \big\}.\] Note that for every \(\theta\in H\), the tangent space to \(H\) at any \(\theta\) is: \[T H := \bigl\{v\in\mathbb{R}^N \colon \sum v_i=0\bigr\}.\] Let us also define the intrinsic gradient for this surface:

I use the following divergence theorem on the affine hyperplane \(H\), which follows from Green’s formula in \(\mathbb{R}^{N-1}\) (see e.g. [44]).

12.2 Proof of Proposition 1↩︎

I show that, for \(\eta>0\) sufficiently small, every incentive-compatible allocation rule \(y\) that is feasible with supplies \(\eta s\) satisfies \(y_i(v)<1/N\) for all \(i\) and all \(v\). Let \[M:=\sup\{v_j: v\in\mathcal{V},\;j=1,\dots,N\} \;<\;\infty.\] Since each good is valued positively by a positive mass of agents, for every \(i\) there exists \(\delta_i>0\) such that \[Z_i \;:=\;F\bigl(\{v\in\mathcal{V}:\;v_i\ge \delta_i\}\bigr)>0.\] Also, define \[\bar\eta \;:=\; \min_i\frac{\delta_i Z_i}{4MN\sum_j s_j}.\] Now, for \(k\ge 0\), define \[m(k)\;:=F\big(\{v\in\mathcal{V}:\;\textstyle\sum_j y_j(v) \ge k\}\big).\] Since \(y\) is feasible for supplies \(\eta s\), it satisfies the supply constraint: \[\int_{\mathcal{V}} \sum_j y_j(v)\, dF(v) \;\le\; \sum_j \int_{\mathcal{V}} y_j(v)\, dF(v) \;\le\; \eta \sum_j s_j.\] Hence, by Markov’s inequality, for \(k>0\), \(m(k)\;\le\;\frac{1}{k}\,\eta\sum_j s_j,\) so \(m(k)\to 0\) as \(k\to\infty\). In particular, if we fix any \(i\) and set \(\tilde{k}_i \;:=\; {2\eta\sum_j s_j}/{Z_i},\) we get \(m(\tilde{k}_i)\le Z_i/2\). Therefore the set \(S :=\{v\in\mathcal{V}:\;v_i\ge\delta_i,\;\sum_j y_j(v)\le \tilde{k}_i\}\) has mass at least \(Z_i-m(\tilde{k}_i)\ge Z_i/2>0\). For every \(v\in S\) we then have: \[v\cdot y(v)\;\le\;M\sum_j y_j(v)\;\le\;M\tilde{k}_i = M\cdot\frac{2\eta\sum_j s_j}{Z_i} \;\le\; \frac{\delta_i}{2N}.\] Now suppose toward a contradiction that there exists some \(v'\in\mathcal{V}\) with \(y_i(v')\ge 1/N\). Then every \(v\in S\) would strictly profitably deviate, because for such \(v\) we have \(v\cdot y(v)\le\delta_i/(2N)\), while \[v\cdot y(v') \;\ge\;v_i\,y_i(v') \;\ge\;\delta_i\cdot\frac{1}{N} \;=\;\frac{\delta_i}{N}.\] Since \(i\) was arbitrary, it follows that \(y_i(v)<1/N\) for all \(i\) and all \(v\). For all \(v\in\mathcal{V}\) we then have \(\sum y_i(v) < 1\), so ?? is slack everywhere.

12.3 Proof of Lemma 1↩︎

Consider any feasible allocation rule \(y:\mathcal{V}\to \mathbb{R}_+^N\) in the original problem. By the boundedness argument above, \(y\) is uniformly bounded. Let \(\bar x\) be a measurable version of \(\mathbb{E}[y(V)\mid \Theta=\theta].\) Define \[K:=\overline{\operatorname{co}}\{y(v):v\in\mathcal{V}\}, \quad \text{and, for each }\theta\in\Gamma, \quad \tilde{U}(\theta) := \max_{z\in K}\theta\cdot z.\] Since \(K\) is compact, this is well-defined. Also, since the maximum of a linear function over \(K\) is the same as the supremum over \(\{y(v):v\in\mathcal{V}\}\), we have \[\tilde{U}(\theta) = \sup_{v'\in\mathcal{V}}\theta\cdot y(v').\] Moreover, if \(v\neq \mathbf{0}\), incentive compatibility gives \[\frac{v}{\sum_j v_j}\cdot y(v) \ge \frac{v}{\sum_j v_j}\cdot y(v') \qquad\text{for all }v'\in\mathcal{V}.\] Thus \(\Theta\cdot y(V)=\tilde{U}(\Theta)\) a.s. Note also that since \(\tilde{U}\) is the support function of a compact set, it is continuous.

We now modify \(\bar x\) on a null set so that incentive compatibility holds pointwise. Let \(D\subseteq\Gamma\) be a countable dense set. Since \(D\) is countable and \(q\cdot y(V)\le \tilde{U}(q)\) a.s. for each \(q\in D\), we have, after passing to a common full-measure set, \(q\cdot \bar x(\theta)\le \tilde{U}(q)\) for a.e. \(\theta\) and every \(q\in D.\) Also, since \(\Theta\cdot y(V)=\tilde{U}(\Theta)\) a.s., we get \(\theta\cdot \bar x(\theta)=\tilde{U}(\theta)\) for a.e. \(\theta\). Finally, since \(y(V)\in K\) a.s. and \(K\) is closed and convex, we also have \(\bar x(\theta)\in K\) for a.e. \(\theta.\) Therefore, there is a Borel set \(B\subseteq\Gamma\) with \(G(B)=1\) such that, for every \(\theta\in B\), \[\bar x(\theta)\in K, \qquad \theta\cdot \bar x(\theta)=\tilde{U}(\theta), \qquad q\cdot \bar x(\theta)\le \tilde{U}(q) \quad\text{for every }q\in D.\] Choose a measurable selection \(z^*(\theta)\in\mathop{\mathrm{arg\,max}}_{z\in K}\theta\cdot z\), and define \(x:\Gamma\to\mathbb{R}_+^N\) by \[x(\theta) := \begin{cases} \bar x(\theta), & \theta\in B,\\[0.4em] z^*(\theta), & \theta\notin B. \end{cases}\] Then \(x(\theta)=\mathbb{E}[y(V)\mid \Theta=\theta]\) a.e. We now check pointwise incentive compatibility. First, \(\theta\cdot x(\theta)=\tilde{U}(\theta)\) for every \(\theta\in\Gamma.\) Indeed, this holds by construction if \(\theta\notin B\), and by the definition of \(B\) if \(\theta\in B\). Next fix \(\theta,\theta'\in\Gamma\). If \(\theta'\notin B\), then \(x(\theta')\in K\), so \(\theta\cdot x(\theta') \le \tilde{U}(\theta).\)

If instead \(\theta'\in B\), choose \(q_n\in D\) with \(q_n\to\theta\). Then \(q_n\cdot x(\theta')=q_n\cdot \bar x(\theta')\le \tilde{U}(q_n)\) for every \(n\). Passing to the limit and using continuity of \(\tilde{U}\), we get \(\theta\cdot x(\theta')\le \tilde{U}(\theta)=\theta\cdot x(\theta).\)

We now verify the supply constraint. From the tower property: \[\int_\Gamma x(\theta)\,dG(\theta) = \int_\Gamma \bar x(\theta)\,dG(\theta) = \mathbb{E}\big[\mathbb{E}[y(V)\mid \Theta]\big] = \mathbb{E}[y(V)] = \int_{\mathcal{V}}y(v)\,dF(v) \le s.\] Hence \(x\) is feasible in Problem 1.

Finally, since \(V=(\sum_i V_i)\Theta\) and \(\Theta\cdot y(V)=\tilde{U}(\Theta)\) a.s., \[\begin{align} \int_{\mathcal{V}} v\cdot y(v)\,dF(v) &= \mathbb{E}[V\cdot y(V)]\\ &= \mathbb{E}\Big[\Big(\sum_i V_i\Big)\tilde{U}(\Theta)\Big]\\ &= \mathbb{E}\Big[ \mathbb{E}\Big[\sum_i V_i\mid \Theta\Big]\tilde{U}(\Theta) \Big]\\ &= \int_\Gamma \lambda(\theta)\tilde{U}(\theta)\,dG(\theta)= \int_\Gamma \lambda(\theta)\,\theta\cdot x(\theta)\,dG(\theta). \end{align}\]

Conversely, let \(x\) be feasible in Problem 1. Let \(y(\mathbf{0})=0\) and \(y(v):=x\left({v}/{\sum_i v_i}\right)\) for \(v\neq\mathbf{0}\). The supply constraint follows immediately from the definition of \(G\). Incentive compatibility follows from ?? : for \(v\neq\mathbf{0}\) and \(v'\neq\mathbf{0}\), \[v\cdot y(v) = \big(\textstyle\sum_i v_i\big) \frac{v}{\sum_i v_i}\cdot x\left(\frac{v}{\sum_i v_i}\right) \ge \left(\sum_i v_i\right) \frac{v}{\sum_i v_i}\cdot x\left(\frac{v'}{\sum_i v_i'}\right) = v\cdot y(v').\] The cases involving \(\mathbf{0}\) are trivial. Since \(F\) puts no mass on \(\mathbf{0}\), the welfare equality follows from the definition of \(\lambda\).

12.4 Proof of Fact 1↩︎

For any \(q\in \mathbb{R}_{++}^N\), define: \[x^q(\theta)\in\mathop{\mathrm{arg\,max}}_{z\in\{q_1e_1,\dots,q_Ne_N\}} \theta\cdot z.\] I now show that there exists a unique \(q\) for which \(\int_\Gamma x_i(\theta)g(\theta)d\theta=s_i\) for all \(i\), and thus that there exists a unique pure option mechanism.

Let us write \(y_i:=\log (1/q_i)\); then choosing an option \(i\) to maximize \(\theta_i q_i\) is equivalent to choosing it to maximize \(\log(\theta_i q_i)=\log \theta_i - y_i.\) Thus, the sets of agents choosing each option are given by: \[\Gamma_i(y):=\Bigl\{\theta\in\Gamma:\;\log\theta_i-y_i\ge \log\theta_j-y_j\;\text{for all }j\Bigr\}.\] For any \(y\), the induced aggregate demand for good \(i\) then equals \(e^{-y_i}m_i(y)\), where \(m_i(y):= \int_{\Gamma_i(y)}dG\). Thus, clearing is equivalent to \(e^{-y_i}m_i(y)=s_i\) for all \(i\).

Let us now define the potential \(\Psi:\mathbb{R}^N\to \mathbb{R}\cup \{-\infty\}\), with the convention that \(\log(0) = -\infty\): \[\label{eq:Psi95def} \Psi(y) :=\int_\Gamma \max_{j\in\{1,\dots,N\}}\{\log\theta_j-y_j\}g(\theta)d\theta\;+\;\sum_{j=1}^N s_j e^{y_j}.\tag{13}\]

We now show that \(\Psi(y)\) is differentiable, and that the FOC \(\nabla \Psi (y)=0\) is equivalent to market clearing. For any \(y\) and \(i\neq j\), the indifference set between \(i\) and \(j\) is \[\{\theta:\log\theta_i-y_i=\log\theta_j-y_j\} =\{\theta:\theta_i=e^{y_i-y_j}\theta_j\},\] which has measure zero. Hence, the maximizer is unique for a.e. agent. Thus, the map \(y\mapsto \max_j\{\log\theta_j-y_j\}\) is differentiable a.e., so by Danskin’s theorem and dominated convergence: \[\frac{\partial}{\partial y_i}\int_\Gamma \max_j\{\log\theta_j-y_j\}g(\theta)d\theta = -\,m_i(y).\] This gives \(\frac{\partial\Psi}{\partial y_i}(y)=-m_i(y)+s_i e^{y_i}\) and so \(\nabla\Psi(y)=0\) is equivalent to \(s_i e^{y_i}=m_i(y)\) for all \(i\), i.e. \[e^{-y_i}m_i(y)=s_i\quad \text{for all }i.\] We now show \(\Psi\) is strictly convex. For each fixed \(\theta\), the map \(y\mapsto \max_j\{\log\theta_j-y_j\}\) is the maximum of affine functions of \(y\), hence convex. Since all \(s_i>0\), the second term \(\sum_j s_j e^{y_j}\) is strictly convex in \(y\). Then, since \(\Psi\) is strictly convex and differentiable, it has at most one minimizer and the FOC holds there. It therefore remains to show that a minimizer indeed exists.

To that end, we show \(\Psi(y)\to +\infty\) along any sequence with \(\|y\|\to\infty\). If \(y_i^n\to+\infty\), then \(s_i e^{y_i^n}\to+\infty\), hence \(\Psi(y^n)\to+\infty\). If \(y_i^n\to-\infty\), fix \(\delta\in(0,1)\) and set \(U_{i,\delta}:=\{\theta\in\Gamma:\theta_i>\delta\}\). By full support, \(G(U_{i,\delta})>0\). On \(U_{i,\delta}\), \(\max_j\{\log\theta_j-y_j^n\}\ge \log\theta_i-y_i^n\ge \log\delta-y_i^n\), so \[\Psi(y^n)\;\ge\;\int_\Gamma \max_j\{\log\theta_j-y_j^n\}g(\theta)d\theta \;\ge\;G(U_{i,\delta})(\log\delta-y_i^n)\;\to\;+\infty.\] Since \(\Psi\) is continuous and coercive on \(\mathbb{R}^N\), it attains a minimum.

12.5 Proof of Fact 2↩︎

Let \((p,x)\) be a CEEI. First, note \(p_i>0\) for every \(i\): if \(p_i=0\), then every type with \(\theta_i>0\) would demand arbitrarily large amounts of good \(i\), contradicting feasibility. Now define \(q_i:=\frac{1}{p_i}\). For any bundle \(z\ge 0\) satisfying \(p\cdot z\le 1\), \[\theta\cdot z =\textstyle\sum_{j} \theta_j z_j \le \Big(\max_j \frac{\theta_j}{p_j}\Big)\sum_{j=1}^N p_j z_j \le \max_j \frac{\theta_j}{p_j} = \max_j \theta_j q_j.\] This upper bound is attained by any pure option \(q_i e_i\) with \(i\in\mathop{\mathrm{arg\,max}}_j \theta_j q_j\). Thus, for every type, at least one pure option is utility-maximizing in the CEEI demand problem, and for all but a null set of types this pure option is unique. Since the CEEI allocation clears the market, the vector \(q=(q_1,\dots,q_N)\) is a market-clearing vector of pure options. By Fact 1, this vector is uniquely pinned down, and the induced allocation coincides with the pure option mechanism up to tie-breaking among a null set of types. The argument for the representative endowment economy is analogous.

Now, consider the choice-based lottery. In any pure-strategy Nash equilibrium, the mass \(m_i\) of agents choosing each good \(i\) must satisfy \(m_i>0\); otherwise any agent with \(\theta_i>0\) would deviate to good \(i\) and receive an infinite allocation. Each agent who chose good \(i\) receives \(q_i:=s_i/m_i\) of it. In equilibrium, every type \(\theta\) must be choosing a good \(i\) that maximizes \(\theta_i q_i\); otherwise, switching to a good \(j\) with \(\theta_j q_j>\theta_i q_i\) would be profitable, since the mass of a single agent is zero and such a deviation does not change \(m_j\). Hence the equilibrium allocation coincides with the pure option mechanism with quantities \(q=(q_1,\dots,q_N)\): by Fact 1, this vector is uniquely pinned down, and the induced allocation assigns \(q_i e_i\) to almost every type \(\theta\in\Gamma_i\).

Conversely, let \(q=(q_1,\dots,q_N)\) be the market-clearing vector of pure options. Setting \(p_i=1/q_i\) implements the pure option mechanism as a CEEI. Since market clearing gives \(\sum_i s_i/q_i=1\), the same prices also implement it as a Walrasian equilibrium of the representative endowment economy. Finally, in the choice-based lottery, if each type chooses a good maximizing \(\theta_i q_i\), then \(m_i=s_i/q_i\) and hence \(s_i/m_i=q_i\). No type can profitably deviate, so this action profile is a pure-strategy Nash equilibrium.

12.6 Proof of Theorem 1↩︎

12.6.0.1 Menu structure.

I first establish that any optimal mechanism is either the pure option mechanism or has the three-option form described in ?? .

For each \(z\in[0,1]\), let \(x^z\) denote the threshold allocation rule defined in 5 . I first show that every incentive compatible allocation rule is a positive combination of threshold rules. Let \(x:\Gamma\to\mathbb{R}_+^2\) be incentive compatible and write \[U(1-t,t):=(1-t)x_1(1-t,t)+t x_2(1-t,t), \qquad \Delta(t):=x_2(1-t,t)-x_1(1-t,t).\] By the standard one-dimensional IC characterization, after changing \(x\) on a \(G\)-null set if necessary, \(\Delta\) is non-decreasing and the envelope formula holds: \[U(1-t,t)=U(1,0)+\int_0^t \Delta(s)\,ds.\] Choose a right-continuous version of \(\Delta\), and let \(\mu\) be the finite positive measure on \([0,1]\) satisfying \(\mu((0,t])=\Delta(t)-\Delta(0).\) Then \[U(1-t,t) = U(1,0)+t\Delta(0)+\int_0^t \mu((0,s])\,ds.\] By Tonelli’s theorem, \[\int_0^t \mu((0,s])\,ds = \int_{(0,t]} (t-z)\,\mu(dz).\] Hence \[U(1-t,t)=U(1,0)+t\Delta(0)+\int_{(0,t]} (t-z)\,\mu(dz).\] Since \(x_1(1-t,t)=U(1-t,t)-t\Delta(t)\) and \(x_2(1-t,t)=U(1-t,t)+(1-t)\Delta(t)\) we obtain \[x_1(1-t,t) = U(1,0)-\int_{(0,t]}z\,\mu(dz) \quad \text{and}\quad x_2(1-t,t) = U(1,0)+\Delta(0)+\int_{(0,t]}(1-z)\,\mu(dz).\] Using \(U(1,0)=x_1(1,0)\), \(U(0,1)=x_2(0,1)\) and \(\Delta(0)=x_2(1,0)-x_1(1,0)\), this becomes \[x_1(1-t,t)=x_1(0,1)+\int_{(t,1]} z\,\mu(dz) \quad \text{and}\quad x_2(1-t,t)=x_2(1,0)+\int_{[0,t]} (1-z)\,\mu(dz),\] up to values at cutoff types. Since \(x\ge0\), we have \(x_1(0,1),x_2(1,0)\ge0\). Thus, defining \[\nu:=\mu+x_2(1,0)\delta_0+x_1(0,1)\delta_1,\] we obtain, almost surely, \[\label{eq:measure95rep95x1x295short} x_1(1-t,t)=\int_{(t,1]} z\,\nu(dz) \quad \text{and}\quad x_2(1-t,t)=\int_{[0,t]} (1-z)\,\nu(dz).\tag{14}\] Equivalently, \[\label{eq:measure95rep95xz95short} x(1-t,t)=\int_{[0,1]} x^z(1-t,t)\,\nu(dz)\tag{15}\] up to values at cutoff types, including the endpoints \(t=0,1\).

Conversely, suppose \(x\) is given by 14 for some finite positive measure \(\nu\). Then \(x_1,x_2\ge0\), and \[\Delta(t):=x_2(1-t,t)-x_1(1-t,t) = \nu([0,t])-\int_{[0,1]}z\,\nu(dz),\] which is non-decreasing in \(t\). Moreover, \[U(1-t,t) = (1-t)x_1(1-t,t)+t x_2(1-t,t) = \int_{[0,1]}\max\{z(1-t),(1-z)t\}\,\nu(dz),\] and therefore \[U(1-t,t)=U(1,0)+\int_0^t \Delta(s)\,ds.\] Hence the one-dimensional IC characterization implies that \(x\) satisfies ?? .

Thus the designer’s problem can be rewritten as a linear program over positive measures \(\nu\). Applying Fubini’s theorem to 15 , we obtain \[\int_\Gamma \lambda(\theta)U(\theta)\,dG(\theta) = \int_{[0,1]} w(z)\,\nu(dz) \quad \text{and}\quad \int_\Gamma x(\theta)\,dG(\theta) = \int_{[0,1]}\varphi(z)\,\nu(dz).\] Therefore, the designer’s problem is \[\label{eq:primalLP} W^* = \sup_{\nu\ge0} \left\{ \int_{[0,1]} w(z)\,\nu(dz): \int_{[0,1]}\varphi_1(z)\,\nu(dz)\le s_1,\quad \int_{[0,1]}\varphi_2(z)\,\nu(dz)\le s_2 \right\}.\tag{16}\] The functions \(w,\varphi_1,\varphi_2\) are continuous. Since \(\varphi_1(z)+\varphi_2(z)>0\), continuity guarantees that it is bounded away from zero for \(z\in[0,1]\). Thus the feasible set of 16 has uniformly bounded total mass and is weak-* compact. Since the objective is weak-* continuous, an optimal measure exists. The dual of 16 is \[\inf_{c_1,c_2\ge0} \left\{ c_1s_1+c_2s_2: c_1\varphi_1(z)+c_2\varphi_2(z)\ge w(z) \quad\text{for all }z\in[0,1] \right\}.\] By conic duality, strong duality holds (see e.g.[45]). Let \(\nu^*\) be a primal optimizer and let \((c_1^*,c_2^*)\) be a dual optimizer. Note also that both constraints bind at \(\nu^*\). Indeed, if the first constraint were slack, adding a small mass at \(z=1\) would use only good \(1\) and would strictly increase welfare, since \(w(1)=\mathbb{E}[\lambda(\Theta)\Theta_1]>0\). Similarly, if the second constraint were slack, adding a small mass at \(z=0\) would use only good \(2\) and would strictly increase welfare, since \(w(0)=\mathbb{E}[\lambda(\Theta)\Theta_2]>0\). Therefore \[\int_{[0,1]}\varphi(z)\,\nu^*(dz)=s.\] By strong duality, \[\int_{[0,1]} w(z)\,\nu^*(dz) = c_1^*s_1+c_2^*s_2 = \int_{[0,1]}\bigl(c_1^*\varphi_1(z)+c_2^*\varphi_2(z)\bigr)\nu^*(dz).\] Since \(c_1^*\varphi_1(z)+c_2^*\varphi_2(z)\ge w(z)\) for all \(z\), it follows that \(\nu^*\) is supported on the contact set \[E:= \left\{ z\in[0,1]: c_1^*\varphi_1(z)+c_2^*\varphi_2(z)=w(z) \right\}, \quad \text{and hence} \quad s\in\operatorname{cone}\{\varphi(z):z\in E\}\subset\mathbb{R}^2.\] By Carathéodory’s theorem for cones in \(\mathbb{R}^2\), there exist \(a,b\in E\), with \(a\le b\), and \(m_a,m_b\ge0\) such that \(m_a\varphi(a)+m_b\varphi(b)=s.\) Because \(a,b\in E\), the measure \(\hat{\nu}:=m_a\delta_a+m_b\delta_b\) is feasible and satisfies \[\int_{[0,1]}w(z)\,\hat{\nu}(dz) = \int_{[0,1]}\bigl(c_1^*\varphi_1(z)+c_2^*\varphi_2(z)\bigr)\hat{\nu}(dz) = c_1^*s_1+c_2^*s_2 = W^*.\] Thus there is an optimal measure supported on at most two points.

The induced allocation rule is therefore \(x(1-t,t)=m_a x^a(1-t,t)+m_b x^b(1-t,t)\), so \[x(1-t,t)= \begin{cases} (am_a+bm_b,\,0), & t<a,\\[4pt] (bm_b,\,(1-a)m_a), & a\le t<b,\\[4pt] (0,\,(1-a)m_a+(1-b)m_b), & t\ge b. \end{cases}\] Thus the mechanism offers at most three options: a pure good-\(1\) option, a bundle, and a pure good-\(2\) option.

12.6.0.2 Characterizing optimality of the pure option mechanism.

First, note that by Fact 1, the pure option mechanism is unique. In the threshold-rule representation, it is given by the Dirac measure \[\frac{s_1}{\varphi_1(\theta^0_2)}\delta_{\theta^0_2}.\] The welfare of the pure option mechanism is thus \[\label{eq:pure95welfare95short} \frac{s_1}{\varphi_1(\theta^0_2)}w(\theta^0_2).\tag{17}\] By the preceding argument, the pure option mechanism is optimal if and only if no nondegenerate mechanism of the form in ?? generates higher welfare. Such mechanisms are exactly those generated by two distinct thresholds \(a,b\in(0,1)\), with \(a<b\), and weights \(m_a,m_b>0\) satisfying \[m_a\varphi(a)+m_b\varphi(b)=s.\] Since the ratio \(\varphi_1(z)/\varphi_2(z)\) is strictly increasing, the vectors \(\varphi(a)\) and \(\varphi(b)\) are linearly independent, so this equation has at most one solution. Moreover, a strictly positive solution exists if and only if \(s\) lies in the interior of the cone generated by \(\varphi(a)\) and \(\varphi(b)\), or equivalently \[\frac{\varphi_1(a)}{\varphi_2(a)} < \frac{s_1}{s_2} < \frac{\varphi_1(b)}{\varphi_2(b)}.\] Since \(\theta^0_2\) is the pure-option cutoff, we have \[\frac{s_1}{s_2} = \frac{\varphi_1(\theta^0_2)}{\varphi_2(\theta^0_2)}.\] By strict monotonicity of \(\varphi_1/\varphi_2\), the preceding condition is therefore equivalent to \(a<\theta^0_2<b.\) Finally, the welfare generated by this nondegenerate mechanism is \(m_aw(a)+m_bw(b)\). Condition ?? is therefore satisfied if and only if the pure option mechanism gives weakly higher welfare than any such menu.

12.7 Proof of Corollary 5↩︎

Let \[M(\rho):=\max_{z\in[0,1]}\frac{w(z)}{\rho\varphi_1(z)+\varphi_2(z)}.\] By the proof of Theorem 1, the designer’s problem has dual \[\inf_{c_1,c_2\ge0} \left\{ c_1s_1+c_2s_2: c_1\varphi_1(z)+c_2\varphi_2(z)\ge w(z) \quad\text{for all }z\in[0,1] \right\}.\] Evaluating the dual constraint at \(z=1\), where \(\varphi(1)=(1,0)\), and at \(z=0\), where \(\varphi(0)=(0,1)\), gives \(c_1\ge w(1)>0\) and \(c_2\ge w(0)>0\). Thus, we can write \(\rho=c_1/c_2\). Dual feasibility is then equivalent to \[c_2\ge \frac{w(z)}{\rho\varphi_1(z)+\varphi_2(z)} \quad\text{for all }z\in[0,1],\] and hence \(c_2\ge M(\rho)\). Conversely, for every \(\rho>0\), the pair with \(c_2=M(\rho),\) \(c_1=\rho M(\rho)\) is dual feasible. Therefore, the dual value is \[\inf_{\rho>0}(\rho s_1+s_2)M(\rho).\] In particular, if \(\rho^*\) solves the minimization problem in the statement, then the pair with \(c_2^*:=M(\rho^*),\) \(c_1^*:=\rho^*M(\rho^*)\) is dual optimal.

Now, let \(E\) be the contact set of this dual optimizer: \[E:= \left\{ z\in[0,1]: w(z)=c_1^*\varphi_1(z)+c_2^*\varphi_2(z) \right\}.\] Since \(c_1^*=\rho^*c_2^*\), we have \[E=\mathop{\mathrm{arg\,max}}_{z\in[0,1]}\frac{w(z)}{\rho^*\varphi_1(z)+\varphi_2(z)}.\] Moreover, the maximizers are interior. To see this, fix any \(\rho>0\). If \(0<z<1/(1+\rho)\), then \[\rho\varphi_1(z)+\varphi_2(z)<1-z \quad\text{and}\quad w(z)>(1-z)w(0), \quad \text{and hence} \quad \frac{w(z)}{\rho\varphi_1(z)+\varphi_2(z)} > \frac{w(0)}{\rho\varphi_1(0)+\varphi_2(0)}.\] Thus \(0\) cannot be a maximizer. Similarly, if \(1/(1+\rho)<z<1\), then \[\rho\varphi_1(z)+\varphi_2(z)<\rho z \quad\text{and}\quad w(z)>z w(1), \quad \text{and hence} \quad \frac{w(z)}{\rho\varphi_1(z)+\varphi_2(z)} > \frac{w(1)}{\rho\varphi_1(1)+\varphi_2(1)}.\] Thus \(1\) cannot be a maximizer. Applying this to \(\rho=\rho^*\), all maximizers are interior. Therefore \[E = \mathop{\mathrm{arg\,max}}_{z\in(0,1)}\frac{w(z)}{\rho^*\varphi_1(z)+\varphi_2(z)} = \mathcal{Z}^*.\]

By the cone and ratio-monotonicity arguments in the proof of Theorem 1, applied to the contact set \(E=\mathcal{Z}^*\), there exist \(a,b\in\mathcal{Z}^*\) such that \(a\le\theta_2^0\le b\). If \(a=b\), the construction reduces to the pure option mechanism. Otherwise, the same argument gives unique weights \(m_a,m_b\ge0\) satisfying \(m_a\varphi(a)+m_b\varphi(b)=s,\) with \(m_a,m_b>0\) exactly when \(a<\theta_2^0<b\). Now, suppose \(a<b\), and let \(\nu:=m_a\delta_a+m_b\delta_b\). Since \(a,b\in E\), the measure \(\nu\) is supported on the contact set of a dual optimizer and clears both resources. Therefore, by complementary slackness, \[\int_{[0,1]}w(z)\,\nu(dz) = \int_{[0,1]} \bigl(c_1^*\varphi_1(z)+c_2^*\varphi_2(z)\bigr)\nu(dz) = c_1^*s_1+c_2^*s_2 = W^*,\] and so the allocation induced by \(\nu\) is optimal.

Finally, by the menu-construction step in the proof of Theorem 1, the optimal measure \(\nu=m_a\delta_a+m_b\delta_b\) is implemented by the menu in ?? with quantities given by ?? .

12.8 Proof of Corollary 1↩︎

Because \(g\) and \(\lambda\) are exchangeable and \(s_1=s_2\), the problem is symmetric. Thus, given any feasible allocation rule, we can reflect it by swapping the two goods and then average the original rule with its reflection. This preserves feasibility and welfare, so we can restrict attention to symmetric mechanisms without loss. Then, by Theorem 1, a symmetric optimum is either the symmetric pure option mechanism, with cutoff \(1/2\), or is generated by a symmetric pair of thresholds \(z,1-z\), with \(z\in[0,1/2]\). In the notation of Corollary 5, this means that the symmetric pure option mechanism is optimal if and only if \[\frac{w(1-z)}{\varphi_1(1-z)+\varphi_2(1-z)} \le \frac{w(1/2)}{\varphi_1(1/2)+\varphi_2(1/2)} \qquad\text{for all }z\in[0,1/2).\]

Fix \(z\in[0,1/2)\). By exchangeability, \[w(1-z) = \frac{1}{2} \mathbb{E}\left[ \lambda(\Theta) \left( (1-z)\mathbf{1}_{\{\min_i\Theta_i\ge z\}} + \max_i\Theta_i\,\mathbf{1}_{\{\min_i\Theta_i<z\}} \right) \right],\] and \[\varphi_1(1-z)+\varphi_2(1-z) = \frac{1}{2}\left( 1+(1-2z)\mathbb{P}(\min_i\Theta_i\ge z) \right).\] Moreover, \[\frac{w(1/2)}{\varphi_1(1/2)+\varphi_2(1/2)} = \mathbb{E}[\lambda(\Theta)\max_i\Theta_i].\] Thus, the preceding optimality condition is equivalent to \[\mathbb{E}\left[ \lambda(\Theta) \left(\min_i\Theta_i-z\right) \mathbf{1}_{\{\min_i\Theta_i\ge z\}} \right] \le (1-2z)\, \mathbb{E}[\lambda(\Theta)\max_i\Theta_i]\, \mathbb{P}(\min_i\Theta_i\ge z).\] Since \(\mathbb{P}(\min_i\Theta_i\ge z)>0\) for \(z\in[0,1/2)\), dividing gives ?? .

It remains to prove the sufficient condition. Suppose that \(t\,\lambda(1-t,t)\) is non-decreasing on \([1/2,1]\). On \(\{\min_i\Theta_i\ge z\}\), we have \(\max_i\Theta_i\in[1/2,1-z]\), and hence \[\min_i\Theta_i-z = 1-z-\max_i\Theta_i \le (1-2z)\max_i\Theta_i.\] Therefore \[\mathbb{E}\left[ \lambda(\Theta)(\min_i\Theta_i-z) \;\middle|\; \min_i\Theta_i\ge z \right] \le (1-2z) \mathbb{E}\left[ \lambda(\Theta)\max_i\Theta_i \;\middle|\; \min_i\Theta_i\ge z \right].\] By exchangeability, \[\lambda(\Theta)\max_i\Theta_i = \max_i\Theta_i\, \lambda(1-\max_i\Theta_i,\max_i\Theta_i),\] which is non-decreasing in \(\max_i\Theta_i\) by assumption. Since conditioning on \(\min_i\Theta_i\ge z\) restricts \(\max_i\Theta_i\) to the lower set \([1/2,1-z]\), we have \[\mathbb{E}\left[ \lambda(\Theta)\max_i\Theta_i \;\middle|\; \min_i\Theta_i\ge z \right] \le \mathbb{E}[\lambda(\Theta)\max_i\Theta_i].\] Combining the last two inequalities gives ?? .

12.9 Proof of Fact 4↩︎

It is enough to show that \(J\) is invertible and that \(J^{-1}A\) is strictly positive. Define \(k_i:=c_iq_i.\) Then \(Jc=A\) is equivalent to \(Hk=A,\) where \[H_{ii}=\frac{M_i}{q_i}+\sum_{j\neq i}T_{ij}, \qquad H_{ij}=-T_{ij}\le0\quad(i\neq j).\] For each row \(i\), \[H_{ii}-\sum_{j\neq i}|H_{ij}| = \frac{M_i}{q_i} > 0.\] Thus \(H\) is a strictly diagonally dominant \(Z\)-matrix. Hence \(H\) is nonsingular and is a nonsingular \(M\)-matrix, so \(H^{-1}\ge0\) entrywise. Since \(A>0\), this gives \[k=H^{-1}A\ge0.\] In fact \(k>0\). Indeed, \(H^{-1}\ge0\) and \(H^{-1}\) is invertible, so each row of \(H^{-1}\) contains at least one strictly positive entry. Since \(A>0\), every component of \(H^{-1}A\) is strictly positive. Therefore \(k_i>0\) for every \(i\). Finally, since \(q_i>0\), \[c_i=\frac{k_i}{q_i}>0.\]

12.10 Proof of Proposition 2↩︎

We verify the condition of Theorem 2 with \(\tilde{\mu}=\mu\). The preprocessing condition then holds with equality. Moreover, by the balance condition ?? , \(\mu_i(\Gamma_i)=0\), so \(\mu_i^+(\Gamma_i)=\mu_i^-(\Gamma_i)\). Since the order relation \(\succ_i\) is closed on \(\Gamma_i\), Theorem 3 implies that it is enough to show \(\mu_i(C)\ge 0\) for every closed \(\succ_i\)-upper set \(C\subseteq\Gamma_i\).

Under exchangeability and equal supplies, the pure option mechanism is symmetric, so \(q_1=...=q_N\) and hence \(\theta^0=\frac{1}{N}\mathbf{1}\). Also all \(A_i\) are equal; denote the common value by \(\bar A\). Therefore the shadow costs satisfy \(c=N\bar A\,\mathbf{1}\) and \(\sum_j c_j=N^2\bar A\). Plugging this into 6 , for any Borel set \(\Omega\subseteq\Gamma_i\), \[\label{eq:symmmeasure95new} \mu_i(\Omega) = \int_{\Omega} \lambda\,\theta_i\, g \,d\theta -N^2\bar A\int_{\Omega}\theta_i\big[\operatorname{div}\big((\theta-\theta^0) g\big)+ g \big]\,d\theta +N^2\bar A\int_{\Omega\cap \partial \Gamma }\theta_i\, g \, (\theta-\theta^0)\cdot\nu\; d\sigma.\tag{18}\]

We first claim that for every \(\succ_i\)-upper set \(C\subseteq \Gamma_i\), \[\label{eq:upper95mean95ineq95final} \int_C \lambda\,\theta_i\,g\,d\theta \;\ge\; N\bar A \int_C g\,d\theta.\tag{19}\] Indeed, since \(q_1=...=q_N\), the set \(\Gamma_i\) coincides up to a null set with \(\{\Theta_i\ge \Theta_j\;\forall j\neq i\}\). Also, by definition of \(\succ_i\), every \(\succ_i\)-upper set \(C\subseteq\Gamma_i\) can be written as \(C=\{\theta\in\Gamma_i:\;R_i(\theta)\in B\}\) for some \(\ge\)-lower set \(B\subseteq \mathbb{R}_+^N\). Since \(B^c\) is then \(\ge\)-upper, the assumed stochastic monotonicity implies that for every \(t\ge 0\), \[\mathbb{P} \left[\Theta\in C \,\middle|\, \lambda(\Theta)\Theta_i\ge t,\;\Theta\in\Gamma_i\right] \ge \mathbb{P} \left[\Theta\in C \,\middle|\, \Theta\in\Gamma_i\right].\] Integrating over \(t\) yields \[\mathbb{E} \left[\lambda(\Theta)\Theta_i\,\mathbf{1}_{\{\Theta\in C\}} \,\middle|\, \Theta\in\Gamma_i\right] \ge \mathbb{P} \left[\Theta\in C \,\middle|\, \Theta\in\Gamma_i\right] \mathbb{E} \left[\lambda(\Theta)\Theta_i \,\middle|\, \Theta\in\Gamma_i\right].\] Equivalently, \[\int_C \lambda\,\theta_i\,g\,d\theta \ge \frac{\int_{\Gamma_i}\lambda\,\theta_i\,g\,d\theta}{\int_{\Gamma_i}g\,d\theta}\int_C g\,d\theta.\] Under exchangeability, \(\int_{\Gamma_i}g\,d\theta=\frac{1}{N}\) and \(\int_{\Gamma_i}\lambda\,\theta_i\,g\,d\theta=\bar A\), giving 19 .

Next, let \(C\subseteq\Gamma_i\) be a \(\succ_i\)-upper set with Lipschitz boundary. Applying Theorem 4 to the tangent field \((\theta-\theta^0)g\) on \(C\), and using \(\nabla_H\theta_i=e_i-\frac{1}{N}\mathbf{1}\), we obtain \[\int_C \theta_i\Big[\operatorname{div}\big((\theta-\theta^0)g\big)+g\Big]\,d\theta = \int_{\partial C}\theta_i\,(\theta-\theta^0)\cdot \nu_C\, g\,d\sigma +\frac{1}{N}\int_C g\,d\theta,\] where \(\nu_C\) is the outward unit conormal to \(\partial C\). Substituting this into 18 gives \[\mu_i(C) = \int_C \lambda\,\theta_i\,g\,d\theta - N\bar A\int_C g\,d\theta - N^2\bar A\int_{\partial C\cap \Gamma^\circ}\theta_i\,(\theta-\theta^0)\cdot \nu_C\, g\,d\sigma.\] By 19 , the first two terms are weakly positive. It therefore suffices to show that \((\theta-\theta^0)\cdot \nu_C\le 0\) for a.e. \(\theta\in\partial C\cap\Gamma^\circ\). But if \(\theta\in\Gamma_i\cap\Gamma^\circ\), then for every small \(t>0\) we have \(\theta+t(\theta-\theta^0)\succ_i\theta\): indeed, for every \(k\neq i\), \[\frac{\theta_k+t(\theta_k-\theta_k^0)}{\theta_i+t(\theta_i-\theta_i^0)}\le \frac{\theta_k}{\theta_i} \quad\Longleftrightarrow\quad \frac{\theta_k^0}{\theta_i^0}\ge \frac{\theta_k}{\theta_i},\] and this holds because \(\theta\in\Gamma_i\) and \(\theta^0=\frac{1}{N}\mathbf{1}\). Since \(C\) is \(\succ_i\)-upper, the ray from \(\theta^0\) through any boundary point of \(C\) stays in \(C\) locally beyond that point, so \(\theta-\theta^0\) cannot point outward. Hence \((\theta-\theta^0)\cdot \nu_C\le 0\) a.e. on \(\partial C\cap\Gamma^\circ\), and therefore \(\mu_i(C)\ge 0\).

We now extend this logic to all closed \(\succ_i\)-upper sets using the following lemma:

Finally, let \(C\subseteq\Gamma_i\) be any closed \(\succ_i\)-upper set. By Lemma 4, there exists a decreasing sequence of closed \(\succ_i\)-upper sets \(K_m\downarrow C\), each a finite union of polytopes in \(H\), hence each with Lipschitz boundary. By the previous paragraph, \(\mu_i(K_m)\ge 0\) for every \(m\). Since \(\mu_i\) is finite, continuity from above gives \(\mu_i(C)=\lim_{m\to\infty}\mu_i(K_m)\ge 0\). Thus condition \(1.\) of Theorem 3 holds, so \(\mu_i^+\) \(\succ_i\)-stochastically dominates \(\mu_i^-\). Since this is true for every \(i\), Theorem 2 implies that the pure option mechanism is optimal.

12.11 Proof of Corollary 2↩︎

The i.i.d.assumption implies that the induced \(g\) and \(\lambda\) are exchangeable. Since supplies are symmetric, Proposition 2 applies once we verify its stochastic monotonicity condition.

Fix \(i\), and write \(E_i:=\{V_i\ge V_j\text{ for all }j\neq i\}.\) Conditional on \(V_i=k\) and \(E_i\), the coordinates \(\{V_j:j\neq i\}\) are independent and each has distribution \(F_M\) truncated to \([0,k]\). Hence, for \(j\neq i\) and \(t\in(0,1)\), \[\mathbb{P}\left[\frac{V_j}{V_i}\ge t\;\middle|\;V_i=k,\;E_i\right] = 1-\frac{F_M(tk)}{F_M(k)}.\] It is therefore enough to show that \(F_M(tk)/F_M(k)\) is non-decreasing in \(k\). Differentiating gives \[\frac{\partial}{\partial k}\frac{F_M(tk)}{F_M(k)} = \frac{F_M(tk)}{F_M(k)} \left[ t\,\frac{f_M(tk)}{F_M(tk)} - \frac{f_M(k)}{F_M(k)} \right].\] The bracketed term can be written as \[\frac{1}{k} \left[ tk\,\frac{f_M(tk)}{F_M(tk)} - k\,\frac{f_M(k)}{F_M(k)} \right],\] which is nonnegative by ?? , since \(tk\le k\). Thus \(V_j/V_i\) is \(\ge\)-stochastically decreasing in \(V_i\) conditional on \(E_i\). Since the ratios are conditionally independent across \(j\neq i\), the whole vector \[\left(\frac{V_1}{V_i},\dots,\frac{V_N}{V_i}\right)\] is \(\ge\)-stochastically decreasing in \(V_i\) conditional on \(E_i\); see Theorem 3.3.10 in [46].

Now, let \(C\subseteq\Gamma_i\) be any \(\succ_i\)-upper set. Since \({\Theta_j}/{\Theta_i}={V_j}/{V_i},\) membership in \(C\) is determined by a coordinatewise lower set of the ratio vector \((V_1/V_i,\dots,V_N/V_i)\). The stochastic monotonicity just proved therefore implies that, for every \(t\ge0\), \[\mathbb{P}[\Theta\in C\mid V_i\ge t,\;E_i] \ge \mathbb{P}[\Theta\in C\mid E_i].\] Integrating over \(t\) gives \[\mathbb{E}[V_i\mathbf{1}_{\{\Theta\in C\}}\mid E_i] \ge \mathbb{P}[\Theta\in C\mid E_i]\,\mathbb{E}[V_i\mid E_i].\] Since \(E_i\) and \(C\) are determined by \(\Theta\) and \(\mathbb{E}[V_i\mid \Theta] = \Theta_i\,\mathbb{E}\big[\sum V_j\mid \Theta\big] = \lambda(\Theta)\Theta_i,\) this gives \[\int_C \lambda(\theta)\theta_i g(\theta)\,d\theta \ge \frac{\int_{\Gamma_i}\lambda(\theta)\theta_i g(\theta)\,d\theta}{\int_{\Gamma_i}g(\theta)\,d\theta} \int_C g(\theta)\,d\theta.\] By exchangeability, \(\int_{\Gamma_i}g(\theta)\,d\theta=1/N\) and \(\int_{\Gamma_i}\lambda(\theta)\theta_i g(\theta)\,d\theta=\bar A\), so \[\int_C \lambda(\theta)\theta_i g(\theta)\,d\theta \ge N\bar A\int_C g(\theta)\,d\theta.\] This is exactly the inequality needed in the proof of Proposition 2.

12.12 Proof of Proposition 3↩︎

I use a superscript \(*\) for objects associated with the baseline primitives \(p^*\). For objects associated with other primitive vectors, I write, for example, \(\Gamma_i(p)\), \(q(p)\), \(c(p)\), and \(\mu^p\).

Let \(\mathcal{S}_i(p)\) denote the collection of closed \(\succ_i\)-upper sets \(C\subseteq\Gamma_i(p)\). For \(p\) for which the vector of pure options \(q(p)\) is well defined, define the region-identification map \(\Phi_i^p:\Gamma_i^*\to\Gamma_i(p)\) by \[\Phi_i^p(\theta)=\theta^p,\] where \[r_{ik}^p(\theta) := \frac{q_i(p)/q_k(p)}{q_i^*/q_k^*} \frac{\theta_k}{\theta_i}, \quad k\neq i, \qquad \theta_k^p = \begin{cases} \displaystyle \frac{1}{1+\sum_{l\neq i}r_{il}^p(\theta)}, & k=i,\\[12pt] \displaystyle r_{ik}^p(\theta)\, \frac{1}{1+\sum_{l\neq i}r_{il}^p(\theta)}, & k\neq i. \end{cases}\]

Thus \(\Phi_i^{p^*}\) is the identity on \(\Gamma_i^*\), and \(\Phi_i^p\) is a homeomorphism from \(\Gamma_i^*\) onto \(\Gamma_i(p)\). The following fact comes directly from the definition:

Given a signed measure \(\nu^p\) on \(\Gamma\), define its pasted pullback \(\hat{\nu}^p\) region by region, by requiring that for each \(i\), \[\hat{\nu}^p\restriction_{\Gamma_i^*}(C) := \nu^p(\Phi_i^p(C)), \qquad C\subseteq\Gamma_i^*\text{ Borel}.\] Equivalently, whenever \(C\subseteq\Gamma_i^*\), the notation \(\hat{\nu}^p(C)\) means this \(i\)-th regionwise pullback.

The next lemma gives a convenient sufficient condition for being close in the pulled-back upper-set topology.

We now connect this measure-side topology to primitive perturbations.

We now complete the proof. Apply Lemma 7 with \(r=\eta/2\). After shrinking \(\varepsilon>0\) if necessary, every primitive vector \(p\) satisfying the displayed perturbation bound has \[q(p),\quad c(p),\quad \Gamma_i(p),\quad \Phi_i^p,\quad \mu^p\] well defined, with \(q(p)\in\mathbb{R}^N_{++}\), and satisfies \(d_{\mathrm{US}}^p(\mu^p,\mu^*)<\eta/2.\) By Lemma 5, it follows that, for every \(i\) and every closed \(\succ_i\)-upper set \(D\subseteq\Gamma_i(p)\), \(\mu^p(D)\ge0.\) Now fix \(i\), and write \[\mu_i^p:=\mu^p\restriction_{\Gamma_i(p)}.\] Since the rent measure is regionwise balanced, \(\mu_i^p(\Gamma_i(p))=0.\) Let \((\mu_i^p)^+\) and \((\mu_i^p)^-\) denote the positive and negative parts of \(\mu_i^p\). Then \[(\mu_i^p)^+(\Gamma_i(p)) = (\mu_i^p)^-(\Gamma_i(p)).\] Moreover, for every closed \(\succ_i\)-upper set \(D\subseteq\Gamma_i(p)\), \[(\mu_i^p)^+(D)-(\mu_i^p)^-(D) = \mu_i^p(D) = \mu^p(D) \ge0; \quad \text{equivalently,}\quad (\mu_i^p)^-(D)\le(\mu_i^p)^+(D).\] By Theorem 3, there exists a \(\succ_i\)-monotone transport plan from \((\mu_i^p)^-\) to \((\mu_i^p)^+\). Since \(i\) was arbitrary, this verifies the regionwise transport condition in Theorem 2, with the auxiliary measure chosen to be \(\tilde{\mu}=\mu^p.\) Therefore, Theorem 2 applies to the primitives \(p\), and the pure option mechanism associated with \(p\) is optimal.

12.13 Proof of Proposition 4↩︎

Fix such an allocation rule \(x\); note that Pareto-efficiency implies that supply constraints ?? bind for it. Indeed, if it were slack, we could give every agent a representative share of the remaining supply. Since almost all agents have strictly positive values for every good, this would produce a strict Pareto improvement while preserving ?? .

Next, we show that almost every type receives at most one kind of good. Suppose, towards a contradiction, that a positive mass of types receive a bundle. Then there exist \(i\neq j\) such that \[M:=\{\theta\in\Gamma:\;x_i(\theta)>0,\;x_j(\theta)>0\}\] has positive measure. Since \(G\) admits a density on \(\Gamma\), the faces \(\{\theta_i=0\}\) and \(\{\theta_j=0\}\), as well as every level set \(\{\theta_i/\theta_j=t\}\), have \(G\)-measure zero. Thus, after discarding a null subset of \(M\), the ratio \(\theta_i/\theta_j\) is finite and is not concentrated at a single value, so there exists \(t>0\) such that both \[M^-:=M\cap\{\theta_i/\theta_j<t\}, \qquad M^+:=M\cap\{\theta_i/\theta_j>t\}\] have positive \(G\)-measure. Define \[m^-:=\int_{M^-}x_i(\theta)\,dG(\theta)>0, \qquad m^+:=\int_{M^+}x_j(\theta)\,dG(\theta)>0.\] Choose \(\delta\in(0,1]\) small enough that \(t\delta\frac{m^-}{m^+}\le 1\) and define \(\tilde{x}:\Gamma\to\mathbb{R}_+^N\) by setting \(\tilde{x}_k(\theta)=x_k(\theta)\) for all \(k\notin\{i,j\}\), and \[(\tilde{x}_i(\theta),\tilde{x}_j(\theta))= \begin{cases} \bigl((1-\delta)x_i(\theta),\;x_j(\theta)+t\delta x_i(\theta)\bigr), & \theta\in M^-,\\[3pt] \bigl(x_i(\theta)+\delta\frac{m^-}{m^+}x_j(\theta),\; (1-t\delta\frac{m^-}{m^+})x_j(\theta)\bigr), & \theta\in M^+,\\[3pt] \bigl(x_i(\theta),x_j(\theta)\bigr), & \theta\notin M^-\cup M^+. \end{cases}\] This allocation rule is nonnegative by the choice of \(\delta\).

The aggregate use of goods \(i\) and \(j\) is unchanged because \[\int_\Gamma(\tilde{x}_i-x_i)\,dG = -\delta m^-+\delta\frac{m^-}{m^+}m^+ =0, \qquad \int_\Gamma(\tilde{x}_j-x_j)\,dG = t\delta m^- -t\delta\frac{m^-}{m^+}m^+ =0.\] All other goods are unchanged, so \(\tilde{x}\) satisfies the same supply constraints as \(x\).

Finally, \(\tilde{x}\) Pareto-dominates \(x\). For \(\theta\notin M^-\cup M^+\), utility is unchanged. For \(\theta\in M^-\), \[\theta\cdot(\tilde{x}(\theta)-x(\theta)) = -\delta \theta_i x_i(\theta)+t\delta\theta_j x_i(\theta) = \delta x_i(\theta)(t\theta_j-\theta_i)>0,\] because \(\theta_i/\theta_j<t\) on \(M^-\). Similarly, for \(\theta\in M^+\), \[\theta\cdot(\tilde{x}(\theta)-x(\theta)) = \delta\frac{m^-}{m^+}\theta_i x_j(\theta) - t\delta\frac{m^-}{m^+}\theta_j x_j(\theta) = \delta\frac{m^-}{m^+}x_j(\theta)(\theta_i-t\theta_j)>0,\] because \(\theta_i/\theta_j>t\) on \(M^+\). This contradicts Pareto efficiency. Therefore, for every \(i\neq j\), \[G\bigl(\{\theta:\;x_i(\theta)>0,\;x_j(\theta)>0\}\bigr)=0.\] It follows that \(x\) is pure almost everywhere: for almost every \(\theta\), either \(x(\theta)=0\) or \(x(\theta)=x_i(\theta)e_i\) for some \(i\). For each \(i\), define \[S_i:=\{\theta\in\Gamma:\;x(\theta)=x_i(\theta)e_i,\;x_i(\theta)>0\}.\] Since the \(i\)-th supply constraint binds and \(s_i>0\), each \(S_i\) has positive \(G\)-measure.

Since \(G\) assigns zero mass to the boundary faces, we may ignore types with \(\theta_i=0\) when comparing allocations within \(S_i\). Now take any \(\theta,\theta'\in S_i\). If \(x_i(\theta)>x_i(\theta')\), then type \(\theta'\) would strictly prefer to report \(\theta\), since \[\theta'\cdot x(\theta) = \theta'_i x_i(\theta) > \theta'_i x_i(\theta') = \theta'\cdot x(\theta').\] The reverse inequality is ruled out symmetrically.

Hence there exists \(q_i^*>0\) such that \(x(\theta)=q_i^*e_i\) for a.e. \(\theta\in S_i.\) Define the induced cells \(C_i:=\{\theta\in\Gamma:\;\theta_iq_i^*\ge \theta_kq_k^* \text{ for all }k\}.\) If \(\theta\in S_i\), then incentive compatibility against reports in \(S_k\) implies \[\theta_i q_i^* = \theta\cdot x(\theta) \ge \theta\cdot(q_k^*e_k) = \theta_k q_k^* \qquad\text{for every }k.\] Thus \(S_i\subseteq C_i\).

Conversely, consider the strict part of \(C_i\), \[C_i^\circ := \{\theta\in\Gamma:\;\theta_iq_i^*>\theta_kq_k^* \text{ for all }k\neq i\}.\] For almost every \(\theta\in C_i^\circ\), the allocation \(x(\theta)\) is pure or zero. Such a type must receive \(q_i^*e_i\). Indeed, if it received zero, or if it received \(q_k^*e_k\) for some \(k\neq i\), then reporting any type in \(S_i\) would give utility \(\theta_iq_i^*\), which is strictly larger than its utility from the allocation assigned to it. This violates incentive compatibility. Therefore, \(x(\theta)=q_i^*e_i\) for almost every \(\theta\in C_i^\circ\). The boundaries between the cells \(C_i\) have \(G\)-measure zero, since they are contained in finitely many hyperplanes of the form \(\{\theta:\;\theta_iq_i^*=\theta_jq_j^*\}.\) Hence \(x\) coincides almost everywhere with the pure-option allocation that gives \(q_i^*e_i\) on \(C_i^\circ\). Since all supply constraints bind, this pure-option allocation clears markets: \[s_i = \int_\Gamma x_i(\theta)\,dG(\theta) = q_i^*\,G(C_i) \qquad\text{for every }i.\] Thus \(q^*=(q_1^*,\dots,q_N^*)\) is a market-clearing vector of pure options. By Fact 1, the market-clearing vector of pure options is unique. Hence \(q^*=q\), where \(q\) is the pure-option vector. Moreover, the cells \(C_i^\circ\) coincide with the corresponding pure-option regions \(\Gamma_i^\circ\).

12.14 Proof of Corollary 3↩︎

Let \(\mu\) and \(\mu'\) denote the rent measures associated with \((s,g,\lambda)\) and \((s,g,\tilde{\lambda})\), respectively. Since \(g\) and \(s\) are unchanged, the pure option mechanism and hence \(\theta^0\) and the regions \(\Gamma_i\) are unchanged. Moreover, the existence of a \(\succ_i\)-monotone transport plan from \(\nu_i\) to \(\tilde{\nu}_i\) implies \[\int_{\Gamma_i}\theta_i\tilde{\lambda}\,g\,d\theta = \int_{\Gamma_i}\theta_i\lambda\,g\,d\theta \qquad\text{for every }i,\] so the vector \(A\), and hence the shadow costs \(c=J^{-1}A\), are also unchanged.

Define the signed measure \(\Delta:=\mu'-\mu\). Inspecting the definition of the rent measure, the only term that changes when \(\lambda\) is replaced by \(\tilde{\lambda}\) is the first one. Hence, for every measurable \(\Omega\subseteq\Gamma_i\), \[\Delta_i(\Omega) = \mu'_i(\Omega)-\mu_i(\Omega) = \int_\Omega(\tilde{\lambda}-\lambda)\theta_i g\,d\theta = \tilde{\nu}_i(\Omega)-\nu_i(\Omega).\] Thus \(\Delta_i(\Gamma_i)=0\). Also, if \(C\subseteq\Gamma_i\) is a closed \(\succ_i\)-upper set, then any \(\succ_i\)-monotone transport plan from \(\nu_i\) to \(\tilde{\nu}_i\) can only move mass into \(C\), not out of it. Therefore \(\nu_i(C)\le \tilde{\nu}_i(C)\), and hence \(\Delta_i(C)\ge 0.\)

Now let \(\tilde{\mu}\) be a certificate for \((s,g,\lambda)\) in Theorem 2. We claim that \(\tilde{\mu}+\Delta\) is a certificate for \((s,g,\tilde{\lambda})\). First, for every continuous, convex \(U:\Gamma\to\mathbb{R}_+\), \[\int_\Gamma \frac{U(\theta)}{\theta_*(\theta)}\,d\mu'(\theta) = \int_\Gamma \frac{U(\theta)}{\theta_*(\theta)}\,d\mu(\theta) + \int_\Gamma \frac{U(\theta)}{\theta_*(\theta)}\,d\Delta(\theta) \le \int_\Gamma \frac{U(\theta)}{\theta_*(\theta)}\,d\tilde{\mu}(\theta) + \int_\Gamma \frac{U(\theta)}{\theta_*(\theta)}\,d\Delta(\theta),\] where the inequality uses the preprocessing condition for \(\tilde{\mu}\). Thus the preprocessing condition holds for \(\tilde{\mu}+\Delta\).

It remains to verify regionwise transport. Fix \(i\). Since \(\tilde{\mu}\) is a certificate, the second condition of Theorem 2 gives a \(\succ_i\)-monotone transport plan from \(\tilde{\mu}_i^-\) to \(\tilde{\mu}_i^+\). Equivalently, by Theorem 3, this implies \(\tilde{\mu}_i(C)\ge 0\) for every closed \(\succ_i\)-upper set \(C\subseteq\Gamma_i\). Combining this with \(\Delta_i(C)\ge0\), we get \[(\tilde{\mu}_i+\Delta_i)(C)\ge0\] for every closed \(\succ_i\)-upper set \(C\subseteq\Gamma_i\). Also, \(\tilde{\mu}_i(\Gamma_i)=0\) because \(\tilde{\mu}_i^-\) can be transported to \(\tilde{\mu}_i^+\), and \(\Delta_i(\Gamma_i)=0\) by normalization. Hence \((\tilde{\mu}_i+\Delta_i)(\Gamma_i)=0\). Applying Theorem 3 again, there exists a \(\succ_i\)-monotone transport plan from \((\tilde{\mu}_i+\Delta_i)^-\) to \((\tilde{\mu}_i+\Delta_i)^+\). Thus \(\tilde{\mu}+\Delta\) satisfies the regionwise transport condition. Therefore, by Theorem 2, the pure option mechanism is optimal for \((s,g,\tilde{\lambda})\).

12.15 Proof of Proposition 5↩︎

Necessity has been shown in the main body. Let us then show sufficiency. We first show the following lemma.

Assume that \(U:\Gamma\to\mathbb{R}_+\) is convex and satisfies ?? . Let \(\mathcal{D}\subseteq \Gamma^\circ\) denote the set of points at which \(\nabla_H U\) exists. For \(\theta\in\mathcal{D}\), define \(x_U(\theta)\) by ?? . By Lemma 8, there is some \(M_U>0\) such that \[0\le (x_U)_k(\theta)\le M_U \qquad\text{for every }k,\;\theta\in\mathcal{D}\] and \(U\) is Lipschitz on \(\Gamma\). We now extend \(x_U\) to all of \(\Gamma\). For each \(\theta\in\Gamma\), let \[X(\theta) := \left\{ z\in\mathbb{R}_+^N: \begin{array}{l} \text{there exists a sequence } \theta^m\in\mathcal{D} \text{ such that } \theta^m\to\theta\\ \text{and } x_U(\theta^m)\to z \end{array} \right\}.\] This set is nonempty because \(\mathcal{D}\) is dense in \(\Gamma\), and it is compact because \(x_U(\mathcal{D})\subseteq[0,M_U]^N\). The graph of the correspondence \(X\) is closed, and its values are nonempty compact subsets of \([0,M_U]^N\). Hence, by the measurable selection theorem, there exists a Borel measurable selection \(x(\theta)\in X(\theta)\). Then \(x(\theta)\in\mathbb{R}_+^N\) for every \(\theta\in\Gamma\).

We claim that this allocation rule implements \(U\). Fix \(\theta\in\Gamma\), and take a sequence \(\theta^m\in\mathcal{D}\) such that \(\theta^m\to\theta\) and \(x_U(\theta^m)\to x(\theta)\). Since \(U(\theta^m)=\theta^m\cdot x_U(\theta^m)\) for every \(m\), and since \(U\) is continuous, passing to the limit gives \[\label{eq:U-implemented-by-extension} U(\theta)=\theta\cdot x(\theta).\tag{22}\]

We now verify incentive compatibility. To that end, define \(p(\theta) := x(\theta) - \mathbf{1}\,\tfrac1N\sum x_j(\theta).\) We show: \[\label{eq:p-subgradient-extension} U(\theta')\ge U(\theta)+p(\theta)\cdot(\theta'-\theta) \qquad\text{for every }\theta'\in\Gamma.\tag{23}\] Indeed, for each \(m\), set \[p^m := x_U(\theta^m) - \mathbf{1}\,\tfrac1N\sum (x_U)_j(\theta^m).\] Because \(\nabla_H U(\theta^m)\in TH\), the definition of \(x_U\) implies \(p^m=\nabla_H U(\theta^m)\). Hence, by convexity, \[U(\theta')\ge U(\theta^m)+p^m\cdot(\theta'-\theta^m) \qquad\text{for every }\theta'\in\Gamma.\] Since \(x_U(\theta^m)\to x(\theta)\), we have \(p^m\to p(\theta)\). Passing to the limit gives 23 .

Now, fix \(\theta,\theta'\in\Gamma\). Using 22 at \(\theta'\), we have \[\theta\cdot x(\theta') = U(\theta')+x(\theta')\cdot(\theta-\theta').\] Since \(\theta-\theta'\in TH\), the component of \(x(\theta')\) parallel to \(\mathbf{1}\) drops out, so \[x(\theta')\cdot(\theta-\theta') = p(\theta')\cdot(\theta-\theta').\] By 23 , applied at \(\theta'\), \[U(\theta) \ge U(\theta')+p(\theta')\cdot(\theta-\theta').\] Combining the last three statements gives \(U(\theta)\ge \theta\cdot x(\theta').\) Using again 22 , this is exactly \(\theta\cdot x(\theta) \ge \theta\cdot x(\theta')\) for all \(\theta,\theta'\in\Gamma.\)

12.16 Proof of Proposition 6↩︎

For \(U\in\mathcal{U}\), write \[\Phi(U):=\int_\Gamma \lambda \,U \,g \,d\theta, \qquad \Pi(U):=\int_\Gamma x_U \,g\,d\theta.\] Recall that by definition, \(\Pi(U_{\mathrm{pure}})=s.\) By Fact 4, \(c=J^{-1}A\in\mathbb{R}_{++}^N.\) First suppose \(U_{\mathrm{pure}}\) solves the shadow-cost problem ?? . Let \(U\in\mathcal{U}\) be feasible for 7 . Then \(\Pi(U)\le s\). Since \(c\ge0\), \[\Phi(U) \le \Phi(U)-c\cdot(\Pi(U)-s).\] By optimality of \(U_{\mathrm{pure}}\) in ?? , \[\Phi(U)-c\cdot(\Pi(U)-s) \le \Phi(U_{\mathrm{pure}}) - c\cdot(\Pi(U_{\mathrm{pure}})-s) = \Phi(U_{\mathrm{pure}}).\] Therefore \(\Phi(U)\le \Phi(U_{\mathrm{pure}})\) for every feasible \(U\), so \(U_{\mathrm{pure}}\) solves 7 .

Conversely, suppose \(U_{\mathrm{pure}}\) solves 7 . Define \[P(r):=\sup_{U\in\mathcal{U}}\{\Phi(U):\Pi(U)\le r\}, \qquad r\in\mathbb{R}_+^N.\] The function \(P\) is finite, increasing, and concave. Indeed, if \(\Pi(U)\le r\), then \[0\le U(\theta)=\theta\cdot x_U(\theta) \le \sum_i (x_U)_i(\theta) \qquad \text{a.e.},\] so, writing \(\bar\lambda\) for an upper bound on \(\lambda(\theta)\), \[\Phi(U)\le \bar\lambda\int_\Gamma U\,dG \le \bar\lambda\sum_i\Pi_i(U) \le \bar\lambda\sum_i r_i.\] Thus \(P(r)<\infty\). Monotonicity is immediate. Concavity follows from the convexity of \(\mathcal{U}\) and the identity \[x_{tU+(1-t)V}=tx_U+(1-t)x_V \qquad \text{a.e.}\]

Since \(s\in\mathbb{R}_{++}^N\), \(s\) is an interior point of \(\mathbb{R}_+^N\). Hence the finite concave function \(P\) has a supergradient at \(s\). Thus there exists \(c^*\in\mathbb{R}^N\) such that \[P(r)\le P(s)+c^*\cdot(r-s) \qquad\text{for all }r\in\mathbb{R}_+^N.\] Because \(P\) is increasing, necessarily \(c^*\ge0\).

Since \(U_{\mathrm{pure}}\) solves 7 and \(\Pi(U_{\mathrm{pure}})=s\), we have \(P(s)=\Phi(U_{\mathrm{pure}}).\) Now fix any \(U\in\mathcal{U}\), and set \(r:=\Pi(U)\). Then \[\Phi(U) \le P(r) \le P(s)+c^*\cdot(r-s).\] Hence \[\Phi(U)-c^*\cdot(\Pi(U)-s) \le \Phi(U_{\mathrm{pure}}).\] Using \(\Pi(U_{\mathrm{pure}})=s\), this becomes \[\Phi(U)-c^*\cdot(\Pi(U)-s) \le \Phi(U_{\mathrm{pure}}) - c^*\cdot(\Pi(U_{\mathrm{pure}})-s).\] Thus \(U_{\mathrm{pure}}\) maximizes the Lagrangian with multiplier \(c^*\).

It remains to identify this multiplier. To that end, we show the following lemma.

Let \(h\in\mathbb{R}^N\). For all sufficiently small \(t\), the perturbation \[U_{q+th}(\theta):=\max_i\theta_i(q_i+th_i)\] is admissible in \(\mathcal{U}\). Therefore the function \[t \mapsto \Phi(U_{q+th})-c^*\cdot(\Pi(U_{q+th})-s)\] has a local maximum at \(t=0\). Hence \[0 = \left.\frac{d}{dt}\right|_{t=0} \left[ \Phi(U_{q+th})-c^*\cdot(\Pi(U_{q+th})-s) \right].\] By Lemma 9, \[0 = A\cdot h - \sum_j c_j^*\sum_iJ_{ij}h_i = \sum_i \big(A_i-\sum_jJ_{ij}c_j^*\big)h_i.\] Since \(h\in\mathbb{R}^N\) was arbitrary, \(Jc^*=A.\) By Fact 4, \(c^*=J^{-1}A=c\), so \(U_{\mathrm{pure}}\) solves ?? .

12.17 Proof of Lemma 2↩︎

Step 1: Measure formulation. Dropping the constant \(c\cdot s\), the objective is \[\label{eq:bound1} \int_\Gamma \lambda\,U\, g\,d\theta - \int_\Gamma c\cdot x_U\, g\,d\theta.\tag{24}\] Using the definition of \(x_U\), \[\begin{align} \int_\Gamma x_U\cdot c \, g\, d\theta &= \int_\Gamma \left(\nabla_H U - \mathbf{1}(\nabla_H U \cdot \theta-U) \right) \cdot c \, g\, d\theta\\ &= \int_\Gamma \left(\nabla_H U - (\nabla_H U \cdot \theta) \;\mathbf{1} \right) \cdot c \, g\, d\theta + (\sum c_j) \int_\Gamma U\, g\, d\theta\\ &= \int_\Gamma \bigl( c- (\sum c_j) \,\theta\bigr) \;g \cdot \nabla_H U \;d\theta \;+\; (\sum c_j) \int_\Gamma U\, g\, d\theta. \end{align}\] Now, \(c- (\sum c_j)\,\theta \in TH\) because \(( c- (\sum c_j)\,\theta)\cdot \mathbf{1}=0\); also, \(U\) is Lipschitz by Corollary 4. We can therefore apply Theorem 4 to the former integral on the RHS above. This gives: \[\int_\Gamma \bigl( c - (\sum c_j)\,\theta\bigr) \, g\cdot \nabla_H U\,d\theta = -\int_\Gamma U\,\operatorname{div} \big[\bigl( c - (\sum c_j)\,\theta\bigr)\, g \big]\,d\theta + \int_{\partial \Gamma} U\, \bigl( c - (\sum c_j)\,\theta\bigr)\, g\cdot\nu \, d\sigma.\] We therefore get: \[\int_\Gamma x_U\cdot c \, g\, d\theta = \int_\Gamma U\, \left((\sum c_j)\; g -\operatorname{div} \big[\bigl( c - (\sum c_j)\,\theta\bigr)\, g \big]\right) \,d\theta + \int_{\partial\Gamma} U\,\big( c-(\sum c_j)\theta\big) \;g \cdot\nu \, d\sigma.\] Plugging back into 24 and collecting terms gives: \[\int_\Gamma U\left[ \lambda\, g + \operatorname{div} \left[\bigl( c - (\sum c_j)\,\theta\bigr)\, g \right] - (\sum c_j)\; g \right]d\theta - \int_{\partial\Gamma} U\,\big( c-(\sum c_j)\theta\big) \;g \cdot\nu \, d\sigma.\]

Step 2: Balance on each region \(\Gamma_i\). We now prove that \(\mu\) is balanced on each region \(\Gamma_i\). Applying Theorem 4 with \(\Omega=\Gamma_i^\circ\), \(\eta(\theta)=\theta_i\) and \(X(\theta)=( c-(\sum c_j)\,\theta)\, g(\theta)\) we get: \[\int_{\Gamma_i}\theta_i\,\operatorname{div} \left[ ( c-(\sum c_j)\,\theta)\,g \right]\,d\theta + \int_{\Gamma_i}\nabla_H\theta_i\cdot ( c-(\sum c_j)\,\theta)\,g \,d\theta =\int_{\partial\Gamma_i}\theta_i\, ( c-(\sum c_j)\,\theta)\,g \cdot\nu\,d\sigma .\] Substitute this into the definition of \(\mu(\Gamma_i)\) to obtain: \[\begin{align} \mu(\Gamma_i) &= A_i -\int_{\Gamma_i}\nabla_H\theta_i\cdot\big( c-(\sum c_j)\theta\big)\,g\,d\theta -(\sum c_j) \;\int_{\Gamma_i}\theta_i \;g\,d\theta \nonumber\\ &\qquad +\int_{\partial\Gamma_i}\theta_i\,\big( c-(\sum c_j)\theta\big) \;g \cdot\nu\,d\sigma -\int_{ \partial\Gamma \cap \Gamma_i}\theta_i\,\big( c-(\sum c_j)\theta\big)\;g\cdot\nu\,d\sigma . \label{eq:mu95after95ibp95theta} \end{align}\tag{25}\] Note that \(\nabla_H\theta_i =e_i-\tfrac1N\mathbf{1}\), and hence: \[-\int_{\Gamma_i}\nabla_H\theta_i\cdot\big( c-(\sum c_j)\theta\big)\,g\,d\theta = -\int_{\Gamma_i}( c_i-(\sum c_j)\theta_i)\,g\,d\theta = - c_i M_i+(\sum c_j)\int_{\Gamma_i}\theta_i g\,d\theta.\] Substituting into 25 and simplifying gives: \[\mu(\Gamma_i) = A_i - c_i M_i +\int_{\partial\Gamma_i}\theta_i\,\big( c-(\sum c_j)\theta\big)\, g \cdot\nu \, d\sigma -\int_{ \partial\Gamma \cap \Gamma_i}\theta_i\,\big( c-(\sum c_j)\theta\big)\,g \cdot\nu \, d\sigma .\] Combining the boundary terms gives \[\mu(\Gamma_i) = A_i - c_i M_i +\int_{\partial\Gamma_i\setminus (\partial\Gamma \cap \Gamma_i)}\theta_i\,\big( c-(\sum c_j)\theta\big) \,g \cdot\nu\,d\sigma.\] Note that, up to lower-dimensional edges, we have \(\partial\Gamma_i\setminus (\partial\Gamma \cap \Gamma_i) \;=\; \bigcup_{k\neq i} \Gamma_i \cap \Gamma_k,\) giving: \[\label{eq:mu95boundary95sum} \mu(\Gamma_i) = A_i - c_i M_i + \sum_{k\neq i}\int_{\Gamma_i \cap \Gamma_k} \theta_i\,\big( c-(\sum c_j)\theta\big)\,g \cdot\nu_{ik}^{(i)} \,d\sigma,\tag{26}\] where \(\nu_{ik}^{(i)}\) is the outward unit conormal from \(\Gamma_i\) into \(\Gamma_k\) along \(\Gamma_i \cap \Gamma_k\). Now, fix \(k\neq i\) and note \(\Gamma_i \cap \Gamma_k\) is the level set of \(q_i\theta_i-q_k\theta_k\), with \(q_i\theta_i-q_k\theta_k=0\) on \(\Gamma_i \cap \Gamma_k\), and: \[\nu_{ik}^{(i)}=-\frac{\nabla_H (q_i\theta_i-q_k\theta_k)}{\|\nabla_H( q_i\theta_i-q_k\theta_k)\|}.\] Thus, the integrand in the last term of 26 becomes: \[\begin{align} \theta_i\,\big( c-(\sum c_j)\theta\big)\,g \cdot\nu_{ik}^{(i)} \;&=\; -\big( c-(\sum c_j)\theta\big)\cdot \nabla_H (q_i\theta_i-q_k\theta_k) \;g \; \frac{\theta_i}{\|\nabla_H( q_i\theta_i-q_k\theta_k)\|} \\ &=-\big( c-(\sum c_j)\theta\big)\cdot (q_i (e_i-\tfrac1N \mathbf{1}) - q_k (e_k-\tfrac1N \mathbf{1})) \;g \; \frac{\theta_i}{\|\nabla_H( q_i\theta_i-q_k\theta_k)\|} \\ &=-\left[ q_i( c_i-(\sum c_j)\theta_i)-q_k( c_k-(\sum c_j)\theta_k) \right] \;g \; \frac{\theta_i}{\|\nabla_H( q_i\theta_i-q_k\theta_k)\|} \\ &=(q_k c_k-q_i c_i) \;g \; \frac{\theta_i}{\|\nabla_H( q_i\theta_i-q_k\theta_k)\|}, \end{align}\] where the last line follows because on \(\Gamma_i \cap \Gamma_k\) we have \(q_i\theta_i=q_k\theta_k\), so the \((\sum c_j)\)-terms cancel. Since \(q_k c_k-q_i c_i\) is constant along \(\Gamma_i \cap \Gamma_k\), substituting into 26 gives: \[\mu(\Gamma_i) = A_i - c_i M_i + \sum_{k\neq i} \; (q_k c_k-q_i c_i)\int_{\Gamma_i \cap \Gamma_k} g\,\frac{\theta_i}{\|\nabla_H(q_i\theta_i-q_k\theta_k)\|} \,d\sigma.\] Moreover: \[\nabla_H\bigl(q_i\theta_i-q_k\theta_k\bigr) = q_i (e_i-\tfrac1N \mathbf{1}) - q_k (e_k-\tfrac1N \mathbf{1}) \quad \Longrightarrow \quad \bigl\| \nabla_H\bigl(q_i\theta_i-q_k\theta_k\bigr) \bigr\|^2 = (q_i^2+q_k^2)-\frac{(q_i-q_k)^2}{N},\] and therefore: \[\mu(\Gamma_i) = A_i- c_i M_i +\sum_{k\neq i}(q_k c_k-q_i c_i)\,T_{ik}.\] Finally, the \(i\)th row of the system \(J c=A\) gives exactly: \[A_i- c_i M_i +\sum_{k\neq i}(q_k c_k-q_i c_i)\,T_{ik}=0,\] so \(\mu(\Gamma_i)=0\) by the construction of the cost vector \(c\).

12.18 Proof of Proposition 7↩︎

\((\Leftarrow)\). Suppose there exists a dual certificate \((\gamma_1,\dots,\gamma_N)\). Then, for every \(U\in K\), \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \sum_{i=1}^N \int_{ R_i} B_iU\,d\gamma_i .\] If \(U\) is feasible for 9 , then \(B_iU\le0\) on \(R_i\) for every \(i\). Since each \(\gamma_i\) is nonnegative, \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \sum_{i=1}^N \int_{ R_i} B_iU\,d\gamma_i \le0.\]

By ?? , we have that \(\int_\Gamma \frac{U_{\mathrm{pure}}}{\theta_*}d\mu=0\), which gives \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \int_\Gamma \frac{U_{\mathrm{pure}}}{\theta_*}\,d\mu .\] Thus \(U_{\mathrm{pure}}\) is primal optimal.

\((\Rightarrow)\). We introduce the ordered Banach space \[Y:=\prod_{i=1}^N C( R_i),\] with the product sup norm and the pointwise order. The primal constraints are \(B_iU\le0\) on \(R_i\), for every \(i\). Note also that \(\mathcal{U}\), defined in 8 , can be written as \[\mathcal{U} = \left\{ U\in K: B_iU\le0\text{ on } R_i \text{ for every }i \right\}.\] We first show the following lemma:

We now use Lemma 10 to prove existence of a certificate. Recall that by ?? , \[\int_\Gamma \frac{U_{\mathrm{pure}}}{\theta_*}\,d\mu=0.\] Since \(U_{\mathrm{pure}}\) is optimal for 9 , we have \[\label{eq:KR-nonpositive-no-lip} \int_\Gamma \frac{U}{\theta_*}\,d\mu\le0 \qquad \text{for all } U\in \mathcal{U}.\tag{30}\]

Let \[\mathcal{C} := \left\{ \Big( (- B_iU-w_i)_{i=1}^N,\, \int_\Gamma \frac{U}{\theta_*}\,d\mu-r \right): U\in K,\;(w_i)_{i=1}^N\in Y_{+},\;r\ge0 \Big\} \subseteq Y\times\mathbb{R},\] where \(Y_{+}\) denotes the positive cone of \(Y\). We now show the following fact:

Since \(\overline{\mathcal{C}}\) is a closed convex cone and \((0,1)\notin\overline{\mathcal{C}}\), Hahn–Banach separation gives a nonzero continuous linear functional \[(\Lambda,\lambda)\in Y^*\times\mathbb{R} \quad \text{such that} \quad \Lambda(z)+\lambda q\le0 \quad \text{for all } (z,q)\in\overline{\mathcal{C}}.\] Since \(0\in\overline{\mathcal{C}}\), we can orient the separating functional so that it strictly separates \((0,1)\) from \(\overline{\mathcal{C}}\): \(\Lambda(z)+\lambda q\le0<\Lambda(0)+\lambda=\lambda\) for all \((z,q)\in\overline{\mathcal{C}}.\) Thus \(\lambda>0\). We normalize \(\lambda=1\).

Now take any tuple \(w=(w_1,\dots,w_N)\) with \(w_i\in C( R_i)\) and \(w_i\ge0\) on \(R_i\) for every \(i\). Then \((-w,0)\in\mathcal{C}\), so the separating inequality gives \(-\Lambda(w)\le0\). Thus, \(\Lambda(w)\ge0\) for every componentwise nonnegative tuple \(w\). For every \(U\in K\), taking \(w=0\) and \(r=0\) gives \[\Big( (- B_iU)_{i=1}^N,\, \int_\Gamma \frac{U}{\theta_*}\,d\mu \Big) \in\mathcal{C}.\] Therefore \[\label{eq:functional-dual-no-lip} -\Lambda\bigl(( B_iU)_{i=1}^N\bigr) + \int_\Gamma \frac{U}{\theta_*}\,d\mu \le0, \quad\text{or equivalently,}\quad \int_\Gamma \frac{U}{\theta_*}\,d\mu \le \Lambda\bigl(( B_iU)_{i=1}^N\bigr) \quad \text{for all } U\in K.\tag{31}\] Since \(\Lambda\) is a positive continuous linear functional on \(\prod_{i=1}^N C( R_i)\), the Riesz representation theorem gives finite positive Borel measures \(\gamma_i\in\mathcal{M}_+( R_i)\), \(i=1,\dots,N\), such that \[\Lambda\bigl(( B_iU)_{i=1}^N\bigr) = \sum_{i=1}^N \int_{ R_i} ( B_iU)(\theta,\theta')\,d\gamma_i(\theta,\theta') \qquad \text{for all } U\in K.\] Substituting this representation into 31 gives \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \sum_{i=1}^N \int_{ R_i} ( B_iU)(\theta,\theta')\,d\gamma_i(\theta,\theta') \qquad \text{for all } U\in K.\]

12.19 Proof of Lemma 3↩︎

Let \((\gamma_1,\dots,\gamma_N)\) be a dual certificate. Applying ?? to \(U_{\mathrm{pure}}\), using ?? and \(B_iU_{\mathrm{pure}}\le0\) gives \[0 \le \sum_{i=1}^N\int_{ R_i} B_iU_{\mathrm{pure}}\,d\gamma_i \le0.\] Thus each integral is zero. Since \(B_iU_{\mathrm{pure}}\le0\) and \(\gamma_i\ge0\), we may restrict attention to \[E_i:= \{(\theta,\theta')\in R_i: B_iU_{\mathrm{pure}}(\theta,\theta')=0\}.\]

We first remove the part of the measure supported where both coefficients in \(B_i\) vanish. Let \[Z_i := \{(\theta,\theta')\in R_i:\theta_i=\theta_i'=0\}.\] For every \(U\in K\), \(B_iU(\theta,\theta')=0\) on \(Z_i\). Thus replacing \(\gamma_i\) by \(\gamma_i|_{ R_i\setminus Z_i}\) does not change the functional \(U\mapsto \int_{ R_i} B_iU\,d\gamma_i\). Hence, without loss, assume \(\gamma_i(Z_i)=0\).

Now partition each \(E_i\setminus Z_i\) into such common regions. Set \[S_{i1} := (E_i\setminus Z_i)\cap(\Gamma_1\times\Gamma_1),\] and, for \(j\ge2\), \[S_{ij} := (E_i\setminus Z_i)\cap(\Gamma_j\times\Gamma_j) \setminus \bigcup_{l<j}(\Gamma_l\times\Gamma_l).\] Then \[E_i\setminus Z_i=\bigcup_{j=1}^N S_{ij}, \qquad \eta_{ij}:=\gamma_i|_{S_{ij}}, \qquad \gamma_i=\sum_{j=1}^N\eta_{ij}.\] We now reassign \(\eta_{ij}\) from constraint \(i\) to constraint \(j\). Fix \(i,j\). On \(S_{ij}\), we have \[U_{\mathrm{pure}}(\theta)=q_j\theta_j, \qquad U_{\mathrm{pure}}(\theta')=q_j\theta_j'.\] Since \(B_iU_{\mathrm{pure}}=0\) on \(S_{ij}\), we have \(\theta_i' q_j\theta_j = \theta_i q_j\theta_j'\) and therefore \[\label{eq:commratio} \frac{\theta_i}{\theta_j} = \frac{\theta_i'}{\theta_j'}.\tag{32}\]

Next, we show that \(S_{ij}\subseteq R_j\). Take \((\theta,\theta')\in S_{ij}\) and fix \(k\neq j\). If \(k=i\), the required inequality follows from 32 . If \(k\neq i,j\), then since \((\theta,\theta')\in R_i\), \[\frac{\theta_k}{\theta_i} \ge \frac{\theta_k'}{\theta_i'}.\] Using 32 , we get \[\frac{\theta_k}{\theta_j} = \frac{\theta_k/\theta_i}{\theta_j/\theta_i} \ge \frac{\theta_k'/\theta_i'}{\theta_j'/\theta_i'} = \frac{\theta_k'}{\theta_j'}.\] Therefore \((\theta,\theta')\in R_j\).

We now define a positive Borel measure \(\tilde{\eta}_{ij}\in\mathcal{M}_+( R_j)\) by \[d\tilde{\eta}_{ij}(\theta,\theta') := \frac{\theta_i}{\theta_j}\,d\eta_{ij}(\theta,\theta').\] This measure is finite because \(\theta_j\) is bounded away from zero on \(\Gamma_j\).²¹ Moreover, \[\label{eq:measuretransfrom} \int_{ R_j} B_jU\,d\tilde{\eta}_{ij} = \int_{S_{ij}} B_iU\,d\eta_{ij} \quad \text{for all }U\in K.\tag{33}\] Indeed, on \(S_{ij}\), we have \[\frac{\theta_i}{\theta_j}\theta_j=\theta_i \quad\text{and}\quad \frac{\theta_i}{\theta_j}\theta_j' = \frac{\theta_i'}{\theta_j'}\theta_j' = \theta_i', \quad\text{so}\quad \frac{\theta_i}{\theta_j} \bigl(\theta_jU(\theta')-\theta_j'U(\theta)\bigr) = \theta_iU(\theta')-\theta_i'U(\theta).\] Finally, for each \(j\), define \(\bar\gamma_j:=\sum_{i=1}^N\tilde{\eta}_{ij}\). Then \[\bar\gamma_j\in\mathcal{M}_+( R_j), \qquad \operatorname{supp}(\bar\gamma_j) \subseteq R_j\cap(\Gamma_j\times\Gamma_j).\] Summing over 33 gives \[\sum_{j=1}^N \int_{ R_j} B_jU\,d\bar\gamma_j = \sum_{i=1}^N \int_{ R_i} B_iU\,d\gamma_i \quad \text{for all }U\in K.\] Since the original certificate gave \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \sum_{i=1}^N \int_{ R_i} B_iU\,d\gamma_i \qquad \text{for all } U\in K,\] we obtain \[\int_\Gamma \frac{U}{\theta_*}\,d\mu \le \sum_{j=1}^N \int_{ R_j} B_jU\,d\bar\gamma_j \qquad \text{for all } U\in K.\]

13 Deriving examples↩︎

13.1 Example 1↩︎

Let us compute \(H_\rho(z)\) for this value distribution. For \(z\in[0,\tfrac12]\), \[\mathbb{P}(\Theta_2\le z)=\frac{z}{2(1-z)}, \qquad \mathbb{P}(\Theta_2\ge z)=\frac{2-3z}{2(1-z)}, \qquad \mathbb{E} \left[\max\{zV_1,(1-z)V_2\}\right] =\frac{4z^2-6z+3}{6(1-z)}.\] For \(z\in[\tfrac12,1]\), \[\mathbb{P}(\Theta_2\le z)=\frac{3z-1}{2z}, \qquad \mathbb{P}(\Theta_2\ge z)=\frac{1-z}{2z}, \qquad \mathbb{E} \left[\max\{zV_1,(1-z)V_2\}\right] =\frac{4z^2-2z+1}{6z}.\] Since \(\mathbb{E} \left[\lambda(\Theta)\max\{z\Theta_1,(1-z)\Theta_2\}\right] = \mathbb{E} \left[\max\{zV_1,(1-z)V_2\}\right]\), we get: \[H_\rho(z)= \begin{cases} \displaystyle \frac{1}{3}\, \frac{4z^2-6z+3}{(\rho+3)z^2-5z+2}, & z\in[0,\tfrac12], \\[10pt] \displaystyle \frac{1}{3}\, \frac{4z^2-2z+1}{(3\rho+1)z^2-(\rho+2)z+1}, & z\in[\tfrac12,1]. \end{cases}\] Note also that \(H_\rho(z)=\rho^{-1}H_{1/\rho}(1-z),\) so it is enough to consider \(\rho\le 1\). On \([\tfrac12,1]\), \[H_\rho'(z) = \frac{2\bigl(2\rho z^2-6\rho z+\rho-6z^2+6z\bigr)}{3\bigl((3\rho+1)z^2-(\rho+2)z+1\bigr)^2}.\] Its numerator is strictly decreasing in \(z\), positive at \(z=\tfrac12\), and negative at \(z=1\). Thus \(H_\rho\) has a unique maximizer on \([\tfrac12,1]\), and therefore also on all of \([0,1]\).

Let \(z^*\) be the unique maximizer of \(H_{\rho^*}\), where \(\rho^*\) is as in Theorem 1. Since \(\arg\max H_{\rho^*}=\{z^*\}\), the theorem implies \(a=b=z^*\), so the bundle is redundant. Hence the optimal mechanism offers only two pure options. By Theorem 1, the quantities offered by the pure options are chosen so that supply constraints hold with equality if all agents choose their favorite options.

13.2 Example 3↩︎

For the power family, \[x\frac{f_M(x)}{F_M(x)}=\alpha,\] which is constant, hence non-increasing. The uniform distribution is the special case \(\alpha=1\). For the truncated Weibull family, \[x\frac{f_M(x)}{F_M(x)} = \frac{\alpha\beta x^\alpha}{e^{\beta x^\alpha}-1}.\] Writing \(z=\beta x^\alpha\), this becomes \(\alpha\frac{z}{e^z-1}.\) The function \(z\mapsto z/(e^z-1)\) is decreasing on \((0,\infty)\), since \[\frac{d}{dz}\frac{z}{e^z-1} = \frac{e^z(1-z)-1}{(e^z-1)^2} \le 0.\] Therefore \(x f_M(x)/F_M(x)\) is non-increasing in \(x\). The truncated exponential distribution is the special case \(\alpha=1\). The result follows from Corollary 2.

13.3 Examples 2 and 4↩︎

Let us first consider Example 4. By exchangeability and equal supplies, the pure option mechanism is symmetric. Thus, each pure option gives \(Ns\) units of the corresponding good. Its welfare is \(W_{\mathrm{pure}} = Ns\,\mathbb{E}[\max_j V_j].\) We now construct a feasible incentive-compatible menu that yields strictly higher welfare. Fix some \(\tau\in(1/N,1)\), and define \(p_\tau:=\mathbb{P}(\max_j V_j\le \tau \textstyle\sum_j V_j).\) Consider the menu consisting of \(N\) pure options and one balanced mixed option: \[\{q_\tau e_1,\ldots,q_\tau e_N,\tau q_\tau \mathbf{1}\}, \quad \text{where} \quad q_\tau := \frac{Ns}{1+p_\tau(N\tau-1)}.\] A type \(V\) gets utility \(q_\tau \max_j V_j\) from her favorite pure option and utility \(\tau q_\tau \textstyle \sum_j V_j\) from the mixed option. Hence she chooses the mixed option exactly when \(\max_j V_j\le \tau \textstyle\sum_j V_j,\) and otherwise chooses her favorite pure option. The menu is feasible. Indeed, by exchangeability, conditional on choosing a pure option, each good is chosen with equal probability. Therefore, the amount of any good \(i\) used by this menu is \[q_\tau\frac{1-p_\tau}{N} + \tau q_\tau p_\tau = q_\tau\left(\frac{1-p_\tau}{N}+\tau p_\tau\right) = q_\tau\frac{1+p_\tau(N\tau-1)}{N} = s.\] Thus every supply constraint binds.

The welfare from this menu is \(W_\tau = q_\tau\mathbb{E}[\max\{\max_j V_j,\tau \textstyle\sum_j V_j\}].\) Since \[\max\{\max_j V_j,\tau \textstyle\sum_j V_j\} = \max_j V_j+(\tau \textstyle\sum_j V_j-\max_j V_j)^+,\] we have \[W_\tau>W_{\mathrm{pure}} \quad \text{if and only if} \quad \frac{Ns}{1+p_\tau(N\tau-1)} \mathbb{E}[\max_j V_j+(\tau \textstyle\sum_j V_j-\max_j V_j)^+] > Ns\,\mathbb{E}[\max_j V_j].\] Equivalently, \[\label{eq:common-need-sufficient} \mathbb{E}[(\tau \textstyle\sum_j V_j-\max_j V_j)^+] > p_\tau(N\tau-1)\mathbb{E}[\max_j V_j].\tag{34}\] It remains to verify 34 . Consider first the limiting case \(\varepsilon=0\). Common-need agents have \(\sum_j V_j=N\) and \(\max_j V_j=1\). Since \(\tau>1/N\), they satisfy \[\max_j V_j = 1 < \tau N = \tau\sum_j V_j .\] Specialized-need agents have exactly one nonzero coordinate. If that coordinate is \(j\), then, except at the null type with \(V_j=0\), \(\sum_k V_k=V_j\) and \(\max_k V_k=V_j\). Since \(\tau<1\), they satisfy \[\max_k V_k = V_j > \tau V_j = \tau \textstyle \sum_k V_k .\] Therefore, in the limit, \[p_\tau=p,\quad \mathbb{E}[(\tau \textstyle\sum_j V_j-\max_j V_j)^+] = p(N\tau-1), \quad \text{and} \quad \mathbb{E}[\max_j V_j] = p+(1-p)\frac{1}{2} .\] Hence \[\begin{align} \mathbb{E}[(\tau \textstyle\sum_j V_j-\max_j V_j)^+] - p_\tau(N\tau-1)\mathbb{E}[\max_j V_j] &= p(N\tau-1) - p(N\tau-1)\big(p+(1-p)\tfrac12\big) \\ &= p(1-p)(N\tau-1)\big(1-\tfrac12\big) > 0. \end{align}\]

Finally, the objects appearing in 34 vary continuously as \(\varepsilon\downarrow0\). Indeed, the values are uniformly bounded, and the event \(\{\max_j V_j=\tau \textstyle \sum_j V_j\}\) has probability zero in the limiting distribution. Therefore, the strict inequality continues to hold for all sufficiently small \(\varepsilon>0\). Hence, \(W_\tau>W_{\mathrm{pure}}\), so the pure option mechanism is not optimal. This verifies Example 4.

For Example 2, the argument showing that the pure option mechanism is not optimal is analogous. Recall also that by Theorem 1 an optimal mechanism has either two pure options or two pure options and one bundle. Since the pure option mechanism is not optimal, the optimal mechanism must take the latter form. Since the bundle is not redundant, it must deliver strictly more total quantity than either pure option.

13.4 Example 5↩︎

By symmetry and equal supplies, the market-clearing pure-option vector is symmetric. Hence, up to null indifference sets, \[\Gamma_i = \{\theta\in\Gamma:\theta_i\ge \theta_k \text{ for all }k\}.\] Fix \(i\). Identify \(\Gamma_i\) with the cube \([0,1]^{N-1}\) by the ratio-coordinate map \[R_i(\theta) := \left(\frac{\theta_k}{\theta_i}\right)_{k\neq i}.\] For \(r=(r_k)_{k\neq i}\in [0,1]^{N-1}\), the inverse map is \[\label{eq:invratiomap} \theta_i(r)=\frac{1}{1+\sum_{k\neq i}r_k}, \qquad \theta_k(r)=\frac{r_k}{1+\sum_{l\neq i}r_l} \quad(k\neq i).\tag{35}\]

Moreover, if \(C\subseteq\Gamma_i\) is a closed \(\succ_i\)-upper set, then \(D:=R_i(C)\) is a closed downset in \([0,1]^{N-1}\): whenever \(r\in D\) and \(0\le r'\le r\) coordinatewise, we have \(r'\in D\).

Since \(V\) is uniformly distributed on \([0,1]^N\), the ray \(\{t\theta:t\ge0\}\) remains in \([0,1]^N\) exactly for \(0\le t\le 1/\max_j\theta_j\). Therefore, for a normalizing constant \(K_N>0\), \[g(\theta)=K_N \max_j\theta_j^{-N}, \qquad \lambda(\theta) = \frac{\int_0^{1/\max_j\theta_j} t\cdot t^{N-1}\,dt}{\int_0^{1/\max_j\theta_j} t^{N-1}\,dt} = \frac{N}{N+1}\frac{1}{\max_j\theta_j}.\] On \(\Gamma_i\), \(\max_j\theta_j=\theta_i\). Hence \[g(\theta)=K_N\theta_i^{-N}, \qquad \lambda(\theta)\theta_i=\frac{N}{N+1}.\] The Jacobian of \(R_i^{-1}\) is proportional to \((1+\sum_{k\neq i}r_k)^{-N}=\theta_i^N\). Thus the pushforward of \(g\,dm\) under \(R_i\) is constant. Since, by symmetry, \(G(\Gamma_i)=1/N\), we have \[(R_i)_\#(g\,dm)=\frac{1}{N}\,dr,\] where \(dr\) denotes Lebesgue measure on \([0,1]^{N-1}\). Therefore \[M_i=\int_{\Gamma_i}g(\theta)\,dm(\theta)=\frac{1}{N}, \qquad A_i = \int_{\Gamma_i}\lambda(\theta)\theta_i g(\theta)\,dm(\theta) = \frac{1}{N+1}.\] By symmetry, the shadow costs are all equal. Since the pure-option quantities are equal, each row of the shadow-cost matrix sums to \(M_i=1/N\). Therefore the equation \(Jc=A\) gives, for all \(i\), \(c_i =c_0:=\frac{N}{N+1}.\)

We now compute the rent measure on \(\Gamma_i\). The change of variables above gives \[(R_i)_\#(g\,dm)=\frac{1}{N}\,dr.\] In ratio coordinates, the vector field \(\bigl(c-(\textstyle\sum_j c_j)\theta\bigr)g = c_0(1-N\theta)g\) has \(r_k\)-component density \[b_k(r) = \frac{c_0}{N}(1-r_k)\left(1+\sum_{l\neq i}r_l\right). \quad \text{ hence } \quad \theta_i(r) \sum_{k\neq i}\partial_{r_k}b_k(r) = -\frac{c_0\sum_{k\neq i}r_k}{1+\sum_{k\neq i}r_k}.\] The remaining interior terms \(\theta_i(\lambda g-Nc_0g)\,dm\) contribute \(\tfrac{c_0}{N} \left(1-{N}/{1+\sum_{k\neq i}r_k}\right)dr\). Adding the two interior contributions gives the constant density \(-\frac{N-1}{N+1}\,dr.\) Finally, on the boundary face \(\{r_k=0\}\), the conormal boundary term in the definition of \(\mu\) contributes \[\frac{1}{N+1}\,\mathcal{H}^{N-2}\restriction_{\{r_k=0\}}.\] Therefore \[(R_i)_\#\mu_i = \frac{1}{N+1} \left[ \sum_{k\neq i} \mathcal{H}^{N-2}\restriction_{\{r_k=0\}} - (N-1)\,\mathcal{L}^{N-1}\restriction_Q \right].\] Equivalently, for every closed \(\succ_i\)-upper set \(C\subseteq\Gamma_i\), with \(D:=R_i(C)\), \[\label{eq:uniform-cube-mu-D} \mu_i(C) = \frac{1}{N+1} \left[ \sum_{k\neq i} \mathcal{H}^{N-2}(D\cap\{r_k=0\}) - (N-1)\,\mathcal{L}^{N-1}(D) \right].\tag{36}\]

We next prove the geometric estimate. For a Borel set \(B\subseteq Q\), define \[\bar\alpha(B) := \mathcal{L}^{N-1}(B) + \sum_{k\neq i}\mathcal{H}^{N-2}(B\cap\{r_k=0\}).\] We claim that there exists \(\kappa>0\) such that for every closed downset \(D\subseteq [0,1]^{N-1}\), \[\label{eq:downset-gap} \sum_{k\neq i} \mathcal{H}^{N-2}(D\cap\{r_k=0\}) - (N-1)\,\mathcal{L}^{N-1}(D) \ge \kappa \min\{\bar\alpha(D),\bar\alpha(Q\setminus D)\}.\tag{37}\]

Let \(V:=\mathcal{L}^{N-1}(D)\) and \(P_k:=\mathcal{H}^{N-2}(D\cap\{r_k=0\})\). If \(D=\varnothing\) or \(D=[0,1]^{N-1}\), the claim is immediate. If \(\mathcal{L}^{N-1}(D)=0\), then \(\sum_{k\neq i}P_k-(N-1)V=\sum_{k\neq i}P_k=\bar\alpha(D),\) so 37 holds, for instance with any \(\kappa\le 1\). Hence assume from now on that \(0<V<1\).

First consider \(N=2\). Then the cube becomes \([0,1]\), and a nonempty proper closed downset is of the form \(D=[0,a]\) with \(0\le a<1\). Thus \(V=a\), \(\sum_{k\neq i}P_k=1\), and \(\sum_{k\neq i}P_k-(N-1)V=1-a=\bar\alpha([0,1]^{N-1}\setminus D).\) Hence 37 holds for \(N=2\), with \(\kappa=1\).

Now suppose \(N\ge3\). Since \(D\) is a downset, \(D\cap\{r_k=0\}\) is the coordinate projection of \(D\) onto the face \(\{r_k=0\}\). By the Loomis–Whitney inequality, \[V^{N-2}\le \prod_{k\neq i}P_k \le \left(\frac{\sum_{k\neq i}P_k}{N-1}\right)^{N-1}, \quad \text{and therefore} \quad \sum_{k\neq i}P_k\ge (N-1)\,V^{(N-2)/(N-1)}.\] Hence \[\sum_{k\neq i}P_k-(N-1)V \ge (N-1)\bigl(V^{(N-2)/(N-1)}-V\bigr) = (N-1)V^{(N-2)/(N-1)} \bigl(1-V^{1/(N-1)}\bigr).\]

If \(V\le 1/2\), then \[\frac{\sum_{k\neq i}P_k-(N-1)V}{\sum_{k\neq i}P_k+V} \ge \frac{(N-1)\bigl(1-V^{1/(N-1)}\bigr)}{N-1+V^{1/(N-1)}} \ge \frac{(N-1)\bigl(1-2^{-1/(N-1)}\bigr)}{N-1+2^{-1/(N-1)}} =:\kappa_1>0.\] Since \(\sum_{k\neq i}P_k+V=\bar\alpha(D)\), this gives \(\sum_{k\neq i}P_k-(N-1)V\ge \kappa_1\bar\alpha(D).\) If \(V\ge 1/2\), write \(t:=V^{1/(N-1)}\). Then \[1-V=1-t^{N-1}=(1-t)(1+t+\cdots+t^{N-2}),\] and so \[\frac{\sum_{k\neq i}P_k-(N-1)V}{1-V} \ge \frac{(N-1)t^{N-2}}{1+t+\cdots+t^{N-2}} \ge 2^{-\frac{(N-2)}{(N-1)}} =:\kappa_2>0.\] Moreover, \[\bar\alpha\left([0,1]^{N-1}\setminus D\right) = (1-V)+\sum_{k\neq i}(1-P_k) = N(1-V)-\bigl(\sum_{k\neq i}P_k-(N-1)V\bigr) \le N(1-V).\] Therefore \[\sum_{k\neq i}P_k-(N-1)V \ge \frac{\kappa_2}{N}\bar\alpha\left([0,1]^{N-1}\setminus D\right).\]

Combining the cases proves 37 , with \(\kappa := \min\left\{ 1,\kappa_1,{\kappa_2}/{N} \right\} >0.\)

Finally, recall the inverse ratio map \(R_i^{-1}:[0,1]^{N-1}\to\Gamma_i\) is given by 35 . Since \(r\in [0,1]^{N-1}\), the denominator is bounded above and below away from zero. Hence the Jacobian of \(R_i^{-1}\), as well as the Jacobians of its restrictions to the lower faces \(\{r_k=0\}\), are bounded by a constant depending only on \(N\). Therefore, by the area formula, there exists \(B_N<\infty\) such that, for every Borel \(B\subseteq [0,1]^{N-1}\), \[\alpha(R_i^{-1}(B)) \le B_N\Big[ \mathcal{L}^{N-1}(B) + \sum_{k\neq i} \mathcal{H}^{N-2}(B\cap\{r_k=0\}) \Big] = B_N\bar\alpha(B).\]

Applying this to \(B=D\) and \(B=[0,1]^{N-1}\setminus D\), we get \[\min\{\bar\alpha(D),\bar\alpha(Q\setminus D)\} \ge \frac{1}{B_N} \min\{\alpha(C),\alpha(\Gamma_i\setminus C)\}.\] Combining this with 36 and 37 yields \[\mu_i(C) \ge \frac{\kappa}{(N+1)B_N} \min\{\alpha(C),\alpha(\Gamma_i\setminus C)\}.\] Thus ?? holds with \(\eta:=\frac{\kappa}{(N+1)B_N}>0.\)

References↩︎

---

1. I am grateful to Ben Brooks, Eric Budish, Laura Doval, Piotr Dworczak, Joey Feffer, Jan Kożuszek, Jacob Leshno, Shengwu Li, Axel Niemeyer, Ilya Segal, Takuo Sugaya, Andrzej Skrzypacz, Frank Yang, and Leeat Yariv for their helpful comments and suggestions.↩︎

2. See, among others, [1]–[4].↩︎

3. Under this unit-demand interpretation, \(y_i(v)\) is the probability that a type-\(v\) agent receives good \(i\). Given appropriate technical conditions, the exact law of large numbers allows such interim probabilities to be implemented by independent individual lotteries that satisfy exact aggregate feasibility; see [25].↩︎

4. While the optimal allocation is not Pareto-efficient subject to 3 alone, it is Pareto-efficient within the class of allocation rules satisfying both 3 and 2 .↩︎

5. Recall \(V=\mathbf{0}\) occurs with probability zero. We therefore exclude this null type without loss: it values every allocation at zero, and assigning it zero allocation makes all IC constraints involving it trivial. Thus \(\Theta\) is defined only for \(\sum_j V_j>0\), avoiding division by zero.↩︎

6. Related renormalizations appear in [26], [27]. There, values are normalized by agents’ marginal utility of money, so the analogue of \(\lambda\) is the expected marginal utility of money among agents with a given willingness to pay for a good.↩︎

7. Indeed, the requirement that \((1-a,a)\) and \((1-b,b)\) straddle \(\theta^0\) is equivalent to the existence of such weights. Intuitively, when this is the case, one threshold rule uses more of good \(1\) than the pure option mechanism, while the other uses relatively more of good \(2\). This in turn lets us mix them in such a way that their combination uses the whole available supply.↩︎

8. For \(A_i\) and \(M_i\), this follows as \(\lambda,g> 0\) and each \(\Gamma_i\) has positive measure. For \(T_{ij}\), this is because the surface has a positive \((N-2)\)-dimensional Hausdorff measure and because \(\theta_i>0\) on its interior.↩︎

9. On indifference boundaries, fix an arbitrary measurable tie-breaking rule.↩︎

10. See [20] and [24] for related discussions.↩︎

11. The transport condition is related to the stochastic-dominance certificates used by [23], [24] in the study of multi-product monopoly pricing. I discuss this connection in detail in Section 8.↩︎

12. The only other possible distortion is to discard some of the supply.↩︎

13. While working with ?? in the simplex representation \(\Gamma\) is more analytically convenient in my setting, one can also characterize it in terms of an indirect utility \(\tilde{U}:\mathbb{R}_+^N\to\mathbb{R}\) defined on unnormalized values \(v\). In a quasilinear model with transfers, \(\tilde{U}\) satisfies incentive compatibility if and only if the corresponding indirect utility \(\tilde{U}\) is convex and non-decreasing in each coordinate [31]. Without transfers, incentive compatibility additionally forces \(\tilde{U}\) to be positively homogeneous of degree one: for all \(v\in\mathbb{R}_+^N\) and \(k>0\), \(\tilde{U}(kv)=k\,\tilde{U}(v)\) [32].↩︎

14. See, for instance, [19]–[21], [23], [24].↩︎

15. Indeed, if \(x\) implements \(U\), then for every \(\theta'\in\Gamma\), \(U(\theta')\ge U(\theta)+x(\theta)\cdot(\theta'-\theta).\) At every point where \(\nabla_H U(\theta)\) exists, this implies that the projection of \(x(\theta)\) onto the tangent hyperplane of \(\Gamma\) equals \(\nabla_H U(\theta)\). Together with \(U(\theta)=\theta\cdot x(\theta)\), this uniquely determines \(x(\theta)\), and the formula is exactly ?? .↩︎

16. One could also integrate the objective by parts to obtain a representation involving the allocation rule \(x(\theta)\). However, because \(x\) is a vector field, such a representation is not unique: it depends on a choice of vector-valued flows which, intuitively, correspond to sets of paths in the type space \(\Gamma\) along which one integrates by parts. Then, when optimizing over \(x\) to maximize such an expression, one implicitly accounts only for the effects of perturbing \(x\) that propagate through local IC constraints along these paths. In general, this can lose important information about effects propagating through other local IC constraints.

    Representing the designer’s objective in terms of \(U(\theta)\) avoids this issue: since \(U\) is a scalar potential, the objective can be rewritten in terms of \(U(\theta)\) without having to select paths along which indirect utility is integrated. As a result, this representation encodes information about effects propagating through all local IC constraints.↩︎

17. For example, the Amsterdam housing lottery allows applicants to enter two draws per week. See https://www.wooninfo.nl/nieuws/2013/04/nieuw-een-woning-via-loting/.↩︎

18. As in the static unit-demand interpretation, the constraint is stated at the reduced-form aggregate level. Implementing the associated interim probabilities by individual randomizations while satisfying exact aggregate feasibility requires the usual exact-law-of-large-numbers argument; see footnote 2.↩︎

19. A function \(f:\mathbb{R}^n\to\mathbb{R}\) is sublinear if it satisfies \(f(x+y)\le f(x)+f(y)\) and \(f(\lambda x)=\lambda f(x)\) for all \(x,y\in\mathbb{R}^n\) and all \(\lambda\ge0\). Equivalently, \(f\) is sublinear if and only if it is convex and positively homogeneous.↩︎

20. Indeed, if one of them were zero and the other were positive, the equality \(B_iU_{\mathrm{pure}}(\theta,\theta')=0\) would be impossible because \(U_{\mathrm{pure}}>0\) on \(\Gamma\); and the case \(\theta_i=\theta_i'=0\) has been removed.↩︎

21. \(\theta_i/\theta_j\) is bounded on \(S_{ij}\) since \(\theta\in\Gamma_j\) gives \(q_j\theta_j = U_{\mathrm{pure}}(\theta) \ge \frac{\min_k q_k}{N}\), and thus \(\theta_j\) is bounded away from zero on \(\Gamma_j\).↩︎