Fair division problem in which the items to divide are discrete rather than continuous
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:
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.
White elephant gift exchange parties
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:
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.
These ingredients are explained in detail below.
^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.
^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)
and 24 Related for: Fair item allocation information
Fairitemallocation 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...
goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fairallocation. For example, when there is a single...
Egalitarian itemallocation, also called max-min itemallocation is a fairitemallocation problem, in which the fairness criterion follows the egalitarian...
Proportional itemallocation is a fairitemallocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle...
houses. Fairitemallocation - each agent may get any number of objects. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). "House Allocation with Existing...
endowments. In the fairitemallocation problem, the Nash-optimal rule is no longer PM. In contrast, round-robin itemallocation is PM. Moreover, round-robin...
objects are taken; this leads to the round-robin itemallocation procedure. This procedure is fairer, but it is not strategyproof. Both procedures are...
to construct subsets that satisfy a given criterion of fairness, such as max-min itemallocation. When m is variable (a part of the input), both problems...
: 30–31 The basic TTC algorithm is illustrated by the following house allocation problem. There are n {\displaystyle n} students living in the student...
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates...
strengthening of Pareto efficiency in the context of fairitemallocation. An allocation of indivisible items is fractionally Pareto-efficient (fPE or fPO) if...
Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students...
to the setting in which the users' demands are indivisible (as in fairitemallocation). For the indivisible setting, they relax envy-freeness to EF1. They...
Maximin share (MMS) is a criterion of fairitemallocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value...
included in the plan, showing which items should be sacrificed if total funding must be reduced. Resource allocation may be decided by using computer programs...
least a given threshold. In the fair indivisible chore allocation problem (a variant of fairitemallocation), the items represent chores, and there are...
apportionment describes mathematical principles and algorithms for fairallocation of identical items among parties with different entitlements. Such principles...
constraints on the allocation. One may want to maximize the welfare among all allocations that are fair, for example, envy-free up to one item (EF1), proportional...
problems have been studied: Fairitem assignment – dividing a set of indivisible and heterogeneous goods. Fair resource allocation – dividing a set of divisible...
someone else's gift, even a gift that is out of play.[citation needed] Fairitemallocation Secret Santa White elephant sale Other names include Shifty Santa...
-democratic 1-out-of-c MMS-fairallocation. These allocations can be found efficiently using a variant of round-robin itemallocation, with weighted approval...
the term OXS valuation (not to be confused with XOS valuation). Fairitemallocation in this setting was studied by Benabbou, Chakraborty, Elkind, Zick...
Global Information