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, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings.
Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses.

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. This is in contrast to the fair cake-cutting problem, where the dividend is divisible and a fair division always exists. In some cases, the indivisibility problem can be mitigated by introducing monetary payments or time-based rotation, or by discarding some of the items.^[1]^:285 But such solutions are not always available.

An item assignment problem has several ingredients:

The partners have to express their preferences for the different item-bundles.
The group should decide on a fairness criterion.
Based on the preferences and the fairness criterion, a fair assignment algorithm should be executed to calculate a fair division.

These ingredients are explained in detail below.

Preferences

Combinatorial preferences

A naive way to determine the preferences is asking each partner to supply a numeric value for each possible bundle. For example, if the items to divide are a car and a bicycle, a partner may value the car as 800, the bicycle as 200, and the bundle {car,bicycle} as 900 (see Utility functions on indivisible goods for more examples). There are two problems with this approach:

It may be difficult for a person to calculate exact numeric values to the bundles.
The number of possible bundles can be huge: if there are $m$ items then there are $2^{m}$ possible bundles. For example, if there are 16 items then each partner will have to present his preferences using 65536 numbers.

The first problem motivates the use of ordinal utility rather than cardinal utility. In the ordinal model, each partner should only express a ranking over the $2^{m}$ different bundles, i.e, say which bundle is the best, which is the second-best, and so on. This may be easier than calculating exact numbers, but it is still difficult if the number of items is large.

The second problem is often handled by working with individual items rather than bundles:

In the cardinal approach, each partner should report a numeric valuation for each item;
In the ordinal approach, each partner should report a ranking over the items, i.e, say which item is the best, which is the second-best, etc.

Under suitable assumptions, it is possible to lift the preferences on items to preferences on bundles. ^[2]^:44-48 Then, the agents report their valuations/rankings on individual items, and the algorithm calculates for them their valuations/rankings on bundles.

Additive preferences

To make the item-assignment problem simpler, it is common to assume that all items are independent goods (so they are not substitute goods nor complementary goods). ^[3] Then:

In the cardinal approach, each agent has an additive utility function (also called: modular utility function). Once the agent reports a value for each individual item, it is easy to calculate the value of each bundle by summing up the values of its items.
In the ordinal approach, additivity allows us to infer some rankings between bundles. For example, if a person prefers w to x to y to z, then he necessarily prefers {w,x} to {w,y} or to {x,y}, and {w,y} to {x}. This inference is only partial, e.g, we cannot know whether the agent prefers {w} to {x,y} or even {w,z} to {x,y}.^[4]^[5]

The additivity implies that each partner can always choose a "preferable item" from the set of items on the table, and this choice is independent of the other items that the partner may have. This property is used by some fair assignment algorithms that will be described next.^[1]^:287–288

Compact preference representation languages

Compact preference representation languages have been developed as a compromise between the full expressiveness of combinatorial preferences to the simplicity of additive preferences. They provide a succinct representation to some natural classes of utility functions that are more general than additive utilities (but not as general as combinatorial utilities). Some examples are:^[1]^:289–294

2-additive preferences: each partner reports a value for each bundle of size at most 2. The value of a bundle is calculated by summing the values for the individual items in the bundle and adding the values of pairs in the bundle. Typically, when there are substitute items, the values of pairs will be negative, and when there are complementary items, the values of pairs will be positive. This idea can be generalized to k-additive preferences for every positive integer k.
Graphical models: for each partner, there is a graph that represents the dependencies between different items. In the cardinal approach, a common tool is the GAI net (Generalized Additive Independence). In the ordinal approach, a common tool is the CP net (Conditional Preferences) and its extensions: TCP net, UCP net, CP theory, CI net (Conditional Importance) and SCI net (a simplification of CI net).
Logic based languages: each partner describes some bundles using a first order logic formula, and may assign a value for each formula. For example, a partner may say: "For (x or (y and z)), my value is 5". This means that the agent has a value of 5 for any of the bundles: x, xy, xz, yz, xyz.
Bidding languages: many languages for representing combinatorial preferences have been studied in the context of combinatorial auctions. Some of these languages can be adapted to the item assignment setting.

