Entitlement (fair division)

Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:

• In partnership resolution settings, each partner is entitled to a fraction of the common assets in proportion to his/her investment in the partnership.
• In inheritance settings, the law in some jurisdictions prescribes a different share to each heir according to his/her proximity to the deceased person. For example, according to the Bible, the firstborn son must receive twice as much as every other son. In contrast, according to the Italian law, when there are three heirs - parent, brother and spouse - they are entitled to 1/4, 1/12 and 2/3 respectively.^[1]
• In parliamentary democracies, each party is entitled to a number of seats in the parliament that is, in general, proportional to the number of votes it received.

The idea is based on the normal idea of entitlement. Entitlements can be determined by agreeing on a cooperative game and using its value as the entitlement.

When agents have equal entitlements, it is reasonable to require that the solution satisfies the axiom of anonymity (also called: symmetry), that is, agents are treated only by their valuations and not by their names. In contrast, when agents have different entitlements, anonymity is no longer valid, and the solutions must be asymmetric.

Various problems of fair division with different entitlements have been studied.

Dividing money

Even when only money is to be divided and some fixed amount has been specified for each recipient, the problem can be complex. The amounts specified may be more or less than the amount of money, and the profit or loss will then need to be shared out. The proportional rule is normally used in law nowadays, and is the default assumption in the theory of bankruptcy. Other rules however are often used, for example:

• The Shapley value is one common method of deciding bargaining power as can be seen in the airport problem. In economics an allocation which cannot be improved upon by any coalition is said to have the core property.
• Welfare economics on the other hand tries to determine allocations depending on fairness criteria.
• The people can also agree on their relative entitlements by a consensus process. For instance they could say what they think everyone else is entitled to and if the assessments agree then they have an agreed impartial consensus division.^[2]
• Priority rules are another kind of mechanism for allocation with different entitlements.^[3]

In the Talmud

The Talmud has a number of examples where entitlements are not decided on a proportional basis.

• The disputed garment problem. If one person claims the whole of a cloth and another half then it is divided 3/4 and 1/4.^[4]
• The estate division problem. Three wives have claims to 100, 200 and 300 zuz. Three cases are considered, if the estate is 100 zuz then they get 33 and a third each, if 200 then 50, 75, 75, and if 300 then 50, 100 and 150.^[5]
• Profits from a joint fund. If two people put 200 and 100 into a fund and buy an ox for ploughing and use it for that purpose they divide the profit evenly between them. But if they instead then slaughter the ox they divide the profit in proportion. This is discussed in the Babylonian Talmud just after the estate division problem.
• Ibn Ezra's problem. This is a later problem of estate division that was solved in a different way. A man with an estate of 120 dies bequeathing 120, 60, 40 and 30 to his four sons. The recommendation was to award (120-60)/1+(60-40)/2+(40-30)/3+(30-0)/4 to the first and sums with leading terms removed for the rest ending with 30/4 for the last. This allocation is different from the previous estate division

These solutions can all be modeled by cooperative games. The estate division problem has a large literature and was first given a theoretical basis in game theory by Robert J. Aumann and Michael Maschler in 1985.^[6] See Contested garment rule.

Dividing continuous resources

Fair cake-cutting is the problem of dividing a heterogeneous continuous resource. There always exists a proportional cake-cutting respecting the different entitlements. The two main research questions are (a) how many cuts are required for a fair division? (b) how many queries are needed for computing a division? See:

• Proportional cake-cutting with different entitlements.
• Envy-free cake-cutting with different entitlements.

Cloud computing environments require to divide multiple homogeneous divisible resources (e.g. memory or CPU) between users, where each user needs a different combination of resources.^[7] The setting in which agents may have different entitlements has been studied by ^[8] and.^[9]

Fair item allocation

Identical indivisible items - dividing seats in parliaments

In parliamentary democracies with proportional representation, each party is entitled to seats in proportion to its number of votes. In multi-constituency systems, each constituency is entitled to seats in proportion to its population. This is a problem of dividing identical indivisible items (the seats) among agents with different entitlements. It is called the apportionment problem.

The allocation of seats by size of population can leave small constituencies with no voice at all. The easiest solution is to have constituencies of equal size. Sometimes, however, this can prove impossible – for instance, in the European Union or United States. Ensuring the 'voting power' is proportional to the size of constituencies is a problem of entitlement.

