An allocation is determined by an n-by-m matrix z, where each element z[i,o] is a real number between 0 and 1.
The integral allocation maximizing the product of utilities (also called the Nash welfare) is PE but not fPO.
Moreover, in any integral fPO allocation, there exists an agent Ai who receives only (at most) the good gi - otherwise a similar trade can be done.
The following example[2]: Sec.6.6 shows that fPO is incompatible with a fairness notion known as EQx - equitability up to any good.
There are three goods {g1,g2,g3} and two agents with the following values (where e is a small positive constant): Only two discrete allocations are EQx: The same instance shows that fPO is incompatible with a fairness notion known as EFx - envy-freeness up to any good.
[2]: Rem.5 An allocation is fPO if-and-only-if it maximizes a weighted sum of the agents' utilities.
Formally, let w be a vector of size n, assigning a weight wi to every agent i.
[5] It was later extended to general valuations (mixtures of goods and bads) by Sandomirskiy and Segal-Halevi.
[6]: Lem.2.3, App.A An allocation is fPO if-and-only-if it its directed consumption graph does not contain cycles with product smaller than 1.
[5] It was later extended to general valuations (mixtures of goods and bads) by Sandomirskiy and Segal-Halevi.
For example, it can be found using serial dictatorship: agent 1 takes all objects for which he has positive value; then agent 2 takes all remaining objects for which he has positive value; and so on.
This challenge can be solved for n agents and m objects with mixed (positive and negative) valuations, in strongly-polynomial time, using O(n2 m2 (n+m)) operations.
Therefore, the above lemma implies an efficient algorithm for finding a fractional PROP+fPO allocation, with at most n-1 sharings.
Similarly, if z is an unequal split, then z* is weighted-proportional (proportional for agents with different entitlements).
This implies an efficient algorithm for finding a fractional WPROP+fPO allocation with at most n-1 sharings.
Combining the above lemma with more advanced algorithms can yield, in strongly-polynomial time, allocations that are fPO and envy-free, with at most n-1 sharings.
[6]: Cor.2.6 There is an algorithm that enumerates all consumption graphs that correspond to fPO allocations.
Several recent works have considered the existence and computation of a discrete allocation that is both fPO and satisfies a certain notion of fairness.