Fair item assignment
Fair item assignment is a kind of a fair division problem in which the items to divide are indivisible. The items have to be divided among several partners who 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:
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:
These ingredients are explained in detail below.
A naive way to determine the preferences is asking each partner to supply a numeric value for each possible bundle. For example, if the items to divide are a car and a bicycle, a partner may value the car as 800, the bicycle as 200, and the bundle {car,bicycle} as 900 (see Utility functions on indivisible goods for more examples). There are two problems with this approach:
The first problem motivates the use of ordinal utility rather than cardinal utility. In the ordinal model, each partner should only express a ranking over the different bundles, i.e, say which bundle is the best, which is the second-best, and so on. This may be easier than calculating exact numbers, but it is still difficult if the number of items is large.
The second problem is often handled by working with individual items rather than bundles:
Under suitable assumptions, it is possible to lift the preferences on items to preferences on bundles. Then, the agents report their valuations/rankings on individual items, and the algorithm calculates for them their valuations/rankings on bundles.
...
Wikipedia