1 Introduction↩︎

A central problem in microeconomic theory concerns the fair and efficient assignment of objects to agents based on their preferences over the objects. The formal study of the canonical formulation of this problem with \(n\) agents and \(n\) objects, such that each object must be allocated to exactly one agent, goes back to [1] and [2]. [3] provided an early algorithmic solution to this problem for cardinal preferences. When objects are indivisible, it is impossible to deterministically assign objects such that agents with the same preferences receive the same objects. “Equal treatment of equals” is usually ensured via randomization, i.e., by assigning lotteries over objects to the agents. An extensive body of research has investigated random assignment rules with respect to properties such as Pareto efficiency, envy-freeness, and strategyproofness.

In contrast to existing work on random assignment, we only impose minimal restrictions on preference relations. In particular, we allow more general preference relations on lotteries than those that can be represented by expected (vNM) utility functions, which [4] have axiomatically characterized using completeness, transitivity, continuity, and independence. Independence prescribes that a lottery \(x\) is preferred to lottery \(y\) if and only if a coin toss between \(x\) and a third lottery \(z\) is preferred to a coin toss between \(y\) and \(z\) (with the same coin used in both cases). There is experimental evidence that human decision makers systematically violate the independence axiom. Allais’s Paradox is the most famous example [5]. [6], [7] and [8] provide detailed reviews of such violations, including those reported by [9]. Similarly, a number of scholars have concluded that transitivity can be unnecessarily demanding [10]–[16]. For example, [15] states that “once considered a cornerstone of rational choice theory, the status of transitivity has been dramatically reevaluated by economists and philosophers in recent years.” In a similar vein, [13] proclaims that “transitivity is obviously a great practical convenience and a nice thing to have for mathematical purposes, but long ago this author ceased to understand why it should be a cornerstone of normative decision theory.”

Our most general result merely requires that preferences are continuous and convex. [17] has shown that such relations always admit maximal elements, even in the absence of transitivity. Generalizing the pseudo-market mechanism by [18], we prove the existence of weakly efficient and envy-free random assignments. We then move on to the subset of skew-symmetric bilinear (SSB) preferences. SSB preferences, which are significantly more general than vNM preferences, have been characterized by [19] and [20] and admit a convenient compact representation via skew-symmetric matrices [21], [22]. We construct an SSB preference profile that does not admit a (strongly) efficient and envy-free random assignment and suggest two methods to circumvent this negative result. First, we propose a mild additional restriction on preferences that guarantees the existence of efficient and envy-free random assignments. Secondly, for general SSB preferences, we leverage Kakutani’s fixed-point theorem to prove the existence of efficient and approximately envy-free random assignments.

Our findings have noteworthy implications for the well-explored setting where random assignments only depend on the agents’ ordinal preferences over objects. Identifying ordinal preferences with their canonical SSB utility function leads to the pairwise comparison (\(\mathit{PC}\)) preference extension, which refines the widely studied stochastic dominance (\(\mathit{SD}\)) preference extension. A lottery is \(\mathit{PC}\)-preferred to another lottery if the former is more likely to return a better alternative than the latter. While the probabilistic serial (\(\mathit{PS}\)) rule is \(\mathit{SD}\)-efficient, we point out that it frequently and significantly violates weak \(\mathit{PC}\)-efficiency, i.e., there is another random assignment in which every agent strictly \(\mathit{PC}\)-prefers her lottery to the one she receives under \(\mathit{PS}\). At the same time, random serial dictatorship and popular random assignments fail to satisfy \(\mathit{PC}\)-envy-freeness. These results lead to the natural question of whether there are rules that satisfy both \(\mathit{PC}\)-efficiency and \(\mathit{PC}\)-envy-freeness, which we answer in the affirmative using our generalization of the Hylland–Zeckhauser pseudo-market.

Related Work↩︎

The work most directly related to ours is the seminal contribution of [18], who introduced the pseudo-market approach to random assignment by combining equal artificial budgets with price-supported lotteries. Their mechanism can be viewed as an assignment market: competitive prices decentralize individually optimal choices and together with market clearing lead to an efficient allocation [23].

A related line of work, originating with [24], weakens the preference assumptions under which competitive equilibria exist. [25] and [26] establish existence results for economies without transitivity under continuity, convexity, and non-satiation-type assumptions. This last assumption is not well suited to the assignment problem, in which agents choose lotteries over a finite set of objects. This difficulty has been addressed in different ways: [27] relaxes the notion of equilibrium, whereas [28] provides additional conditions that restore equilibrium existence. Closest to our approach is the abstract-economy theorem of [29]. Our baseline fixed-point argument in [theorem:market95existence] can be viewed as a specialization of this abstract-economy logic to the Hylland–Zeckhauser pseudo-market. Our work further contributes to the literature on pseudo-markets as mechanisms for achieving normatively desirable outcomes [30], [31]. The idea to obtain efficient and envy-free allocations via competitive-equilibrium-from-equal-incomes mechanisms has also been applied in other fair division settings [32], [33].

Several papers have explored extensions of classic results for vNM utilities to the more general model of SSB utility functions. For instance, [34] have generalized the existence of Nash equilibria [35]. [36] have proved an efficiency-welfare theorem connecting efficiency to affine welfare maximization [37], which we utilize in the proof of [theorem:alpha-envy-free]. [38] have shown that the no-show paradox [39] disappears for SSB preferences, as a randomized Condorcet extension called maximal lotteries satisfies participation. [20] characterized a rich subdomain of SSB preferences—the \(\mathit{PC}\) domain—that allows for Arrovian aggregation [40] and a corresponding social welfare function. [41] and [42] have shown negative results for efficient and strategyproof social choice functions, similar in spirit to classic results by [43] and [44].

