Proportional item allocation

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.[1]^:296–297

Since the items are indivisible, a proportional assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will have a value of 0, which is less than 1/2. Therefore, the literature considers various relaxations of the proportionality requirement.

Proportional allocation

An allocation of objects is called proportional (PROP) if every agent i values his bundle at least 1/n of the total. Formally, for all i (where M is the set of all goods):

• ${\displaystyle V_{i}(X_{i})\geq V_{i}(M)/n}$.

A proportional division may not exist. For example, if the number of people is larger than the number of items, then some people will get no item at all and their value will be zero. Nevertheless, such a division exists with high probability for indivisible items under certain assumptions on the valuations of the agents.[2]

Deciding whether a PROP allocation exists

1. Suppose the agents have cardinal utility functions on items. Then, the problem of deciding whether a proportional allocation exists is NP-complete: it can be reduced from the partition problem.[3]

2. Suppose the agents have ordinal rankings on items, with or without indifferences. Then, the problem of deciding whether a necessarily-proportional allocation exists can be solved in polynomial time: it can be reduced to the problem of checking whether a bipartite graph admits a feasible b-matching (a matching when the edges have capacities).[4]

For two agents, a simpler algorithm exists.[5]

3. Suppose the agents have ordinal rankings on items, without indifferences. Then, the problem of deciding whether a necessarily-proportional allocation exists can be solved in polynomial time. It is not known whether the same is true when the agents are allowed to express indifferences.[4]

Relation to other fairness criteria

With additive valuations:

• Every envy-free item allocation is also proportional. The opposite implication is true when n=2, but not when n>2.
• Every proportional allocation satisfies the maximin share. The opposite implication is not true.

PROP1 allocations

An allocation is called proportional up to the best c items (PROPc) if for every agent i, there exists a subset of at most c items that, if given to i, brings the total value of i to at least 1/n of the total. Formally, for all i (where M is the set of all goods):[6]

• ${\displaystyle \exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq c,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$.

An equivalent definition is: the value of each agent i is at least (1/n of the total) minus (the most valuable c items not assigned to i):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{Y\subseteq M\setminus X_{i},|Y|\leq c}V_{i}(Y)}$

PROP0 is equivalent to proportionality, which might not exist. In contrast, a PROP1 allocation always exists and can be found e.g. by round-robin item allocation. The interesting question is how to combine it with efficiency conditions such as Pareto efficiency (PE).

Finding efficient PROP1 allocations

Conitzer, Freeman and Shah[6] proved that, in the context of fair public decision making, a PROP1 allocation that is also PE.

Barman and Krishnamurthy[7] presented a strongy-polynomial-time algorithm finding a PE+PROP1 allocation for goods (objects with positive utility).

Branzei and Sandomirskiy[8] extended the condition of PROP1 to chores (objects with negative utility). Formally, for all i:

• ${\displaystyle \exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n}$.

They presented an algorithm finding a PE+PROP1 allocation of chores. The algorithm is strongly-polynomial-time if either the number of objects or the number of agents (or both) are fixed.

Aziz, Caragiannis, Igarashi and Walsh[9] extended the condition of PROP1 to mixed valuations (objects can have both positive and negative utilities). In this setting, an allocation is called PROP1 if, for each agent i, if we remove one negative item from i's bundle, or add one positive item to i's bundle, then i's utility is at least 1/n of the total. Their Generalized Adjusted Winner algorithm finds a PE+EF1 allocation for two agents; such an allocation is also PROP1.

Aziz, Moulin and Sandomirskiy[10] presented a strongly-polynomial-time algorithm for finding an allocation that is fractionally-PE (stronger than PE) and PROP1, with general mixed valuations, even if the number of agents or objects is not fixed, and even if the agents have different entitlements.

Relation to other fairness criteria

With additive valuations:

• Every EF1 allocation is also PROP1, but the opposite is not necessarily true even with two agents.[11]^:App.A
• The same is true for any c ≥ 1: Every EFc allocation is also PROPc, but the opposite is not necessarily true even with two agents.

PROP*(n-1) allocations

An allocation is called proportional from all except c items (PROP*c) for an agent i if there exists a set of at most c items that, if removed from the set of all items, then i values his bundle at least 1/n of the remainder. Formally, for all i:[12]

• ${\displaystyle \exists Y\subseteq M:~~~|Y|\leq c,~~~V_{i}(X_{i})\geq V_{i}(M\setminus Y)/n}$.

PROP*(n-1) is slightly stronger than PROP1: when n=2, PROP*(n-1) is equivalent to EF1, but PROP1 is weaker. A PROP*(n-1) allocation always exists and can be found e.g. by round-robin item allocation.

