| paper | d4-journals-geb-2024-0100 |
| 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: \(\mathsf{NP}\text{-hard}\) for every fixed rational \(1<c\leq 2\), even with equal dyadic masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Let \(T\) be a finite set of agent types, each with side, weight \(w_t\), compatible opposite-side types, and a strict ranking \(\succ_t\) over those types; let \(X_t\) be an atomless cohort of rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Copies of the same partner type are tied. A feasible matching \(\pi\) is a measurable one-to-one pairing of compatible agents, with unmatched agents allowed; write \(r_t^\pi(z)\) for the type of \(z\)’s partner, or \(\bot\) if unmatched, with \(\bot\) ranked last. Define \(\Delta(\pi,\pi')=\sum_{t\in T}\int_{X_t}w_t\bigl(\mathbf{1}[r_t^\pi(z)\succ_t r_t^{\pi'}(z)]-\mathbf{1}[r_t^{\pi'}(z)\succ_t r_t^\pi(z)]\bigr)\,d\lambda(z)\). Given the type graph and masses, does there exist a feasible \(\pi\) such that \(\Delta(\pi,\pi')\ge0\) for every feasible matching \(\pi'\)?
A two-sided atomless market with finitely many types, rational type masses \(\mu_t\), type-level weights and strict rankings over compatible partner types. A feasible matching pairs individual mass one-to-one, allowing each type’s mass to split across partner types; compare matchings on the same population, with copies of a partner type treated as interchangeable. The type-pair masses \(x_{ab}\) describe each matching’s marginals, while the popularity test compares the individual assignments across matchings.
The paper assumes strict rankings of named neighbors, so its agents cannot be interchangeable under the proposed shared ordering of individual copies; the repair ties copies of a partner type, and the paper does not establish how its theorem behaves under that preference extension.
fatal: False
The mirror covers Theorem 9’s existence problem for \(1<c\le2\) and the stated uniform side weights. It leaves aside Theorem 8’s restricted-weight hardness, Theorem 12’s maximum-utility inapproximability, and Theorem 24’s algorithm for \(c>3\).
The strongest mirror is Atomless Popular Matching with Weighted Type Populations, anchored on Theorem 9. A plausible regime is a large two-sided placement market: millions of applicants and positions, but far fewer distinct preference and voting-weight profiles. An applicant type records its side, weight, acceptable partner types, and complete ranking; a position type records the same information from the other side. Each type has a rational mass, with the number of people \(N\) much larger than the number of types \(\tau\). For example, one side could have voting weight \(c\) because its members represent constituencies, while the other side has unit weight.
Here is the problem I would hand to a prover. The input is a finite bipartite graph of compatible types, rational type masses \(\mu_t\), and strict preference rankings over compatible types. Represent each type \(t\) by an atomless set \(X_t\) of measure \(\mu_t\). To preserve strict rankings when a type contains many interchangeable people, use a shared public ordering within each type; thus every member of a type has the same complete ranking over individual partners. A feasible solution is a measurable one-to-one pairing \(\pi\) of population mass along compatible type pairs, with unmatched mass allowed. Each individual is matched to one individual or remains unmatched. The type-level edge mass \(x_{ab}\) may be fractional, because it records how much of each cohort is assigned across that edge.
Call \(\pi\) popular if, for every other feasible pairing \(\pi'\),
\[
\Delta_\mu(\pi,\pi') =
\sum_t \int_{X_t} w_t
\left(
\mathbf{1}[\pi(z)\succ_t \pi'(z)]
-
\mathbf{1}[\pi'(z)\succ_t \pi(z)]
\right)\,d\lambda(z)
\ge 0.
\]
The question is whether a popular pairing exists; a solution is such a pairing, or a report that none exists. The comparison is over individuals in the same underlying population, so the pairing itself—not just its type-to-type mass totals—specifies who gets which partner. This keeps the paper’s global pairwise vote criterion intact while making the population the continuous object.
Theorem 9, proved in this paper, says that for every constant \(c\) with \(1<c\le 2\), deciding whether a popular matching exists is NP-complete even when every vertex in \(A\) has weight \(c\) and every vertex in \(B\) has weight \(1\). The authors prove the hardness by reduction from 3-SAT, using variable, clause, and 6-path gadgets to encode a satisfying assignment as a popular matching and recover an assignment from any popular matching. They establish NP membership using the weighted-vote characterization cited earlier in the paper; the hardness reduction and the theorem are their result.
This is a close mirror of that underlying existence problem. Popularity remains a weighted majority comparison between matchings, and a matching remains a one-to-one assignment of individuals. Only the population representation changes: mass can divide among partner types even though each individual receives an integral assignment. That is a natural high-multiplicity question for this paper, whose motivation already treats weights as votes cast with multiplicity. It does not continuize outcomes into lotteries or turn the task into a question about matching axioms.
I would provisionally expect this mirror to be tractable (Class A). The 3-SAT reduction relies on discrete choices in its gadgets; an atomless cohort can split across those choices. The vote margin is linear in mass, and the paper’s witness characterization comes from LP duality, so a type-level flow and witness formulation seems plausible. That is a research conjecture, not an implication of Theorem 9: the prover would need to show that the matching variable and popularity comparisons admit a finite formulation, perhaps an LP with a manageable separation problem. The mirror covers only the existence result for \(1<c\le2\), not the paper’s maximum-utility result or its algorithmic regime \(c>3\).
The main questions it opens are whether existence is decidable in time polynomial in \(\tau\) and the mass bit length; whether the paper’s witness method extends to atomless pairings; and what dictionary holds between this problem and finite markets with \(N_t\) repeated agents of each type. In particular, does a popular continuous pairing imply popular matchings in sufficiently large finite blow-ups, or can divisibility create solutions that no finite blow-up has?
The weakest point is the treatment of preferences among copies of a type. The paper has strict rankings over named neighbors; an atomless cohort needs a shared within-type ordering to retain strictness, and that convention could affect pairwise comparisons. Also, Theorem 9’s reduction does not establish that its gadget choices remain meaningful when type mass can split. Those are precisely the right things to test: if the authors reject the shared ordering or show that the mirror has discarded the assignment distinctions their problem needs, this proposed formulation would need revision.
Theorem 9 is a real computational anchor, so the “no computational result to mirror” objection does not apply. The strongest case against it is that the paper’s matching problem does not have an obvious finite type population while preserving its strict, identity-specific preferences.
Each vertex is both a voter and a potential partner, and its preference list ranks named neighbors. If many copies of a vertex type are to be interchangeable, their partners must treat them alike. But strict rankings force every partner to distinguish those copies. The proposed shared public ordering supplies that distinction by rank: as the market grows, a copy’s position in that ordering becomes part of its description, and the number of types grows with the population. That undercuts the high-multiplicity compression the mirror is meant to study. It also means type-to-type edge masses alone do not record who prefers one matching to another: popularity compares the assignments of the same individuals across two matchings.
The best repair is to rank partner *types* and make copies within a type interchangeable. That gives a coherent atomless matching market, but it changes the voting model: copies of a partner type are now indistinguishable, so changing which particular copy someone receives can no longer affect their vote. One can instead keep strict preferences among copies, but then their rank positions must be represented, bringing back the growing type space. A proper type-level version might still be a worthwhile extension, and the authors could recognize it as the natural anonymous model. The paper alone does not establish that they would reject it.
There is adjacent work on popular fractional matchings, including results on the geometry of the finite-agent fractional matching polytope. That is not a collision: it continuizes the matching outcome, not the population, and does not settle the weighted type-population question.[Popularity, Mixed Matchings, and Self-Duality](https://pubsonline.informs.org/doi/10.1287/moor.2020.1063) Still, if the repaired mirror reduces directly to that framework, its novelty would need to come from the population and weight dimensions rather than from fractional matching itself.
So the strongest negative case is that the proponent’s strict-ranking formulation does not yet deliver a finite-support high-multiplicity instance; its natural repair changes how agents compare partners. That is a substantial modeling challenge, but it does not defeat every plausible type-level mirror. I cannot honestly support the universal claim that no worthwhile continuous mirror exists.
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.