Fair random assignment

Last updated February 22, 2024

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 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.

History

Random assignment is mentioned already in the Bible: a lottery was used to allocate the lands of Canaan among the Tribes of Israel (Numbers 26:55).

In the US, lotteries were used to assign public lands to homesteaders (e.g. Oklahoma in 1901), and to assign radio spectra to broadcasters (e.g. FCC 1981-1993). Lottery is still used to assign green cards.^[1]

Methods

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:

Random Priority (RP, aka Random Serial Dictatorship or RSD) is a very simple mechanism that only requires agents to have ordinal ranking on individual items. It chooses a random priority-ordering on the items and lets each agent in turn pick his favorite remaining item.
Probabilistic Serial (PS)^[2] is another mechanism that works only with ordinal ranking on items. Agents "eat" their favorite remaining items in a constant speed, and the fraction each agent managed to eat is his/her probability to get this item.
Competitive Equilibrium from Equal Incomes (CEEI)^[3] is a market-based mechanism: each item is viewed as a divisible commodity. Each agent is given an equal budget of a fiat currency, then the agents are allowed to trade until there is a price equilibrium. This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on lotteries).

Properties

Efficiency

One desired property of a random assignment rule is Pareto efficiency (PE). There are three variants of PE:

Ex-post PE means that, after the final allocation is determined, no other allocation is better for some agent and at least as good for the others. All three rules above (RP, PS and CEEI) are ex-post PE.
Ex-ante PE is a stronger property, relevant for agents with cardinal utilities. It means that no other lottery is better for some agent and at least as good for the others. CEEI is ex-ante PE when agents compare lotteries based on their expected utility.
Possible PE (or sd-PE) is an intermediate property, relevant for agents with ordinal utilities. It means that the allocation is ex-ante PE for some valuation functions consistent with the agents' ordinal ranking. PS is possible-PE, but RP is not.

For PE, the implications are: ex-ante → sd(possible) → ex-post.

Fairness

Another desired property is envy-freeness (EF). Again, there are three variants of EF:

Ex-post EF means that, after the final allocation is determined, no agent prefers the allocation of another agent. No rule satisfies this strong property; indeed, it may be impossible to find an ex-post EF allocation of indivisible objects.
Ex-ante EF is a weaker property, relevant for agents with cardinal utilities. It means that no agent prefers the lottery of another agent. CEEI is ex-ante EF w.r.t. expected utilities.
Necessary EF (or sd-EF) is an intermediate property, relevant for agents with ordinal utilities. It means that the allocation is ex-ante EF (see below) for all valuation functions consistent with the agents' ordinal ranking. PS is necessary-EF, but RP is not. RP is weakly ex-ante sd-EF; it is EF when agents compare lotteries by lexicographic dominance (ld-EF).^[4]

For EF, the implication direction is opposite to that of efficiency: ex-post → sd(necessary) → ex-ante.

Truthfulness

A third desired property is truthfulness (also called strategyproofness). Again, there are three variants:

Ex-ante truthfulness, relevant for agents with cardinal utilities, means that no agent can get a better lottery by reporting false valuations. This is a strong property, that is not satisfied by any non-trivial mechanism.

Possible truthfulness is a weaker property, relevant for agents with ordinal utilities. It means that an agent cannot get a stochastically-dominating lottery by reporting a false ranking. This weak property is satisfied by PS when all rankings are strict, and there is at most one object per person. In this setting it is also truthful w.r.t. lexicographic dominance (ld-truthful).^[4] It is not satisfied when the rankings are weak.^[5]
Necessary truthfulness is a stronger property, relevant for agents with ordinal utilities. It means that an agent reporting a false ranking always gets a stochastically-dominated lottery. This strong property is satisfied by RP, and it can be extended in a truthful way also to the general case when there are more objects than people.

The following table compares the various rules' properties (the RP and PS columns are based on ^[6]):


	#items ≤ #agents			#items > #agents
	RP	PS	CEEI	RP	PS	CEEI
