Serial dictatorship mechanisms with reservation prices: heterogeneous objects

We consider the problem of allocating heterogeneous indivisible objects to agents when each agent receives at most one object and pays a non-negative price. Each agent’s preferences over receiving an object and his own payment are given by a general utility function that is not necessarily quasilinear. A mechanism selects an outcome for the problem by allocating an object and specifying a payment for each agent, i.e., it selects an allotment for each agent. We are interested in mechanisms that have desirable properties. More specifically, we consider mechanisms that: satisfy mild efficiency criteria (minimal tradability and non-wasteful tie-breaking); induce voluntarily participation (individual rationality); elicit agents’ true preferences over objects (strategy-proofness); select outcomes that are robust, in the sense of remaining invariant when agents leave from the problem with their allotments (consistency) or when we remove undesired objects (independence of unallocated objects); and in which the names of the objects do not matter and the objects can be relabelled while the payments are kept invariant (neutrality).

We show that a mechanism \(\varphi \) satisfies all the properties mentioned above if and only if there exists a reservation price vector r, which specifies an individual reservation price for each agent that is the same for all objects, and a priority ordering \(\succ \) over the set of agents, such that \(\varphi \) is a serial dictatorship mechanism with reservation prices that is based on r and \(\succ \) (Theorem 1). Our characterization is tight in the sense that each property used is indispensable.

Intuitively, a serial dictatorship mechanism with reservation prices works as follows. Agents sequentially get to choose feasible objects according to their priority, where the feasible objects are those remaining after all preceding agents made their choices: If the choosing agent’s value for his most preferred object among the feasible ones exceeds his reservation price, he takes the object and he pays his reservation price; otherwise, he receives and pays nothing.

Our model, properties, and mechanisms, are well-suited for understanding markets in which: wealth inequality among agents can be substantial; income redistribution is not feasible; sequential priorities as a main criteria for rationing demand are considered fair (Konow 2003) and just (Dold and Khadjavi 2017)—and are thus desirable, while maintaining compatibility with some payments is also required. An example of such markets, albeit in a less general model than ours, is the allocation of similar “consultant-led” medical procedures in Australia (Klaus and Nichifor 2020, Section 5); we briefly revisit this example in Sect. 4, after we present our main result (Theorem 1).

Our work is closely related to that of Klaus and Nichifor (2020). We extend their homogeneous indivisible objects model, normative properties, and the class of serial dictatorship mechanisms with reservation prices that they introduced, to heterogeneous indivisible objects. Our characterization (Theorem 1), which uses one additional key property, neutrality, provides a counterpart to the main result of Klaus and Nichifor (2020, Theorem 1).¹

For settings in which agents’ preferences are given by linear orders and there are no payments, several characterizations of the classical serial dictatorship mechanisms are available, e.g., Svensson (1994, 1999), Ergin (2000), and Ehlers and Klaus (2007). Relative to those settings, we extend the model to allow for general utility functions, and we adapt the properties used to characterize classical serial dictatorship mechanisms, as well as the mechanism itself, in a way in which we maintain sequential priorities as the main rationing criteria (as desired), but we relax the earlier limitations that ruled out any payments. Our model and key properties end up being closer to those of Tadenuma and Thomson (1991) and Svensson and Larsson (2002), who do not characterize any mechanism as such;² in contrast, we characterize the class of serial dictatorship mechanisms with reservation prices. Furthermore, in our characterization, the reservation price vector and the priority ordering are both derived from the properties, together with the serial dictatorship mechanism with reservation prices that is based on them; in this sense, our approach is related to the recent characterizations of deferred acceptance mechanisms (Kojima and Manea 2010; Ehlers and Klaus 2014, 2016) in which the priorities (or more generally, the choice functions) that the mechanisms are based on, and the mechanisms, are all derived together from the properties.

Our model extends the homogeneous objects model of Klaus and Nichifor (2020) to heterogeneous objects; to ease the comparison, our exposition and notation are closely based on that of Klaus and Nichifor (2020).

A set of heterogeneous indivisible objects are to be allocated to a set of agents; the sets of objects and the set of agents can change. Let \({\mathbb {N}}\) be the set of potential agents and \({\mathcal {N}}\) be the set of all non-empty finite subsets of \({\mathbb {N}}\), \({\mathcal {N}} \equiv \left\{ N \subseteq {\mathbb {N}} : 0< |N| < \infty \right\} \). Let \({\mathbb {O}}\) be the set of potential real objects and \({\mathcal {O}}\) be the set of all non-empty finite subsets of \({\mathbb {O}}\), \({\mathcal {O}} \equiv \left\{ O \subseteq {\mathbb {O}} : 0< |O| < \infty \right\} \). We assume that \(|{\mathbb {O}}|>1\) and that \({\mathbb {O}}\) is infinite.³ By 0 we denote the null object, which represents not receiving a real object in \({\mathbb {O}}\).