Relation to other fairness criteria

With additive valuations:

• EF1 implies PROP*(n-1). The opposite implication is true when n=2, but not when n>2. Thus, the relation between EF1 and PROP*(n-1) is analogous to the relation between envy-freeness and proportionality, which shows that PROP*(n-1) is a more natural relaxation of proportionality than PROP1.
• Moreover, for any integer c ≥ 0, EFc implies PROP*((n-1)c). The opposite implication is true when n=2, but not when n>2.[12]^:Lem.2.3

The following maximin-share approximations are implied by PROP*(n-1):[12]^:Lem.2.7

• Multiplicative approximation: 1/n-fraction MMS (the 1/n is tight);[12]^:Prop.3.6
• Ordinal approximation: 1-of-(2n-1) MMS (the 2n-1 is tight). Similarly, for every integer c, PROP*c implies 1-of-(c+n) MMS.
• MMS when the value function is binary. The opposite implication holds too.

PROPx allocations

An allocation is called proportional up to the worst item (PROPx) if for every agent i, for any subset with at most one item not allocated to i, if the subset is given to i, then it brings his value to at least 1/n of the total. Formally, for all i:[13]

• ${\displaystyle \forall Y\subseteq M\setminus X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$

An equivalent definition is: the value of each agent i is at least (1/n of the total) minus (the least valuable item not assigned to i):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\min _{Y\subseteq M\setminus X_{i},|Y|=1}V_{i}(Y)}$

Obviously, PROPx is stronger than PROP1. Moreover, while PROP1 allocations always exist, PROPx allocations may not exist.[13][10]

PROPm allocations

An allocation is called proportional up to the maximin item (PROPm) if the value of each agent i is at least (1/n of the total) minus (the maximin item not assigned to i), where the maximin item the maximum over all the other n-1 agents j, of the least-valuable item allocated to j. Formally:[14]

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{j\neq i}\min _{Y\subseteq X_{j},|Y|=1}V_{i}(Y)}$

Obviously, PROPx is stronger than PROPm, which is stronger than PROP1. A PROPm allocation exists when the number of agents is at most 5.[14]

References

1. 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)
2. Suksompong, Warut (2016). "Asymptotic existence of proportionally fair allocations". Mathematical Social Sciences. 81: 62–65. arXiv:1806.00218. doi:10.1016/j.mathsocsci.2016.03.007.
3. 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.
4. Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Fair assignment of indivisible objects under ordinal preferences". Artificial Intelligence. 227: 71–92. arXiv:1312.6546. doi:10.1016/j.artint.2015.06.002.
5. Pruhs, Kirk; Woeginger, Gerhard J. (2012). "Divorcing Made Easy". Fun with Algorithms. Lecture Notes in Computer Science. 7288. p. 305. doi:10.1007/978-3-642-30347-0_30. ISBN 978-3-642-30346-3.
6. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). "Fair Public Decision Making | Proceedings of the 2017 ACM Conference on Economics and Computation". arXiv:1611.04034. doi:10.1145/3033274.3085125. S2CID 30188911. Cite journal requires |journal= (help)
7. Barman, Siddharth; Krishnamurthy, Sanath Kumar (2019-07-17). "On the Proximity of Markets with Integral Equilibria". Proceedings of the AAAI Conference on Artificial Intelligence. 33 (1): 1748–1755. doi:10.1609/aaai.v33i01.33011748. ISSN 2374-3468. S2CID 53793188.
8. Brânzei, Simina; Sandomirskiy, Fedor (2019-07-03). "Algorithms for Competitive Division of Chores". arXiv:1907.01766 [cs.GT].
9. Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (2018-12-11). "Fair allocation of combinations of indivisible goods and chores". arXiv:1807.10684 [cs.GT].
10. Aziz, Haris; Moulin, Herve; Sandomirskiy, Fedor (2019-09-02). "A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation". arXiv:1909.00740 [cs.GT].
11. Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2020-12-07). "Computing Fair Utilitarian Allocations of Indivisible Goods". arXiv:2012.03979 [cs].
12. Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Democratic fair allocation of indivisible goods". Artificial Intelligence. 277: 103167. arXiv:1709.02564. doi:10.1016/j.artint.2019.103167. ISSN 0004-3702. S2CID 203034477.
13. Moulin, Hervé (2019-08-02). "Fair Division in the Internet Age". Annual Review of Economics. 11 (1): 407–441. doi:10.1146/annurev-economics-080218-025559. ISSN 1941-1383.
14. Baklanov, Artem; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel (2021-01-14). "Achieving Proportionality up to the Maximin Item with Indivisible Goods". arXiv:2009.09508 [cs].