Social:Envy-free item allocation

From HandWiki
Revision as of 16:27, 11 January 2022 by imported>NBrush (fixing)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.[1]:296–297 Since the items are indivisible, an EF 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 envy. Therefore, the division procedures provide various kinds of relaxations.

Envy-free allocation of items and money

Envy-freeness is attainable when, in addition to the indivisible items, there is also a divisible good ("money").

A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by two requirements: (a) the number of agents equals the number of objects, (b) the total amount of money paid by the agents must equal the total rent (which is fixed in advance). This is known as the Rental Harmony problem.

A second special case is when selling objects to buyers. In this case, the sum of payments is not fixed in advance, and the goal is to maximize either the seller's revenue, or the social welfare, subject to envy-freeness. Additionally, the number of objects may be different than the number of agents, and some objects may be discarded. This is known as the Envy-free Pricing problem.

A third case is when a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation, and it was studied in several settings.

Unit-demand agents

Unit-demand agents are interested in at most a single item. In the economics literature, it is common to assume that each agent has a utility function on bundles (a bundle is a pair of an object and a certain amount of money). The utility function should be continuous and increasing in money. It does not have to be linear in money, but does have to be "Archimedean", i.e., there exists some value V such that, for every two objects j and k, the utility of object j plus V should be larger than the utility of object k (alternatively, the utility of getting object j for free is larger than the utility of getting object k and paying V). Quasilinear utility is a special case of Archimedean utility, in which V is the largest value-difference (for the same agent) between two objects.

Svensson[2] first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.

Demange, Gale and Sotomayor[3] showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.

Maskin[4] proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than (n-1)V. The proofs use competitive equilibrium.

Note that a subsidy of (n-1)V may be required: if all agents value a single object at V and the other objects at 0, then envy-freeness requires a subsidy of V for each agent who does not receive the object.

Tadenuma and Thomson[5] study several consistency properties of envy-free allocation rules.

Aragones[6] characterizes the minimum amount of subsidy required for envy-freeness. The allocation that attains this minimum subsidy is almost unique: there is only one way to combine objects with agents, and all agents are indifferent among all minimum-subsidy allocations. It coincides with the solution called the "money-Rawlsian solution" of Alkan, Demange and Gale.[7] It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.

Klijn[8] presents another polynomial-time algorithm for the same setting. His algorithm uses the polytope of side-payments that make a given allocaton envy-free: this polytope is nonempty iff the original allocation is Pareto-efficient. Connectivity of the undirected envy graph characterizes the extreme points of this polytope. This implies a method for finding extreme envy-free allocations.

Additive agents

Additive agents are more general, and may receive several items.

Alkan, Demange and Gale[7] showed that an envy-free allocation always exists when the amount of money is sufficiently large. This is true even when items may have negative valuations.

Meertens, Potters and Reijnierse[9] prove the existence of envy-free and Pareto-optimal allocations under very mild assumptions on the valuations (not necessarily quasilinear).

Cavallo[10] 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. He looks for a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. The VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of Bailey[11] and Cavallo[12] is.

Halpern and Shah[13] study subsidy in the general item-allocation setting. They consider two cases:

  1. The allocation is given in advance. In this case, it is "envy-freeable" if and only if it maximizes the sum of utilities across all reassignments of its bundles to agents, if and only if its envy-graph has no cycles. If the value of each good for each agent is at most V, then a subsidy of at most (n-1)mV is always sufficient, and may be necessary. An envy-free allocation with minimum subsidy can be found in strongly-polynomial time.
  2. The allocation can be chosen. In this case, a subsidy of (n-1)V is sufficient in the following cases:
    • When the agents' valuations are binary (0 or 1). Then, any max-product allocation or leximin-optimal allocation requires at most (n-1)V subsidy, and can be found in polynomial time. Computing the minimum subsidy required to achieve EF is Turing-equivalent to checking the existence of an envy-free allocation, which is NP-hard when restricted to non-wasteful allocations.
    • When all agents have the same additive valuation. Then, every allocation is envy-freeable. An allocation that requires at most (n-1)V subsidy can be found in polynomial time. An allocation minimizes the subsidy iff it minimizes the maximum utility to any agent. Computing such an allocation is NP-hard, and can be solved by the max-product algorithm.
    • When there are two agents, round-robin item allocation with a specific agent ordering finds an allocation that is envy-freeable with subsidy at most V.