Fairness criteria

Individual guarantee criteria

An individual guarantee criterion is a criterion that should hold for each individual partner, as long as the partner truthfully reports his preferences. Five such criteria are presented below. They are ordered from the weakest to the strongest (assuming the valuations are additive):^[6]

1. Max-min fair-share (MFS): The max-min-fair-share (also called: max-min-share-guarantee) 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.^[7] 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.^[6] 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.^[6] 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:^[6]

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

4. Envy-freeness (EF): every agent weakly prefers his own bundle to any other bundle. Every envy-free allocation of all items 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.^[8] See envy-free item assignment for more details.

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 regardless of additivity. When the agents' preferences are additive and strict (each bundle has a different value), CEEI implies Pareto efficiency.^[6]

Several recently-suggested fairness criteria are:^[9]

6. Envy-freeness-except-1 (EF1): For each two agents A and B, if we remove from the bundle of B the item most valuable for A, then A does not envy B (in other words, the "envy level" of A in B is at most the value of a single item). Under additivity, an EF1 allocation always exists.

7. Envy-freeness-except-cheapest (EFx): For each two agents A and B, if we remove from the bundle of B the item least valuable for A, then A does not envy B. EFx is strictly stronger than EF1. It is not known whether EFx allocations always exist.

Global optimization criteria

A global optimization criterion evaluates a division based on a given social welfare function:

The egalitarian social welfare is minimum utility of a single agent. An item assignment is called egalitarian-optimal if it attains the maximum possible egalitarian welfare, i.e, it maximizes the utility of the poorest agent. Since there can be several different allocations maximizing the smallest utility, egalitarian optimality is often refined to leximin-optimality: from the subset of allocations maximizing the smallest utility, it selects those allocations that maximize the second-smallest utility, then the third-smallest utility, and so on.
The Nash social welfare is the product of the utilities of the agents. An assignment called Nash-optimal or Maximum-Nash-Welfare if it maximizes the product of utilities. Nash-optimal allocations have some nice fairness properties.^[9]

An advantage of global optimization criteria over individual criteria is that welfare-maximizing allocations are Pareto efficient.

Assignment algorithms

Max-min-share fairness

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

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

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.^[6]

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

Proportionality

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

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.^[6]

Envy-freeness (without money)

Main article: envy-free item assignment

Envy-freeness (with money)

Envy-freeness becomes easier to attain when it is assumed that agents' valuations are quasilinear in money, and thus transferable across agents.

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).^[12]

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

Cavallo^[14] generalizes the traditional binary criteria of envy-freeness, proportionality, and efficiency (welfare) to measures of degree that range between 0 and 1. In the canonical fair division settings, under any allocatively-efficient mechanism the worst-case welfare rate is 0 and disproportionality rate is 1; in other words, the worst-case results are as bad as possible. This strongly motivates an average-case analysis. He looks for a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. He shows that the VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of ^[15] and ^[16] is.

Egalitarian-optimal allocations

With general cardinal valuations, finding egalitarian-optimal allocations, or even approximately-optimal allocations, is NP-hard. This can be proved by reduction from the partition problem. When the valuations are more restricted, better approximations are possible:^[17]

With additive utilities, for every integer $k$ , a $(1-1/k)$ fraction of the agents receive utility at least $OPT/k$ . This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for this linear program.
With two classes of goods, an $O({\sqrt {n}})$ approximation exists.
With submodular utility functions, an $(m-n+1)$ approximation exists.

^[18] and ^[19] present some stronger hardness results.

The special case of optimizing egalitarian welfare with additive utilities is called "the Santa Claus problem". ^[20] The problem is still NP-hard and cannot be approximated within a factor > 1/2, but there is an $O(n)$ approximation^[21] and a more complicated $O({\sqrt {n}}\cdot \log ^{3}{n})$ approximation.^[22] See also ^[23] for a branch-and-bound algorithm for two partners.

The Decreasing Demand procedure returns a egalitarian-optimal division in an ordinal sense: it maximizes the rank, in the linear-ranking of bundles, of the agent with the lowest rank. It works for any number of agents with any ordering of bundles.

Nash-optimal allocations

