Fair random assignment
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. For agents with cardinal utilities, Zhou proves that no mechanism satisfies ex-ante efficiency, ex-ante truthfulness, and equal treatment of equals (= agents with identical utility functions should get the same utility). For agents with strict ordinal utilities, Bogomolnaia and Moulin prove that no mechanism satisfies possible efficiency, necessary truthfulness, and equal treatment of equals. For agents with weak ordinal utilities, Katta and Sethuraman prove that no mechanism satisfies possible efficiency, possible truthfulness, and necessary envy-freeness. In the classic setting, in which m=n, this can be done using the Birkhoff algorithm. It can decompose any n-by-n matrix of agent-object probabilities into a convex combination of O(n 2 ) permutation matrices, each of which represents a matching. However, the decomposition is not unique, and some decompositions may be better than others. Budish, Che, Kojima and Milgrom generalize Birkhoff's algorithm to arbitrary m and n. They also allow to add constraints on the assignments, under a maximal set of conditions on the set of constraints. They also present a decomposition method that minimizes the variance in the utility experienced by the agents between the different matchings. Demeulemeester, Goossens, Hermans and Leus present a polynomial-time decomposition algorithm that maximizes the worst-case number of agents who receive an object. Their algorithm guarantees that the worst-case number of agents equals the expected number of agents rounded down, which is the best possible. They present another decomposition algorithm that maximizes the worst-case number of assigned agents while guaranteeing that all matchings in the decomposition be ex-post PE; the second algorithm can be used only for fractional assignments outputted by PS, but not those corresponding to RP. For RP, it is only possible to attain a 1/2-factor approximation to the optimal worst-case number of assigned agents. For general fractional assignments, maximizing the worst-case number of assigned agents subject to ex-post PE is NP-hard. They also present a column generation framework that can be used to optimize other worst-case criteria. When agents are risk-seeking, the expected social welfare of PS is larger than RP, and the difference grows rapidly when n≠m. In contrast, when n=m RP attains a higher social welfare in most cases. With RP, the fraction of envious agents is near zero when n ≥ m, but generates envy when m>n. The envy of RP decreases when risk-seekingness increases. The gain from manipulating PS decreases when agents are more risk-seeking. When agents are risk-averse, the social welfare gap between RP and PS becomes smaller (though still statistically-significant). The fraction of envious agents in RP increases, but the envy remains below 0.01 when n ≥ m. The manipulability of PS goes to 1 when m/n grows.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1348083690 under CC BY-SA 4.0; modifications have been made.