Fairly Allocating Goods and (Terrible) Chores

There is a defensible positive case, but it depends on choosing the right regime. The literal limit with a fixed finite set of one-off items is useless: as the population grows, almost everyone receives the empty bundle. The credible mirror is a repeated-batch regime in which both agents and physical item copies scale, while each individual still receives an indivisible bundle.

My lead anchor is Theorem 2, proved in this paper. It states that for separable lexicographic mixed instances containing terrible chores, an EFX and PO allocation always exists and can be computed in polynomial time.

A natural setting is a large review, hospital-shift, or emergency-duty clearinghouse. There are \(N\) agents, but only \(\tau\ll N\) complete role-types. A type records the agent’s good/chore classification of each task category and its complete importance ordering. For example, many reviewers may share the same expertise and contract, regarding certain papers as desirable assignments and others as especially undesirable out-of-field work. The item catalogue contains task categories, each with many physical copies. Copies remain indivisible; the repeated catalogue is what makes a high-multiplicity population meaningful.

I would define the following problem.

Sep-LEX-EFX-PO\(_\infty\). An instance consists of a finite catalogue \(M\), a finite type set \(T\), rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), and rational per-capita supplies \(\lambda_o\) for \(o\in M\). A type \(t\) has a good set \(G_t\subseteq M\), chore set \(C_t=M\setminus G_t\), and lexicographic ordering \(\triangleright_t\). Each agent receives at most one copy of each item category. The type orderings are separable, and every type has at least one terrible chore.

An allocation is a configuration census \(x=(x_{t,B})\), where \(B\subseteq M\) is an indivisible bundle and \(x_{t,B}\) is the mass of type-\(t\) agents receiving exactly \(B\). It must satisfy \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=\lambda_o\) for each item category \(o\). Thus \(x\) is a distribution over whole bundles, not fractional allocation of an item.

The census is EFX if, for every two positive-mass configurations \((t,B)\) and \((u,D)\), whenever \(D\succ_t B\), then \(B\succeq_t D\setminus\{o\}\) for every \(o\in G_t\cap D\), and \(B\setminus\{o\}\succeq_t D\) for every \(o\in C_t\cap B\). This is support-wise EFX, not an average-envy relaxation.

It is PO if there is no other feasible census \(y\), using the same supplies, that makes every type’s agents weakly better off and a positive mass strictly better off. Formally, a typewise coupling may match old bundles \(B\) to new bundles \(D\), with \(D\succeq_t B\) for every matched unit of mass and strict preference on some positive mass.

The computational question is: given the rational data, find such an \(x\), or report that none exists.

This is recognizably the authors’ problem. It preserves lexicographic preferences, indivisible bundles, EFX, Pareto optimality, terrible chores, and the separability restriction. Only the census of repeated agents replaces a list of named but otherwise identical agents. If all masses have denominator \(q\), multiplying by \(q\) produces \(q\mu_t\) agents of type \(t\) and \(q\lambda_o\) physical copies of item \(o\). Conversely, a repeated finite instance aggregates to \(x\). That is the high-multiplicity bridge.

I expect Sep-LEX-EFX-PO\(_\infty\) to be Class A. The reason is structural rather than merely optimistic: the proof of Theorem 2 already proceeds through serial dictatorship, priority positions, and the PO-preservation Lemma 1. Those mechanisms suggest a type-level algorithm using mass quotas, threshold orders, and flow-like bookkeeping. The intended complexity target would be polynomial in \(m\), \(\tau\), and the bit-length of the rational masses and supplies, without expanding the population into \(N\) clones. Establishing that compressed algorithm is a new theorem; Theorem 2 does not prove it automatically.

The main further questions are whether the type-level serial dictatorship can maintain support-wise EFX when a type’s mass splits across bundles; whether a polynomial-size configuration support always exists; and whether a column-generation formulation has an efficient pricing problem. Finite-\(q\) rounding is also important: one would want bounds relating a continuous census to a finite repeated allocation.

A second, worthwhile anchor is Theorem 1, also proved in this paper through a reduction from X3C. It states that deciding whether an EFX allocation exists for a lexicographic mixed instance is NP-complete, even for objective instances in which all agents agree on which items are goods and chores.

The corresponding problem is Mixed-LEX-EFX\(_\infty\): use exactly the same mass-and-configuration model above, but drop separability and ask whether any rational census \(x\) satisfies the support-wise EFX constraints. The objective subproblem requires \(G_t=G_u\) for all types \(t,u\), while allowing different importance orders.

I would expect this general mirror to be the harder companion, most plausibly Class C, although I would not claim a hardness transfer without a new proof. The paper’s X3C construction relies on discrete choices by particular agent groups. In a mass model, identical type mass can split across different whole-bundle configurations, potentially turning an exact-cover obstruction into a fractional covering phenomenon. That is precisely why the continuous problem is interesting: the population relaxation may dissolve the original NP-hardness, or it may create a new support-selection hardness that survives despite mass divisibility. The combinatorics now live in the item catalogue and the EFX support constraints rather than in the number of named agents.

This second problem is still author-recognizable: it asks exactly for EFX existence under the same lexicographic mixed preferences, merely in the repeated-agent/repeated-item regime. But I would present it as an open boundary question, not as “Theorem 1 transfers.”

My case deliberately covers only Theorem 2 and Theorem 1. I would not stretch it to Theorem 3’s EF1-plus-PO result or Theorems 4 and 5 concerning MMS and rank maximality without separately defining a satisfactory continuum MMS benchmark and checking how rank maximality behaves under repeated copies.

The weakest point is unavoidable: scaling item supplies is a substantive modelling choice. If the referee insists that only the population may be continuized while the paper’s \(m\) items remain one-off objects, then the mirror degenerates and my case fails. I therefore claim an extension-level mirror for large repeated allocation markets, not a literal continuum limit of every finite instance. In that regime, however, the model is a natural high-multiplicity version of the paper’s fair-division problem, and Theorem 2 gives a particularly credible route to a genuinely compressed, computationally useful Class A theory.