Envy-free item assignment

Envy-free item assignment (EF assignment) is a fair item assignment problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that he believes 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.

Finding an envy-free allocation if it exists

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

In the worst case, the agents may have to evaluate all possible bundles, so the run-time might be exponential in the number of items.

Finding a partial envy-free 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' preference relations on bundles are responsive (weakly additive) and returns an allocation that is necessarily envy-free (NEF) - it is EF for all weakly-additive valuations that are consistent with the reported rankings.

Bounding the maximum envy

Several procedures find an allocation that is Envy-free except one item (EF1): for each two agents A and B, there exists an item that can be removed from the bundle of B such that A does not envy B.[2]

Round-robin protocol

When all agents have weakly additive utilities, the following protocol (which is similar to Round-robin scheduling) attains a complete EF1 allocation:

  1. Order the agents arbitrarily.
  2. While there are unassigned items:
    • Let each agent from 1 to pick an item.
Proof:[3] For every agent , divide the selections made by the agents to sub-sequences: the first subsequence starts at agent 1 and ends at agent ; the latter subsequences start at and end at . In the latter subsequences, agent chooses first, so he can choose his best item, so he does not envy any other agent. Agent can envy only one of the agents , and the envy comes only from an item they selected in the first subsequence. If this item is removed, agent does not envy.

The round-robin protocol requires weak additivity, since it requires each agent to pick his "best item" without knowing what other items he is going to get. In other words, it assumes that the items are independent goods.

Unenvied-agent protocol

The unenvied-agent procedure returns a complete EF1 allocation for arbitrary preference relations. 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.

A-CEEI protocol

The A-CEEI mechanism returns a partial EF1 allocation for arbitrary preference relations. The only requirement is that the agents can rank bundles of items.

A small number of items might remain unallocated; the allocation is Pareto-efficient with respect to the allocated items. Moreover, the A-CEEI mechanism is approximately strategyproof when the number of agents is large.

Maximum-Nash-Welfare

The Maximum-Nash-Welfare (MNW) 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 EF1 and Pareto-efficient.[3]

If the agents' utilities are not additive, the MNW solution is not necessarily EF1; but if the agents' utilities are at least submodular, the MNW solution satisfies a weaker property called Marginal-Envy-Freeness except-1-item (MEF1).

EF1 vs EFx

There is an alternative criterion called Envy-freeness-except-cheapest (EFx): For each two agents A and B, if we remove from the bundle of B any item, then A does not envy B. EFx is strictly stronger than EF1. As of this writing, it is not known whether EFx allocations always exist.[3]

Minimizing the envy-ratio

Given an allocation X, define the envy ratio of i in j as:

so the ratio is 1 if i does not envy j, and it is larger when i envies j. Define the envy ratio of an assignment as:

The envy ratio minimization problem is the problem of finding an allocation X with smallest envy ratio.

General valuations

With general valuations, any deterministic algorithm that computes an alloation with minimum envy-ratio requires a number of queries which is exponential in the number of goods in the worst case.[4]:3

Additive and identical valuations

With additive and identical valuations:[4]:4-6

Additive and different valuations

With additive and different valuations:[6]

Dividing one item

The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to divide a single item. It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.

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

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

Envy-freeness vs. other fairness criteria

See Fair item assignment for details and references.

Summary table

Below, the following shorthands are used:

Name #partners Input Preferences #queries Fairness Efficiency Comments
Undercut 2 Bundle ranking Strictly monotone EF Complete If-and-only-if a complete EF allocation exists
AL 2 Item ranking Weakly additive Necessarily-EF Partial, but not Pareto-dominated by another NEF
Adjusted winner 2 Item valuations Additive EF and equitable PE Might divide one item.
Round-robin Item ranking Weakly additive Necessarily-EF1 Complete
Unenvied-agent Bundle ranking Monotone EF1 Complete
A-CEEI Bundle ranking Any ? EF1, and -maximin-share Partial, but PE w.r.t. allocated items Also approximately strategyproof when there are many agents.
Maximum-Nash-Welfare[3] Item valuations Additive NP-hard (but there are approximations in special cases) EF1, and approximately--maximin-share PE

With submodular utilities, allocation is PE and MEF1.

References

  1. 1 2 Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)
  2. 1 2 Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061. doi:10.1086/664613.
  3. 1 2 3 4 5 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. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.
  4. 1 2 3 Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "On approximately fair allocations of indivisible goods". Proceedings of the 5th ACM conference on Electronic commerce - EC '04. p. 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0.
  5. Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416. doi:10.1137/0117039.
  6. Nguyen, Trung Thanh; Rothe, Jörg (2014). "Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods". Discrete Applied Mathematics. 179: 54. doi:10.1016/j.dam.2014.09.010.
  7. . doi:10.1613/jair.2467 (inactive 2016-10-15). Missing or empty |title= (help)
  8. De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences". Algorithmic Decision Theory. Lecture Notes in Computer Science. 5783. p. 98. doi:10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4.
  9. 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. Retrieved 26 August 2016. ACM link
This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.