Entitlement (fair division)

Last updated

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:

Contents

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:

In the Talmud

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

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:

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 rti ui (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:

Related Research Articles

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

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.

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:

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.

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.

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

Combinatorial participatory budgeting,also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

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.

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.

Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.

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.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin 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.

An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in computational social choice.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

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.

Population monotonicity (PM) is a principle of consistency in allocation problems. It says that, when the set of agents participating in the allocation changes, the utility of all agents should change in the same direction. For example, if the resource is good, and an agent leaves, then all remaining agents should receive at least as much utility as in the original allocation.

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.

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. ↑ Game Theoretic Analysis of a bankruptcy Problem from the Talmud 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, Elsevier, 2: 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.
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.