2 Preliminaries↩︎

Let \(N= \{1,\dots,n\}\) be a set of \(n\) agents and \(O\) be a set of \(n\) objects. A deterministic assignment (or pure matching) is a permutation matrix in \(\mathbb{R}^{n\times n}\). A random assignment is a probability distribution over deterministic assignments, which we represent as a bistochastic matrix \(X = (x_i(o))_{i \in N, o \in O}\) where \(x_i(o)\) is the probability with which agent \(i\) receives object \(o\).¹ The set of all random assignments is denoted by \(\mathcal{M}\). By the Birkhoff–von Neumann decomposition, every bistochastic matrix can be written as a probability distribution over deterministic assignments [1], [2]. The set of all probability distributions (or lotteries) over \(O\) is denoted by \(\Delta\). For a random assignment \(X\in\mathcal{M}\) and \(i\in N\), we write \(x_i\) for the \(i\)th row of \(X\), i.e., the lottery over \(O\) assigned to agent \(i\); thus, \(x_i\in\Delta\). A lottery is degenerate if it puts all probability on a single object.

As an example, consider the following random assignment \(X\) where \(n=3\) and \(O=\{a,b,c\}\). \[X = \begin{pmatrix} \frac{1}{3} & \frac{2}{3} & 0\\ \frac{2}{3} & \frac{1}{12} & \frac{1}{4} \\ 0 & \frac{1}{4} & \frac{3}{4} \end{pmatrix}\] Here, \(x_1(a)=\frac{1}{3}\) and \(x_3=(0,\frac{1}{4}, \frac{3}{4})\).

Every agent \(i\in N\) has an asymmetric, binary preference relation \(\succ_i\) over the elements of \(\Delta\). As a consequence, there are no externalities, and agents are only concerned with their own assignment.

For lotteries \(x,y\in\Delta\), write \(x\sim y\) if neither \(x\succ y\) nor \(y\succ x\), and \(x\succsim y\) if either \(x\succ y\) or \(x\sim y\). A preference profile \((\succ_1, \dots, \succ_n)\) is an \(n\)-tuple of preference relations.

Throughout, we assume that agents have continuous and convex preferences in the sense that the graph of \(\succ\) is open and both weak and strict upper contour sets are convex. More precisely, we demand that \[G(\succ) \mathrel{\vcenter{:}}= \{(x, y) \in \Delta \times \Delta \colon x \succ y\} \text{ is open.}\] Furthermore, we require that for all \(x\in\Delta\), \[\text{W(x) \mathrel{\vcenter{:}}= \{y\in\Delta \colon y\succsim x\} and U(x) \mathrel{\vcenter{:}}= \{y\in\Delta \colon y\succ x\} are convex.}\] Continuity implies that both strict upper contour sets and strict lower contour sets are open.

[17] has shown that convexity of strict upper contour sets and openness of strict lower contour sets suffice to guarantee the existence of maximal elements in every non-empty, compact, and convex set of lotteries, even when preferences are intransitive [45], [46]. Furthermore, demanding that weak upper contour sets are convex ensures that sets of maximal elements are convex. Continuity ensures that strict preference comparisons are robust to small perturbations of both lotteries.

A subset of the domain of continuous and convex preferences admits a representation by skew-symmetric bilinear (SSB) utility functions. A preference relation can be expressed by an SSB utility function \(\phi\colon\Delta\times\Delta\rightarrow \mathbb{R}\) if for all \(x,y\in\Delta\), \[x\succ y \text{ if and only if }\phi(x,y) > 0\text{.} \] Skew-symmetry requires that \(\phi(x,y) = - \phi(y,x)\) for all \(x,y\in\Delta\) and bilinearity that \(\phi\) is linear in both arguments. Note that, by skew-symmetry, linearity in the first argument implies linearity in the second argument and that, due to bilinearity, \(\phi\) is completely determined by its function values for degenerate lotteries. Thus, with slight abuse of notation, we will represent every SSB utility function \(\phi\) by a skew-symmetric matrix \(\phi\in \mathbb{R}^{O\times O}\). As mentioned in 1, SSB utility was introduced by [19] as a generalization of classic linear expected utility that does not require the somewhat controversial axioms of independence and transitivity [21], [22]. When \(\phi\) is separable, i.e., \(\phi(x,y) = u(x) - u(y)\) for some \(u\in \mathbb{R}^O\), the preferences represented by \(\phi\) boil down to vNM expected utility with utility function \(u\). Through the representation of \({\succ}\) as a skew-symmetric matrix \(\phi\), it becomes apparent that the Minimax Theorem [47] implies the existence of maximal elements of \(\succ\). This was noted by [21] and already follows from [17].

The central question pursued in this paper is under which conditions on preferences the existence of efficient and envy-free random assignments can be guaranteed.

A random assignment \(X\in\mathcal{M}\) is efficient if there is no \(Y\in\mathcal{M}\) such that \[y_i \succsim_i x_i \text{ for all }i\in N \text{ and }y_i \succ_i x_i \text{ for some } i\in N\text{.} \] If there is such an \(Y\in\mathcal{M}\), we say that \(Y\) Pareto dominates \(X\).

