| paper | Budget-feasible Egalitarian Allocation of Conflicting Jobs |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 11
statement extracted from the paper’s text layer
Given finite agent types \(A\) with rational masses \(\mu_a\), finite job types \(J\) with rational per-capita supplies \(\nu_j\), additive type-dependent utilities and costs \(p_a(j)\) and \(c_a(j)\), a common budget \(B\), and a type-level compatibility relation, decide for rational \(q\) whether nonnegative variables \(y_{a,b}\) assign every agent mass to a compatible bundle \(b\) containing at most two job copies, with \(p_a(b)\ge q\), \(c_a(b)\le B\), \(\sum_b y_{a,b}=\mu_a\), and \(\sum_{a,b}m_j(b)y_{a,b}=\nu_j\) for every \(j\); equivalently, maximize \(q\).
A finite configuration or transportation LP over agent types \(a\), job types \(j\), and singleton or pair bundles \(b\), using mass variables \(y_{a,b}\), egalitarian threshold \(q\), exact agent-mass and job-supply constraints, and type-level conflicts.
Theorem 11’s matching reduction is tied to identical utility and cost functions, whereas a nontrivial agent-type distribution yields agent–bundle hyperedges and the finite conflict catalogue restricts the paper’s arbitrary conflict graphs.
fatal: False
The mirror covers the paper’s \(s=2\) exact allocation and optimization slice, while leaving the hardness results, unrestricted bundle sizes, structural parameterized algorithms, and approximation schemes unmirrored.
The strongest positive case is a narrow, result-specific mirror of the paper’s bundle-size-two regime.
My lead anchor is Theorem 11, proved in this paper: “When \(s=2\), BCFEA admits a polynomial-time algorithm.” The mirror is Typed \(2\)-BCFEA\(_\infty\).
There are finitely many agent types \(A\), with rational masses \(\mu_a\) satisfying \(\sum_a\mu_a=1\), and finitely many job types \(J\), with rational per-capita supplies \(\nu_j\). An agent type completely specifies the additive utility and cost of every job type, \(p_a(j)\) and \(c_a(j)\), together with any type-specific budget parameters. A job type also specifies its conflict behaviour: a compatibility relation determines which pairs of job copies may occur in one bundle. Thus agents and jobs are interchangeable exactly when the original problem treats them identically.
For a target egalitarian level \(q\), let \(\mathcal B_a(q)\) be the set of compatible bundles for type \(a\) consisting of at most two jobs, satisfying
\[ p_a(b)\ge q,\qquad c_a(b)\le B. \]
The decision problem asks whether there are nonnegative variables \(y_{a,b}\), where \(y_{a,b}\) is the mass of type-\(a\) agents receiving the complete bundle \(b\), such that
\[ \sum_{b\in\mathcal B_a(q)}y_{a,b}=\mu_a \]
for every agent type \(a\), and
\[ \sum_{a}\sum_{b\in\mathcal B_a(q)}m_j(b)y_{a,b}=\nu_j \]
for every job type \(j\). Here \(m_j(b)\in\{0,1,2\}\) counts copies of \(j\) in \(b\). The optimization version maximizes \(q\).
This is a genuine continuous population problem. A positive \(y_{a,b}\) does not mean that one agent receives a fractional job: it means that a corresponding subpopulation of identical agents receives the whole bundle \(b\). With bundle size at most two, there are only \(O(|A||J|^2)\) possible configurations, so the formulation is a rational transportation LP of polynomial size. Hence I expect, and in this formulation directly obtain, a Class A result.
The regime is plausible in large-scale shift assignment: millions of workers may fall into a small catalogue of qualification, shift, contract, and preference types, while jobs recur by a small catalogue of time-slot and skill types. Each worker receives at most two tasks, conflicting tasks cannot share a worker, workload is bounded by \(B\), and every worker must reach satisfaction \(q\). This preserves the paper’s budget, conflict-free, and egalitarian structure. It is not merely fractional allocation: every infinitesimal agent receives an indivisible one- or two-job bundle.
The high-multiplicity bridge is exact. A finite typed instance with \(M\) agents maps to \(\mu_a=n_a/M\) and \(\nu_j=N_j/M\). Conversely, any rational solution \(y\) can be multiplied by a common denominator to produce a finite clone population in which every agent receives a whole bundle. Thus the continuous problem is the high-multiplicity version of the paper’s \(s=2\) problem, not an unrelated divisible-goods model.
I would not claim that Theorem 1’s NP-hardness transfers. Its Partition reduction relies on many individually distinguished item sizes; after aggregation, divisible mass of one job type can often be routed continuously, destroying the subset-sum obstruction. That is a feature of the mirror, not a defect: the proposed question asks where the population-multiplicity hardness disappears.
The weakest point is that this covers only the paper’s \(s=2\) slice and assumes a finite conflict-type catalogue. If conflicts encode unique pairwise relationships, then the number of job types approaches the number of jobs and the high-multiplicity interpretation loses force. But the restriction is anchored by the paper’s own Theorem 11, is practically defensible, and retains the paper’s core problem rather than replacing it with average welfare or fractional goods. The natural next questions are whether the same LP/configuration approach extends to fixed \(s>2\), and when unrestricted bundle sizes require a genuinely difficult pricing problem.
The case against rests on a mismatch between the proposed mirror and the result it claims to mirror.
Theorem 11 is proved in the paper’s identical-utility-and-cost setting. There, when \(s=2\), every feasible singleton or pair is simply an edge in an auxiliary graph on the items, and the problem reduces to matching. Agent identities do not affect which bundles are feasible. The proposed formulation instead allows \(p_a(j)\) and \(c_a(j)\) to vary with the agent type \(a\). Then a pair of jobs may be feasible for one agent type but not another. The relevant objects are hyperedges consisting of an agent type and one or two jobs, not the matching instance of Theorem 11. This is a new typed allocation problem, not a continuization of the named theorem.
The faithful continuization of Theorem 11 fares poorly as a population model. If utilities, costs, and budgets are identical across agents, then all agents are one type for the purposes of the problem. The distribution \(\mu\) is therefore vacuous: only the total agent mass matters. The nontrivial masses in the proposed LP are the job supplies \(\nu_j\). Thus the construction continuizes the supply of items, not the society of agents, which is outside ChoCo’s stated scope.
The proponent can try to repair this by retaining heterogeneous agent types. But then the theorem’s matching structure has been abandoned. Or they can try to preserve the arbitrary conflict graph by treating every job’s neighbourhood as part of its type. That is required by the programme’s own definition of type: two jobs are interchangeable only if they have the same conflict behaviour as well as the same utility and cost data. For an arbitrary conflict graph, this usually makes every job a distinct type. The finite-type LP then disappears.
The remaining option is to impose a finite catalogue of job types and a type-level compatibility relation. This restricts the conflict graph to a blow-up of a fixed finite template. That may describe recurring shift slots, but it is a different structured scheduling model, not the high-multiplicity regime of the paper’s graph-constrained allocation problem. The paper’s arbitrary item-level conflict structure has been replaced by a uniform compatibility schema.
There is also a genuine degeneracy if one tries to make only the agent population large while retaining finitely many indivisible jobs. Since \(s=2\) and every item must be allocated, \(n\le 2k\). With \(n\) fixed and \(k\) tending to infinity, almost all agents receive nothing, so any positive egalitarian threshold disappears. Making \(n\) grow as well avoids that collapse only by introducing a growing population of jobs; with arbitrary conflicts, those jobs are again mostly distinct and cannot be represented by a fixed type space.
The exact rational-cloning argument therefore establishes that the proponent’s LP is a coherent high-multiplicity model of a new, two-sided typed allocation problem. It does not establish that Theorem 11 has a worthwhile continuous *population* mirror. Under a strict reading of ChoCo, the anchor should fail: with identical agents the population axis is empty; with heterogeneous agents the theorem being mirrored has changed; and with arbitrary conflicts the finite type space disappears.
The weakness in this negative case is that the proposed recurring-shift scenario is genuinely plausible if ChoCo permits two-sided high multiplicity and blow-up conflict graphs. In that broader interpretation, the mirror is well-posed and the negative verdict cannot honestly be universal. The strongest defensible conclusion is therefore a strict-scope “no” rather than a proof that the underlying typed LP is uninteresting.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.