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.^{[1]: 296–297}

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.

Proportional allocation

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):

• ${\displaystyle V_{i}(X_{i})\geq V_{i}(M)/n}$.

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

PROP1 allocations

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

• ${\displaystyle \exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq c,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$.

An equivalent definition is: the value of each agent i is at least (1/n of the total) minus (the most valuable c items not assigned to i):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{Y\subseteq M\setminus X_{i},|Y|\leq c}V_{i}(Y)}$

PROP0 is equivalent to proportionality, which might not exist. In contrast, a PROP1 allocation always exists and can be found e.g. by round-robin item allocation. The interesting question is how to combine it with efficiency conditions such as Pareto efficiency (PE).

PROP*(n-1) allocations

An allocation is called proportional from all except c items (PROP*c) for an agent i if there exists a set of at most c items that, if removed from the set of all items, then i values his bundle at least 1/n of the remainder. Formally, for all i:^[12]

• ${\displaystyle \exists Y\subseteq M:~~~|Y|\leq c,~~~V_{i}(X_{i})\geq V_{i}(M\setminus Y)/n}$.

PROP*(n-1) is slightly stronger than PROP1: when n=2, PROP*(n-1) is equivalent to EF1, but PROP1 is weaker. A PROP*(n-1) allocation always exists and can be found e.g. by round-robin item allocation.

PROPx allocations

An allocation is called proportional up to the worst item (PROPx) if for every agent i, for any subset with one item not allocated to i, if the subset is given to i, then it brings his value to at least 1/n of the total. Formally, for all i:^[13]

• ${\displaystyle \forall Y\subseteq M\setminus X_{i}:~~~|Y|=1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$

An equivalent definition is: the value of each agent i is at least (1/n of the total) minus (the least valuable item not assigned to i):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\min _{Y\subseteq M\setminus X_{i},|Y|=1}V_{i}(Y)}$

Obviously, PROPx is stronger than PROP1. Moreover, while PROP1 allocations always exist, PROPx allocations may not exist.^[13][10]

PROPm allocations

An allocation is called proportional up to the maximin item (PROPm) if the value of each agent i is at least (1/n of the total) minus (the maximin item not assigned to i), where the maximin item the maximum over all the other n-1 agents j, of the least-valuable item allocated to j. Formally:^[14]

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{j\neq i}\min _{Y\subseteq X_{j},|Y|=1}V_{i}(Y)}$

Obviously, PROPx is stronger than PROPm, which is stronger than PROP1. A PROPm allocation exists when the number of agents is at most 5.^[14]

References