Efficiency:	Ex-post PE	Possible PE	ex-ante PE	No	possible PE	ex-ante PE
Fairness:	Weak sd-EF; ld-EF	Necessary EF	ex-ante EF	Weak sd-EF	sd-EF	EF
Truthfulness:	Necessary truthful	Possible sd-truthful; ld-truthful _{[strict prefs]} None _{[weak prefs]}	No	sd-truthful*	No	No

Impossible combinations

Some combinations of the above three properties cannot be simultaneously satisfied by any mechanism:

For agents with cardinal utilities, Zhou^[7] 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^[2] prove that no mechanism satisfies possible efficiency, necessary truthfulness, and equal treatment of equals.
For agents with weak ordinal utilities, Katta and Sethuraman^[5] prove that no mechanism satisfies possible efficiency, possible truthfulness, and necessary envy-freeness.

Decomposing a fractional allocation

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. However, since the final allocation must be a matching, one must find a decomposition of this matrix into a lottery on matchings.

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²) 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^[1] 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^[8] 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.

Empirical comparison

Hosseini, Larson and Cohen^[6] compare RP to PS in various settings. They show that:

When there are at most 2 objects and at most 3 agents, RP and PS return the same allocation.
When there are at most 2 objects, for any number of agents, PS is sd-truthful and RP is sd-envy-free, and in most instances, PS dominates RP, particularly with 4 or more agents.
When there are 3 or more objects (and 3 or more agents), RP and PS may return different allocations, and no allocation Pareto-dominates the other. For example, suppose there are three objects a,b,c and three agents with preference-rankings (1) a>c>b, (2) a>b>c, (3) b>a>c. Then, to agent (1), both RP and PS give 1/2 a + 1/2 c; to agent (2), RP gives 1/2 a + 1/6 b + 1/3 c while PS gives 1/2 a + 1/4 b + 1/4 c which is stochastically-dominant; and to agent (3), RP gives 5/6 b + 1/6 c while PS gives 3/4 b + 1/4 c which is stochastically-dominated. So (1) is indifferent, (2) strictly prefers PS and (3) strictly prefers RP.
The fraction of preference profiles for which PS sd-dominates RP is large when the number of agents and objects differ, but approaches 0 when the numbers are equal. The same is true for ld-domination.
When agents are risk-neutral, the expected social welfare of PS is larger than RP, but the difference is substantial only when n≠m. With RP, the fraction of envious agents is near zero when n ≥ m. PS is manipulable, and the gain from manipulation increases when m>n.
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.

Extensions

Tao and Cole^[9] study the existence of PE and EF random allocations when the utilities are non-linear (can have complements).

Yilmaz^[10] studies the random assignment problem where agents have endowments.

Shen, Wang, Zhu, Fain and Munagala^[11] study the random assignment problem when agents have priorities (agents with higher priorities should get their preferred goods before agents with lower priorities), but the priorities are uncertain.

Duddy^[12] studies egalitarian random assignment.

Related Research Articles

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners $i$ and $j$ :

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Fractional approval voting is an electoral system using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction p_j between 0 and 1, such that the sum of p_j is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions p_j can be interpreted in various ways, depending on the setting. Examples are:

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings:

References