\(X\in\mathcal{M}\) is weakly efficient if there is no \(Y\in\mathcal{M}\) such that \[y_i \succ_i x_i \text{ for all }i\in N\text{.} \] If there is such an \(Y\in\mathcal{M}\), we say that \(Y\) strongly Pareto dominates \(X\).

A random assignment \(X\in\mathcal{M}\) is envy-free if \[x_i\succsim_i x_j \text{ for all }i,j\in N\text{.} \]

3 Incompatibility of Efficiency and Envy-Freeness↩︎

We first show that efficiency and envy-freeness cannot always be satisfied simultaneously, even when preferences are represented by SSB utility functions. This is demonstrated by the following preference profile for three agents.

The proof of [theorem:counter-example] can be found in 8. The intransitivity, even over degenerate lotteries, of agent \(3\)’s preference relation plays a key role in the proof. In particular, when restricted to degenerate lotteries (identified with pure objects in \(O\)), agents \(1\) and \(2\) share the transitive strict order \(a\succ b\succ c\), while agent \(3\)’s preference is given by \(b\succ_3 a\), \(a\succ_3 c\), and \(b\sim_3 c\). This has the consequence that agent \(3\) is indifferent between the lottery \(x_3 = (0, \frac{1}{2}, \frac{1}{2})\) and every other lottery.

4 A Generalized Pseudo-Market↩︎

Pseudo-markets provide a natural framework for decentralizing allocation problems without monetary transfers. Agents are endowed with artificial budgets and use these to purchase probabilistic shares of indivisible objects; in the assignment problem, each object is available in unit supply. [18] proposed a competitive mechanism for vNM utilities and showed that every random assignment at market equilibrium satisfies efficiency and envy-freeness, assuming agents are given equal budgets and each agent selects a cost-minimal element from the set of budget-feasible utility maximizers. We revisit this construction at the level of abstract preferences over lotteries, and prove that our versions of continuity and convexity suffice to retain existence of a pseudo-market equilibrium. [theorem:counter-example] already suggests that the axiomatic properties of the equilibrium cannot carry over verbatim to our more general preference model; nevertheless, we prove that the equilibrium assignment satisfies weak efficiency in conjunction with envy-freeness.

In 4.1, we further identify a preference domain restriction which restores (strong) efficiency of the pseudo-market equilibrium by ruling out obstructions of the type seen in [theorem:counter-example]. As we show, this domain restriction still includes all weak preference relations that are transitive on degenerate lotteries. Hence, this domain remains a significant generalization of the vNM domain originally considered by [18].

Assume each agent \(i \in N\) receives a budget \(b_i>0\) to buy probability shares of the objects in \(O\); assume also that \(\sum_{i\in N} b_i=1\). There is a common price vector \(p \in \mathbb{R}^n_{\geq 0}\), where the component \(p_o\) denotes the price of one full probability share of object \(o \in O\). The price vectors are normalized so that they lie in a compact price set \(P \subseteq \mathbb{R}^n_{\geq0}\) that satisfies \(\min_{o \in O} p_o = 0\) for all \(p \in P\).² Given a price vector \(p\in P\) and a lottery \(x \in \Delta\), the cost of \(x\) under the price vector \(p\) is given by the inner product \(p \cdot x\). Each agent \(i\) can choose a lottery whose cost does not exceed her budget \(b_i\). Therefore, the budget set of agent \(i\) is defined as \[B_i(p) \mathrel{\vcenter{:}}= \{x\in \Delta\colon p\cdot x \le b_i\}. \] We assume that each agent \(i\) is rational in the sense that she selects, among the lotteries in \(B_i(p)\), a maximal element according to her preference relation \(\succ_i\). The demand set of agent \(i\) at prices \(p\) is the set of maximal affordable lotteries, \[D_i(p) \mathrel{\vcenter{:}}= \{x\in B_i(p)\colon x \succsim_i y \text{ for all } y\in B_i(p)\}. \]

A pseudo-market equilibrium is then a pair consisting of a price vector \(p^\ast\) and a profile \(X^\ast = (x^\ast_i)_{i \in N}\) of lotteries with \(x^\ast_i \in D_i(p^\ast)\) for each agent \(i\), such that aggregate demand exactly exhausts the unit supply of every object.

Formally, a pair \((X^\ast,p^\ast) \in \Delta^n \times P\) is a pseudo-market equilibrium if it satisfies

1. \(x_i^\ast \in D_i(p^\ast)\) for every agent \(i \in N\) (rationality)

2. \(\sum_{i\in N} x_i^\ast(o) = 1\) for every object \(o \in O\) (market-clearing)

By the market-clearing condition, we can identify \(X^\ast = (x^\ast_i)_{i \in N}\) as a random assignment, that is, \(X^\ast \in\mathcal{M}\).

The proof of [theorem:market95existence], using Kakutani’s fixed-point theorem, is deferred to 9. The key ingredients are: (i) the budget set correspondence \(B_i(\cdot)\) is continuous with non-empty, compact and convex values, (ii) the demand correspondence \(D_i(\cdot)\) is upper hemicontinuous with non-empty, compact and convex values, and (iii) the normalized price-selection correspondence is upper hemicontinuous with non-empty, compact and convex values. Kakutani’s theorem then yields the existence of a pseudo-market equilibrium.

Even in our generalized preference model, the pseudo-market equilibrium satisfies envy-freeness, under the assumption that agents’ budgets are equal.