For any set of agents \(N\in {\mathcal {N}}\) and any set of real objects \(O\in {\mathcal {O}}\), an allocation vector \(a=(a_{i})_{i\in N}\in \big (O\cup \{0\}\big )^{N}\) such that [for any two agents \(i,j\in N\), \(i\ne j\), \(a_i=a_j\) implies \(a_i=a_j=0\)] describes which agent in N receives which object in \(O\cup \{0\}\); we allow for the possibilities that no real objects, or only some, are allocated. We denote the set of allocation vectors for a set of agents \(N\in {\mathcal {N}}\) and a set of real objects \(O\in {\mathcal {O}}\) by \({\mathcal {A}}(N,O).\)

We assume that an agent \(i\in {\mathbb {N}}\) pays a non-negative price \(p_i\in {\mathbb {R}}_+\), and we denote the set of payment vectors for a set of agents \(N\in {\mathcal {N}}\) by \({\mathcal {P}}(N) \equiv \left\{ p=(p_i)_{i\in N}: p \in {\mathbb {R}}^{N}_+\right\} \).

We assume that agents only care about the object they receive and their own payment. Each agent \(i\in {\mathbb {N}}\) has preferences that are: (i) for any object, strictly decreasing in the price paid; (ii) such that for any real object, either there exists a price which makes the agent indifferent between [receiving the real object at this price] and [receiving the null object and paying nothing], or he strictly prefers to [obtain the real object, whatever the price] over [receiving the null object and paying nothing], or he strictly prefers to [receive the null object and pay nothing] over [obtaining the real object, whatever the price]; and (iii) strict when comparing any two real objects at the same price. Formally, for each \(O \in {\mathcal {O}}\) and each \(i\in {\mathbb {N}}\), we represent agent i’s preferences by a utility function \(u_i:(O\cup \{0\})\times {\mathbb {R}}_+\rightarrow {\mathbb {R}}\) that satisfies the following three properties: Given \(u_i:(O\cup \{0\})\times {\mathbb {R}}_+\rightarrow {\mathbb {R}}\) and \(o\in O\), \(u_{i,o}:{\mathbb {R}}_+\rightarrow {\mathbb {R}}\) denotes agent i’s induced utility function for object o, i.e., for any payment \(p_i\), \(u_{i,o}(p_i)=u_i(o,p_i)\).

An example of an agent i’s preferences are quasilinear preferences \(u_i\) with valuation vector \(v_i\) such that for all \(o_1,o_2\in O\), \(o_1\ne o_2\), \(v_{i,o_1}\ne v_{i,o_2}\) and for each \((a_i,p_i)\in (O\cup \{0\})\times {\mathbb {R}}_+\), \(u_i(a_i,p_i)= v_{i,a_i} - p_i\).

For any set of agents \(N \in {\mathcal {N}}\) and any set of real objects \(O \in {\mathcal {O}}\), we denote the set of utility (function) profiles by \({\mathcal {U}}(N,O)\) and the associated set of valuation (vector) profiles by \({\mathcal {V}}(N,O)\).

A problem \(\gamma \) is specified by a triple (N, O, u) such that \((N,O) \in {\mathcal {N}} \times {\mathcal {O}}\) and \(u\in {\mathcal {U}}(N,O)\). We denote the set of all problems for \((N,O) \in {\mathcal {N}} \times {\mathcal {O}}\) by \(\Gamma (N,O)\).

An outcome for any problem \(\gamma \in \Gamma (N,O)\) consists of an allocation vector \(a\in {\mathcal {A}}(N,O)\) and a payment vector \(p\in {\mathcal {P}}(N)\). We denote the set of outcomes for a problem \(\gamma \in \Gamma (N,O)\) by \({\mathcal {O}} (N,O)\equiv {\mathcal {A}}(N,O) \times {\mathcal {P}}(N).\)

A mechanism \(\varphi \) is a function that assigns an outcome to each problem. Formally, for each \((N,O) \in {\mathcal {N}}\times {\mathcal {O}}\) and each \(\gamma \in \Gamma (N,O)\), \(\varphi (\gamma ) \in {\mathcal {O}}(N,O)\). Note that we can also represent a mechanism \(\varphi \) by its allocation rule \(\alpha \) and payment rule \(\pi \), i.e., for each \((N,O) \in {\mathcal {N}}\times {\mathcal {O}}\) and each \(\gamma \in \Gamma (N,O)\), \(\alpha : \Gamma (N,O) \rightarrow {\mathcal {A}}(N,O)\), \(\pi : \Gamma (N,O) \rightarrow {\mathcal {P}}(N)\), and \(\varphi (\gamma )=(\alpha (\gamma ),\pi (\gamma ))\). We denote the allotment of agent i at outcome \(\varphi (\gamma )\) by \(\varphi _i(\gamma ) = (\alpha _i(\gamma ),\pi _i(\gamma ))\).