1 2 Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). "Designing Random Allocation Mechanisms: Theory and Applications". American Economic Review. 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282.
1 2 Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.
↑ Hylland, Aanund; Zeckhauser, Richard (1979). "The Efficient Allocation of Individuals to Positions". Journal of Political Economy. 87 (2): 293. doi:10.1086/260757. S2CID 154167284.
1 2 Kate, Hosseini, Hadi Larson (2015-07-24). Strategyproof Quota Mechanisms for Multiple Assignment Problems. OCLC 1106222190.{{cite book}}: CS1 maint: multiple names: authors list (link)
1 2 Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory. 131: 231–250. doi:10.1016/j.jet.2005.05.001.
1 2 Hadi Hosseini, Kate Larson, Robin Cohen (2018). "Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes". Autonomous Agents and Multi-Agent Systems. 32 (4): 534–567. arXiv: 1703.00320 . doi:10.1007/s10458-018-9387-y. S2CID 14041902.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Zhou, Lin (1990-10-01). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52 (1): 123–135. doi:10.1016/0022-0531(90)90070-Z. ISSN 0022-0531.
↑ Demeulemeester, Tom; Goossens, Dries; Hermans, Ben; Leus, Roel (2023). "A pessimist's approach to one-sided matching". European Journal of Operational Research. 305 (3): 1087–1099. arXiv: 2101.00579 . doi:10.1016/j.ejor.2022.07.013. S2CID 245669132.
↑ Cole, Richard; Tao, Yixin (2021-04-01). "On the existence of Pareto Efficient and envy-free allocations". Journal of Economic Theory. 193: 105207. arXiv: 1906.07257 . doi:10.1016/j.jet.2021.105207. ISSN 0022-0531. S2CID 189999837.
↑ Yılmaz, Özgür (2009). "Random assignment under weak preferences". Games and Economic Behavior. 66: 546–558. doi:10.1016/j.geb.2008.04.017.
↑ Shen, Zeyu; Wang, Zhiyi; Zhu, Xingyu; Fain, Brandon; Munagala, Kamesh (2023). "Fairness in the Assignment Problem with Uncertain Priorities". arXiv: 2301.13804 [cs.GT].
↑ Duddy, Conal (2022). "Egalitarian random assignment". doi:10.2139/ssrn.4197224. S2CID 252192116. SSRN 4197224.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:12-1] 1 2 Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). "Designing Random Allocation Mechanisms: Theory and Applications". American Economic Review. 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282.

[bm01-2] 1 2 Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.

[hz79-3] Hylland, Aanund; Zeckhauser, Richard (1979). "The Efficient Allocation of Individuals to Positions". Journal of Political Economy. 87 (2): 293. doi:10.1086/260757. S2CID 154167284.

[:1-4] 1 2 Kate, Hosseini, Hadi Larson (2015-07-24). Strategyproof Quota Mechanisms for Multiple Assignment Problems. OCLC 1106222190.{{cite book}}: CS1 maint: multiple names: authors list (link)

[ks06-5] 1 2 Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory. 131: 231–250. doi:10.1016/j.jet.2005.05.001.

[:0-6] 1 2 Hadi Hosseini, Kate Larson, Robin Cohen (2018). "Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes". Autonomous Agents and Multi-Agent Systems. 32 (4): 534–567. arXiv: 1703.00320 . doi:10.1007/s10458-018-9387-y. S2CID 14041902.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[7] Zhou, Lin (1990-10-01). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52 (1): 123–135. doi:10.1016/0022-0531(90)90070-Z. ISSN 0022-0531.

[8] Demeulemeester, Tom; Goossens, Dries; Hermans, Ben; Leus, Roel (2023). "A pessimist's approach to one-sided matching". European Journal of Operational Research. 305 (3): 1087–1099. arXiv: 2101.00579 . doi:10.1016/j.ejor.2022.07.013. S2CID 245669132.

[9] Cole, Richard; Tao, Yixin (2021-04-01). "On the existence of Pareto Efficient and envy-free allocations". Journal of Economic Theory. 193: 105207. arXiv: 1906.07257 . doi:10.1016/j.jet.2021.105207. ISSN 0022-0531. S2CID 189999837.

[y09-10] Yılmaz, Özgür (2009). "Random assignment under weak preferences". Games and Economic Behavior. 66: 546–558. doi:10.1016/j.geb.2008.04.017.

[11] Shen, Zeyu; Wang, Zhiyi; Zhu, Xingyu; Fain, Brandon; Munagala, Kamesh (2023). "Fairness in the Assignment Problem with Uncertain Priorities". arXiv: 2301.13804 [cs.GT].

[12] Duddy, Conal (2022). "Egalitarian random assignment". doi:10.2139/ssrn.4197224. S2CID 252192116. SSRN 4197224.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]