Brustle, Dippel, Narayan, Suzuki and Vetta[14] improve the upper bounds on the required subsidy:

  • With additive valuations, a subsidy of at most V per agent, and at most (n-1)V in general, is always sufficient. Moreover, there is an allocation attaining this bound that is also EF1 and balanced (the cardinalities of the allocated bundles differ by at most one good). It can be computed in polynomial time by a simple algorithm: iteratively find a maximum-weight matching in the agents-objects bipartite graph.
  • With general monotone valuations, a subsidy of at most 2(n-1)V per agent, and at most O(n2V), is always sufficient. In particular, the required subsidy does not depend on the number of objects. An allocation attaining this bound can be computed in polynomial time using value-queries.

Caragiannis and Ioannidis[15] study the computational problem of minimizing the subsidy:

  • For a constant number of agents, they present an algorithm that approximates the minimum amount of subsidies within any required accuracy. For any ε > 0, it finds an allocation with subsidy at most [math]\displaystyle{ OPT + \varepsilon\cdot \max(v) }[/math], where max(v) is the maximum value that an agent assigns to all objects. The algorithm uses dynamic programming and runs in time [math]\displaystyle{ O((m/\varepsilon)^{n^2+1}) }[/math].
  • For a variable number of agents, a trivial approximation algorithm attains [math]\displaystyle{ OPT + (n-1)\cdot \max(v) }[/math]. However, attaining an approximation factor independent of n is hard: it is NP-hard to compute an allocation with subsidy at most [math]\displaystyle{ OPT + 3\cdot 10^{-4}\cdot \operatorname{sum}(v) }[/math]. The proof is by reduction from a restricted variant of maximum 3-dimensional matching, in which each vertex appears exactly twice.

Note that an envy-free allocation with subsidy remains envy-free if a fixed amount is taken from every agent. Therefore, similar methods can be used to find allocations that are not subsidized:

  • Charging each agent the average payment yields an envy-free allocation that is also budget-balanced. Minimizing the subsidy is equivalent to minimizing the maximum amount that any individual agent has to pay.
  • It is also possible to use negative subsidy (tax), while minimizing the total amount that all agents have to pay.

Multi-dimensional objectives

Often, some other objectives have to be attained besides fairness. For example, when assigning tasks to agents, it is required both to avoid envy, and to minimize the makespan (- the completion time of the last agent). Mu'alem presents a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item allocations using monetary payments.[16]

Aziz[17] aims to attain, using monetary transfers, an allocation that is both envy-free and equitable. He studies not only additive positive utilities, but also for any superadditive utilities, whether positive or negative:

  • For superadditive utilities, there is a polynomial-time algorithm that attains envy-freeness, equitability, and budget balance (it is easy to exchange budget-balance with subsidy).
  • If a given allocation is EFEQ-convertible, then the minimum subsidy required to make it EF+EQ can be found in linear time.
  • Finding an allocation that is EFEQ-convertible with minimum subsidy is NP-hard, and cannot be approximated within any positive factor. This is simply because checking the existence of an EF allocation (which requires 0 subsidy) is NP-hard.
  • A subsidy of at most (n-1)mV is always sufficient, and may be necessary whether an allocation is given or not.

Finding an envy-free allocation whenever it exists

Preference-orderings on bundles: envy-freeness

The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monotone, but does not need to assume that they are responsive preferences. In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.

Preference-orderings on items: necessary/possible envy-freeness

It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc.

Given an item-ranking:

  • An allocation is necessarily envy-free (NEF) if it is envy-free according to all responsive bundle-rankings consistent with the item-ranking;
  • An allocation is possibly envy-free (PEF) if it is envy-free according to at least one responsive bundle-ranking consistent with the item-ranking;
  • An allocation is necessarily Pareto-optimal (NPE) if it is Pareto-optimal according to all responsive bundle-rankings consistent with the item-ranking;
  • An allocation is possibly Pareto-optimal (PPE) if it is Pareto-optimal according to at least one responsive bundle-ranking consistent with the item-ranking.

