| paper | Dividing Conflicting Items Fairly |
| authors | Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda |
| venue | IJCAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 14(1)
statement extracted from the paper’s text layer
Given a finite conflict graph \(G=(M,E)\), rational per-agent resource capacities \(q_g\), and finitely many complete agent types \(T\) with rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\), where each bundle contains at most one copy of each resource label and must be an independent set of \(G\), decide whether there exist masses \(\pi_{t,S}\ge0\) over types \(t\) and independent-set bundles \(S\) such that \(\sum_S\pi_{t,S}=\mu_t\), \(\sum_{t,S:g\in S}\pi_{t,S}\le q_g\), every pair of bundles in the positive support satisfies support-wise EF1 under \(v_t\), and every resource with positive residual supply is blocked by every positive-support bundle. The search version must output such a family \(\pi\).
A high-multiplicity allocation of replicated courses, shifts, or positions: \(\mu_t\) is cohort mass, \(q_g\) is per-capita supply, \(\pi_{t,S}\) is mass assigned to independent-set bundle \(S\), and feasibility requires support-wise EF1 and residual-supply maximality.
The paper's fixed-\(n\) reduction does not establish hardness for the capacity-scaled model, and the precise blow-up semantics for repeated resources must be stipulated rather than inferred from \(G\) and \(q_g\).
fatal: False
The mirror covers the multi-agent maximal-EF1 existence problem underlying Theorem 14(1), including its independent-set conflict structure. It does not directly cover the two-agent algorithm of Theorem 10, the finite counterexamples, or the paper's other existence and chore results.
The strongest positive case is a high-multiplicity extension of the paper’s maximal-EF1 problem, rather than a literal replacement of its finite agent set by an atomless one.
The anchor is Theorem 14(1), proved in this paper: “determining whether a maximal EF1 allocation exists is NP-hard for any fixed \(n\ge4\), even for identical and additive valuation.” The reduction is proved through Lemma 15, from Independent Set; the Independent Set hardness itself is cited to Karp (1972). I would not use Theorem 11 as a primary anchor: it is a finite counterexample for three agents with non-additive valuations, and cloning may change its behaviour.
Call the continuous problem HM-Maximal-EF1 under Conflicting Resources. An instance consists of:
The intended regime is a large university, employer, or scheduling system: millions of students or workers, perhaps only dozens of valuation/eligibility types, and many repeated course sections, shifts, or positions. Agents of one type have identical valuations, eligibility, prices, and all other problem-relevant data. The conflict graph says which resource labels cannot occur together in one bundle. Copies remain indivisible; \(q_g\) is only their density per agent.
A solution is a family of numbers \(\pi_{t,S}\), where \(S\) ranges over independent sets of \(G\), and \(\pi_{t,S}\) is the mass of type-\(t\) agents receiving the discrete bundle \(S\). It must satisfy
\[ \sum_{S}\pi_{t,S}=\mu_t \]
for every \(t\), and
\[ \sum_{t,S:g\in S}\pi_{t,S}\le q_g \]
for every resource \(g\).
The allocation is EF1 in the original, individual sense—not merely in expectation—if, whenever \(\pi_{t,S}>0\) and \(\pi_{u,R}>0\), either \(R=\varnothing\), or some \(g\in R\) satisfies
\[ v_t(S)\ge v_t(R\setminus\{g\}). \]
It is maximal if every resource with unused supply is blocked for every bundle appearing with positive mass: for every \(t,S\) with \(\pi_{t,S}>0\) and every \(g\) with positive residual supply, either \(g\in S\) or \(g\) is adjacent in \(G\) to some member of \(S\). The decision problem asks whether such a \(\pi\) exists; the search version must output one.
This is a genuine high-multiplicity formulation. Given a finite population of size \(N\), \(\mu_t=n_t/N\), \(q_g=r_g/N\), and \(\pi_{t,S}=n_{t,S}/N\), where \(r_g\) is the number of indivisible copies of resource \(g\). Conversely, any rational \(\pi\) can be denominator-cleared into a finite allocation of discrete bundles. Thus the continuous variables record frequencies of discrete bundles, not fractional goods or averaged utilities. The original one-copy-per-good instance is the special normalization \(q_g=1/n\); the large-population regime scales both agents and resource copies so that fairness does not become vacuous.
This should be recognizable to the authors. Their motivating applications already include courses, overlapping work shifts, and job scheduling. The proposed mirror preserves the central objects exactly: independent-set bundles, a conflict graph, additive valuation, maximality, and EF1. What changes is that a large cohort is represented by type masses and repeated resource supply. It is therefore an extension of their question, not a tractability-driven replacement by a different fairness notion.
I would expect this problem to be Class B, with hardness transferring. The paper’s reduction does not exploit named-agent identities or arbitrary valuation heterogeneity; its combinatorial core is an Independent Set choice inside the resource conflict graph. Any configuration formulation over bundle types faces independent-set pricing or separation on \(G\), which remains difficult even when the population has one homogeneous type. In that sense the source of hardness lies in the agenda of conflicting resources, not in population multiplicity.
The main further questions are whether the NP-hardness of Theorem 14(1) survives the chosen resource-supply scaling; whether every feasible instance has a polynomial-support rational solution; and whether the support constraints admit a useful configuration LP or separation oracle. A related positive question is whether the additive two-agent algorithm of Theorem 10, also proved here, extends to a genuinely large-cohort version with the same scaled indivisible-resource semantics.
The weakest point is substantial: the paper’s theorem fixes \(n\ge4\), while the proposed mirror has \(N\to\infty\) agents and proportionally many resource copies. Homogeneity can change fair-division feasibility—the paper itself makes clear that duplication may improve fractional or high-multiplicity behaviour—so Theorem 14(1) does not automatically reduce to this continuous problem. A literal atomless-agent model with only the paper’s finitely many goods would also fail: almost every agent would receive nothing, and maximality or EF1 would become degenerate. The positive case therefore depends on accepting joint population/resource scaling as the natural high-multiplicity regime for indivisible allocation. If that extension is admissible, this is a precise and author-recognizable mirror; if only fixed-resource continuization is allowed, the case is much weaker.
The proponent has identified the strongest possible rescue, and it exposes why the negative case cannot honestly be universal. But their anchor is still not a faithful continuization of the paper’s result.
Theorem 14(1) concerns a fixed \(n\ge4\), one copy of each good, and identical additive valuations. Merely cloning the agents with the same finite goods is degenerate: almost everyone receives \(\varnothing\), while maximality and EF1 are governed by a finite set of exceptional recipients. The proposed repair scales resource supply as well as population. That is sensible, but it is no longer the paper’s instance regime.
More importantly, \(G\) and the capacities \(q_g\) do not determine the resulting indivisible-resource model. To realise \(q_g\) copies of good \(g\), one must decide whether copies of \(g\) conflict with one another, whether they have identical values, and whether copies of adjacent goods form a complete blow-up of the original graph. If copies of \(g\) form a clique, the result is a capacity-constrained blow-up problem; if they do not, an agent may receive multiple copies of what was one good. Denominator clearing therefore gives a finite realization of the proponent’s new model, not a rational-clone equivalence with the paper’s model.
The paper’s hardness reduction does not repair this gap. Its fixed-size bad gadget and its \(n\) agent roles rely on exactly \(n\) bundles. With many homogeneous clones, agents can redistribute across many bundles and the gadget’s EF1 gap need not survive. Restoring the roles requires protected cohorts, eligibility restrictions, or extra agent types. Those are reasonable modelling choices, but they make the source of the problem the newly introduced cohort structure rather than Theorem 14 itself.
The support-wise EF1 condition also means that the proposed “continuous” variable does not smooth the fairness problem. If \(\pi_{t,S}>0\) and \(\pi_{u,R}>0\), the condition must hold for that pair regardless of how tiny either mass is. Thus feasibility depends primarily on selecting a globally compatible support of integral bundles; the masses then solve capacity equations. This is a coherent configuration problem, but it is not an LP-like population relaxation in which fractional mass softens the original combinatorics.
Theorem 10 does not provide a second anchor. Its algorithm is intrinsically a two-agent cut-and-choose construction, using a chain of allocations and a sign change between two bundles. Keeping two agents leaves no population-continuization. Cloning them creates many agents and an all-pairs EF1 condition, for which the chain and cut-and-choose argument no longer apply. Restricting the population to two protected cohorts would again define a new two-cohort problem.
So the strongest negative conclusion is limited: the proponent has shown a plausible replicated-course or replicated-shift extension, not a direct continuous mirror of the paper’s computational results. The negative case is therefore not airtight. With joint population/resource scaling accepted, the extension is author-recognizable and could be worth studying as a new Class-B or Class-C configuration problem. I would reject a claim that the paper has no worthwhile mirror in any scenario; I would only reject calling this particular construction a faithful continuization of Theorem 14 or Theorem 10.
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.