| paper | d4-conf-wine-2009-0052 |
| 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}\text{-complete}\): a qualifying priority order exists exactly when \(H\) has a Hamiltonian path. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 4
statement extracted from the paper’s text layer
Given a type graph \(H=(T,E)\) with \(\tau\) worker types of mass \(1/\tau\), and \(\tau\) firms each with capacity \(1/\tau\), all types share the strict firm ranking \(f_1 \succ \cdots \succ f_\tau\), and firms share a strict priority order \(\pi\) over types. A complete mass matching is an array \(x_{t,f} \ge 0\) whose row and column sums are all \(1/\tau\). For each edge \(\{t,u\} \in E\) with \(t \succ_\pi u\), local stability requires \(x_{t,f_j}x_{u,f_i}=0\) whenever \(i<j\). Does there exist an order \(\pi\) for which exactly one complete locally stable mass matching exists?
A continuous population over finitely many worker types, with mass \(1/\tau\) per type and a referral graph on types. Firms have finite per-capita capacities, workers share a strict ranking over firms, and firms prioritize types by one strict order. The decision variable is that priority order; the outcome is the aggregate type-to-firm mass assignment.
The paper’s hardness reduction uses distinct individual priorities and arbitrary worker neighborhoods, whereas this mirror gives each cohort one priority and shared referral links; the paper does not establish the result for that block-network model.
fatal: False
The mirror covers Corollary 4’s uniqueness-under-priority-order question. It leaves aside the lattice result, convergence of the local Gale–Shapley algorithm, and the efficiency bounds in Theorems 7 and 8.
My lead—and only anchor—is Corollary 4, proved in this paper. It says that, given a worker social graph \(G\) and \(k\), it is NP-complete to decide whether there is a labeling of the workers such that, when every firm ranks workers by that labeling, the complete locally stable matching is unique. The proof reduces the \(k=1\) case to Hamiltonian path: Theorem 2 characterizes locally stable matchings as topological orderings of an oriented version of \(G\), and Lemma 2 characterizes when that ordering is unique. Those are proof ingredients, not extra anchors. Corollary 4 is the paper’s clearest computational-complexity result.
A plausible regime is a large hiring market divided into occupational, location, and credential cohorts, with many applicants in each cohort. The mirror assumes that people in a cohort share their employer ranking and their referral neighborhood: if two cohorts are linked, every worker in one can learn about jobs held by workers in the other. This is a strong but coherent version of a block-structured professional network. The number of workers \(N\) can be \(q\tau\), with \(q\) people per cohort and \(\tau\) cohorts; the continuous input records cohort masses rather than listing those \(N\) people. A high-multiplicity version of the job supply scales with the worker mass.
I would ask a prover to study Continuous Cohort Priority-Order Uniqueness. Its instance is a cohort graph \(H=(T,E)\) with \(\tau\) worker types, each of mass \(1/\tau\), and total job capacity \(1\). Jobs have a strict common rank \(r\in[0,1]\): every worker prefers a lower rank. All employers use one strict priority order \(\pi\) over worker types, which is the decision variable. An edge in \(H\) means workers in those cohorts can refer one another to employers. A complete mass matching is a family of measures \(x_t\) on job ranks, with \(x_t([0,1])=1/\tau\) and \(\sum_{t\in T}x_t=\lambda\), where \(\lambda\) is the uniform job-capacity measure.
For every edge oriented \(t\to u\) when \(\pi\) prioritizes \(t\) over \(u\), local stability requires \((x_t\otimes x_u)\{(r,s):r>s\}=0\). Otherwise some mass of higher-priority workers is at worse-ranked jobs than lower-priority workers they can reach, creating a visible blocking pair. The question is: does there exist an order \(\pi\) for which the set of complete locally stable mass matchings contains exactly one matching? A yes solution is such an order and its unique mass assignment. There is no welfare objective in this anchor; the decision is whether the equilibrium prediction is unique.
I expect Class B: hardness transfers, with a particularly direct explanation. For a fixed \(\pi\), orient \(H\)’s edges from higher to lower priority. Each topological ordering gives a stable assignment that places the types, in that order, on consecutive rank intervals of length \(1/\tau\). If the orientation has more than one topological ordering, these give distinct assignments. If it has exactly one, its consecutive edge constraints force the unique interval assignment. Thus an order yielding uniqueness exists exactly when \(H\) has a Hamiltonian path. On this equal-mass restriction, the mirror appears to have the same yes-instances as Hamiltonian path and therefore to be NP-complete. The combinatorics survive because they lie in the graph of distinct cohort types, not in the number of people within a cohort. Natural follow-ups are how this behaves for unequal rational masses and whether restrictions on \(H\) make the problem tractable.
The scope is deliberately narrow: this mirrors Corollary 4’s uniqueness-under-priority-order result, not the paper’s convergence or efficiency-loss results. The authors could recognize the question: it preserves the local-visibility rule, aligned rankings, and the question of whether stable outcomes are uniquely predictable, while treating indistinguishable workers as mass.
The weakest point is the network regime. Exact type identity requires identical referral neighborhoods; ordinary sparse, person-specific networks may force \(\tau\) close to \(N\), leaving little high-multiplicity compression. The mirror also asks for uniqueness of the aggregate type-to-job assignment, whereas Corollary 4 asks for uniqueness among individually labeled matchings. That quotient is a natural consequence of treating genuinely indistinguishable agents as one type, but it is a real modeling change that the authors would need to accept.
Corollary 4 is a genuine computational result, so the strongest available objection is about whether its hard instances have a high-multiplicity regime. The reduction uses the workers as the vertices of a Hamiltonian-path instance. Under Assumption 1, firms rank every worker strictly, giving each worker a distinct priority. A type must include that priority and the worker’s referral neighborhood. Consequently, workers cannot be grouped into positive-mass types while preserving the theorem’s model: its natural representation has \(\tau=N\), with each worker carrying mass \(1/N\). That is a continuous encoding of a finite graph, not compression of a large population into repeated types.
The best proposed mirror groups workers into cohorts, gives every cohort a common priority, and treats links between cohorts as referral access across the whole pair of cohorts. This is coherent, and its equal-mass version appears to preserve the Hamiltonian-path question: a priority order yields a unique aggregate allocation exactly when the induced graph orientation has a unique topological order. The obstacle is that this changes the object in Corollary 4. Workers within a cohort no longer have strict, distinct priorities, and the referral graph becomes a block network. The paper’s theorem does not establish the result for that model. Its mirror also asks for uniqueness of a type-to-rank mass allocation, which deliberately forgets which named worker gets which job.
That leaves a real but limited negative case: the paper’s own hardness result does not demonstrate hardness in a high-multiplicity population. A cohort version would be a new, plausible extension whose relevance depends on whether the authors regard block networks and cohort-level priorities as their problem. I cannot honestly turn that limitation into a universal objection. The proposed cohort model has a natural interpretation and a clear computational question, so this anchor remains difficult to defeat; the case against a worthwhile mirror is weak on the material provided.
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.