| paper | d4-conf-ecai-2025-0542 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given student types \(T\) with rational masses \(\mu_t\), schools \(S\) with per-capita capacities \(q_s\), strict student preferences, school priority orders over types, and an acquaintance graph \(H\) on types, does there exist an assignment of individuals to schools or to being unmatched whose aggregate masses \(x_{t,s}\) satisfy \(\sum_s x_{t,s}=\mu_t\) and \(\sum_t x_{t,s}\le q_s\), and which is locally envy-free and Pareto efficient? Interpret each edge of \(H\) as acquaintance between every individual in its endpoint cohorts; local envy occurs when positive mass of type \(t\) prefers school \(s\) to its assignment, positive mass of adjacent type \(u\) attends \(s\), and \(t\) has higher priority than \(u\) at \(s\). Pareto efficiency rules out any feasible reassignment that weakly improves almost every individual and strictly improves a positive mass.
A distribution over complete student types, including preferences and priority class, with a cohort-level acquaintance graph \(H\). The decision variables \(x_{t,s}\) are masses of type \(t\) assigned to each school or unmatched; every individual receives an integral assignment, while the aggregate may be fractional.
An edge between positive-mass types makes their cohorts mutually acquainted, so the mirror covers block-dense cohort networks rather than preserving the paper’s sparse individual networks.
fatal: False
Covers Theorem 4’s existence question for cohort-level locally envy-free and Pareto-efficient assignments; it leaves the other existence, impossibility, and mechanism results unmirrored.
The strongest mirror is the paper’s LEE problem, because it is anchored in a hardness result about the paper’s central fairness and efficiency concepts.
Anchor — Theorem 4, proved in this paper. The theorem says that deciding whether a given matching market with a student acquaintance graph has *any matching that is both locally envy-free and Pareto efficient* is NP-complete. The paper proves membership by noting that local envy-freeness and Pareto efficiency can be checked in polynomial time; it proves hardness by reducing from the NP-hard SD-feasibility problem of Saban and Sethuraman, cited as [37, Theorem 2]. The reduction adds a student and a school and uses the acquaintance graph and priorities to force a designated student–school pair. Thus the hardness is proved here, though the source problem is cited.
My lead mirror would be Continuous LEE. An instance has a finite set \(T\) of student types, each with mass \(\mu_t\ge 0\), where \(\sum_{t\in T}\mu_t=1\); a set of schools \(S\) with per-capita capacities \(q_s\); strict school preferences \(\succ_t\) over schools and being unmatched; school priority orders \(\succ_s\) over types; and an acquaintance graph \(H\) on the types. A type records everything relevant here: the student’s preferences, priority class, and cohort role in the acquaintance structure. An edge in \(H\) means that students in those two cohorts count as acquaintances for the local-envy test.
The population is atomless within each type. An assignment gives each individual one school or leaves them unmatched, while its aggregate is \(x_{t,s}\), the mass of type \(t\) assigned to \(s\). It must satisfy
\[
\sum_{s\in S\cup\{\varnothing\}}x_{t,s}=\mu_t,
\qquad
\sum_{t\in T}x_{t,s}\le q_s.
\]
Ask whether there is such an assignment that is locally envy-free and Pareto efficient. Local envy is a violation if adjacent types \(t,u\) have positive mass with \(u\) assigned to \(s\), positive mass of \(t\) assigned to a less-preferred option, and \(t\succ_s u\). Pareto efficiency means there is no feasible reassignment that makes almost every individual weakly better off and a positive mass strictly better off. A solution is an assignment of individuals to schools, or equivalently its type-by-school mass totals together with a partition realizing them.
This is a sensible high-multiplicity regime for large school-admissions markets: there may be tens of thousands of students but relatively few preference, priority, and community-role types. The acquaintances could represent feeder-school or residential cohorts in a district where fairness concerns apply across familiar groups. Capacities then scale with the population, and fractional \(x_{t,s}\) records a type’s average allocation without giving any individual a fractional school assignment. That preserves the paper’s Pareto and envy questions rather than replacing them with an outcome-space relaxation.
I think the authors would recognize Continuous LEE as a real extension of their problem: it asks the same existence question using the same two properties, with mass replacing headcounts. Its complexity is open. I would tentatively expect hardness to remain, perhaps for continuum-specific reasons, because local-envy constraints and Pareto efficiency interact through choices of which types receive which schools. But Theorem 4 alone does not establish that prediction. Its reduction uses named students and the combinatorics of SD feasibility; fractional cohort assignments may change those choices. Calling the mirror Class B would require a discrete-to-continuous embedding that preserves the answer. I would investigate hardness and exact algorithms as functions of \(m\), \(\tau\), and input bit length, and whether restrictions such as bounded acquaintance-graph treewidth make the problem tractable.
The soft spot is the cohort acquaintance model. In the paper, acquaintances are individual edges, so a type-level edge compresses those relationships into a relation between cohorts; priorities within a type also become a common priority class. Those are substantive co-modifications. If a referee requires exact individual networks and strict within-cohort priorities, this mirror may not qualify as a high-multiplicity version. The positive case is that the paper’s local-fairness idea is explicitly defined through an acquaintance relation, and cohort-level familiarity is a plausible large-market version of that relation.
Theorem 4 is a genuine computational anchor: it proves that LEE is NP-complete. The strongest objection is that its hardness is built around named students and a designated student–school pair in the reduction from SD feasibility. If each student’s preferences, priority position, or graph role makes them a distinct type, the type support grows with the instance and there is no high-multiplicity compression. If students are duplicated into cohorts, the continuous model permits mass to split across schools, so the reduction’s designated-pair argument no longer carries over. That does not make the continuous question uninteresting; it means Theorem 4 alone gives little reason to expect a faithful continuous mirror.
The proposed type graph also struggles to preserve the paper’s defining local structure. In a large sparse acquaintance network, such as a path or a bounded-treewidth graph, only a vanishing fraction of pairs are adjacent. An edge between two positive-mass types instead treats their cohorts as related at positive scale; treating an edge as only a few individual links makes it disappear in the atomless limit. A useful limit would need to retain neighborhood or component structure, which the proposed distribution over student types does not encode.
A better version could model a population of repeated, fixed-size acquaintance groups, with types describing roles inside each group and allocations keeping each student’s assignment integral. That is a plausible high-multiplicity regime. But it becomes a configuration problem over whole groups, and Theorem 4 does not establish that its hardness survives aggregation. I cannot honestly rule out that mirror: the programme’s scope permits the necessary co-modification, and the resulting question is well-posed.
So the negative case is limited. It defeats the proposed type-level graph as a general mirror and weakens Theorem 4 as evidence for continuous hardness. It does not support the universal claim that no worthwhile mirror exists in any scenario; repeated-group markets remain a credible, narrower candidate.
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.