As mentioned, the pseudo-market equilibrium does not directly inherit efficiency from the Hylland–Zeckhauser mechanism for vNM utilities. The key property that holds for vNM utilities and fails in our more general model is: if \(x_i, y_i \in B_i(p)\), with \(x_i\) maximal and \(y_i\) not maximal, then \(x_i \succ_i y_i\) (this follows directly from the linearity of vNM utility functions). Even if we strengthen the rationality assumption to require that agents break ties between multiple maximal affordable lotteries by minimizing the cost \(p \cdot x\) (following [18]), the equilibrium assignment may be Pareto-dominated. This violation can be seen as a consequence of [theorem:counter-example].

On the other hand, as we show below, the pseudo-market equilibrium satisfies weak efficiency.

As a consequence of [proposition:equilibrium-envy-freeness,proposition:equilibrium-wefficiency], the existence of pseudo-market equilibria, as shown by [theorem:market95existence], immediately yields random assignments that are both weakly efficient and envy-free.

4.1 SSB Preferences with Strict Maximality↩︎

[theorem:counter-example] has established that even the restricted domain of SSB preferences allows large indifference regions that prevent pseudo-market equilibria from being efficient. We now identify a further domain restriction within SSB preferences that precisely rules out this obstruction. Specifically, we impose a strict maximality condition that requires, for each agent \(i \in N\), that the strict part \(\succ_i\) separates the maximal elements in \(\Delta\) from the rest of the simplex \(\Delta\). Denote the set of maximal elements of the preference relation \(\succ_i\) in the simplex \(\Delta\) by \[M_i \mathrel{\vcenter{:}}= \{x\in\Delta\colon x \succsim_i y \text{ for all }y\in\Delta\} \] Then \(\succ_i\) satisfies strict maximality if \[x \succ_i y \text{ for all }x\in M_i,\;y\notin M_i\text{.} \]

Within the domain of SSB preferences, the strict maximality condition can be characterized by the following equivalent condition on the matrix representation \(\phi_i\).

A proof of [proposition:characterization95SSB95strict95maximality] can be found in 9.1. Note that by this characterization, strict maximality implies that the set \(M_i\) of maximal elements is a face of the simplex, with vertices given exactly by the set \(T \subseteq O\) of objects corresponding to the top-left zero block of the reordered matrix \(\phi_i\).

It turns out that the pseudo-market equilibrium returns a random assignment satisfying efficiency and envy-freeness in the domain of SSB preferences satisfying strict maximality. In addition to the rationality and market-clearing conditions of our defined pseudo-market equilibrium, we require that each agent \(i\) selects a cost-minimizing element from her demand set \(D_i(p)\). That is to say, we refine the demand correspondence \(D_i(\cdot)\). Given a price vector \(p\), we assume that agent \(i\) selects from \[\widehat D_i(p) \mathrel{\vcenter{:}}= \mathop{\mathrm{arg\,min}}_{x\in D_i(p)} p\cdot x.\]

Under SSB preferences, the correspondence \(\widehat{D}_i(\cdot)\) inherits the properties required for our fixed-point existence argument, which is otherwise similar to the proof of [theorem:market95existence].

The proof of [theorem:existence-with-cost-minimization] is given in 9.1.

For SSB preferences satisfying strict maximality, we strengthen the efficiency guarantee of 2 from weak efficiency to (strong) efficiency for the refined version of the pseudo-market equilibrium. The necessity of tie-breaking by cost-minimization to obtain efficiency of the equilibrium assignment is already recognized by [18].

Combining the existence of a pseudo-market equilibrium with cost minimization ([theorem:existence-with-cost-minimization]), envy-freeness under equal budgets (1), and the strengthened efficiency guarantee of [proposition:equilibrium-sefficiency], we obtain the existence of efficient and envy-free random assignments for the domain of SSB preferences satisfying strict maximality.

5 Efficiency and \(\alpha\)-Envy-Freeness for SSB Preferences↩︎

In 3, we showed that the existence of efficient and envy-free random assignments is unattainable in the full domain of SSB preferences. We bypassed this impossibility in 4.1 by restricting the SSB domain using strict maximality. In this section, we show that [theorem:counter-example] can be circumvented in the full SSB domain by relaxing envy-freeness. In particular, we prove, for the full SSB domain, the existence of random assignments that are efficient and induce arbitrarily small envy among agents.

Let \(\phi = (\phi_1, \dots, \phi_n)\) be a profile of SSB utility functions, and let \(\alpha\) be a positive constant. A random assignment \(X \in \mathcal{M}\) is \(\alpha\)-envy-free if \[\phi_i(x_j, x_i) \leq \alpha \text{ for all }i, j \in N\text{.}\]

We provide a fixed-point argument inspired by [48], while leveraging an efficiency-welfare theorem for SSB preferences due to [36]. This theorem is restated below.

The main theorem of this section is the following.

Let \(\alpha > 0\) be arbitrary. The high-level proof idea is to construct a Kakutani mapping \(\Gamma\) which acts on a pair \((X, \omega)\) of a random assignment \(X\) and a weight vector \(\omega \in \mathbb{R}^n_{>0}\). At a fixed point, we show that the random assignment \(X\) is efficient and \(\alpha\)-envy-free.

