Fair Division in a Variable Setting

The strongest honest mirror is a population-scaled version of the paper’s identical-valuation restoration problem, anchored in Theorem 3.5. This theorem is proved in the paper, via Lemmas 4.1 and 4.2; it is not imported from prior work. It states that for identical monotone valuations, every near-EF1 allocation can be restored, and that with identical additive valuations at most \(m/n\) valid transfers suffice, with the bound tight.

The natural regime is a large workforce repeatedly assigned discrete tasks or machine slots. Workers have the same valuation over a finite catalogue of task types, while there are many copies of each task type. Thus \(N\), the number of workers, is large while the number \(\tau\) of valuation types is \(1\). A disruption may affect a positive-mass cohort: for example, one shift loses a class of tasks, or a new cohort of workers enters with empty bundles. A single lost item affecting one named worker would have vanishing mass in the limit; that is not the regime I am claiming.

Here is the precise mirror, which I would call Cohort-EF1-Restoration\(_\infty\). Let \(Q\) be a finite set of item classes, let \(v:2^Q\to\mathbb{Q}_{\ge 0}\) be the common monotone valuation, and let \(\beta_q\) be the number of copies of class \(q\) per unit population. At finite population size \(N\), there are \(N\beta_q\) physically distinct, indivisible copies of \(q\). Each worker receives a discrete bundle \(B\subseteq Q\), with at most one copy of each class.

The continuous allocation is a distribution \(\lambda=(\lambda_B)_{B\subseteq Q}\), where \(\lambda_B\) is the fraction of workers holding bundle \(B\). It must satisfy \(\sum_B\lambda_B=1\) and \(\sum_{B:q\in B}\lambda_B=\beta_q\) for each \(q\). Thus \(\lambda\) is a distribution over discrete bundles, not a fractional assignment of an item to an individual. When all \(\lambda_B\) are rational with denominator \(N\), it is exactly an \(N\)-worker allocation.

For a bundle \(D\), define \(h(D)=0\) if \(D=\varnothing\), and otherwise \(h(D)=\min_{q\in D}v(D\setminus\{q\})\). A worker holding \(B\) is EF1-happy precisely when \(v(B)\ge h(D)\) for every occupied bundle \(D\). Equivalently, their EF1-envy amount toward \(D\) is \(e(B,D)=\max\{0,h(D)-v(B)\}\).

The input includes a marked cohort \(U\) of mass \(\eta>0\), initially allowed to be the only unhappy cohort. An aggregate transfer chooses a mass \(\delta\) of workers holding \(D\), a mass \(\delta\) of recipient workers holding \(B\), and an item class \(q\in D\setminus B\). It changes their bundles to \(D\setminus\{q\}\) and \(B\cup\{q\}\). At finite \(N\), this is exactly \(\delta N\) ordinary item transfers. A transfer is valid when the new distribution remains near-EF1 and the marked cohort’s EF1-envy amounts do not increase. A solution is a finite sequence of valid aggregate transfers ending in an EF1 distribution. The optimization version minimizes total moved mass \(\Phi=\sum\delta\), the continuous analogue of the number of transfers.

This is recognizably the authors’ question. It preserves the central ingredients: an already nearly fair allocation, a local input shock, restoration through intermediate near-EF1 states, and minimal disturbance. The only change is the correct high-multiplicity scaling: “agent 1” becomes a positive-mass cohort, and one transfer becomes a batch of parallel transfers among indistinguishable workers.

I expect this mirror to be Class A, most confidently for identical additive valuations and plausibly for the monotone setting of Theorem 3.5. The proof’s key choice—take an agent whose bundle remains most valuable after removing its best item—becomes a choice of an occupied bundle class \(D\) maximizing \(v(D\setminus\{q_D\})\), followed by a mass transfer from that class to the unhappy cohort. For additive valuations, the continuous bound becomes \( \Phi_U/\eta\le \sum_{q\in Q}\beta_q\), the normalized form of \(m/n\), with tight examples obtained by equal task values and equal loads. The finite-support formulation is a flow/configuration LP; the genuinely interesting algorithmic question is whether it admits a compact pricing or separation procedure under succinct monotone valuations.

This mirror covers Theorem 3.5, Lemma 4.1, Lemma 4.2, and the analogous chores statement in Remark 4.3. It deliberately does not claim to cover the mixed-goods-and-chores or EFX negative result in Remark 4.4; those are useful boundary questions. One should ask whether the continuous additive problem has an exact minimum-transfer algorithm, whether arbitrary monotone valuations require an exponential configuration oracle, and how closely finite-\(N\) solutions approximate the mass optimum.

The paper’s graphical result gives a possible secondary mirror, but I consider it weaker. Theorem 3.6, proved here through Theorems 5.2 and 5.3, concerns additive binary valuations on multigraphs and restores an EF1 orientation using at most \(K(n-1)\) transfers. A corresponding high-multiplicity regime would have many agents at each of finitely many graph-role types, with many copies of each edge-item type. The continuous state would be the distribution of agents over discrete oriented bundles, and aggregate transfers would move edge-copy mass between endpoint cohorts. The expected direction is again Class A, with mass routed along the finite envy graph; the analogue of the bound is \(K(|R|-1)\) transfers per unit unhappy mass for role set \(R\). This is plausible because the paper’s proof is already a shortest-path argument, but it requires care: heterogeneous bundle distributions among clones may prevent the envy graph from collapsing cleanly to the role graph.

I would not use Theorem 3.7 as a positive anchor. Although its PSPACE-completeness result is proved here, its reduction assigns highly individualized valuation functions to the agents corresponding to vertices of a perfect-matching instance. The number of valuation types therefore grows with the hard instance. That is hardness in the agenda and role structure, not hardness caused by population multiplicity. A continuous version might well be Class B if the discrete reconfiguration embeds, but the paper itself does not provide a convincing high-multiplicity regime for it.

The weakest point in the positive case is the scaling of the disruption. The paper literally allows one agent to lose one item or one new agent to arrive. In a normalized continuum, that event has mass zero and cannot change the aggregate allocation. My mirror therefore replaces it with a positive cohort shock and extensive item copies. That is a genuine extension, not a notational rewrite. I nevertheless think it is the right extension for the paper’s own motivating examples—large workforces, task assignments, and machine slots—and it is exactly what makes the population, rather than the items or outcomes, the continuous object.