Fair item assignment

Fair item assignment is a kind of a fair division problem in which the items to divide are indivisible. The items have to be divided among several partners who value them differently. A typical scenario is when several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings.

The indivisibility of the items implies that a fair division may not be possible. As an extreme example, if there is only a single item (e.g. a house), it must be given to a single partner, but this is not fair to the other partners. There are several solutions to such cases, like monetary payments or time-based rotation.

There are two prominent ways to model the preferences of the partners:

• In the cardinal model, each partner has a value function that assigns a certain numeric value to each item. Usually it is assumed that the functions are additive utility functions, which means that the value of a set of items is the sum of the values of the items.
• In the ordinal model, each partner has only a ranking between the items, which says which item is the best, which is the second-best, etc.

For each type of preferences, there are different fairness criteria and different division procedures.

The cardinal-additive model

Fairness criteria

Various fairness criteria have been studied. Five of the more common criteria are presented below, ordered from the weakest to the strongest:^[1]

1. Max-min fair-share (MFS): The max-min-fair-share (also called: max-min-share) of an agent is the most preferred bundle he could guarantee himself as divider in divide-and-choose against adversarial opponents. An allocation is called MFS-fair if every agent receives a bundle that he weakly prefers over his MFS.^[2] The MFS of an agent can be interpreted as the maximal utility that an agent can hope to get from an allocation if all the other agents have the same preferences, when he always receives the worst share. It can be considered as the minimal amount of utility that an agent could feel to be entitled to, based on the following argument: if all the other agents have the same preferences as me, there is at least one allocation that gives me this utility, and makes every other agent (weakly) better off; hence there is no reason to give me less. It is also the maximum utility that an agent can get for sure in the allocation game “I cut, I choose last”: the agent proposes her best allocation and leaves all the other ones choose one share before taking the remaining one.^[1] MFS-fairness can also be described as the result of the following negotiation process. A certain allocation is suggested. Each agent can object to it by suggesting an alternative partition of the items. However, in doing so he must let all other agents chose their share before he does. Hence, an agent would object to an allocation only if he can suggest a partition in which all bundles are better than his current bundle. An allocation is MFS-fair iff no agent objects to it, i.e, for every agent, in every partition there exists a bundle which is weakly worse than his current share.

2. Proportional fair-share (PFS): The proportional-fair-share of an agent is 1/n of his utility from the entire set of items. An allocation is called proportional if every agent receives a bundle worth at least his proportional-fair-share.

3. Min-max fair-share (mFS): The min-max fair-share of an agent is the minimal utility that she can hope to get from an allocation if all the other agents have the same preferences as her, when she always receives the best share. It is also the minimal utility that an agent can get for sure in the allocation game “Someone cuts, I choose first”. An allocation is mFS-fair if all agents receive a bundle that they weakly prefer over their mFS.^[1] mFS-fairness can be described as the result of the following negotiation process. A certain allocation is suggested. Each agent can object to it by demanding that a different allocation be made by another agent, letting him choose first. Hence, an agent would object to an allocation only if in all partitions, there is a bundle that he strongly prefers over his current bundle. An allocation is mFS-fair iff no agent objects to it, i.e, for every agent there exists a partition in which all bundles are weakly worse than his current share.

For every agent with subadditive utility, the mFS is worth at least $1/n$. Hence, every mFS-fair allocation is proportional. For every agent with superadditive utility, the MFS is worth at most $1/n$. Hence, every proportional allocation is MFS-fair. Both inclusions are strict, even when every agent has additive utility. This is illustrated in the following example:^[1]

There are 3 agents and 3 items:

• Alice values the items as 2,2,2. For her, MFS=PFS=mFS=2.
• Bob values the items as 3,2,1. For him, MFS=1, PFS=2 and mFS=3.
• Carl values the items as 3,2,1. For him, MFS=1, PFS=2 and mFS=3.

The possible allocations are as follows:

• Every allocation which gives an item to each agent is MFS-fair.
• Every allocation which gives the first and second items to Bob and Carl and the third item to Alice is proportional.
• No allocation is mFS-fair.

The above implications do not hold when the agents' valuations are not sub/superadditive.^[3]