Fix \(\varepsilon>0\)³ and define \[\Omega_\varepsilon \mathrel{\vcenter{:}}= \left\{ \omega \in \mathbb{R}^n \colon \omega_i \geq \varepsilon \text{ for all } i \text{ and } \sum_{i \in N} \omega_i = 1 \right\}.\] The set \(\Omega_\varepsilon\) is compact and convex. Each vector \(\omega\in \Omega_\varepsilon\) assigns every agent a strictly positive weight, uniformly bounded away from zero. The lower bound \(\varepsilon\) is introduced for technical reasons: the set of all strictly positive normalized weights is relatively open in the unit simplex and therefore not compact. Since Kakutani’s fixed-point theorem requires a non-empty compact convex domain, we work on \(\Omega_\varepsilon\) instead. The value of \(\varepsilon\) will later be chosen sufficiently small as a function of the desired approximation parameter \(\alpha\).

For a weight vector \(\omega \in \Omega_\varepsilon\), define \[F(\omega) \mathrel{\vcenter{:}}= \left\{ X \in \mathcal{M} \colon \sum_{i \in N} \omega_i \phi_i(x_i, y_i) \geq 0 \text{ for all } Y \in \mathcal{M} \right\}.\] Since every \(\omega \in \Omega_\varepsilon\) is strictly positive, 1 implies that every \(X \in F(\omega)\) is efficient. So, for a given \(\omega\), the correspondence \(F\) maps to a set of efficient random assignments.

On the other hand, for a given random assignment \(X\), we will update the welfare weights \(\omega\) so that weights of envious agents in \(X\) are increased at the expense of non-envious agents. This weight update function can be described in two steps. First, we increase the weight \(\omega_i\) associated with each agent \(i\) in proportion to the maximum envy (above the \(\alpha\) threshold) she suffers against any other agent \(j\) in the assignment \(X\): \[\begin{align} \nu_i(X) &\mathrel{\vcenter{:}}= \max_{j \in N} \max\{\phi_i(x_j, x_i) -\alpha, 0\}, \\ \mu(X, \omega) &\mathrel{\vcenter{:}}= \omega + \nu(X). \end{align}\] Note that the updated weight vector \(\mu' = \mu(X, \omega)\) may leave \(\Omega_\varepsilon\) by violating the constraint that weights sum to 1. Therefore, the second step is to project \(\mu'\) back into \(\Omega_\varepsilon\) via the Euclidean projection: \[\begin{align} g(X, \omega) &\mathrel{\vcenter{:}}= \operatorname{proj}_{\Omega_\varepsilon} \mu(X, \omega) \\ &= \mathop{\mathrm{arg\,min}}_{\omega' \in \Omega_\varepsilon} \left\lVert\omega' - \mu(X, \omega)\right\rVert. \end{align}\]

Finally, we combine the two mappings \(F\) and \(g\) in the correspondence \(\Gamma: \mathcal{M} \times \Omega_\varepsilon \rightrightarrows \mathcal{M} \times \Omega_\varepsilon\) with \[\Gamma(X, \omega) \mathrel{\vcenter{:}}= F(\omega) \times \{ g(X, \omega) \}.\]

The proof of [proposition:fixed-point-existence] uses Kakutani’s fixed-point theorem, and is given in 10. We further claim that the random assignment \(X^\ast\) at the guaranteed fixed point satisfies both efficiency and \(\alpha\)-envy-freeness ([proposition:fixed-point-efficiency,proposition:fixed-point-envy-freeness]), which, together with [proposition:fixed-point-existence], imply [theorem:alpha-envy-free].

This follows directly from 1, since \(X^\ast \in F(\omega^\ast)\).

The proof of [proposition:fixed-point-envy-freeness] is provided in 10.

One might hope that the existence of random assignments that satisfy arbitrarily good approximations of envy-freeness while maintaining efficiency would imply the existence of an exactly envy-free assignment that is also efficient. Indeed, the fact that the space of random assignments, namely the Birkhoff polytope, is compact, implies that any sequence of efficient and \(\alpha\)-envy-free assignments with \(\alpha \to 0\) has a convergent subsequence whose limit assignment is exactly envy-free. Unfortunately, it is not guaranteed that the limit assignment remains efficient; nevertheless, the limit assignment is guaranteed to be weakly efficient. These observations are due to the following result, whose proof is deferred to 10.

This fact implies the existence of random assignments satisfying weak efficiency and exact envy-freeness, by taking the limit of a convergent sequence of efficient and \(\alpha\)-envy-free random assignments, with \(\alpha \to 0\). We remark that this implication coincides with 1 in the SSB domain.

6 Ordinal Random Assignment↩︎

The results from the previous sections have interesting consequences for the widely studied problem of ordinal random assignment. An ordinal random assignment rule returns a random assignment for each profile of complete and transitive preference relations over objects \(O\) (rather than lotteries over objects \(\Delta\)). Random assignment rules are typically evaluated in terms of efficiency, envy-freeness, and strategyproofness by systematically extending the preferences over objects to preferences over lotteries. The most widely studied way of extending preferences to lotteries is based on stochastic dominance (\(\mathit{SD}\)), where one lottery stochastically dominates another lottery if the former yields at least as much expected utility as the latter for every vNM function that is consistent with the ordinal preferences [49], [50]. The \(\mathit{SD}\) relation is generally incomplete, i.e., there are incomparable pairs of lotteries. This leads to two notions of envy-freeness—strong and weak \(\mathit{SD}\)-envy-freeness—depending on how incomparabilities are treated.

[36] initiated the study of extending preferences via the pairwise comparison (\(\mathit{PC}\)) relation, a complete refinement of the \(\mathit{SD}\) relation admitting a natural interpretation. For an asymmetric preference relation \(\succ\) over \(O\) and two lotteries \(x, y \in \Delta\), \(x\) is \(\mathit{PC}\)-preferred to \(y\), written \(x \succsim^\mathit{PC} y\), if and only if \[\sum_{o, \hat{o}\in O\colon o \succ \hat{o}} x(o) \cdot y(\hat{o}) \geq \sum_{o, \hat{o}\in O\colon o \succ \hat{o}} y(o) \cdot x(\hat{o}). }\] Lottery \(x\) is preferred to lottery \(y\) if it is as least as likely that \(x\) yields a better object than \(y\) than vice versa. Alternatively, the terms in the inequality above can be associated with ex ante regret (the probability of ex post regret): a decision maker would less frequently regret choosing \(x\) than \(y\) ex post. \(\mathit{PC}\) preferences have been considered in decision theory [51]–[53]. [52] calls them the rule of expected dominance and [53] refers to them as a preference for the most probable winner. [36], [41], [38], [20], and [42] have studied efficiency, strategyproofness, and related properties with respect to \(\mathit{PC}\) preferences. When there are at least four objects, \(\mathit{PC}\) preferences over lotteries can be cyclic even when preferences over objects are transitive. This phenomenon is known as the Steinhaus–Trybula paradox [51], [52], [54]–[56].

