Fair random assignment

Fair random assignment is a kind of a fair division problem.

In the assignment problem, n objects have to be allocated fairly among n agents. Each agent has to receive exactly one object. Examples include the assignment of jobs to workers, of rooms to housemates, of 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.

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 $1/n$-share of each commodity, then the agents are allowed to trade until there is equilibrium. This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on tteries).

Properties

• Random Priority (RP) is a truthful mechanism. It is ex-ante envy-free, and ex-post Pareto efficient, but not ex-ante Pareto-efficient. It is a very simple mechanism that only requires agents to have ordinal ranking on individual items.
• Probabilistic Serial (PS) is an algorithm that guarantees ex-ante sd-envy-freeness, ex-ante and ex-post sd-Pareto efficiency, but is not truthful. It requires only ordinal ranking on items.
• Competitive Equilibrium from Equal Incomes (CEEI) is a market-based mechanism: each item is viewed as a divisible commodity. Each agent is given $1/n$-share of each commodity, then the agents are allowed to trade until there is equilibrium. It is ex-ante and ex-post Pareto-efficient, and ex-ante envy-free, but not truthful. This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on lotteries).

Comparison

Hosseini, Larson and Cohen compare RP to PS in various settings. They show that:

• When there are at most 2 objects and at most 3 agents, RP and PS return the same allocation.
• When there are at most 2 objects, for any number of agents, PS is truthful and RP is envy-free.
• When there are 3 or more objects (and 3 or more agents), RP and PS may return different allocations, and no allocation Pareto-dominates the other. For example, suppose there are three objects a,b,c and three agents with preference-rankings (1) a>c>b, (2) a>b>c, (3) b>a>c. Then, to agent (1), both RP and PS give 1/2 a + 1/2 c; to agent (2), RP gives 1/2 a + 1/6 b + 1/3 c while PS gives 1/2 a + 1/4 b + 1/4 c which is stochastically-dominant; and to agent (3), RP gives 5/6 b + 1/6 c while PS gives 3/4 b + 1/4 c which is stochastically-dominated. So (1) is indifferent, (2) strictly prefers PS and (3) strictly prefers RP.

See also

• Rental harmony is a variant of the assignment problem in which fairness is attained using monetary payments, instead of randomization.
• Fair item allocation is a setting in which agents may get more than one item.