Bouveret and Endriss and Lang[18] study the algorithmic questions of finding a NEF/PEF allocation with an additional efficiency condition, particularly, completeness or NPE or PPE. In general, PEF is computationally easy while NEF is computationally hard.

Deciding whether an EF allocation exists

The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard:[1]:300–310

  • Deciding whether an EF and complete allocation exists is NP complete. This is true even when there are only two agents, and even when their utilities are additive and identical, since in this case finding an EF allocation is equivalent to solving the partition problem.[19]
  • Deciding whether a fair allocation exists requires exponential communication (in the number of goods) when there are more than two agents. When there are two agents, the communication complexiy depends on specific combinations of parameters.[20]
  • Deciding whether an EF and Pareto efficient allocation exists is above NP: it is [math]\displaystyle{ \Sigma {2}^{\textrm{P}} }[/math]-complete even with dichotomous utilities[21] and even with additive utilities.[22] ([math]\displaystyle{ \Sigma {2}^{\textrm{P}} }[/math] is the class of problems that can be solved in nondeterministic time given an oracle that can solve any problem in NP).

The decision problem may become tractable when some parameters of the problem are considered fixed small constants:[23]

  • Considering the number of objects m as a parameter, the existence of a PE+EF allocation can be decided in time [math]\displaystyle{ O^*(m^{2m}) }[/math] for additive or dichotomous utilities. When the utilities are binary and/or identical, the runtime drops to [math]\displaystyle{ O^*(m^{m}) }[/math]. Here, the notation [math]\displaystyle{ O^* }[/math] hides expressions that are polynomial in the other parameters (e.g. number of agents).
  • Considering the number of agents n as a parameter, the existence of a PE+EF allocation remains hard. With dichotomous utilities, it is NP-hard even for n=2.[21] However, it is now in NP, and can be solved efficiently with an NP oracle (e.g. a SAT solver). With [math]\displaystyle{ n\geq 5 }[/math] agents, it can be done with [math]\displaystyle{ 2^{n+1} }[/math]such oracles, and at least [math]\displaystyle{ 2^{n-4} }[/math] oracles are needed unless P=NP. With additive utilities, it is NP-hard even for n=2.[21] Moreover, it is W[1]-complete w.r.t. the number of agents even if all utilities are identical and encoded in unary.
  • Considering both the number of agents n and the largest utility V as parameters, the existence of a PE+EF allocation can be decided in time [math]\displaystyle{ O^*((m\cdot V + 1)^{n^2}\cdot mn^2) }[/math] for additive utilities using dynamic programming.
  • Considering both the number of agents n and the number of utility levels z as parameters, the existence of a PE+EF allocation for identical additive utilities can be decided using an integer linear program with [math]\displaystyle{ d = n\cdot z^n }[/math] variables; Lenstra's algorithm allows solving such ILP in time [math]\displaystyle{ O^*(d ^{2.5d}) }[/math].

Finding an allocation with a bounded level of envy

Many procedures find an allocation that is "almost" envy-free, i.e., the level of envy is bounded. There are various notions of "almost" envy-freeness:

EF1 - envy-free up to at most one item

An allocation is called EF1 if for every two agents A and B, if we remove at most one item from the bundle of B, then A does not envy B.[24] An EF1 allocation always exists and can be found efficiently by various procedures, particularly:

  • When all agents have weakly additive utilities, the round-robin protocol finds a complete EF1 allocation. Weak additivity is required since each agent should be able to pick, in each situation, a "best item".
  • In the more general case, when all agents have monotonically-increasing utilities, the envy-graph procedure finds a complete EF1 allocation. The only requirement is that the agents can rank bundles of items. If the agents' valuations are represented by a cardinal utility function, then the EF1 guarantee has an additional interpretation: the numeric envy-level of each agent is at most the maximal-marginal-utility - the largest marginal utility of a single item for that agent.
  • When agents have arbitrary utilities (not necessarily additive or monotone), the A-CEEI mechanism returns a partial EF1 allocation. The only requirement is that the agents can rank bundles of items. A small number of items might remain unallocated, and a small number of items may have to be added. The allocation is Pareto-efficient with respect to the allocated items.
  • The Maximum Nash Welfare algorithm selects a complete allocation that maximizes the product of utilities. It requires each agent to provide a numeric valuation of each item, and assumes that the agents' utilities are additive. The resulting allocation is both EF1 and Pareto-efficient.[25]
  • Various other algorithms return EF1 allocations that are also Pareto-efficient; see Efficient approximately-fair item allocation.
  • For two agents with arbitrary monotone valuations, or three agents with additive valuations, an EF1 allocation can be computed using a number of queries logarithmic in the number of items.[26]
  • For two agents with arbitrary utility functions (not necessarily monotone), an EF1 allocation can be found in polynomial time.[27]
  • For at most 4 agents with arbitrary monotone valuations, or n agents with identical monotone valuations, there always exists an EF1 allocation that is also connected (when items are pre-ordered on a line, such as houses in a street). The proof uses an algorithm similar to the Simmons–Su protocols. When there are n > 4 agents, it is not known whether a connected EF1 allocation exists, but a connected EF2 allocation always exists.[28]

