[1] This situation arises in various real-life scenarios: The indivisibility of the items implies that a fair division may not be possible.
In some cases, the indivisibility problem can be mitigated by introducing monetary payments or time-based rotation, or by discarding some of the items.
A naive way to determine the preferences is asking each partner to supply a numeric value for each possible bundle.
[3]: 44–48 Then, the agents report their valuations/rankings on individual items, and the algorithm calculates for them their valuations/rankings on bundles.
They are ordered from the weakest to the strongest (assuming the valuations are additive):[7] 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 against adversarial opponents.
An allocation is called MMS-fair if every agent receives a bundle that he weakly prefers over his MMS.
[8] 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.
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.
Every envy-free allocation of all items is mFS-fair; this follows directly from the ordinal definitions and does not depend on additivity.
[9] Weaker versions of EF include:[10] 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).
When the agents' preferences are additive and strict (each bundle has a different value), CEEI implies Pareto efficiency.
[7] A global optimization criterion evaluates a division based on a given social welfare function: An advantage of global optimization criteria over individual criteria is that welfare-maximizing allocations are Pareto efficient.
Some recent papers study settings in which the distinction between divisible and indivisible is more fuzzy.
There are tight upper bounds on the number of shared objects / sharings required for various kinds of fair allocations among n agents: This raises the question of whether it is possible to attain fair allocations with fewer sharings than the worst-case upper bound: Liu, Lu, Suzuki and Walsh[27] survey some recent results on mixed items, and identify several open questions: 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.
[28] It is common to assume that each party should receive ministries according to the number of seats it has in the parliament.
The classic item allocation setting corresponds to the special case in which all groups are singletons.
[36] Common solution concepts for public goods allocation are core stability (which implies both Pareto-efficiency and proportionality),[37] maximum Nash welfare, leximin optimality and proportionality up to one item.
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.
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.
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 n subsets (one for each agent).