Proportional item allocation

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

Since the items are indivisible, a proportional assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will have a value of 0, which is less than 1/2. Therefore, the literature considers various relaxations of the proportionality requirement.

An allocation of objects is called proportional (PROP) if every agent i values his bundle at least 1/n of the total. Formally, for all i (where M is the set of all goods):

A proportional division may not exist. For example, if the number of people is larger than the number of items, then some people will get no item at all and their value will be zero. Nevertheless, such a division exists with high probability for indivisible items under certain assumptions on the valuations of the agents.

Suppose the agents have cardinal utility functions on items. Then, the problem of deciding whether a proportional allocation exists is NP-complete: it can be reduced from the partition problem.

Suppose the agents have ordinal rankings on items. An allocation is called necessary-proportional (or sd-proportional) if it is proportional according to all valuations consistent with the rankings. It is called possibly-proportional if it is proportional according to at least one set of consistent valuations.

With additive valuations:

An allocation is called proportional up to the best c items (PROPc) if for every agent i, there exists a subset of at most c items that, if given to i, brings the total value of i to at least 1/n of the total. Formally, for all i (where M is the set of all goods):