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.
[1] 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: One desired property of a random assignment rule is Pareto efficiency (PE).
Again, there are three variants: The following table compares the various rules' properties (the RP and PS columns are based on [6]): ld-EF None [weak prefs] Some combinations of the above three properties cannot be simultaneously satisfied by any mechanism: Both the PS and the CEEI rules compute a matrix of expected assignments, i.e., the marginal probabilities with which each agent receives each object.
It can decompose any n-by-n matrix of agent-object probabilities into a convex combination of O(n2) permutation matrices, each of which represents a matching.
Demeulemeester, Goossens, Hermans and Leus[8] present a polynomial-time decomposition algorithm that maximizes the worst-case number of agents who receive an object.
They show that: Tao and Cole[9] study the existence of PE and EF random allocations when the utilities are non-linear (can have complements).