| paper | d4-conf-sagt-2017-0006 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 4 is a genuine computational result, but the proposed mass version changes its defining incentive guarantee: coalitions whose mass vanishes are no longer covered. The suggested priority-coordinate repair would introduce a continuum of identity-bearing types, rather than the stated finite preference-type input, and no continuous algorithmic question in that repaired model is established by the cases. The proposed finite-type question is meaningful, but it does not preserve the anchored result closely enough to count as its continuous mirror.
fails bit b-changes — the continuum limit changes the question
The proposed mirror concerns Theorem 4's one-to-one stable marriage mechanism; it leaves the college-admissions extension and the paper's other results aside.
My strongest case is the paper’s core one-to-one matching result. Theorem 4 says that for a stable marriage market with indifferences and \(n\) total agents, there is an \(O(n^4)\)-time algorithm whose output is a group-strategyproof, Pareto-stable mechanism. This theorem is proved in the paper, using the tiered-slope construction and the correspondence established in Appendix C. The paper has no named hardness result, so this algorithmic result is the right kind of anchor.
A plausible high-multiplicity regime is a large, centralized internship clearinghouse: many applicants and many single-slot positions, but only a relatively small catalogue of applicant preference types and position priority types. A type is a complete weak ranking of the other side’s types, with everyone indifferent among members of the same type. A type’s mass is its fraction of the applicant or position population. This is a clone-market version of the paper’s problem, not a claim that every real matching market has few types.
I would ask the following:
Atomless Group-Strategyproof Pareto-Stable Matching. The input is finite type sets \(R,S\); for each \(r\in R\), a weak order \(\succeq_r\) on \(S\cup\{0\}\); for each \(s\in S\), a weak order \(\succeq_s\) on \(R\cup\{0\}\); and rational masses \(\mu_r,\nu_s\) summing to one on each side. The populations are atomless within each type. The output is a deterministic measurable one-to-one matching of individuals. Its aggregate description is a mass matrix \(x_{rs}\geq 0\), with \(\sum_s x_{rs}\leq\mu_r\) and \(\sum_r x_{rs}\leq\nu_s\). Atomlessness lets the mechanism divide each cohort into subsets, but each individual still gets one actual partner or remains unmatched.
Require individual rationality and weak stability: for no pair \((r,s)\) may positive mass of type \(r\) strictly prefer \(s\) to their assigned partner *and* positive mass of type \(s\) strictly prefer \(r\) to theirs. Require Pareto-stability: there is no feasible reassignment, on the same populations, that weakly improves almost every individual and strictly improves a positive mass. Finally, require group strategyproofness for the applicants: no positive-mass coalition can change its reported types so that every coalition member receives a strictly preferred partner under their true ranking. That is the continuum counterpart of the paper’s stated no-side-payments notion of group strategyproofness. The solution is a rule that maps reported type profiles to such matchings, together with an algorithm for evaluating it from the reported masses.
I expect this problem to be Class A, though the incentive condition is the hard part. The aggregate matching has only \(|R||S|\) type-pair masses, and the paper’s tiered-slope market suggests a route through continuous assignment optimization. The question is whether that route preserves the coalition guarantee when outcomes are cohort splits. Its further questions are whether evaluation can be polynomial in the number of supported types and mass bit length, and whether the result is the limit of finite clone markets.
The main reason I think the authors would recognize this as their problem is that the proposed instance is a high-multiplicity stable marriage market with ties: agents still have integral partners, and the objectives are still stability, Pareto improvement, and applicant-side group strategyproofness. It covers the paper’s one-to-one result, not its college-admissions extension.
My weakest point is the mechanism’s use of a distinct, report-independent priority for each man. In the paper, those priorities are central to the tiered-slope construction and its strategyproofness proof. A mass vector does not itself specify individual priorities. A continuum version needs a fixed priority order to realize cohort splits, and the authors might judge that this reintroduces individual identity into the model. If preserving that priority structure forces the type count to grow with the population, the proposed tractability gain would disappear. That is the real test for this mirror; it is not a reason to dismiss the clone-market question in advance.
Theorem 4 is a real computational anchor, and the internship clearinghouse is a plausible high-multiplicity setting. Clone markets with finitely many preference types also have a sensible mass-matching description: a matrix \(x_{rs}\) can represent feasible assignments, and individual rationality, weak stability, and Pareto comparisons can be stated in terms of those assignments. So the case against cannot rest on the absence of a computational result or on the claim that matching has no multiplicity regime.
The difficulty is the theorem’s defining incentive guarantee. Its input is a profile of named men’s reports, and its construction assigns each man a distinct, report-independent priority \(\pi_i\). A mass matrix over preference types forgets which clone has which priority. In an atomless model, a finite coalition has measure zero, so its reports leave the aggregate input unchanged. The proposed positive-mass-coalition condition is meaningful, but it tests macroscopic deviations; it does not directly represent the paper’s guarantee against coalitions of every size. In finite clone markets, a fixed-size coalition has mass tending to zero, so this part of the theorem has no direct continuum counterpart.
The best repair is to add a priority coordinate \(q\in[0,1]\) within each preference type and match by type and priority. That could preserve the mechanism’s identity-sensitive ordering, but it changes the input from a finite-support distribution over preference types to a distribution over preference–priority pairs. Finite approximations then need more and more priority levels, and the rule must specify how reports, priorities, and individual assignments fit together. This is a coherent new model, but it does not show that the proposed finite-type mirror preserves the theorem’s central property or yields the programme’s usual complexity question in \(m,\tau,L\).
That is the strongest case against this anchor: the most natural mass formulation captures the matching constraints while losing the scale of deviations that group strategyproofness quantifies over; the repair restores that scale by adding a priority dimension that the mass formulation had compressed away. I cannot honestly make the universal negative airtight. A continuum model with priority coordinates and a macroscopic coalition notion may still be worth studying, and the paper’s authors might recognize it as an extension. The negative case is therefore a serious scope and bridge objection, rather than a proof that no worthwhile 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.