Fair item allocation

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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: * Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings. * Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses. * Gift-exchange party games featuring white elephant-type items.

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. But such solutions are not always available. An item assignment problem has several ingredients: # The partners have to express their preferences for the different item-bundles. # The group should decide on a fairness criterion.…

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: Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings. Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses.

Gift-exchange party games featuring white elephant-type items. 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. But such solutions are not always available.

An item assignment problem has several ingredients: The partners have to express their preferences for the different item-bundles. The group should decide on a fairness criterion. Based on the preferences and the fairness criterion, a fair assignment algorithm should be executed to calculate a fair division.

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. Bismuth, Makarov, Shapira and Segal-Halevi study fair allocation with identical valuations, which is equivalent to Identical-machines scheduling, and also the more general setting of Uniform-machines scheduling.

They study the run-time complexity of deciding the existence of a fair allocation with s sharings or shared objects, where s is smaller than the worst-case upper bound of n−1. They prove that, for sharings, the problem is NP-hard for any s ≤ n−2; but for shared objects and n ≥ 3, the problem is polynomial for s = n−2 and NP-hard for any s ≤ n−3.

When n is not fixed, the problem is strongly NP-hard. Bismuth, Bliznets and Segal-Halevi also study the run-time complexity of deciding the existence of a fair allocation with s sharings or shared objects, where the valuations are not identical but have other structural properties (binary valuations, equal-sum generalized-binary valuations, or non-degenerate).

Li, Li, Liu and Wu study a setting in which each agent may have a different "indivisibility ratio" (= proportion of items that are indivisible). Each agent is guaranteed an allocation that is EF/PROP up to a fraction of an item, where the fraction depends on the agent's indivisibility ratio. The results are tight up to a constant for EF and asymptotically tight for PROP.

Li, Liu, Lu, Tao and Tao study the price of fairness in both indivisible and mixed item allocation. They provide bounds for the price of EF1, EFx, EFM and EFxM. They provide tight bounds for two agents and asymptotically tight bounds for n agents, for both scaled and unscaled utilities.

Liu, Lu, Suzuki and Walsh survey some recent results on mixed items, and identify several open questions: Is EFM compatible with Pareto-efficiency? Are there efficient algorithms for maximizing Utilitarian social welfare among EFM allocations? Are there bounded or even finite algorithms for computing EFM allocations in the Robertson–Webb query model?

Does there always exist an EFM allocation when there are indivisible chores and a cake? 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?

Is there a truthful EFM algorithm for agents with binary additive valuations? \mathcal{A} = \{(A^1, \dots, A^n) \mid \forall i \in [n] \colon A^i \subseteq [m] , \quad \forall i \neq j \in [n] \colon A^i \cap A^j = \emptyset, \quad \cup_{i=1}^n A^i = [m] \} In the stochastic setting, a solution is a probability distribution over the set \mathcal{A} . That is, the set of all stochastic allocations (i.e., all feasible solutions to the problem) can be described as follows: \mathcal{D} = \{d \mid p_d \colon \mathcal{A} \to [0,1], \sum_{A \in \mathcal{A}} p_d(A) = 1\} There are two functions related to each agent, a utility function associated with a and an expected utility function associated with a stochastic allocation E_i \colon \mathcal{D} \to \mathbb{R}_{+} which defined according to u_i as follows: E_i(d) = \sum_{A \in \mathcal{A}}p_d(A) \cdot u_i(A) Utilitarian rule: this rule says that society should choose the solution that maximize the sum of utilities.

That is, to choose a stochastic allocation d^*\in \mathcal{D} that maximizes the utilitarian welfare: d^* = \underset{d \in \mathcal{D}}\operatorname{argmax}\sum_{i=1}^n \sum_{A \in \mathcal{A}}\left(p_d(A)\cdot u_i(A)\right) Kawase and Sumita 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 A^* = \underset{A \in \mathcal{A}\colon p_{d^*}(A)>0}\operatorname{argmax}\sum_{i=1}^n u_i(A) is at least the utilitarian value of d^* : \sum_{i=1}^n \sum_{A \in \mathcal{A}}\left(p_{d^*}(A)\cdot u_i(A)\right) = \sum_{A \in \mathcal{A}}p_{d^*}(A)\sum_{i=1}^n u_i(A) \leq \max_{A \in \mathcal{A}\colon p_{d^*}(A)>0}\sum_{i=1}^n u_i(A) 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 d^*\in \mathcal{D} that maximizes the egalitarian welfare: d^* = \underset{d \in \mathcal{D}}\operatorname{argmax}\min_{i =1,\ldots,n} \sum_{A \in \mathcal{A}}\left(p_d(A)\cdot u_i(A)\right) In contrast to the utilitarian rule, here, the stochastic setting allows society to achieve higher value — as an example, consider the case where are two identical agents and only one item that worth . It is easy to see that in the deterministic setting the egalitarian value is , while in the stochastic setting it is .

Hardness: Kawase and Sumita prove that finding a stochastic allocation that maximizes the egalitarian welfare is NP-hard even when agents' utilities are all budget-additive; and also, that it is NP-hard to approximate the egalitarian welfare to a factor better than 1-\tfrac{1}{e} even when all agents have the same submodular utility function. Algorithm: Kawase and Sumita 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 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369234356 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

11 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.