While \(\mathit{PC}\) preferences cannot be represented by a vNM utility function, they constitute a special case of SSB preferences. In fact, any asymmetric preference relation \(\succ\) over \(O\) can be conveniently represented by an SSB utility function \(\phi\) whose entries are restricted to \(\{-1,0,+1\}\) such that \[\phi(o, \hat{o}) = \begin{cases*} +1, & if o \succ \hat{o} \\ \phantom{+}0, & if o \sim \hat{o} \\ -1, & if o \prec \hat{o} \end{cases*}.extension}\] This representation can be viewed as the canonical SSB representation of ordinal preferences and yields preferences identical to the \(\mathit{PC}\) relation. It follows from a more general observation by [57] that the \(\mathit{PC}\) relation is a complete refinement of the \(\mathit{SD}\) relation when preferences over objects are transitive [36]. This implies that the efficiency notions based on the \(\mathit{PC}\) relation, which we call \(\mathit{PC}\)-efficiency, are stronger than their counterparts based on the \(\mathit{SD}\) relation, which we call \(\mathit{SD}\)-efficiency.⁴ On the other hand, \(\mathit{PC}\)-envy-freeness, the envy-freeness notion obtained from the \(\mathit{PC}\) relation, is weaker than strong \(\mathit{SD}\)-envy-freeness (though it is stronger than weak \(\mathit{SD}\)-envy-freeness). The logical relationships between these properties are visualized in 1.

Three central ordinal random assignment rules are widely studied in the literature: random serial dictatorship, the probabilistic serial rule, and the popular random assignment rule. We will introduce these rules and compare them to the extended version of the Hylland–Zeckhauser pseudo-market mechanism. The rules were originally defined for strict preference orders but later generalized to weak preference orders. Since our negative results hold even when preferences are strict, we focus on this preference domain.

For random serial dictatorship (\(\mathit{RSD}\)), a picking order of agents is drawn uniformly at random, and the agents then successively choose their most preferred of the remaining objects in the drawn order [58]. [50] showed that \(\mathit{RSD}\) violates \(\mathit{SD}\)-efficiency but satisfies weak \(\mathit{SD}\)-envy-freeness. The following example shows that \(\mathit{RSD}\) violates the stronger property of \(\mathit{PC}\)-envy-freeness.

The probabilistic serial (\(\mathit{PS}\)) rule was introduced by [50] and works by letting agents “eat” probability shares from their most preferred object at uniform speed subject to availability. [50] showed that \(\mathit{PS}\) satisfies strong \(\mathit{SD}\)-envy-freeness and strong \(\mathit{SD}\)-efficiency. While strong \(\mathit{SD}\)-envy-freeness implies \(\mathit{PC}\)-envy-freeness, the following example, adapted from [59], shows that \(\mathit{PS}\) violates weak \(\mathit{PC}\)-efficiency.⁵

The above example is not exceptional. [62] sampled thousands of preference profiles for varying \(n\) and observed that the fraction of profiles at which \(\mathit{PS}\) violates weak \(\mathit{PC}\)-efficiency quickly approaches one as \(n\) increases. \(\mathit{PS}\) violates weak \(\mathit{PC}\)-efficiency in more than one quarter of all profiles when \(n=4\). The probability that a randomly sampled profile for \(n=7\) has this property already exceeds 90%. The \(\mathit{PC}\) probability margin (i.e., the maximal difference of both sides of the \(\mathit{PC}\) inequality above) also increases with \(n\). When \(n=5\), this margin can already exceed . This means there are profiles where the \(\mathit{PS}\) random assignment is dominated by another random assignment in which some agents are twice as likely to be better off. Weak \(\mathit{PC}\)-efficiency failures of \(\mathit{RSD}\) are even more frequent and more pronounced.