EFx - envy-free up to at most any item

An allocation is called EFx if for every two agents A and B, if we remove any item from the bundle of B, then A does not envy B.[29] EFx is strictly stronger than EF1: EF1 lets us eliminate envy by removing the item most valuable (for A) from B's bundle; EFx requires that we eliminate envy by removing the item least valuable (for A). An EFx allocation is known to exist in some special cases:

  • When there are two agents, or when there are n agents with identical valuations. In this case, the leximin-optimal allocation is EFx and Pareto-optimal. However, it requires exponentially many queries to compute.[30][27]
  • When there are n agents with additive valuations, but there are at most two different values for goods. In this case, any max-Nash-welfare allocation is EFx. Moreover, there is an efficient algorithm for calculating an EFx allocation (though not necessarily max-Nash-welfare).[31]
  • IWhen there are n agents with additive valuations, but there are at most two different kinds of valuations.[32]
  • When there are three agents with additive valuations. In this case, a polynomial-time algorithm exists.[33]

Some approximations are known:

  • A 1/2-approximate EFx allocation (that also satisfies a different approximate-fairness notion called Maximin Aware) can be found in polynomial time.[34]
  • A 0.618-approximate EFx allocation (that is also EF1 and approximates other fairness notions called groupwise maximin share and pairwise maximin share) can be found in polynomial time.[35]
  • There always exists a partial EFx allocation, where the Nash welfare is at least half of the maximum possible Nash welfare. In other words, after donating some items to a charity, the remaining items can be allocated in an EFx way. This bound is the best possible. In large markets, where the valuations of an agent for every item is relatively small, the algorithm attains EFx with almost optimal Nash welfare.[36] It is sufficient to donate n-1 items, and no agent envies the set of donated items.[37]

It is an open question whether an EFx allocation exists in general. The smallest open case is 4 agents with additive valuations.

In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFx allocation may requires a linear number of queries even when there are two agents with identical additive valuations.[26]

Another difference between EF1 and EFx is that the number of EFX allocations can be as few as 2 (for any number of items), while the number of EF1 allocations is always exponential in the number of items.[38]

EFm - approximate envy-free for a mixture of divisible and indivisible items

Some division scenarios involve both divisible and indivisible items, such as divisible lands and indivisible houses. An allocation is called EFm if for every two agents A and B:[39]

  • If B's bundle contains some divisible goods, then A does not envy B (as in an EF allocation).
  • If B's bundle contains only indivisible goods, then A does not envy B after removing at most one item from B's bundle (as in an EF1 allocation).

An EFm allocation exists for any number of agents. However, finding it requires an oracle for exact division of a cake. Without this oracle, an EFm allocation can be computed in polynomial time in two special cases: two agents with general additive valuations, or any number of agents with piecewise-linear valuations.

In contrast to EF1, which is compatible with Pareto-optimality, EFm may be incompatible with it.

Minimizing the envy

Rather than using a worst-case bound on the amount of envy, one can try to minimize the amount of envy in each particular instance. See envy minimization for details and references.

Finding a partial EF allocation

The AL procedure finds an EF allocation for two agents. It may discard some of the items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other. The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).

The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to cut a single item (alternatively, one item remains in shared ownership). It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.

When each agent may get at most a single item, and the valuations are binary (each agent either likes or dislikes each item), there is a polynomial-time algorithm that finds an envy-free matching of maximum cardinality.[40]

