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

  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.

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