Given \(N\in {\mathcal {N}}\), a vector \(x\in {\mathbb {R}}^N\), and \(M\subseteq N\), let \(x_{M} \equiv (x_{i})_{i\in M}\in {\mathbb {R}}^M\) be the restriction of vector x to the subset of agents M. We also use the notation \(x_{-i}=x_{N\backslash \{i\}}\). For example, \(({\bar{x}}_{i},x_{-i})\) denotes the vector obtained from x by replacing \(x_{i}\) with \({\bar{x}}_{i}\). We use corresponding notational conventions for utility profiles.

We adapt the class of serial dictatorships with reservation prices introduced by Klaus and Nichifor (2020) for the allocation of homogeneous indivisible objects to our model with heterogeneous indivisible objects as follows.

First, we need to define and fix reservation prices and a priority ordering.

We assume that for each agent \(i\in {\mathbb {N}}\) a (fixed) reservation price \(f_i\ge 0\) exists. We interpret \(f_i\) as the price at which a real object can be allocated to agent i. Note that the reservation price \(f_i\) is the same for different real objects. We denote a vector of (fixed) reservation prices for the set of potential agents \({\mathbb {N}}\) by \(f=(f_i)_{i\in {\mathbb {N}}}\) and by \({\mathcal {F}}\) we denote the set of all (fixed) reservation price vectors for \({\mathbb {N}}\).

A priority ordering \(\vartriangleright \) over the set of potential agents \({\mathbb {N}}\) is a complete, asymmetric, and transitive binary relation, with the interpretation that for any two distinct agents \(i,j\in {\mathbb {N}}\), \(i\vartriangleright j\) means that i has a higher priority than j. Note that the priority ordering \(\vartriangleright \) is the same for different real objects. Let \({\mathcal {P}}\) denote the set of all priority orderings over \({\mathbb {N}}\).

Given a reservation price vector \(f\in {\mathcal {F}}\) and a priority ordering \(\vartriangleright \in {\mathcal {P}}\), the serial dictatorship mechanism with reservation prices based on f and \(\vartriangleright \) is denoted by \(\psi ^{(f,\vartriangleright )}\) and determines an outcome for each problem \(\gamma = (N,O,u)\in \Gamma (N,O)\) with associated valuation vector \(v\in {\mathcal {V}}(N,O)\) as follows.

Step 1: The agent with the highest priority in N is considered. Let \(i\in N\) be this agent.Step l: The agent with the \(l^{\mathrm {th}}\) highest priority in N is considered. Let \(j\in N\) be this agent.We continue until either all real objects are allocated or all agents have been considered. We denote the resulting outcome by \(\psi ^{(f,\vartriangleright )}(N,O,u)\).⁷

We formally prove Theorem 1 in Appendix A. Below, we discuss how our result relates to that of Klaus and Nichifor (2020, Theorem 1), and we explain and sketch the more involved uniqueness part of our proof.

Recall that we extended the homogeneous indivisible objects model of Klaus and Nichifor (2020), their normative properties, and their class of serial dictatorship mechanisms with reservation prices to heterogeneous indivisible objects. For our characterization (Theorem 1), we use all the properties that are used by Klaus and Nichifor (2020, Theorem 1), suitably adapted from homogeneous to heterogeneous objects, to which we add one new key property: neutrality.

Except for neutrality, Klaus and Nichifor (2020, Section 5) interpret properties and mechanisms similar to those in our Theorem 1 in the context of allocating similar “consultant-led” medical procedures (e.g., mole removal surgeries) to patients in Australia. The same intuition and interpretation can be used for the allocation of heterogeneous objects by assuming that these objects are composed of a homogeneous item, corresponding to a specific medical procedure, together with a unique time slot.⁸ Furthermore, for such heterogeneous objects, neutrality has the natural interpretation that it requires the out-of-pocket cost paid by a patient for the underlying medical procedure to be the same, regardless of when this procedure is scheduled.⁹

In our characterization (Theorem 1), as well as in that of Klaus and Nichifor (2020, Theorem 1), the uniqueness proof consists of four parts; next, we sketch these parts, highlighting the role played by neutrality.

The following examples present mechanisms that satisfy all the properties in Theorem 1, except for the one in the title of the example.

Let \({\widetilde{f}} \in {\mathcal {F}}\) be such that for all \(i\in {\mathbb {N}}\), \({\widetilde{f}}_i=1\) (all reservation prices are equal to 1) and \({\widetilde{\vartriangleright }} \in {\mathcal {P}}\) be such that for any \(i,j\in {\mathbb {N}}\), \(i< j\) implies \(i\mathbin {{\widetilde{\vartriangleright }}}j\) (lower indexed agents have higher priority). Most of our independence examples are modifications of the serial dictatorship mechanism with reservation prices based on \({\widetilde{f}}\) and \({\widetilde{\vartriangleright }}\), \(\psi ^{({\widetilde{f}},{\widetilde{\vartriangleright }})}\).