Existence of EF allocations with random valuations

If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability. Particularly:[41]

  • If the number of items is sufficiently large: [math]\displaystyle{ m = \Omega(n \log n) }[/math], then w.h.p. an EF allocation exists (the probability goes to 1 as m goes to infinity).
  • If the number of items is not sufficiently large, i.e., [math]\displaystyle{ m = n + o(n) }[/math], then w.h.p. an EF allocation does not exist.

Envy-freeness vs. other fairness criteria

  • Every EF allocation is min-max-fair. This follows directly from the ordinal definitions and does not depend on additivity.
  • If all agents have additive utility functions, then an EF allocation is also proportional and max-min-fair. Otherwise, an EF allocation may be not proportional and even not max-min-fair.
  • Every allocation of a competitive equilibrium from equal incomes is also envy-free. This is true regardless of additivity.[24]
  • Every Nash-optimal allocation (allocation that maximizes the product of utilities) is EF1.[29]
  • Group-envy-freeness is a strengthening of envy-freeness, which is applicable to both divisible and indivisible objects.

See Fair item allocation for details and references.

Summary table

Below, the following shorthands are used:

  • [math]\displaystyle{ n }[/math] = the number of agents participating in the division;
  • [math]\displaystyle{ m }[/math] = the number of items to divide;
  • EF = envy-free, EF1 = envy-free except-1-item (weaker than EF), MEF1 = marginal-envy-free except-1-item (weaker than EF1).
  • PE = Pareto-efficient.
Name #partners Input Preferences #queries Fairness Efficiency Comments
Undercut 2 Bundle ranking Strictly monotone [math]\displaystyle{ 2^m }[/math] EF Complete If-and-only-if a complete EF allocation exists
AL 2 Item ranking Weakly additive [math]\displaystyle{ Poly(m) }[/math] Necessarily-EF Partial, but not Pareto-dominated by another NEF
Adjusted winner 2 Item valuations Additive [math]\displaystyle{ Poly(m) }[/math] EF and equitable PE Might divide one item.
Round-robin [math]\displaystyle{ n }[/math] Item ranking Weakly additive [math]\displaystyle{ m }[/math] Necessarily-EF1 Complete
Envy-graph [math]\displaystyle{ n }[/math] Bundle ranking Monotone [math]\displaystyle{ O(m n^3) }[/math] EF1 Complete
A-CEEI [math]\displaystyle{ n }[/math] Bundle ranking Any ? EF1, and [math]\displaystyle{ (n+1) }[/math]-maximin-share Partial, but PE w.r.t. allocated items Also approximately strategyproof when there are many agents.
Maximum-Nash-Welfare[29] [math]\displaystyle{ n }[/math] Item valuations Additive NP-hard (but there are approximations in special cases) EF1, and approximately-[math]\displaystyle{ n }[/math]-maximin-share PE

With submodular utilities, allocation is PE and MEF1.

