| paper | d4-conf-ecai-2024-0156 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(O(L)\) time. Equality holds if and only if \(|B|=1\); whenever \(|B|>1\), \(\sum_{a,b}z_{ab}\le |B|-1+\max_b\nu_b<|B|\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given finite type sets \(A,B\), positive rational masses \(\mu_a,\nu_b\) with \(\sum_{a\in A}\mu_a=\sum_{b\in B}\nu_b=1\), and strict rankings of \(B\)-types by each \(A\)-type and of \(A\)-types by each \(B\)-type, run mass deferred acceptance: each unmatched \(A\)-mass proposes in ranking order, each \(B\)-type retains up to \(\nu_b\) mass according to its ranking, and rejected mass advances. Let \(z_{ab}\) be the total mass of type \(a\) that proposes to type \(b\). Decide whether \(\sum_{a\in A,b\in B} z_{ab}=|B|\), the universal upper bound when each unit of mass proposes to each \(B\)-type at most once.
A two-sided placement market with finite support \(A,B\), rational type masses \(\mu,\nu\), and strict type-level rankings. The measured proposal flows \(z_{ab}\) and retained allocation \(x_{ab}\) are mass quantities; the decision predicate is whether mass DA reaches the proposal-volume ceiling \(\sum_{a,b}z_{ab}=|B|\).
For fixed masses, \(|B|\) is a universal upper bound, not necessarily the attainable maximum, so this predicate can be stricter than MaxProp.
fatal: False
The mirror addresses only Theorem 6’s MaxProp-recognition aspect. It does not transfer the \(O(n)\) verifier to rational support size or cover MaxRou, Theorem 3’s uniqueness implication, Theorem 4’s characterization, or the SPC/NCC comparisons and \(n=2\) results.
The strongest positive case is narrow: the paper’s maximum-proposal condition has a plausible high-multiplicity version in large placement markets. Think of a national placement round with many applicants and many unit slots. Slots can be treated as the receiving side of a one-to-one market. Applicants sharing a complete ranking over slot types form a type, as do slots sharing a ranking over applicant types. There may be hundreds of thousands of agents but only tens or hundreds of positive-mass types. The mass of a type is its fraction of that year’s market.
Here is a concrete problem to hand a prover: Cohort-MaxProp Recognition. An instance consists of finite type sets \(A\) and \(B\), rational masses \(\mu_a,\nu_b\geq 0\) summing to \(1\) on each side, and strict rankings \(\succ_a\) over \(B\) and \(\succ_b\) over \(A\). Run mass deferred acceptance: unmatched mass of type \(a\) proposes to its most-preferred type it has not tried; type \(b\) retains its most-preferred offers up to capacity \(\nu_b\), and rejected mass continues. Let \(z_{ab}\) be the mass of type \(a\) that proposes to \(b\). Each pair is tried at most once, so the maximum possible proposal volume is \(\sum_{a,b}z_{ab}=|B|\). The decision question is whether the weighted DA run attains that maximum. A solution is a yes/no answer; on yes instances, it can also provide the rational proposal-mass table and the resulting allocation \(x_{ab}\). The objective is this maximal proposal-volume predicate, not an optimization over matchings. The allocation is a mass flow because type totals need not yield integral bundles.
My computational anchor is Theorem 6, proved in this paper: for an ordinary \(n\)-by-\(n\) preference profile, both isMaxProp and isMaxRou can be checked in \(O(n)\) time. I rely on its isMaxProp assertion; the theorem’s full statement also gives the same \(O(n)\) bound for isMaxRou. The paper’s Theorem 3 supplies the reason MaxProp matters: every MaxProp profile has a unique stable matching. And Theorem 4 explains the structural route behind the verifier: a common last-ranked woman, paired first and penultimate choices, and an acyclicity condition on second choices characterize MaxProp. Those results are proved here, rather than merely cited.
The continuous question is whether that kind of certificate survives when a society is a distribution over cohort types. I expect Cohort-MaxProp Recognition to be tractable in the support size and input bit length: the type-level DA process has finitely many type pairs and rational mass thresholds, and the paper suggests looking for a direct structural test instead of simulating DA. Whether a weighted analogue of Theorem 4 provides that test is open within this proposed mirror. A further question is whether maximal proposal volume implies a unique stable mass allocation, as Theorem 3 gives uniqueness in the finite model. That implication should be proved, not assumed.
This mirrors the paper’s DA-extremality question, with population mass as the input object; fractional \(x\) is the matching representation forced by that population model. It covers the MaxProp verification result and its connection to uniqueness, not the paper’s full comparison of MaxProp with SPC, NCC, or its \(n=2\) cases. High-multiplicity matching markets support the plausibility of the regime, but do not themselves establish a novelty collision.
My weakest point is the bridge from individual rankings to type rankings. In the paper, agents rank named individuals; here, agents rank types and DA can divide a cohort’s mass as rejections arrive. Also, finite MaxProp singles out one woman, whose normalized mass vanishes as the market grows. The all-type proposal-volume condition is a natural limit of that extremal behavior, but it is not an exact finite-to-continuous identity. A two-way dictionary—and confirmation that the authors regard type-level DA as their problem—would be needed to firm up the mirror.
The proposed anchor is Theorem 6, but its \(O(n)\) verifier depends on an identity-level extreme. Theorem 4 characterizes MaxProp using an ordering of individual men and women: one woman is every man’s last choice, while each other woman is paired with a particular man who ranks her penultimate. MaxProp’s proposal count also relies on one named woman receiving exactly one proposal. In a cohort model, proposals carry divisible mass. There is no corresponding “one proposal” event for an individual of measure zero, and no canonical pairing of the \(i\)-th man with the \(i\)-th woman. Rank partners by type and allow mass to split, and you have changed both the certificate and the matching object; keep named partners, and the proposed type compression loses information the paper’s conditions use.
There is also a gap in the proposed extremality predicate. The bound \(\sum_{a,b} z_{ab}\leq |B|\) follows because each unit of type-\(a\) mass can propose to each type in \(B\) at most once. But that bound is not shown to be the attainable maximum in the mass market. With balanced positive capacities, some mass is accepted in the first round and therefore stops proposing; the paper’s exact finite maximum, by contrast, is derived from its discrete proposal structure. Asking whether the run attains \(|B|\) is thus not yet a mass analogue of MaxProp. Replacing the bound with the true maximum for weighted markets might define a worthwhile problem, but it would require a new extremal characterization rather than a translation of Theorem 4 or its verifier.
Theorem 3’s uniqueness result does not bridge that gap. It is a consequence of the individual-level MaxProp structure, so it does not establish uniqueness for a mass allocation. There are established continuum matching models with their own stability definitions and DA analogues: Azevedo and Leshno study a continuum of students matched to finite colleges, and Arnosti gives a continuum model with finite capacities and a DA analogue that yields a unique stable outcome ([Azevedo and Leshno](https://www.journals.uchicago.edu/doi/10.1086/687476), [Arnosti](https://arxiv.org/abs/2205.12881)). That work is not a computational-complexity collision, but it makes a new uniqueness question less distinctive; the proposal does not yet identify what complexity question remains after adopting those models.
So the proponent has not established a worthwhile mirror of this paper’s MaxProp results. The strongest replacement would be a new complexity study of weighted DA extremality or uniqueness for a precisely specified typed market. That could be valuable, but the paper’s named results do not yet supply its central problem or certificate. I would argue against this paper as a strong ChoCo anchor; I cannot honestly conclude that no author-recognizable continuous matching question exists in any scenario.
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.