4. Envy-freeness (EF): An allocation is envy-free if every agent weakly prefers his own bundle to any other bundle. Every envy-free allocation is mFS-fair; this follows directly from the ordinal definitions and does not depend on additivity. If the valuations are additive, then an EF allocation is also proportional and MFS-fair. Otherwise, an EF allocation may be not proportional and even not MFS.^[3]

5. Competitive equilibrium from Equal Incomes (CEEI): This criterion is based on the following argument: the allocation process should be considered as a search for an equilibrium between the supply (the set of objects, each one having a public price) and the demand (the agents’ desires, each agent having the same budget for buying the objects). A competitive equilibrium is reached when the supply matches the demand. The fairness argument is straightforward: prices and budgets are the same for everyone. CEEI implies EF with regardless of additivity. When the agents' preferences are additive and strict (each bundle has a different value), CEEI implies Pareto-efficiency.^[1]

Max-min-share fairness

The problem of calculating the MFS of an agent is NP-complete: it can be reduced from the partition problem.^[1]

MFS allocations exist in almost all cases, but not always. There are very rare cases in which they do not exist.^[4]

The problem of deciding whether an MFS allocation exists is in $NP^{NP}$, i.e, it can be solved in nonderetministic-polynomial time using an oracle to an NP problem (the oracle is needed to calculate the max-min-share of an agent). However, the exact computational complexity of this problem is still unknown.^[1]

Allocations that guarantee each partner 2/3 of the above value always exist.^[4] This division procedure have been implemented in the spliddit website.^[5]

Proportionality

The problem of deciding whether a proportional allocation exists is NP-complete: it can be reduced from the partition problem.^[1]

Min-max-share fairness

The problem of calculating the mFS of an agent is coNP-complete.

The problem of deciding whether an MFS allocation exists is in $NP^{NP}$, but its exact computational complexity is still unknown.^[1]

Envy-freeness (without money)

The problem of deciding whether an envy-free allocation exists is NP-complete.^[6]

The problem of deciding whether an envy-free and Pareto-efficient allocation exists is ΣP2-complete.^[7]

Envy-freeness (with money)

Demange, Gale and Sotomayor showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand bidders (where each bidder is interested in at most one item).^[8]

Fair by Design is a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item assignments using monetary payments.^[9]

The ordinal model

Two partners, envy-free allocation

Suppose there are two partners, Alice and George, whose valuations are ordinal. I.e, each partner can order the items from the most preferred to the least preferred (without ties).

An item assignment is called envy-free for Alice if there is an injection f from George's items to Alice's items, such that for each item x received by George, Alice prefers f(x) to x. The property envy-free for George is defined analogously. An item assignment is called envy-free (EF) if it is envy-free for both partners. Note that in an EF assignment, Alice and George receive the same number of items.

The following division procedure can be used to find an EF allocation:^[10]

• Put all items on the table.
• While there are items on the table, do:
  • Ask the partners to choose their favorite item from all items on the table.
  • If the choices are different, then give each partner his/her favorite item and continue.
  • If the choices are identical, then move the chosen item to the Contested Pile. It will not be allocated.

This procedure, while very simple, is not very efficient, since many items are discarded to the contested pile. A slightly more complicated procedure ^[11] finds an EF allocation which is also Pareto efficient (PE), i.e., there is no other EF allocation which is weakly better for both partners. The idea is that, before moving an item to the contested pile, the procedure tries to allocate it to one partner while compensating the other partner with another item. Only if this doesn't succeed, the item is sent to the contested pile.

For example, suppose there are 4 items (1, 2, 3, 4) and the preferences of the partners are:

• Alice: 1 > 2 > 3 > 4
• George: 2 > 3 > 4 > 1

The first procedure gives 1 to Alice and 2 to George, since these are their favorites and they are different. Then, both Alice and George choose 3 so it is discarded. Then, both choose 4 so it is also discarded. The final allocation is: Alice←{1}, George←{2}. It is EF but not PE.

The second procedure also starts by giving 1 to Alice and 2 to George. Then, instead of discarding item 3, it is given to Alice, and George is compensated with item 4. The final allocation is: Alice←{1,3}, George←{2,4}. It is EF and PE.

Both procedures are manipulable: a partner can gain by reporting incorrect preferences. However, such manipulation requires knowledge of the other partner's preferences, so it is difficult in practice.

