d4-conf-wine-2024-0018

The strongest mirror is the paper’s minimum-social-cost problem under EQ1. It asks the same economic question—assign indivisible chores to minimize total disutility while meeting a person-by-person fairness condition—but represents a large workforce by cost types and masses.

Imagine a large organization assigning recurring chore units. A worker’s type \(t\) is their complete cost vector \(c_t(j)\) over chore classes \(j\): workers of the same type have identical costs for every chore. The population is a distribution \(\mu\) over \(\tau\) types, with \(\sum_t\mu_t=1\). Chore supplies scale with the workforce: \(b_j\) is the number of units of class \(j\) per worker. Each worker still receives an integral bundle \(A\) of chores; only the mass of workers receiving each bundle can be fractional. This is a plausible regime when many workers share a small number of roles, shift patterns, or accessibility profiles.

Here is the lead question, Continuous-Type Chore Allocation with EQ1 (CT-SC-EQ1). An instance gives finite chore classes \(J\), rational per-worker supplies \(b_j\), rational type costs \(c_t(j)\), and rational masses \(\mu_t\). As in the paper, take \(\sum_{j\in J}c_t(j)=1\). Let \(x_{t,A}\) be the mass of type \(t\) receiving integral bundle \(A\subseteq J\). Require \(\sum_A x_{t,A}=\mu_t\) and \(\sum_{t,A:j\in A}x_{t,A}=b_j\). For every two positive-mass classes \((t,A)\) and \((u,B)\), require an item \(j\in A\) with \(c_t(A\setminus\{j\})\leq c_u(B)\). Find a feasible \(x\) minimizing \(\sum_{t,A}x_{t,A}c_t(A)\), or, for additive approximation \(\epsilon\), return a feasible \(x\) of cost at most \(\mathrm{OPT}+\epsilon\). This applies EQ1 to the bundles people actually receive, not to fractional average bundles. That distinction preserves the paper’s fairness question.

The lead anchor is Theorem 5, proved in this paper. It states that for every \(n\geq3\), unless \(P=NP\), no polynomial-time algorithm approximates SC-EQ1 within an additive factor smaller than \(1/2\), with agents’ total costs normalized to \(1\). The proof reduces from Partition. The reduction has a useful high-multiplicity feature: the first \(n-1\) agents have identical cost vectors, and only the last agent has a different one. Its instances therefore have just two cost types, even as \(n\) varies. That makes the mirror more than a generic “large workforce” story: the paper’s own hardness construction already uses repeated types. I would initially expect CT-SC-EQ1 to be continuum-specifically hard. Partition’s item choices may survive in the integral bundle patterns, while EQ1 depends on which bundle patterns have positive mass—a support-sensitive condition that does not automatically become a linear program. The discrete reduction itself does not prove this prediction.

A second, worthwhile anchor is Theorem 8, also proved here. It states that for every \(n\geq3\), unless \(P=NP\), no polynomial-time algorithm approximates SC-EF1 within an additive factor smaller than \((n-1)/(2n+2)\), again with normalized costs. The proof reduces from Partition-into-\((n-1)\)-sets; agents \(1,\ldots,n-1\) again share a cost vector, with agent \(n\) having another. This motivates a separate problem, CT-SC-EF1, with the same instance, supply, and objective as CT-SC-EQ1, but with this fairness condition: for every positive-mass \((t,A)\) and \((u,B)\), there must be \(j\in A\) such that \(c_t(A\setminus\{j\})\leq c_t(B)\). This retains EF1’s defining comparison: the worker evaluates both bundles using their own costs. My provisional expectation is also continuum-specific hardness, for the same support-selection reason. The paper’s proof is evidence for the relevance of this mirror, not a proof that its gap survives mass splitting.

The scale needs care. The paper’s social cost is a sum over \(n\) agents; these mirror objectives are per-worker averages because population mass is normalized to \(1\). For an empirical \(n\)-worker society, the corresponding total cost is \(n\) times the stated objective. Thus the theorems’ additive gaps translate to \(1/(2n)\) and \((n-1)/(n(2n+2))\) in the average-cost convention. They do not directly establish constant-gap hardness for the continuous questions. A natural follow-up is to determine whether either problem is tractable when type masses stay bounded away from zero, or whether bundle-support constraints retain hardness in that balanced regime.

I consider Theorem 5 the stronger anchor: its two-type construction makes the high-multiplicity connection especially visible, and EQ1 supplies a clean first mirror. Theorem 8 adds a distinct and meaningful EF1 question rather than another version of the same constraint. Both mirrors cover only the paper’s problems of minimizing social cost subject to fairness. They do not mirror its cost-of-fairness bounds or its two-agent approximation schemes.

My weakest point is the gap between repeated types and a genuinely large continuum of every type. In the paper’s reduction, the exceptional type has mass \(1/n\) in the empirical distribution, so it becomes vanishingly rare as \(n\) grows. A workforce with several substantial cohorts is a plausible application, but the paper does not establish hardness in that balanced-mass regime. Also, because the mirror scales chore supplies with population size, it is a co-modification of the original model. I think the authors would recognize the resulting question as their underlying fair cost-minimization problem, but whether they accept that supply-scaling as the right continuous variant is the key plausibility test.