^[18] and ^[19] prove hardness of calculating utilitarian-optimal and Nash-optimal allocations.

^[24] present an approximation procedure for Nash-optimal allocations.

Picking sequences

Main article: Picking sequence

A picking sequence is a simple protocol where the agents take turns in selecting items, based on some pre-specified sequence of turns. The goal is to design the picking-sequence in a way that maximizes the expected value of a social welfare function (e.g. egalitarian or utilitarian) under some probabilistic assumptions on the agents' valuations.

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,^[25] 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,^[26] 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 ^[27] for another experiment focusing on envy-freeness.

References

1 2 3 Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet, "Fair Allocation of Indivisible Goods". Chapter 12 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)
↑ Barberà, S., Bossert, W., & Pattanaik, P. K. (2004). "Ranking sets of objects.". Handbook of utility theory (PDF). Springer US.
↑ Sylvain Bouveret, Ulle Endriss, Jérôme Lang (2010). Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence. Retrieved 26 August 2016.
↑ Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003). "Fair Division of Indivisible Items". Theory and Decision. 55 (2): 147. doi:10.1023/B:THEO.0000024421.85722.0a.
↑ Brams, S. J. (2005). "Efficient Fair Division: Help the Worst off or Avoid Envy?". Rationality and Society. 17 (4): 387. doi:10.1177/1043463105058317.
1 2 3 4 5 6 7 8 9 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. 30 (2): 259. doi:10.1007/s10458-015-9287-3.
↑ Budish, E. (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061. doi:10.1086/664613.
1 2 Heinen, Tobias; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Fairness and Rank-Weighted Utilitarianism in Resource Allocation". Algorithmic Decision Theory. Lecture Notes in Computer Science. 9346. p. 521. doi:10.1007/978-3-319-23114-3_31. ISBN 978-3-319-23113-6.
1 2 Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare. Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.
1 2 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.
↑ http://www.spliddit.org/apps/goods
↑ Demange G, Gale D, Sotomayor M (1986). "Multi-Item Auctions". Ournal of Political Economy. 94: 863–872. JSTOR 1833206.
↑ 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.
↑ Ruggiero Cavallo (2012). Fairness and Welfare Through Redistribution When Utility is Transferable (PDF). AAAI-12.
↑ Bailey, Martin J. (1997). Public Choice. 91 (2): 107. doi:10.1023/A:1017949922773. Missing or empty |title= (help)
↑ Cavallo, Ruggiero (2006). "Optimal decision-making with minimal waste". Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06. p. 882. doi:10.1145/1160633.1160790. ISBN 1595933034.
↑ Golovin, Daniel (2005). "Max-min fair allocation of indivisible goods". CMU. Retrieved 27 August 2016.
1 2 Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation". Annals of Mathematics and Artificial Intelligence. 68: 65. doi:10.1007/s10472-012-9328-4.
1 2 Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation". Autonomous Agents and Multi-Agent Systems. 28 (2): 256. doi:10.1007/s10458-013-9224-2.
↑ Bansal, Nikhil; Sviridenko, Maxim (2006). "The Santa Claus problem". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. p. 31. doi:10.1145/1132516.1132522. ISBN 1595931341.
↑ Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods". ACM SIGecom Exchanges. 5 (3): 11. doi:10.1145/1120680.1120683.
↑ Asadpour, Arash; Saberi, Amin (2010). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970. doi:10.1137/080723491.
↑ Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly". Mathematical Social Sciences. 54 (3): 218. doi:10.1016/j.mathsocsci.2007.04.008.
↑ Trung Thanh Nguyen and Jörg Rothe (2013). Envy-ratio and average-nash social welfare optimization in multiagent resource allocation. AAMAS 13.
↑ Herreiner, Dorothea; Puppe, Clemens. "Distributing Indivisible Goods Fairly: Evidence from a Questionnaire Study". Loyola Marimount University - Economics Faculty Works.
↑ 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.
↑ Herreiner, Dorothea K.; Puppe, Clemens D. (2007). "Envy Freeness in Experimental Fair Division Problems". Theory and Decision. 67: 65. doi:10.1007/s11238-007-9069-8.

This article is issued from Wikipedia - version of the 11/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.