Finally, we consider popular random assignments (\(\mathit{POP}\)), as proposed by [63]. A random assignment is popular if there does not exist another random assignment that is preferred by an expected majority of agents. Popular random assignments always exist, but need not be unique. As pointed out by [64], popular random assignments are a special case of maximal lotteries, which exhibit desirable properties in social choice theory [20], [65], [66]. Maximal lotteries (and hence popular random assignments) maximize utilitarian SSB welfare for \(\mathit{PC}\) utility functions [38]. As a consequence, all popular random assignments are strongly \(\mathit{PC}\)-efficient. However, [64] constructed a preference profile that admits no popular random assignment that satisfies strong \(\mathit{SD}\)-envy-freeness. [67] extended this incompatibility to weak \(\mathit{SD}\)-envy-freeness. [62] showed via computer simulations that \(\mathit{PC}\)-envy-freeness violations of popular random assignments occur more frequently as \(n\) increases and that \(\mathit{PC}\)-envy probability margins can already exceed \(\frac{1}{3}\) when \(n=5\).

By contrast, the ordinal random assignment rule which returns a pseudo-market equilibrium with cost minimization,⁶ which we denote by \(\mathit{PCHZ}\), satisfies both \(\mathit{PC}\)-efficiency and \(\mathit{PC}\)-envy-freeness (see 4.1).

To get more intuition into \(\mathit{PCHZ}\) and how it differs from existing random assignment rules, consider the following example.

1 gives an overview of our results on ordinal random assignment. Note that \(\mathit{RSD}\) and \(\mathit{PS}\) already violate weak \(\mathit{PC}\)-efficiency.

7 Conclusion and Discussion↩︎

We extended the Hylland–Zeckhauser pseudo-market to continuous and convex preference relations. The resulting market equilibrium is weakly efficient and envy-free. Strong efficiency can be retained by restricting preferences to a natural subdomain of SSB preferences or by relaxing envy-freeness. These findings lead to a new ordinal random assignment rule that satisfies \(\mathit{PC}\)-efficiency and \(\mathit{PC}\)-envy-freeness.

As acknowledged by [18], their pseudo-market is not strategyproof. Moreover, [68] proved that no efficient assignment rule that satisfies equal treatment of equals is strategyproof. [69] formalize in which sense HZ pseudo-markets are approximately strategyproof when there are many agents.

When comparing \(\mathit{PCHZ}\) to other ordinal random assignment rules, it has to be mentioned that \(\mathit{RSD}\) is strongly \(\mathit{SD}\)-strategyproof and \(\mathit{PS}\) is weakly strategyproof. Note, however, that for weak preferences over objects, the canonical extension of \(\mathit{PS}\) fails to meet weak \(\mathit{SD}\)-strategyproofness. In fact, every \(\mathit{SD}\)-efficient and strongly \(\mathit{SD}\)-envy-free random assignment rule violates weak \(\mathit{SD}\)-strategyproofness [70]. We conjecture that no random assignment rule satisfies equal treatment of equals, \(\mathit{SD}\)-efficiency, and weak \(\mathit{SD}\)-strategyproofness for weak preferences. For strict preferences, we conjecture that equal treatment of equals is incompatible with \(\mathit{PC}\)-efficiency and \(\mathit{PC}\)-strategyproofness.⁷

[72] constructed a vNM utility profile whose unique HZ equilibrium uses irrational probabilities. Furthermore, [73] show that computing approximate HZ equilibria is PPAD-hard once agents’ vNM utilities take at least four distinct values. By contrast, [74] provide a polynomial-time algorithm for computing a constant-factor approximation by reducing the original market to a bi-valued instance. [75] showed that approximately computing any efficient and envy-free random assignment is PPAD-hard for vNM utilities. Since SSB preferences are more general than vNM preferences, these negative results carry over to SSB preferences. An interesting open question is whether similar results can be shown for \(\mathit{PC}\) preferences.

Acknowledgements↩︎

This material is based on work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/14-1. We are grateful to Matthias Greger for supplying 2.

8 Incompatibility of Efficiency and Envy-Freeness↩︎

9 A Generalized Pseudo-Market↩︎

Recall from 4 the basic set-up of the pseudo-market, most of which we inherit from [18]. In this section, we give more detailed definitions of the price set \(P\), the demand correspondence \(D_i\) for each agent \(i \in N\), and a price update mechanism that responds to excess demand and ensures market clearing at a fixed point. Along the way, we collect auxiliary lemmas that show that, even for general continuous and convex preferences, these three components together satisfy the conditions necessary for Kakutani’s fixed-point theorem.

9.0.0.1 Price set.

The price set \(P\), formally defined by \[P \mathrel{\vcenter{:}}= \left\{ p\in\mathbb{R}^{n}_{\ge 0}\colon \min_{o\in O}p_o=0 \text{ and } \left\|p-\frac{p\cdot\mathbf{1}}{n}\mathbf{1}\right\|_1\le 2 \right\},\] is not convex. Therefore, we follow [18] in obtaining \(P\) via a homeomorphic normalization map from a compact and convex parameter space \(S\). Let \[S \mathrel{\vcenter{:}}=\left\{s \in \mathbb{R}^{n} \colon \sum_{o\in O} s_o = 0 \text{ and } \|s\|_1 \le 2 \right\}.\] Define the normalization map \(f \colon S \to \mathbb{R}^{n}_{\ge 0}\) by \[f(s) \mathrel{\vcenter{:}}= s - \min_{o\in O}s_o \, \mathbf{1}.\] With this, we obtain \(P = f(S)\), noting that \(f\) is a homeomorphism. A key identity, which we use in the proof of [theorem:market95existence], is that for every zero-sum vector \(z\in \mathbb{R}^{n}\), \[\label{eq:price-identity} f(s)\cdot z = \bigl(s - \min_o s_o \, \mathbf{1} \bigr) \cdot z = s \cdot z.\tag{4}\]

