Fair Allocation of Indivisible Goods and Chores

The strongest honest positive case is a high-multiplicity mirror of the paper’s two-agent EF1-and-PO result. I would make this the lead.

The paper contains no numbered NP-hardness theorem of its own. Its statement that finding Pareto improvements is NP-hard is attributed to earlier papers, so it cannot serve as an anchor under the requested rule. The useful anchors here are therefore algorithmic.

My lead anchor is Theorem 3, proved in this paper: “For two agents, a Pareto-optimal and EF1 complete allocation always exists and can be computed in polynomial time.” The theorem applies to additive utilities in the full mixed setting: an item may be a good for one agent and a chore for the other, and objective goods and chores may coexist. Its algorithm first assigns subjective items to the agent who regards them as goods, then treats the remaining objective goods and chores by designating a winner and loser, sorting items by the ratio \( |u_\ell(o)|/|u_w(o)| \), and transferring goods from the winner to the loser and chores from the loser to the winner until the loser is EF1. Every intermediate allocation is Pareto-optimal.

A natural continuous problem is:

Continuous Two-Type Adjusted-Winner Allocation. The society has two agent types \(A\) and \(B\), with masses \(\mu_A,\mu_B>0\) and \(\mu_A+\mu_B=1\). Type \(t\) has additive utility \(u_t(o)\in\mathbb{Q}\) for each item class \(o\in O\). There are \(\rho_o\in[0,1]\) copies of each item class per unit population. At finite population size \(N\), this means \(N\rho_o\) indivisible copies of \(o\); each individual may receive at most one copy of each class. Thus the copies remain indivisible. Only their aggregate assignment is represented continuously.

A solution is a mass allocation \(z_{t,B}\ge 0\), where \(B\subseteq O\) is an integral bundle and \(z_{t,B}\) is the mass of type-\(t\) agents receiving \(B\), satisfying \(\sum_Bz_{t,B}=\mu_t\) and \(\sum_{t}\sum_{B\ni o}z_{t,B}=\rho_o\) for every \(o\).

Let \(p_t(o)=\mu_t^{-1}\sum_{B\ni o}z_{t,B}\), and let \(V_t(s)\) be type \(t\)’s evaluation of the average bundle received by type \(s\): \(V_t(s)=\mu_s^{-1}\sum_Bz_{s,B}\sum_{o\in B}u_t(o)\). The allocation is type-average EF1 if, whenever \(V_t(t)<V_t(s)\), there is an item class \(o\) such that either removing one \(o\) from the type-\(t\) bundles eliminates the envy, \(V_t(t)-u_t(o)p_t(o)\ge V_t(s)\), or removing one \(o\) from the type-\(s\) bundles does so, \(V_t(t)\ge V_t(s)-u_t(o)p_s(o)\). It is Pareto-optimal if no other feasible mass allocation weakly improves both \(V_A(A)\) and \(V_B(B)\), with one improvement strict.

This is recognisably the same problem as Theorem 3. The agents still have the same mixed good/chore utilities, the bundles are still integral, EF1 still means removing one item, and Pareto-optimality is still defined by utility improvements. The only change is that many agents share one of two complete utility types, and item supplies scale with population size.

The appropriate regime is, for example, two large homogeneous groups of workers receiving recurring tasks, benefits, or assignments. There may be millions of agents but only two or a few utility types. A finite realization has \(N\mu_A\) type-\(A\) agents and \(N\mu_B\) type-\(B\) agents, with item-copy counts \(N\rho_o\). The continuous variables are population proportions such as \(p_t(o)\), not fractional individual items.

I would expect this problem to be Class A. After subjective items are assigned to the type that values them positively, the remaining transfers can be organized by the same adjusted-winner ratio as in Theorem 3, with utilities normalized by type masses. The relevant ordering is determined by quantities such as \((|u_B(o)|/\mu_B)/(|u_A(o)|/\mu_A)\). A fractional aggregate transfer of an item class is not fractional allocation of an item: it means that, among many indivisible copies, some copies go to type \(A\) agents and the rest to type \(B\) agents. Such an aggregate assignment can be realized by a distribution over integral bundles. The expected continuous result is therefore a ratio-sorting algorithm, perhaps with a configuration-LP formulation.

The further questions are meaningful rather than cosmetic: can the algorithm be made polynomial in \(m\) and the encoding length of \(\mu,\rho,u\); can one enforce EF1 for every microscopic pair of agents rather than in expectation over types; and what happens with three or more types?

My second anchor is Theorem 1, also proved in this paper: the double round robin algorithm returns a complete EF1 allocation for additive utilities in \(O(\max\{m^2,mn\})\) time, even when items can be subjective goods or chores. The algorithm first allocates the items that are non-positive for every agent as chores, adding zero-valued dummy chores so that every agent receives the same number of chores. It then allocates the remaining goods in reverse round-robin order, starting with the agent worst off after the chore phase, and finally removes the dummy chores.

Its continuous counterpart would be:

Continuous Double-Round-Robin EF1. The input is a finite type set \(T\), a rational society distribution \(\mu\), item classes \(O\) with per-capita supplies \(\rho_o\), and additive utilities \(u_t(o)\). The output is a feasible mass distribution \(z_{t,B}\) over integral bundles satisfying the same type-average EF1 condition above. No optimization objective is required: any such complete allocation is a solution.

Here the high-multiplicity regime is \(|T|=\tau\ll N\): many agents share one of a small number of complete utility vectors. I would expect Class A for every fixed \(\tau\). For a fixed choice of EF1 witness item and witness side for each ordered pair of types, the constraints on \(z\) are linear. The bundles \(B\) give an exponential-size configuration LP, but the pricing problem is additive over items: a best bundle can be formed by deciding independently whether to include each item class. The finite theorem also gives an existence argument: apply Theorem 1 to increasingly large rational finite realizations and take a convergent subsequence of their bundle distributions. The unresolved issue is whether the dependence on \(\tau\) can be made polynomial rather than merely polynomial for fixed \(\tau\).

I would not use Theorems 5 or 6 as anchors. Their cake and path-contiguity results primarily continuize the item or outcome space, whereas the programme’s target is the population. Likewise, I would not claim that the paper already contains a continuous-population model: it does not. The proposed mirrors are genuinely new high-multiplicity formulations, while retaining the paper’s utility model, indivisible bundles, mixed goods and chores, EF1, and Pareto efficiency.

The weakest point is the fairness notion. EF1 in the paper is ex post and compares two named agents’ actual bundles. My mirror uses the natural population-scale analogue: type-average EF1, where each unit of mass still receives an integral bundle but the type’s reported allocation is an average. The programme explicitly permits such fractional type-level averages, but an author might argue that this weakens EF1 too much. The stronger follow-up would require every pair of bundles in the supports of two types to satisfy ordinary EF1. I would not pretend that this stronger version is automatically tractable. Still, the type-average version is a credible continuous analogue of the paper’s central two-agent result, and it gives the paper a concrete Class A continuous-population research question rather than merely replacing indivisible goods by divisible ones.