Repeated Fair Allocation of Indivisible Items

The strongest honest mirror is a high-multiplicity market for recurring task slots. Take \(rH\) agents, where \(H\) is large, and \(H\) indistinguishable copies of each of \(m\) recurring items in every round. Each micro-copy remains indivisible. Agents fall into \(\tau\) complete utility types \(t\), with rational mass \(\mu_t\); \(r,m,\tau\) stay fixed while \(H\) grows. This describes, for example, a large university assigning recurring course slots, or a large institution distributing recurring chores, where many employees have one of finitely many preference profiles.

After normalising by \(rH\), type \(t\) has mass \(\mu_t\), and each item label has supply \(1/r\) per round. Thus the continuum is in the population and its assignment frequencies, not in the individual item copies. Rational mass solutions can be implemented by cyclic allocations in sufficiently large finite instances, giving the required high-multiplicity bridge.

My lead anchor is Theorem 7, proved by the authors here. It states that for every \(n\ge 2\) and \(k\in n\mathbb N\), a sequence that is proportional and Pareto-optimal overall exists and can be computed; the proof uses exhaustive enumeration, so the finite algorithm is exponential.

The corresponding continuous problem, which I would call Continuous Repeated PROP–PO\(_\infty\), is:

Given \(r,m,\tau\), rational type masses \(\mu_t\), rational utilities \(u_t(o)\), and \(k\in r\mathbb N\), choose rational variables \(x_{t,o}\), where \(x_{t,o}\in[0,k]\) is the average number of copies of item \(o\) received by one unit of type \(t\) over the \(k\) rounds. They must satisfy

\[ \sum_t \mu_t x_{t,o}=k/r \]

for every item \(o\), and

\[ \sum_o u_t(o)x_{t,o}\ge \frac{k}{r}\sum_o u_t(o) \]

for every type \(t\). Among these feasible assignments, maximise

\[ \sum_t\mu_t\sum_o u_t(o)x_{t,o}. \]

A solution is the rational matrix \(x\), together with a flow or cyclic decomposition into round-by-round allocations of indivisible copies. The welfare objective certifies Pareto-optimality: any type-wise Pareto improvement would strictly increase the objective.

This is a genuine continuous computational mirror of Theorem 7. Its variables represent mass of identical agents receiving indivisible copies; they do not turn one item into a divisible good. The discrete ILP in Figure 1 becomes a polynomial-size LP with \(O(\tau m)\) variables. I would expect this problem to be Class A, with exact polynomial-time solution in the standard rational encoding, followed by rounding or cyclic reconstruction for finite \(H\). It also produces the programme’s desired downward transfer: an LP solution gives preprocessing and additive approximations for large finite populations.

The paper’s authors should recognise this as their problem in a high-multiplicity regime. “A course” or “a household chore” is naturally a recurring item type with many copies across a large institution. Agents with the same utility vector are indistinguishable for the allocation problem, exactly as the programme’s definition of type requires.

A second worthwhile anchor is Theorem 16, also proved by the authors, although its proof relies on cited decomposition results. It states that with rational utilities there exists some number of rounds \(k\) and a sequence that is envy-free and Pareto-optimal overall while satisfying per-round PROP\([1,1]\).

Its population mirror is Minimum-Horizon Repeated EF–PO–PROP[1,1]\(_\infty\). An instance consists of the same \((r,m,\tau,\mu,u)\). A solution is a positive integer \(k\) and a finite rational mass table \(z_{t,h}\), where \(h=(S_1,\ldots,S_k)\) is a history of bundles \(S_\ell\subseteq I\), and \(z_{t,h}\) is the mass of type \(t\) receiving history \(h\). The table must satisfy

\[ \sum_h z_{t,h}=\mu_t \]

and, for every round \(\ell\) and item \(o\),

\[ \sum_{t,h:o\in S_\ell}z_{t,h}=1/r. \]

Overall envy-freeness requires that every type \(t\) weakly prefer its own history to every other supported history, evaluated using \(u_t\). Overall Pareto-optimality means that no alternative mass schedule can weakly improve every positive-mass agent, with a strict improvement for positive mass. Per-round PROP\([1,1]\) requires that each supported bundle \(S_\ell\) can be made proportional by removing at most one item from it and adding at most one item to it, using the benchmark \((1/r)\sum_o u_t(o)\).

The optimisation objective is to minimise \(k\); the bounded decision version asks whether a feasible schedule exists with \(k\le K\). I expect the fixed-type feasibility version to fall on the Class A side through configuration LPs and rational decomposition. The minimum-\(k\) problem is a legitimate further question and may be substantially harder; I would not claim a polynomial theorem for it. Theorem 16 nevertheless supplies an unusually strong existence guarantee and, crucially, its proof already gives the conceptual bridge: fractional assignment, rational lottery, then repeated translation. The continuous population model adds the missing \(\mu\)-dimension rather than merely reusing outcome-space fractionalisation.

I would not anchor on the paper’s two-agent polynomial result, Theorem 15. It is correct and interesting, but its fixed \(n=2\) premise makes the population mirror less compelling unless one introduces two large homogeneous camps, which risks becoming a disguised replication rather than a population-continuum problem. Nor does this paper contain a named NP-hardness or W[1]-hardness theorem, so there is no honest hardness-transfer anchor here.

The weakest point is that the limit must scale item copies with the population. If one keeps only \(m\) indivisible items while sending the number of agents to infinity, almost everyone receives nothing and the paper’s fairness notions degenerate. Replicated course slots or chore instances are therefore a substantive modelling choice, not a cosmetic limit. A second vulnerability is that the LP mirror naturally expresses type-mass or ex-ante fairness; demanding ex-post fairness for every named clone produces a stronger support-constrained problem. Those are real qualifications, but they do not destroy the case: the replicated slots remain indivisible, the agent population is genuinely continuous, the type regime is realistic, and Theorem 7 yields a clean LP whose discrete counterpart is exactly the sort of high-multiplicity computational relaxation ChoCo is meant to study.