Efficient lottery design

Indeed we are not aware of any stochastic mechanisms in use for any practical assignment problem.

PS treats each object as a continuum of probability shares and allows agents to simultaneously “eat away” from their favorite objects at the same speed until each agent has eaten a total of 1 probability share. The share of an object an agent has eaten during the process represents the probability with which she assigned the object by PS. See Sect. 5 for a more precise description.

For example, as far as we are aware, a nontrivial lottery mechanism satisfying sd-efficiency (or the stronger ex-ante efficiency) is yet to be reported or studied. Additionally imposing strategy-proofness readily leads to impossibilities (Zhou 1990; Bogomolnaia and Moulin 2001).

Budish et al. (2013) develop tools for handling complex constraints while working directly with stochastic mechanisms.

See Example 3 of Abdulkadiroğlu and Sönmez (2003a).

Improving upon a “status quo” allocation (or a partial allocation) while respecting other considerations has been a common goal in various applications of indivisible goods allocation. Examples of applications include housing markets, on-campus housing, kidney exchange, and school choice. All these applications, however, have focused on achieving ex post properties.

In a related paper, Manea (2008) shows the existence of lotteries that improve upon the RSD outcome. Differently than here, his approach is based on working directly with stochastic assignments.

The reason for this will be clear when relating the sd-efficiency of a lottery with the Pareto efficiency of an assignment in a replica economy in the next section.

This tractability assumption holds generally in practice and is satisfied by lotteries induced by all well-known mechanisms.

See Hugh-Jones et al. (2014) for an experimental evaluation of PS.

Simply apply the TTC to the problem where the support of the lottery is interpreted as an extended housing market with endowments. Then the following is easy to show. The support of the lottery is Pareto efficient if and only if the TTC algorithm generates only self-cycles.

Because of its appealing efficiency and incentive features, a number of mechanisms based on the TTC method have been proposed and characterized for a variety of applications such as on-campus housing, school choice, and kidney exchange. Although for deterministic settings, all proposed TTC based mechanisms are Pareto efficient, little is known about the applicability of this procedure to the stochastic assignment context or its relation to sd-efficiency, for that matter. An exception is Kesten (2009) who shows that if a simple version of the TTC method is applied to a market in which each agent is initially endowed with an equal probability share of each object, then the resulting outcome is sd-efficient and coincides with that of PS.

It is quite challenging to check whether or not the TRSD\(^{K}\) is sd-strategy-proof, for the following reasons. First, BM’s and Nesterov’s (2014) impossibility theorems show the incompatibility of sd-strategy-proofness, sd-efficiency, and equal treatment of equals for problems with unit quotas. Thus their results are not applicable since TRSD\(^{K}\) is not necessarily sd-efficient in general, and nor does our setting assume unit quotas. Second, we need at least four agents for the outcomes of RSD and TRSD\(^{K}\) to differ, which makes it cumbersome to calculate the stochastic assignments of TRSD\(^{K}\).

In fact, we can show a more general result in which any sd-efficient stochastic assignment (and not only PS) can be represented as an equal-weight lottery using the same algorithm.

This step is missing in the example since all priorities have the same weight.

For a general case of an arbitrary sd-efficient assignment, objects can also be relabeled according to the exhausting order, although the underlying eating algorithm proceeds not using constant eating speed functions but some other profile of eating speed functions (Bogomolnaia and Moulin 2001). Alternatively, we can order the objects using the following hierarchical procedure: at each step agents point to their most preferred object among the remaining objects and we choose the most popular object (choose one of them arbitrarily if there are several) to be the next in our order of objects. Intuitively, this ordering of objects is similar to the exhausting order in the eating algorithm: at each step j the agents in \(E(a_{j})\) prefer object \(a_{j}\) over the remaining objects. This is the key feature of the ordering \(l_{ex}\) in our lottery decomposition.