Empirical evidence

Several experiments have been conducted with people, in order to find out what is the relative importance of several division criteria. In particular, what is the importance of fairness versus efficiency? Do people prefer divisions which are fair but inefficient, or efficient but unfair?

In one experiment,^[12] subjects were asked to answer questionnaires regarding the division of indivisible items between two people. The subjects were shown the subjective value that each (virtual) person attaches to each item. The predominant aspect considered was equity - satisfying each individual's preferences. The efficiency aspect was secondary. This effect was slightly more pronounced in economics students, and less pronounced in law students (who chose a Pareto-efficient allocation more frequently).

In another experiment,^[13] subjects were divided into pairs and asked to negotiate and decide how to divide a set of 4 items between them. Each combination of items had a pre-specified monetary value, which was different between the two subjects. Each subject knew both his own values and the partner's values. After the division, each subject could redeem the items for their monetary value.

The items could be divided in several ways: some divisions were equitable (e.g., giving each partner a value of 45), while other divisions were Pareto efficient (e.g., giving one partner 46 and another partner 75). The interesting question was whether people prefer the equitable or the efficient division. The results showed that people preferred the more efficient division, but only as long as it was not "too much" unfair. A difference of 2-3 units of value was considered sufficiently small for most subjects, so they preferred the efficient allocation. But a difference of 20-30 units (such as in the 45:45 vs. 46:75 example) was perceived as too large: 51% preferred the 45:45 division.

The effect were less pronounced when the subjects were only shown the rank of the item combinations for each of them, rather than the full monetary value.

This experiment also revealed a recurring process which was used during the negotiation. The subjects first find the most equitable division of the goods. They take this as a reference point, and try to find Pareto improvements. An improvement is implemented only if the inequality it causes is not too large. Hence the authors call this process CPIES: Conditioned Pareto Improvement from Equal Split.

See also

• Rental harmony - a fair division problem where indivisible items and a fixed total cost have to be divided simultaneously.

References

1. Bouveret, Sylvain; Lemaître, Michel (2015). "Characterizing conflicts in fair division of indivisible goods using a scale of criteria". Autonomous Agents and Multi-Agent Systems. doi:10.1007/s10458-015-9287-3.
2. Budish, E. (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy 119 (6): 1061. doi:10.1086/664613.
3. Heinen, Tobias; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Algorithmic Decision Theory". Lecture Notes in Computer Science 9346: 521. doi:10.1007/978-3-319-23114-3_31. ISBN 978-3-319-23113-6. |chapter= ignored (help)
4. Procaccia AD, Wang J (2014). "Fair enough: guaranteeing approximate maximin shares". EC '14 Proceedings of the fifteenth ACM conference on Economics and computation: 675–692. doi:10.1145/2600057.2602835. ISBN 9781450325653.
5. http://www.spliddit.org/apps/goods
6. Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Proceedings of the 5th ACM conference on Electronic commerce - EC '04": 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0. |chapter= ignored (help)
7. De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Algorithmic Decision Theory". Lecture Notes in Computer Science 5783: 98. doi:10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4. |chapter= ignored (help)
8. Demange G, Gale D, Sotomayor M (1986). "Multi-Item Auctions". ournal of Political Economy 94: 863–872.
9. Mu'alem A (2014). "Fair by design: Multidimensional envy-free mechanisms". Games and Economic Behavior 88: 29–46. doi:10.1016/j.geb.2014.08.001.
10. Taylor SJ, Brams AD (2000). The win-win solution: guaranteeing fair shares to everybody (1st ed.). New York: W.W. Norton. ISBN 978-0393320817.
11. Brams SJ, Kilgour DM, Klamler C (1 February 2014). "Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm". Notices of the American Mathematical Society 61 (2): 130. doi:10.1090/noti1075.
12. Herreiner, Dorothea and Puppe, Clemens. "Distributing Indivisible Goods Fairly: Evidence from a Questionnaire Study". Loyola Marimount University - Economics Faculty Works.
13. Herreiner DK, Puppe C (November 2010). "Inequality aversion and efficiency with ordinal and cardinal social preferences—An experimental study". Journal of Economic Behavior & Organization 76 (2): 238–253. doi:10.1016/j.jebo.2010.06.002.