There are a number of methods which compute a voting power for different sized or weighted constituencies. The main ones are the Shapley–Shubik power index, the Banzhaf power index. These power indexes assume the constituencies can join up in any random way and approximate to the square root of the weighting as given by the Penrose method. This assumption does not correspond to actual practice and it is arguable that larger constituencies are unfairly treated by them.

Heterogeneous indivisible items

In the more complex setting of fair item allocation, there are multiple different items with possibly different values to different people.

Aziz, Gaspers, Mackenzie and Walsh^{[10]: sec.7.2} define proportionality and envy-freeness for agents with different entitlements, when the agents reveal only an ordinal ranking on the items, rather than their complete utility functions. They present a polynomial-time algorithm for checking whether there exists an allocation that is possibly proportional (proportional according to at least one utility profile consistent with the agent rankings), or necessarily proportional (proportional according to all utility profiles consistent with the rankings).

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin, Seddighin and Yami^[11] defined the Weighted Maximin Share (WMMS) as a generalization of the maximin share to agents with different entitlements. They showed that the best attainable multiplicative guarantee for the WMMS is 1/n in general, and 1/2 in the special case in which the value of each good to every agent is at most the agent's WMMS. Aziz, Chan and Li^[12] adapted the notion of WMMS to chores (items with negative utilities). They showed that, even for two agents, it is impossible to guarantee more than 4/3 of the WMMS (Note that with chores, the approximation ratios are larger than 1, and smaller is better). They present a 3/2-WMMS approximation algorithm for two agents, and an WMMS algorithm for n agents with binary valuations. They also define the OWMMS, which is the optimal approximation of WMMS that is attainable in the given instance. They present a polynomial-time algorithm that attains a 4-factor approximation of the OWMMS.

The WMMS is a cardinal notion in that, if the cardinal utilities of an agent changes, then the set of bundles that satisfy the WMMS for the agent may change. Babaioff, Nisan and Talgam-Cohen^[13] introduced another adaptation of the MMS to agents with different entitlements, which is based only on the agent's ordinal ranking of the bundles. They show that this fairness notion is attained by a competitive equilibrium with different budgets, where the budgets are proportional to the entitlements. This fairness notion is called Ordinal Maximin Share (OMMS) by Chakraborty, Segal-Halevi and Suksompong.^[14] The relation between various ordinal MMS approximations is further studied by Segal-Halevi.^[15][16]

Babaioff, Ezra and Feige^[17] present another ordinal notion, stronger than OMMS, which they call the AnyPrice Share (APS). They show a polynomial-time algorithm that attains a 3/5-fraction of the APS.

Aziz, Moulin and Sandomirskiy^[18] present a strongly polynomial time algorithm that always finds a Pareto-optimal and WPROP(0,1) allocation for agents with different entitlements and arbitrary (positive or negative) valuations.

Relaxations of WEF have been studied, so far, only for goods. Chakraborty, Igarashi and Suksompong^[19] introduced the weighted round-robin algorithm for WEF(1,0). In a follow-up work, Chakraborty, Schmidt-Kraepelin and Suksompong generalized the weighted round-robin algorithm to general picking-sequences, and studied various monotonicity properties of these sequences.

Items and money

In the problem of fair allocation of items and money, monetary transfers can be used to attain exact fairness of indivisible goods.

Corradi and Corradi^[20] define an allocation as equitable if the utility of each agent i (defined as the value of items plus the money given to i) is r t_i u_i (AllItems), where r is the same for all agents.

They present an algorithm that finds an equitable allocation with r >= 1, which means that the allocation is also proportional.

Bargaining

Cooperative bargaining is the abstract problem of selecting a feasible vector of utilities, as a function of the set of feasible utility vectors (fair division is a special case of bargaining).

Three classic bargaining solutions have variants for agents with different entitlements. In particular:

• Kalai^[21] extended the Nash bargaining solution by introducing the max weighted Nash welfare rule;
• Thomson^[22] extended the Kalai-Smorodinsky bargaining solution;
• Driesen^[23] extended the leximin rule by introducing the asymmetric leximin rule.

References

