Fair item allocation is a kind of a
fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inh ...
problem in which the items to divide are ''discrete'' rather than continuous. 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:
* 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
A white elephant gift exchange, Yankee swap or Dirty Santa
is a party game where amusing and impractical gifts are exchanged during festivities. The goal of a white elephant gift exchange is to entertain party-goers rather than to gain a gen ...
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
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
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.
[Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet, "Fair Allocation of Indivisible Goods". Chapter 12 in: ] 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.
Preferences
Combinatorial preferences
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 as 900 (see
Utility functions on indivisible goods Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an ...
for more examples). There are two problems with this approach:
# It may be difficult for a person to calculate exact numeric values to the bundles.
# The number of possible bundles can be huge: if there are
items then there are
possible bundles. For example, if there are 16 items then each partner will have to present their preferences using 65536 numbers.
The first problem motivates the use of
ordinal utility In economics, an ordinal utility function is a function representing the preferences of an agent on an ordinal scale. Ordinal utility theory claims that it is only meaningful to ask which option is better than the other, but it is meaningless to a ...
rather than
cardinal utility
In economics, a cardinal utility function or scale is a utility index that preserves preference orderings uniquely up to positive affine transformations. Two utility indices are related by an affine transformation if for the value u(x_i) of one i ...
. 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:
* In the cardinal approach, each partner should report a numeric valuation for each item;
* In the ordinal approach, each partner should report a ranking over the items, i.e., say which item is the best, which is the second-best, etc.
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.
Additive preferences
To make the item-assignment problem simpler, it is common to assume that all items are
independent goods
Independent goods are goods that have a zero cross elasticity of demand. Changes in the price of one good will have no effect on the demand for an independent good. Thus independent goods are neither complements nor substitutes.
For example, a ...
(so they are not
substitute goods nor
complementary goods
In economics, a complementary good is a good whose appeal increases with the popularity of its complement. Technically, it displays a negative cross elasticity of demand and that demand for it increases when the price of another good decreases. I ...
).
Then:
* In the cardinal approach, each agent has an
additive utility function (also called: ''modular'' utility function). Once the agent reports a value for each individual item, it is easy to calculate the value of each bundle by summing up the values of its items.
* In the ordinal approach, additivity allows us to infer some rankings between bundles. For example, if a person prefers w to x to y to z, then he necessarily prefers to or to , and to . This inference is only partial, e.g., we cannot know whether the agent prefers to or even to .
The additivity implies that each partner can always choose a "preferable item" from the set of items on the table, and this choice is independent of the other items that the partner may have. This property is used by some fair assignment algorithms that will be described next.
[
]
Compact preference representation languages
''Compact preference representation languages'' have been developed as a compromise between the full expressiveness of combinatorial preferences to the simplicity of additive preferences. They provide a succinct representation to some natural classes of utility functions that are more general than additive utilities (but not as general as combinatorial utilities). Some examples are:[
* ''2-additive preferences'': each partner reports a value for each bundle of size at most 2. The value of a bundle is calculated by summing the values for the individual items in the bundle and adding the values of pairs in the bundle. Typically, when there are substitute items, the values of pairs will be negative, and when there are complementary items, the values of pairs will be positive. This idea can be generalized to ''k-additive preferences'' for every positive integer ''k''.
* ''Graphical models'': for each partner, there is a graph that represents the dependencies between different items. In the cardinal approach, a common tool is the ''GAI net'' (Generalized Additive Independence). In the ordinal approach, a common tool is the ''CP net'' (Conditional Preferences) and its extensions: ''TCP net'', ''UCP net'', ''CP theory'', ''CI net'' (Conditional Importance) and ''SCI net'' (a simplification of CI net).
* ''Logic based languages'': each partner describes some bundles using a ]first order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
formula, and may assign a value for each formula. For example, a partner may say: "For (x or (y and z)), my value is 5". This means that the agent has a value of 5 for any of the bundles: x, xy, xz, yz, xyz.
* ''Bidding languages'': many languages for representing combinatorial preferences have been studied in the context of combinatorial auction
A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete heterogeneous items, or “packages”, rather than individual items or continuous quantities. These packages can be also called lot ...
s. Some of these languages can be adapted to the item assignment setting.
Fairness criteria
Individual guarantee criteria
An ''individual guarantee criterion'' is a criterion that should hold for each individual partner, as long as the partner truthfully reports his preferences. Five such criteria are presented below. They are ordered from the weakest to the strongest (assuming the valuations are additive):
Maximin share
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into ''n'' parts and taking the part with th ...
The maximin-share (also called: max-min-fair-share guarantee) of an agent is the most preferred bundle he could guarantee himself as divider in divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
against adversarial opponents. An allocation is called ''MMS-fair'' if every agent receives a bundle that he weakly prefers over his MMS.
Proportional fair-share (PFS)
The proportional-fair-share of an agent is 1/''n'' of his utility from the entire set of items. An allocation is called ''proportional'' if every agent receives a bundle worth at least his proportional-fair-share.
Min-max fair-share (mFS)
The min-max-fair-share of an agent is the minimal utility that she can hope to get from an allocation if all the other agents have the same preferences as her, when she always receives the best share. It is also the minimal utility that an agent can get for sure in the allocation game “Someone cuts, I choose first”. An allocation is ''mFS-fair'' if all agents receive a bundle that they weakly prefer over their mFS.[ mFS-fairness can be described as the result of the following negotiation process. A certain allocation is suggested. Each agent can object to it by demanding that a different allocation be made by another agent, letting him choose first. Hence, an agent would object to an allocation only if in ''all'' partitions, there is a bundle that he strongly prefers over his current bundle. An allocation is mFS-fair iff no agent objects to it, i.e., for every agent there exists a partition in which all bundles are weakly worse than his current share.
For every agent with subadditive utility, the mFS is worth ''at least'' . Hence, every mFS-fair allocation is proportional. For every agent with superadditive utility, the MMSis worth ''at most'' . Hence, every proportional allocation is MMS-fair. Both inclusions are strict, even when every agent has additive utility. This is illustrated in the following example:][
::There are three agents and three items:
::*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.]
Envy-freeness Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by a ...
(EF)
Every agent weakly prefers his own bundle to any other bundle. Every envy-free allocation of all items is mFS-fair; this follows directly from the ordinal definitions and does not depend on additivity. If the valuations are additive, then an EF allocation is also proportional and MMS-fair. Otherwise, an EF allocation may be not proportional and even not MMS.[ See envy-free item assignment for more details.
]
Competitive equilibrium
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and se ...
from Equal Incomes (CEEI)
This criterion is based on the following argument: the allocation process should be considered as a search for an equilibrium between the supply (the set of objects, each one having a public price) and the demand (the agents’ desires, each agent having the same budget for buying the objects). A competitive equilibrium is reached when the supply matches the demand. The fairness argument is straightforward: prices and budgets are the same for everyone. CEEI implies EF regardless of additivity. When the agents' preferences are additive and strict (each bundle has a different value), CEEI implies Pareto efficiency
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engi ...
.[
Several recently suggested fairness criteria are:][
]
Envy-freeness-except-1 (EF1)
For each two agents A and B, if we remove from the bundle of B the item most valuable for A, then A does not envy B (in other words, the "envy level" of A in B is at most the value of a single item). Under monotonicity, an EF1 allocation always exists.
Envy-freeness-except-cheapest (EFx)
For each two agents A and B, if we remove from the bundle of B the item ''least'' valuable for A, then A does not envy B. EFx is strictly stronger than EF1. It is not known whether EFx allocations always exist.
Global optimization criteria
A ''global optimization criterion'' evaluates a division based on a given social welfare function
In welfare economics, a social welfare function is a function that ranks social states (alternative complete descriptions of the society) as less desirable, more desirable, or indifferent for every possible pair of social states. Inputs of the f ...
:
* The ''egalitarian'' social welfare is minimum utility of a single agent. An item assignment is called ''egalitarian-optimal'' if it attains the maximum possible egalitarian welfare, i.e., it maximizes the utility of the poorest agent. Since there can be several different allocations maximizing the smallest utility, egalitarian optimality is often refined to ''leximin-optimality'': from the subset of allocations maximizing the smallest utility, it selects those allocations that maximize the second-smallest utility, then the third-smallest utility, and so on.
* The ''Nash'' social welfare is the product of the utilities of the agents. An assignment called ''Nash-optimal'' or ''Maximum-Nash-Welfare'' if it maximizes the product of utilities. Nash-optimal allocations have some nice fairness properties.
An advantage of global optimization criteria over individual criteria is that welfare-maximizing allocations are Pareto efficient
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engin ...
.
Allocation algorithms
Various algorithms for fair item allocation are surveyed in pages on specific fairness criteria:
* Maximin-share item allocation;
* Proportional item allocation;
* Minimax-share item allocation: The problem of calculating the mFS of an agent is coNP-complete. The problem of deciding whether an mFS allocation exists is in , but its exact computational complexity is still unknown.
* Envy-free item allocation Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.
Since the items are i ...
;
* Egalitarian item allocation;
* Nash-optimal allocation: and prove hardness of calculating utilitarian-optimal and Nash-optimal allocations. present an approximation procedure for Nash-optimal allocations.
* Picking sequence A picking sequence is a protocol for fair item assignment. Suppose ''m'' items have to be divided among ''n'' agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A ...
: a simple protocol where the agents take turns in selecting items, based on some pre-specified sequence of turns. The goal is to design the picking-sequence in a way that maximizes the expected value of a social welfare function (e.g. egalitarian or utilitarian) under some probabilistic assumptions on the agents' valuations.
*Competitive equilibrium: various algorithms for finding a CE allocation are described in the article on Fisher market Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:
* A set of m divisible products with pre-specified supplies (usually normalized such that the supply of each good is 1).
* A set of n buyers.
* For ea ...
.
Variants and extensions
Different entitlements
In this variant, different agents are entitled to different fractions of the resource. A common use-case is dividing cabinet ministries among parties in the coalition. It is common to assume that each party should receive ministries according to the number of seats it has in the parliament. The various fairness notions have to be adapted accordingly. See and and for discussions of this problem and some solutions.
Allocation to groups
In this variant, bundles are given not to individual agents but to groups of agents. Common use-cases are: dividing inheritance among families, or dividing facilities among departments in a university. All agents in the same group consume the same bundle, though they may value it differently. The classic item allocation setting corresponds to the special case in which all groups are singletons.
With groups, it may be impossible to guarantee ''unanimous fairness'' (fairness in the eyes of all agents in each group), so it is often relaxed to ''democratic fairness'' (fairness in the eyes of e.g. at least half the agents in each group).
Public decision making
In this variant, several agents have to accept decisions on several issues. A common use-case is a family that has to decide what activity to do each day (here each issue is a day). Each agent assigns different utilities to the various options in each issue. The classic item allocation setting corresponds to the special case in which each issue corresponds to an item, each decision option corresponds to giving that item to a particular agent, and the agents' utilities are zero for all options in which the item is given to someone else. In this case, proportionality means that the utility of each agent is at least 1/''n'' of his "dictatorship utility", i.e., the utility he could get by picking the best option in each issue. Proportionality might be unattainable, but PROP1 is attainable by Round-robin item allocation
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as ...
.
See also
* Bin covering problem and Bin packing problem
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
- two well-studied optimization problems that can be seen as special cases of ''indivisible goods allocation'' and ''indivisible chores allocation'', respectively. Many techniques used for these problems are useful in the case of fair item allocation, too.
* Fair division experiments - including some case-studies and lab experiments related to fair item assignment.
*Rental harmony 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 problem and room-assignment-rent-division are alternative names to the same problem.
In the t ...
- a fair division problem where indivisible items and a fixed total cost have to be divided simultaneously.
*Fair random assignment Fair random assignment (also called probabilistic one-sided matching) is a kind of a fair division problem.
In an ''assignment problem'' (also called '' house-allocation problem'' or '' one-sided matching''), there ''m'' objects and they have to be ...
- a fair division problem without money, in which fairness is attained through randomization.
* House allocation problem - a fair division problem in which each agent should get exactly one object, with neither monetary transfers nor randomization.
* Price of fairness In the theory of fair division, the price of fairness (POF) is the ratio of the largest economic welfare attainable by a division to the economic welfare attained by a ''fair'' division. The POF is a quantitative measure of the loss of welfare that ...
- a general measure of the trade-off between fairness and efficiency, with some results about the item assignment setting.
*Fair subset sum problem The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset S of ''n'' integers and a positive integer ''m'' represe ...
References
{{reflist
*