Fair random assignment (also called probabilistic one-sided matching) is a kind of a fair division problem.
In an assignment problem (also called house-allocation problem or one-sided matching), there m objects and they have to be allocated among n agents, such that each agent receives at most one object. Examples include the assignment of jobs to workers, rooms to housemates, dormitories to students, time-slots to users of a common machine, and so on.
In general, a fair assignment may be impossible to attain. For example, if Alice and Batya both prefer the eastern room to the western room, only one of them will get it and the other will be envious. In the random assignment setting, fairness is attained using a lottery. So in the simple example above, Alice and Batya will toss a fair coin and the winner will get the eastern room.
History
Random assignment is mentioned already in the Bible: a lottery was used to allocate the lands of Canaan among the Tribes of Israel (Numbers 26:55).
In the US, lotteries were used to assign public lands to homesteaders (e.g. Oklahoma in 1901), and to assign radio spectra to broadcasters (e.g. FCC 1981-1993). Lottery is still used to assign green cards.
Methods
There are several ways to extend the "coin toss" method to situations in which there are more than two agents, and they may have different preference relations on the objects:
Random Priority (RP, aka Random Serial Dictatorship or RSD) is a very simple mechanism that only requires agents to have ordinal ranking on individual items. It chooses a random priority-ordering on the items and lets each agent in turn pick his favorite remaining item. Probabilistic Serial (PS) is another mechanism that works only with ordinal ranking on items. Agents "eat" their favorite remaining items in a constant speed, and the fraction each agent managed to eat is his/her probability to get this item. Competitive Equilibrium from Equal Incomes (CEEI) is a market-based mechanism: each item is viewed as a divisible commodity. Each agent is given an equal budget of a fiat currency, then the agents are allowed to trade until there is a price equilibrium. This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on lotteries).
Properties
Efficiency
One desired property of a random assignment rule is Pareto efficiency (PE). There are three variants of PE:
Ex-post PE means that, after the final allocation is determined, no other allocation is better for some agent and at least as good for the others. All three rules above (RP, PS and CEEI) are ex-post PE. Ex-ante PE is a stronger property, relevant for agents with cardinal utilities. It means that no other lottery is better for some agent and at least as good for the others. CEEI is ex-ante PE when agents compare lotteries based on their expected utility. Possible PE (or sd-PE) is an intermediate property, relevant for agents with ordinal utilities. It means that the allocation is ex-ante PE for some valuation functions consistent with the agents' ordinal ranking. PS is possible-PE, but RP is not. For PE, the implications are: ex-ante → sd(possible) → ex-post.
Fairness
Another desired property is envy-freeness (EF). Again, there are three variants of EF:
Ex-post EF means that, after the final allocation is determined, no agent prefers the allocation of another agent. No rule satisfies this strong property; indeed, it may be impossible to find an ex-post EF allocation of indivisible objects. Ex-ante EF is a weaker property, relevant for agents with cardinal utilities. It means that no agent prefers the lottery of another agent. CEEI is ex-ante EF w.r.t. expected utilities. Necessary EF (or sd-EF) is an intermediate property, relevant for agents with ordinal utilities. It means that the allocation is ex-ante EF (see below) for all valuation functions consistent with the agents' ordinal ranking. PS is necessary-EF, but RP is not. RP is weakly ex-ante sd-EF; it is EF when agents compare lotteries by lexicographic dominance (ld-EF). For EF, the implication direction is opposite to that of efficiency: ex-post → sd(necessary) → ex-ante.
Truthfulness
A third desired property is truthfulness (also called strategyproofness). Again, there are three variants:
Ex-ante truthfulness, relevant for agents with cardinal utilities, means that no agent can get a better lottery by reporting false valuations. This is a strong property, that is not satisfied by any non-trivial mechanism.