Fair item allocation

Last updated

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. [1] This situation arises in various real-life scenarios:

Contents

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. [2] :285 But such solutions are not always available.

An item assignment problem has several ingredients:

  1. The partners have to express their preferences for the different item-bundles.
  2. The group should decide on a fairness criterion.
  3. 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:

  1. It may be difficult for a person to calculate exact numeric values to the bundles.
  2. The number of possible bundles can be huge: if there are items then there are possible bundles. For example, if there are 16 items then each partner will have to present their 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 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:

Under suitable assumptions, it is possible to lift the preferences on items to preferences on bundles. [3] :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). [4] Then:

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. [2] :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: [2] :289–294

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): [7]

Maximin share

The maximin-share (also called: max-min-fair-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 MMS-fair if every agent receives a bundle that he weakly prefers over his MMS. [8]

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.

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. [7] 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. Hence, every mFS-fair allocation is proportional. For every agent with superadditive utility, the MMSis worth at most. Hence, every proportional allocation is MMS-fair. Both inclusions are strict, even when every agent has additive utility. This is illustrated in the following example: [7]

There are three agents and three items:
  • Alice values the items as 2,2,2. For her, MMS=PFS=mFS=2.
  • Bob values the items as 3,2,1. For him, MMS=1, PFS=2 and mFS=3.
  • Carl values the items as 3,2,1. For him, MMS=1, PFS=2 and mFS=3.
The possible allocations are as follows:
  • Every allocation which gives an item to each agent is MMS-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. [9]

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 MMS-fair. Otherwise, an EF allocation may be not proportional and even not MMS. [9]

Weaker versions of EF include: [10]

  • 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 monotonicity, an EF1 allocation always exists.
  • 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.

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

Global optimization criteria

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

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

Allocation algorithms

Various algorithms for fair item allocation are surveyed in pages on specific fairness criteria:

Between divisible and indivisible

Traditional papers on fair allocation either assume that all items are divisible, or that all items are indivisible. Some recent papers study settings in which the distinction between divisible and indivisible is more fuzzy.

Bounding the amount of sharing

Several works assume that all objects can be divided if needed (e.g. by shared ownership or time-sharing), but sharing is costly or undesirable. Therefore, it is desired to find a fair allocation with the smallest possible number of shared objects, or of sharings. There are tight upper bounds on the number of shared objects / sharings required for various kinds of fair allocations among n agents:

This raises the question of whether it is possible to attain fair allocations with fewer sharings than the worst-case upper bound:

Mixture of divisible and indivisible goods

Liu, Lu, Suzuki and Walsh [27] survey some recent results on mixed items, and identify several open questions:

  1. Is EFM compatible with Pareto-efficiency?
  2. Are there efficient algorithms for maximizing Utilitarian social welfare among EFM allocations?
  3. Are there bounded or even finite algorithms for computing EFM allocations in the Robertson–Webb query model?
  4. Does there always exist an EFM allocation when there are indivisible chores and a cake?
  5. More generally: does there always exist an EFM allocation when both divisible items and indivisible items may be positive for some agents and negative for others?
  6. Is there a truthful EFM algorithm for agents with binary additive valuations?

Variants and extensions

Different entitlements

In this variant, different agents are entitled to different fractions of the resource. A common use-case is dividing cabinet ministries among parties in the coalition. [28] It is common to assume that each party should receive ministries according to the number of seats it has in the parliament. The various fairness notions have to be adapted accordingly. Several classes of fairness notions were considered:

Allocation to groups

In this variant, bundles are given not to individual agents but to groups of agents. Common use-cases are: dividing inheritance among families, or dividing facilities among departments in a university. All agents in the same group consume the same bundle, though they may value it differently. The classic item allocation setting corresponds to the special case in which all groups are singletons.

With groups, it may be impossible to guarantee unanimous fairness (fairness in the eyes of all agents in each group), so it is often relaxed to democratic fairness (fairness in the eyes of e.g. at least half the agents in each group). [35]

Allocation of public goods

In this variant, each item provides utility not only to a single agent but to all agents. Different agents may attribute different utilities to the same item. The group has to choose a subset of items satisfying some constraints, for example:

Allocation of private goods can be seen as a special case of allocating public goods: given a private-goods problem with n agents and m items, where agent i values item j at vij, construct a public-goods problem with n·m items, where agent i values each item i,j at vij, and the other items at 0. Item i,j essentially represents the decision to give item j to agent i. This idea can be formalized to show a general reduction from private-goods allocation to public-goods allocation that retains the maximum Nash welfare allocation, as well as a similar reduction that retains the leximin optimal allocation. [36]

Common solution concepts for public goods allocation are core stability (which implies both Pareto-efficiency and proportionality), [37] maximum Nash welfare, leximin optimality and proportionality up to one item. [36]

Public decision making

In this variant, several agents have to accept decisions on several issues. A common use-case is a family that has to decide what activity to do each day (here each issue is a day). Each agent assigns different utilities to the various options in each issue. The classic item allocation setting corresponds to the special case in which each issue corresponds to an item, each decision option corresponds to giving that item to a particular agent, and the agents' utilities are zero for all options in which the item is given to someone else. In this case, proportionality means that the utility of each agent is at least 1/n of his "dictatorship utility", i.e., the utility he could get by picking the best option in each issue. Proportionality might be unattainable, but PROP1 is attainable by Round-robin item allocation. [38]

Repeated allocation

Often, the same items are allocated repeatedly. For example, recurring house chores. If the number of repetitions is a multiple of the number of agents, then it is possible to find in polynomial time a sequence of allocations that is envy-free and complete, and to find in exponential time a sequence that is proportional and Pareto-optimal. But, an envy-free and Pareto-optimal sequence may not exist. With two agents, if the number of repetitions is even, it is always possible to find a sequence that is envy-free and Pareto-optimal. [39]

Stochastic allocations of indivisible goods

Stochastic allocations of indivisible goods [40] is a type of fair item allocation in which a solution describes a probability distribution over the set of deterministic allocations.

Assume that m items should be distributed between n agents. Formally, in the deterministic setting, a solution describes a feasible allocation of the items to the agents — a partition of the set of items into n subsets (one for each agent). The set of all deterministic allocations can be described as follows:

In the stochastic setting, a solution is a probability distribution over the set . That is, the set of all stochastic allocations (i.e., all feasible solutions to the problem) can be described as follows:

There are two functions related to each agent, a utility function associated with a deterministic allocation ; and an expected utility function associated with a stochastic allocation which defined according to as follows:

Fairness criteria

The same criteria that are suggested for deterministic setting can also be considered in the stochastic setting:

  • Utilitarian rule: this rule says that society should choose the solution that maximize the sum of utilities. That is, to choose a stochastic allocation that maximizes the utilitarian walfare: Kawase and Sumita [40] show that maximization of the utilitarian welfare in the stochastic setting can always be achieved with a deterministic allocation. The reason is that the utilitarian value of the deterministic allocation is at least the utilitarian value of :
  • Egalitarian rule: this rule says that society should choose the solution that maximize the utility of the poorest. That is, to choose a stochastic allocation that maximizes the egalitarian walfare: In contrast to the utilitarian rule, here, the stochastic setting allows society to achieve higher value [40] — as an example, consider the case where are two identical agents and only one item that worth 100. It is easy to see that in the deterministic setting the egalitarian value is 0, while in the stochastic setting it is 50.
    • Hardness: Kawase and Sumita [40] prove that finding a stochastic allocation that maximizes the eqalitarian welfare is NP-hard even when agents' utilities are all budget-additive; and also, that it is NP-hard to approximate the eqalitarian welfare to a factor better than even when all agents have the same submodular utility function.
    • Algorithm: Kawase and Sumita [40] present an algorithm that, given an algorithm for finding a deterministic allocation that approximates the utilitarian welfare to a factor α, finds a stochastic allocation that approximates the egalitarian welfare to the same factor α.

See also

Related Research Articles

Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics, dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods.

Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive.

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

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

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

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.

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

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.

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.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

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.

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

  1. Demko, Stephen; Hill, Theodore P. (1988-10-01). "Equitable distribution of indivisible objects". Mathematical Social Sciences. 16 (2): 145–158. doi:10.1016/0165-4896(88)90047-9. ISSN   0165-4896.
  2. 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 )
  3. Barberà, S.; Bossert, W.; Pattanaik, P. K. (2004). "Ranking sets of objects." (PDF). Handbook of utility theory. Springer US.
  4. 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.
  5. 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. S2CID   153943630.
  6. Brams, S. J. (2005). "Efficient Fair Division: Help the Worst off or Avoid Envy?". Rationality and Society. 17 (4): 387–421. CiteSeerX   10.1.1.118.9114 . doi:10.1177/1043463105058317. S2CID   154808734.
  7. 1 2 3 4 5 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. S2CID   16041218.
  8. Budish, E. (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. CiteSeerX   10.1.1.357.9766 . doi:10.1086/664613. S2CID   154703357.
  9. 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. Vol. 9346. p. 521. doi:10.1007/978-3-319-23114-3_31. ISBN   978-3-319-23113-6.
  10. 1 2 Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare (PDF). Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN   9781450339360.
  11. 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 (1–3): 65–90. CiteSeerX   10.1.1.671.3497 . doi:10.1007/s10472-012-9328-4. S2CID   6864410.
  12. 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. S2CID   442666.
  13. Trung Thanh Nguyen; Jörg Rothe (2013). Envy-ratio and average-nash social welfare optimization in multiagent resource allocation. AAMAS 13.
  14. 1 2 Sandomirskiy, Fedor; Segal-Halevi, Erel (May 2022). "Efficient Fair Division with Minimal Sharing". Operations Research. 70 (3): 1762–1782. arXiv: 1908.01669 . doi:10.1287/opre.2022.2279. ISSN   0030-364X.
  15. 1 2 Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Consensus Halving for Sets of Items". Mathematics of Operations Research. 47 (4): 3357–3379. arXiv: 2007.06754 . doi:10.1287/moor.2021.1249. S2CID   246764981.
  16. Misra, Neeldhara; Sethia, Aditi (2021). "Fair Division is Hard Even for Amicable Agents". In Bureš, Tomáš; Dondi, Riccardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence W.H. (eds.). SOFSEM 2021: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 12607. Cham: Springer International Publishing. pp. 421–430. doi:10.1007/978-3-030-67731-2_31. ISBN   978-3-030-67731-2.
  17. Bismuth, Samuel; Makarov, Vladislav; Segal-Halevi, Erel; Shapira, Dana (2023-11-08), Number Partitioning with Splitting, arXiv: 2204.11753
  18. Bei, Xiaohui; Li, Zihao; Liu, Shengxin; Lu, Xinhang (5 January 2021). "Fair division of mixed divisible and indivisible goods". Artificial Intelligence. 293 103436. Elsevier. arXiv: 1911.07048 . doi:10.1016/j.artint.2020.103436.
  19. Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang; Wang, Hongao (2021-06-30). "Maximin fairness with mixed divisible and indivisible goods". Autonomous Agents and Multi-Agent Systems. 35 (2): 34. arXiv: 2002.05245 . doi:10.1007/s10458-021-09517-7. ISSN   1573-7454.
  20. Bhaskar, Umang; Sricharan, A. R.; Vaish, Rohit (2021). "On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources". DROPS-IDN/V2/Document/10.4230/LIPIcs.APPROX/RANDOM.2021.1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs.APPROX/RANDOM.2021.1 .
  21. Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai (2023-08-19). "Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods". Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. IJCAI '23. Macao, P.R.China. pp. 2808–2816. doi:10.24963/ijcai.2023/313. ISBN   978-1-956792-03-4.{{cite book}}: CS1 maint: location missing publisher (link)
  22. Nishimura, Koichi; Sumita, Hanna (2023-08-13), Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods, arXiv: 2302.13342
  23. Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna (2023-11-08), Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods, arXiv: 2306.05986
  24. Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang (2023-10-02), Fair Division with Subjective Divisibility, arXiv: 2310.00976
  25. Li, Bo; Li, Zihao; Liu, Shengxin; Wu, Zekai (2024-04-28), Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio, arXiv: 2404.18132
  26. Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai; Tao, Yichen (2024-01-02), A Complete Landscape for the Price of Envy-Freeness, arXiv: 2401.01516
  27. Liu, Shengxin; Lu, Xinhang; Suzuki, Mashbat; Walsh, Toby (2024-03-24). "Mixed Fair Division: A Survey". Proceedings of the AAAI Conference on Artificial Intelligence. 38 (20): 22641–22649. arXiv: 2306.09564 . doi:10.1609/aaai.v38i20.30274. ISSN   2374-3468.
  28. Brams, Steven J.; Kaplan, Todd R. (2004). "Dividing the Indivisible". Journal of Theoretical Politics. 16 (2): 143. doi:10.1177/0951629804041118. hdl: 10036/26974 . S2CID   154854134.
  29. Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2017-03-23). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". arXiv: 1703.08150 [cs.GT].
  30. Segal-Halevi, Erel (2018-07-09). "Competitive Equilibrium For almost All Incomes". Proceedings of AAMAS 2018. Aamas '18. International Foundation for Autonomous Agents and Multiagent Systems. pp. 1267–1275.
  31. 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–18:39. arXiv: 1909.10502 . doi:10.1145/3457166. ISSN   2167-8375. S2CID   202719373.
  32. Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-12-01). "Picking sequences and monotonicity in weighted fair division". Artificial Intelligence. 301: 103578. arXiv: 2104.14347 . doi:10.1016/j.artint.2021.103578. ISSN   0004-3702. S2CID   233443832.
  33. Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (2022-06-28). "Weighted Fairness Notions for Indivisible Items Revisited". Proceedings of the AAAI Conference on Artificial Intelligence. 36 (5): 4949–4956. arXiv: 2112.04166 . doi: 10.1609/aaai.v36i5.20425 . ISSN   2374-3468. S2CID   244954009.
  34. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-11-15). "Fair-Share Allocations for Agents with Arbitrary Entitlements". arXiv: 2103.04304 [cs.GT].
  35. 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.
  36. 1 2 3 Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (2021). Bojańczy, Miko\laj; Chekuri, Chandra (eds.). "On Fair and Efficient Allocations of Indivisible Public Goods". 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs). 213. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 22:1–22:19. doi: 10.4230/LIPIcs.FSTTCS.2021.22 . ISBN   978-3-95977-215-0. S2CID   236154847.
  37. 1 2 Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (2018-06-11). "Fair Allocation of Indivisible Public Goods". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 575–592. doi:10.1145/3219166.3219174. ISBN   978-1-4503-5829-3. S2CID   3331859.
  38. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). "Fair public decision making". In Daskalakis, Constantinos; Babaioff, Moshe; Moulin, Hervé (eds.). Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017. {ACM}. pp. 629–646. arXiv: 1611.04034 . doi:10.1145/3033274.3085125. ISBN   978-1-4503-4527-9.
  39. Igarashi, Ayumi; Lackner, Martin; Nardi, Oliviero; Novaro, Arianna (2023-04-04). "Repeated Fair Allocation of Indivisible Items". arXiv: 2304.01644 [cs.GT].
  40. 1 2 3 4 5 Kawase, Yasushi; Sumita, Hanna (2020). "On the Max-Min Fair Stochastic Allocation of Indivisible Goods". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 2070–2078. doi: 10.1609/AAAI.V34I02.5580 . S2CID   214407880.