References

  1. ↑ 1.0 1.1 Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016) (in en). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. https://books.google.com/books?id=nMHgCwAAQBAJ.  (free online version)
  2. ↑ Svensson, Lars-Gunnar (1983). "Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness". Econometrica 51 (4): 939–954. doi:10.2307/1912044. ISSN 0012-9682. 
  3. ↑ Demange, Gabrielle; Gale, David; Sotomayor, Marilda (1986). "Multi-Item Auctions". Journal of Political Economy 94 (4): 863–872. doi:10.1086/261411. 
  4. ↑ Maskin, Eric S. (1987), Feiwel, George R., ed., "On the Fair Allocation of Indivisible Goods" (in en), Arrow and the Foundations of the Theory of Economic Policy (London: Palgrave Macmillan UK): pp. 341–349, doi:10.1007/978-1-349-07357-3_12, ISBN 978-1-349-07357-3, https://doi.org/10.1007/978-1-349-07357-3_12, retrieved 2021-02-16 
  5. ↑ Tadenuma, Koichi; Thomson, William (1991). "No-Envy and Consistency in Economies with Indivisible Goods". Econometrica 59 (6): 1755–1767. doi:10.2307/2938288. ISSN 0012-9682. 
  6. ↑ Aragones, Enriqueta (1995). "A derivation of the money rawlsian solution". Social Choice and Welfare 12 (3): 267–276. doi:10.1007/BF00179981. ISSN 0176-1714. 
  7. ↑ 7.0 7.1 Alkan, Ahmet; Demange, Gabrielle; Gale, David (1991). "Fair Allocation of Indivisible Goods and Criteria of Justice". Econometrica 59 (4): 1023–1039. doi:10.2307/2938172. ISSN 0012-9682. 
  8. ↑ Klijn, Flip (2000-03-01). "An algorithm for envy-free allocations in an economy with indivisible objects and money" (in en). Social Choice and Welfare 17 (2): 201–215. doi:10.1007/s003550050015. ISSN 1432-217X. https://doi.org/10.1007/s003550050015. 
  9. ↑ Meertens, Marc; Potters, Jos; Reijnierse, Hans (2002-12-01). "Envy-free and Pareto efficient allocations in economies with indivisible goods and money" (in en). Mathematical Social Sciences 44 (3): 223–233. doi:10.1016/S0165-4896(02)00064-1. ISSN 0165-4896. https://www.sciencedirect.com/science/article/pii/S0165489602000641. 
  10. ↑ Ruggiero Cavallo (2012). "Fairness and Welfare Through Redistribution When Utility is Transferable". AAAI-12. http://www.eecs.harvard.edu/~cavallo/papers/cavallo-aaai12.pdf. 
  11. ↑ Bailey, Martin J. (1997). "The demand revealing process: To distribute the surplus". Public Choice 91 (2): 107–126. doi:10.1023/A:1017949922773. 
  12. ↑ Cavallo, Ruggiero (2006). "Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06". pp. 882. doi:10.1145/1160633.1160790. ISBN 1595933034. 
  13. ↑ Halpern, Daniel; Shah, Nisarg (2019). Fotakis, Dimitris; Markakis, Evangelos. eds. "Fair Division with Subsidy" (in en). Algorithmic Game Theory. Lecture Notes in Computer Science (Cham: Springer International Publishing) 11801: 374–389. doi:10.1007/978-3-030-30473-7_25. ISBN 978-3-030-30473-7. https://link.springer.com/chapter/10.1007/978-3-030-30473-7_25. 
  14. ↑ Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2020-07-13). "One Dollar Each Eliminates Envy". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20 (Virtual Event, Hungary: Association for Computing Machinery): 23–39. doi:10.1145/3391403.3399447. ISBN 978-1-4503-7975-5. https://doi.org/10.1145/3391403.3399447. 
  15. ↑ Caragiannis, Ioannis; Ioannidis, Stavros (2020-02-06). "Computing envy-freeable allocations with limited subsidies". arXiv:2002.02789 [cs.GT].
  16. ↑ Mu'alem, Ahuva (2014). "Fair by design: Multidimensional envy-free mechanisms". Games and Economic Behavior 88: 29–46. doi:10.1016/j.geb.2014.08.001. 
  17. ↑ Aziz, Haris (2020-03-18). "Achieving Envy-freeness and Equitability with Monetary Transfers". arXiv:2003.08125 [cs.GT].
  18. ↑ Sylvain Bouveret, Ulle Endriss, Jérôme Lang (2010). "Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods". ECAI 2010. pp. 387–392. 
  19. ↑ Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Proceedings of the 5th ACM conference on Electronic commerce - EC '04". pp. 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0. 
  20. ↑ Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Communication Complexity of Discrete Fair Division". SIAM Journal on Computing 49 (1): 206–243. doi:10.1137/19M1244305. ISSN 0097-5397. https://epubs.siam.org/doi/abs/10.1137/19M1244305. 
  21. ↑ 21.0 21.1 21.2 Bouveret, S.; Lang, J. (2008). "Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity". Journal of Artificial Intelligence Research 32: 525–564. doi:10.1613/jair.2467. 
  22. ↑ De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Algorithmic Decision Theory". 5783. pp. 98. doi:10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4. 
  23. ↑ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16 (New York, New York, USA: AAAI Press): 102–108. ISBN 978-1-57735-770-4. https://dl.acm.org/doi/abs/10.5555/3060621.3060636. 
  24. ↑ 24.0 24.1 Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy 119 (6): 1061–1103. doi:10.1086/664613. 
  25. ↑ 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. pp. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360. http://eprints.gla.ac.uk/123283/1/123283.pdf. 
  26. ↑ 26.0 26.1 Oh, Hoon; Procaccia, Ariel D.; Suksompong, Warut (2019-07-17). "Fairly Allocating Many Goods with Few Queries" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 33 (1): 2141–2148. doi:10.1609/aaai.v33i01.33012141. ISSN 2374-3468. https://www.aaai.org/ojs/index.php/AAAI/article/view/4046. 
  27. ↑ 27.0 27.1 Bérczi, Kristóf; Bérczi-Kovács, Erika R.; Boros, Endre; Gedefa, Fekadu Tolessa; Kamiyama, Naoyuki; Kavitha, Telikepalli; Kobayashi, Yusuke; Makino, Kazuhisa (2020-06-08). "Envy-free Relaxations for Goods, Chores, and Mixed Items". arXiv:2006.04428 [econ.TH].
  28. ↑ Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Monaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (2018-08-28). "Almost Envy-Free Allocations with Connected Bundles". arXiv:1808.09406 [cs.GT].
  29. ↑ 29.0 29.1 29.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. pp. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360. http://eprints.gla.ac.uk/123283/1/123283.pdf. 
  30. ↑ Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Almost Envy-Freeness with General Valuations". SIAM Journal on Discrete Mathematics 34 (2): 1039–1068. doi:10.1137/19M124397X. ISSN 0895-4801. https://epubs.siam.org/doi/abs/10.1137/19M124397X. 
  31. ↑ Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (2020-06-01). "Maximum Nash Welfare and Other Stories About EFX". arXiv:2001.09838 [cs.GT].
  32. ↑ Mahara, Ryoga (2020-08-20). "Existence of EFX for Two Additive Valuations". arXiv:2008.08798 [cs.GT].
  33. ↑ Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt (2020-05-30). "EFX Exists for Three Agents". arXiv:2002.05119 [cs.GT].
  34. ↑ Chan, Hau; Chen, Jing; Li, Bo; Wu, Xiaowei (2019-10-25). "Maximin-Aware Allocations of Indivisible Goods". arXiv:1905.09969 [cs.GT].
  35. ↑ Amanatidis, Georgios; Ntokos, Apostolos; Markakis, Evangelos (2020). "Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination". Theoretical Computer Science 841: 94–109. doi:10.1016/j.tcs.2020.07.006. 
  36. ↑ Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (2019-06-17). "Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items". Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19 (Phoenix, AZ, USA: Association for Computing Machinery): 527–545. doi:10.1145/3328526.3329574. ISBN 978-1-4503-6792-9. https://doi.org/10.1145/3328526.3329574. 
  37. ↑ Chaudhury, Bhaskar Ray; Kavitha, Telikepalli; Mehlhorn, Kurt; Sgouritsa, Alkmini (2019-12-23), "A Little Charity Guarantees Almost Envy-Freeness", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Proceedings (Society for Industrial and Applied Mathematics): pp. 2658–2672, doi:10.1137/1.9781611975994.162, ISBN 978-1-61197-599-4, https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.162, retrieved 2020-10-02 
  38. ↑ Suksompong, Warut (2020-09-30). "On the number of almost envy-free allocations" (in en). Discrete Applied Mathematics 284: 606–610. doi:10.1016/j.dam.2020.03.039. ISSN 0166-218X. http://www.sciencedirect.com/science/article/pii/S0166218X20301384. 
  39. ↑ Bei, Xiaohui; Li, Zihao; Liu, Jinyan; Liu, Shengxin; Lu, Xinhang (2021). "Fair division of mixed divisible and indivisible goods". Artificial Intelligence 293: 103436. doi:10.1016/j.artint.2020.103436. 
  40. ↑ Aigner-Horev, Elad; Segal-Halevi, Erel (2020-12-22). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527 [cs.DS].
  41. ↑ John P. Dickerson; Jonathan Goldman; Jeremy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). "The Computational Rise and Fall of Fairness". In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (2014). pp. 1405–1411.  ACM link




Retrieved from "https://handwiki.org/wiki/index.php?title=Social:Envy-free_item_allocation&oldid=895176"