Lesson plan

Fair random assignment

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 are 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 Bob 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 Bob will toss a fair coin and the winner will get the eastern room.

Back to article

Article summary

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 are 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 Bob 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 Bob will toss a fair coin and the winner will get the eastern room.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.