1. Corradi, Marco Claudio; Corradi, Valentina (2001-04-21). "The Adjusted Knaster Procedure Under Unequal Entitlements". SSRN 2427304.
2. Geoffroy de Clippel; HerveMoulin; Nicolaus Tideman (March 2008), "Impartial division of a dollar", Journal of Economic Theory, 139 (1): 176–191, CiteSeerX 10.1.1.397.1420, doi:10.1016/j.jet.2007.06.005
3. Moulin, Herve (May 2000). "Priority Rules and Other Asymmetric Rationing Methods". Econometrica. 68 (3): 643–684. doi:10.1111/1468-0262.00126. ISSN 0012-9682.
4. Bava Metzia 2a. The disputed garment
5. Ketubot 93a. The estate division problem
6. Robert J. Aumann and Michael Maschler. Journal of Economic Theory 36, 195-213 (1985)
7. "Dominant Resource Fairness: Fair Allocation of Multiple Resource Types". 2011.
8. Dolev, Danny; Feitelson, Dror G.; Halpern, Joseph Y.; Kupferman, Raz; Linial, Nathan (2012-01-08). "No justified complaints". Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ITCS '12. New York, NY, USA: Association for Computing Machinery. pp. 68–75. doi:10.1145/2090236.2090243. ISBN 978-1-4503-1115-1. S2CID 9105218.
9. Gutman, Avital; Nisan, Noam (2012-04-19). "Fair Allocation Without Trade". arXiv:1204.4286 [cs.GT].
10. Aziz, Haris; Gaspers, Serge; Mackenzie, Simon; Walsh, Toby (2015-10-01). "Fair assignment of indivisible objects under ordinal preferences". Artificial Intelligence. 227: 71–92. arXiv:1312.6546. doi:10.1016/j.artint.2015.06.002. ISSN 0004-3702. S2CID 1408197.
11. Farhadi, Alireza; Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Lahaie, Sébastien; Pennock, David; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2019-01-07). "Fair Allocation of Indivisible Goods to Asymmetric Agents". Journal of Artificial Intelligence Research. 64: 1–20. arXiv:1703.01649. doi:10.1613/jair.1.11291. ISSN 1076-9757. S2CID 15326855.
12. Aziz, Haris; Chan, Hau; Li, Bo (2019-06-18). "Weighted Maxmin Fair Share Allocation of Indivisible Chores". arXiv:1906.07602 [cs.GT].
13. Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2021-02-01). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". Mathematics of Operations Research. 46 (1): 382–403. arXiv:1703.08150. doi:10.1287/moor.2020.1062. ISSN 0364-765X. S2CID 8514018.
14. Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (2021-12-08). "Weighted Fairness Notions for Indivisible Items Revisited". Proceedings of AAAI 2022. arXiv:2112.04166.
15. Segal-Halevi, Erel (2020-02-20). "Competitive equilibrium for almost all incomes: existence and fairness". Autonomous Agents and Multi-Agent Systems. 34 (1): 26. arXiv:1705.04212. doi:10.1007/s10458-020-09444-z. ISSN 1573-7454. S2CID 210911501.
16. Segal-Halevi, Erel (2019-12-18). "The Maximin Share Dominance Relation". arXiv:1912.08763 [math.CO].
17. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-11-15). "Fair-Share Allocations for Agents with Arbitrary Entitlements". arXiv:2103.04304 [cs.GT].
18. Aziz, Haris; Moulin, Hervé; Sandomirskiy, Fedor (2020-09-01). "A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation". Operations Research Letters. 48 (5): 573–578. arXiv:1909.00740. doi:10.1016/j.orl.2020.07.005. ISSN 0167-6377. S2CID 202541717.
19. Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (2021-08-16). "Weighted Envy-freeness in Indivisible Item Allocation". ACM Transactions on Economics and Computation. 9 (3): 18:1–39. arXiv:1909.10502. doi:10.1145/3457166. ISSN 2167-8375. S2CID 202719373.
20. Corradi, Marco Claudio; Corradi, Valentina (2001-04-21). "The Adjusted Knaster Procedure Under Unequal Entitlements". SSRN 2427304.
21. Kalai, E. (1977-09-01). "Nonsymmetric Nash solutions and replications of 2-person bargaining". International Journal of Game Theory. 6 (3): 129–133. doi:10.1007/BF01774658. ISSN 1432-1270. S2CID 122236229.
22. Thomson, William (1994), "Cooperative models of bargaining", Handbook of Game Theory with Economic Applications, 2, Elsevier: 1237–1284, doi:10.1016/S1574-0005(05)80067-0, retrieved 2022-03-29
23. Driesen, Bram W. (2012). The Asymmetric Leximin Solution (Report). doi:10.11588/heidok.00013124.