Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Fair random assignment
open-in-new
<p>Fair random assignment (also called probabilistic one-sided matching) is a kind of a <a href="/facts/Fair_division/v4PN6nfD">fair division</a> problem. </p><p>In an <i>assignment problem</i> (also called <i><a href="/facts/House_allocation_problem/5es9pHGz">house-allocation problem</a></i> or <i><a href="/facts/One-sided_matching/5es9pHGz">one-sided matching</a></i>), there are <i>m</i> objects and they have to be allocated among <i>n</i> 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. </p><p>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. </p>