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: