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 {car, bicycle} as 900 (see Utility functions on indivisible goods for more examples). There are two problems with this approach:

1. It may be difficult for a person to calculate exact numeric values to the bundles.
2. The number of possible bundles can be huge: if there are ${\displaystyle m}$ items then there are ${\displaystyle 2^{m}}$ 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 rather than cardinal utility. In the ordinal model, each partner should only express a ranking over the ${\displaystyle 2^{m}}$ 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. ^{[3]: 44–48} 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 (so they are not substitute goods nor complementary goods). ^[4] 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 {w,x} to {w,y} or to {x,y}, and {w,y} to {x}. This inference is only partial, e.g., we cannot know whether the agent prefers {w} to {x,y} or even {w,z} to {x,y}.^[5][6]

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.^{[2]: 287–288}

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]: 289–294}

• 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 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 auctions. Some of these languages can be adapted to the item assignment setting.

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):^[7]

Global optimization criteria

A global optimization criterion evaluates a division based on a given social welfare function:

• 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.^[10]

An advantage of global optimization criteria over individual criteria is that welfare-maximizing allocations are Pareto efficient.

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.^[14] 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. Several classes of fairness notions were considered:

• Notions based on weighted competitive equilibrium;^[15][16]
• Notions based on weighted envy-freeness;^[17][18][19]
• Notions based on weighted fair share;^[20]

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).^[21]

Allocation of public goods

In this variant, each item provides utility not only to a single agent but to all agents. Different agents may attribute different utilities to the same item. The group has to choose a subset of items satisfying some constraints, for example:

• At most k items can be selected. This variant is closely related to multiwinner voting, except that in multiwinner voting the number of elected candidates is usually much smaller than the number of voters, while in public goods allocation the number of chosen goods is usually much larger than the number of agents. An example is a public library that has to decide which books to purchase, respecting the preferences of the readers; the number of books is usually much larger than the number of readers.^[22]
• The total cost of all items must not exceed a fixed budget. This variant is often known as participatory budgeting.
• The number of items should be as small as possible, subject to that all agents must agree that the chosen set is better than the non-chosen set. This variant is known as the agreeable subset problem.
• There may be general matroid constraints, matching constraints or knapsack constraints on the chosen set.^[23]

Allocation of private goods can be seen as a special case of allocating public goods: given a private-goods problem with n agents and m items, where agent i values item j at v_ij, construct a public-goods problem with n*m items, where agent i values each item i,j at v_ij, and the other items at 0. Item i,j essentially represents the decision to give item j to agent i. This idea can be formalized to show a general reduction from private-goods allocation to public-goods allocation that retains the maximum Nash welfare allocation, as well as a similar reduction that retains the leximin optimal allocation.^[22]

Common solution concepts for public goods allocation are core stability (which implies both Pareto-efficiency and proportionality),^[23] maximum Nash welfare, leximin optimality and proportionality up to one item.^[22]

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.^[24]

Repeated allocation

Often, the same items are allocated repeatedly. For example, recurring house chores. If the number of repetitions is a multiple of the number of agents, then it is possible to find in polynomial time a sequence of allocations that is envy-free and complete, and to find in exponential time a sequence that is proportional and Pareto-optimal. But, an envy-free and Pareto-optimal sequence may not exist. With two agents, if the number of repetitions is even, it is always possible to find a sequence that is envy-free and Pareto-optimal.^[25]

Stochastic allocations of indivisible goods

Stochastic allocations of indivisible goods^[26] is a type of fair item allocation in which a solution describes a probability distribution over the set of deterministic allocations.

Assume that ${\displaystyle m}$ items should be distributed between ${\displaystyle n}$ agents. Formally, in the deterministic setting, a solution describes a feasible allocation of the items to the agents — a partition of the set of items into ${\displaystyle n}$ subsets (one for each agent). The set of all deterministic allocations can be described as follows:${\displaystyle {\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 ${\displaystyle {\mathcal {A}}}$. That is, the set of all stochastic allocations (i.e., all feasible solutions to the problem) can be described as follows:

${\displaystyle {\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 deterministic allocation  ${\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}$; and an expected utility function associated with a stochastic allocation ${\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}$ which defined according to ${\displaystyle u_{i}}$ as follows:

${\displaystyle E_{i}(d)=\sum _{A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}$