9.0.0.2 Demand correspondences.

Recall that each agent is given a virtual budget \(b_i > 0\) satisfying \(\sum_{i \in N} b_i = 1\). The budget set of agent \(i\) with respect to a price vector \(p \in P\) is therefore \[B_i(p) \mathrel{\vcenter{:}}=\{x\in \Delta \colon p \cdot x \le b_i\}.\]

Next, [lemma:demand-compact-convex,lemma:maximal_set_upper_hc] show that the demand correspondence defined as \[D_i(p) \mathrel{\vcenter{:}}=\{x \in B_i(p) \colon x \succsim_i y \text{ for all } y \in B_i(p)\}\] is non-empty, compact, convex and satisfies upper hemicontinuity.

We remark that 4 mirrors [76]. From each agent’s demand correspondence \(D_i(\cdot)\), we now define the aggregate-demand correspondence \(D: P \rightrightarrows \Delta^n\) simply by the Cartesian product \[D(p) \mathrel{\vcenter{:}}= \prod_{i\in N} D_i(p).\] Since each \(D_i(\cdot)\) is non-empty, compact-valued, convex-valued, and upper hemicontinuous, the same is true for \(D\). An element \(X=(x_i)_{i \in N}\) of \(D(p)\) is exactly a selection of lottery \(x_i\) for each agent \(i\), under the assumption that each agent selects an element of her demand set \(D_i(p)\), i.e., a maximal element of the budget set \(B_i(p)\).

9.0.0.3 Price updates.

Recall that the price set \(P = f(S)\) is obtained via a homeomorphic normalization map from a compact convex parameter space \(S\). We now define the price-update dynamics on \(S\), by which the market adjusts prices in response to excess demand in a selection \(X \in D(p)\). Given any selection \(X\in \Delta^n\) of lotteries, the excess demand (compared to the unit supply of each object) is denoted by \[z(X) \mathrel{\vcenter{:}}= \sum_{i\in N} x_i - \mathbf{1}.\] Using this notation, we define the price-update correspondence \(\Pi: \Delta^n \rightrightarrows S\) by \[\Pi(X) \mathrel{\vcenter{:}}= \arg\max_{s\in S}~ s \cdot z(X).\] In words, \(\Pi(X)\) selects those price parameters \(s\in S\) that maximize the dot product with the excess-demand vector induced by the current lottery selection \(X\).

We can now give the proof of [theorem:market95existence].

9.1 SSB Preferences with Strict Maximality↩︎

We first provide the proof of [proposition:characterization95SSB95strict95maximality], which characterizes SSB preferences satisfying strict maximality via its matrix representation.

We now come to the proof of [theorem:existence-with-cost-minimization]: assuming SSB preferences, pseudo-market equilibria with cost-minimization always exist.

Most of the proof is identical to that of [theorem:market95existence]. Specifically, the price set \(P\) and price-update correspondence \(\Pi\) are defined identically. The only difference is that we refine the demand correspondences \(D_i\) by enforcing cost-minimization. Therefore, it suffices to prove that the refined correspondence \(\widehat{D}_i(\cdot)\) is upper hemicontinuous for each agent \(i \in N\).

Note that for all \(p \in P\), the non-emptiness, compactness and convexity of \(\widehat{D}_i(p)\) carry over immediately from the corresponding properties of \(D_i(p)\), since \(\widehat D_i(p)\) is the argmin set of the continuous linear function \(x\mapsto p\cdot x\) on the non-empty compact convex set \(D_i(p)\).

10 Efficiency and \(\alpha\)-Envy-Freeness for SSB Preferences↩︎

Towards proving [proposition:fixed-point-envy-freeness], first define the following instance-dependent parameter \(\sigma\), which is the largest SSB matrix entry taken over all agents. \[\sigma \mathrel{\vcenter{:}}= \max_{i \in N, o, \hat{o} \in O} \phi_i(o, \hat{o}),\] and let \[\rho = \min\left\{\frac{1}{2}, \frac{\alpha}{\sigma}\right\}.\] Note that \(\sigma > 0\) unless every agent is completely indifferent between all lotteries, in which case every random assignment is envy-free and [theorem:alpha-envy-free] holds trivially; we therefore assume \(\sigma > 0\) in the following.

We finally set the value of \(\varepsilon\), the lower bound on the weights \(\omega_i\) in the definition of \(\Omega_\varepsilon\). This value is given by \[\varepsilon \mathrel{\vcenter{:}}= \frac{\rho^{n+1}}{n}.\]

Given any random assignment \(X\), define the directed \(\alpha\)-envy graph of \(X\) to have the set \(N\) of agents as its vertex set, and to include a directed edge from agent \(i\) to agent \(j\) if and only if \(\phi_i(x_j, x_i) > \alpha\). A sink in this graph (a vertex with no outgoing edge) corresponds to an agent who does not envy any other agent by more than \(\alpha\).

Using the above lemma, we can show that whenever there exists an agent who envies another agent by more than \(\alpha\), the weight update map \(g\) maps to a distinct vector of welfare weights, i.e., \(g(X, \omega) \neq \omega\) whenever there are agents \(i, j \in N\) with \(\phi_i(x_j, x_i) > \alpha\).

Finally, we are ready to prove [proposition:fixed-point-envy-freeness].

We now provide a proof for [proposition:eff-not-closed].

References↩︎