| paper | d4-conf-sigecom-2010-0018 |
| 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 \(m,\tau,L\), including exact lexicographic tie-breaking and polynomial-size rational output. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete hospital templates, rational masses \(\mu_t\), and a split \(q_{t,b}\) of each type across the two sides of a fixed bipartition, compute a feasible mass matching of maximum total matched-pair mass. Each template specifies finitely many client slots, its internal compatibility graph, and its slot compatibilities with every other template; each unit of hospital mass uses an internal maximum matching, and external matches join only compatible slots on opposite sides, with each slot used at most once per unit. Break ties by a fixed order on types.
A continuous population of hospitals with mass \(\mu_t\) for each complete template \(t\); decision variables distribute that mass over internal maximum matchings and assign compatible residual slot mass to cross-side pairs, maximizing total matched-pair mass, with type order resolving ties.
This mirrors Theorem 5.2's computation of a maximum-cardinality matching subject to internal-maximum and bipartition constraints. It does not transfer Theorems 5.1 or 6.1: with nonatomic hospital mass, an individual hospital has measure zero, so the paper's dominant-strategy notion would require a new strategic model. The lower bounds and conjectures are also outside this mirror.
The strongest positive case is narrow: the paper has a named polynomial-time result for computing its constrained matching, but no NP-hardness result to anchor a hardness-dissolution story. Theorem 4.1 is an impossibility bound on truthful mechanisms’ approximation ratios; it is not a computational-hardness result. I would use one anchor:
Theorem 5.2, proved in this paper, says that for any number of agents and any fixed bipartition \(\Pi\), \(\match_\Pi\) can be executed in polynomial time. Here \(\match_\Pi\) chooses a largest matching subject to two constraints: every agent’s internal matching is maximum, and there are no matches between agents on the same side of \(\Pi\). It uses serial tie-breaking. The authors prove the algorithmic claim by reducing execution to maximum-weight matching.
A plausible high-multiplicity regime is a large exchange network of regional hospital units with repeated patient-donor profiles. Let the agents be hospitals, and let a type specify the complete local client template and its compatibility pattern with every other type. Suppose there are \(n\) hospitals but only \(\tau\) such types, with \(n\gg\tau\). The society is a rational distribution \(\mu\) over hospital types. Mass means a fraction of hospitals of each type; each type’s client slots consequently have mass proportional to \(\mu_t\). The compatibility template is part of the type, so hospitals grouped together are indistinguishable for every feature this matching problem uses.
One precise mirror is High-Multiplicity \(\match\) Execution. Its input is the type set, the rational masses \(\mu_t\), the client slots and internal compatibility graph for each type, compatibility relations between slots of different types, and a bipartition of the hospital mass into side masses \(q_{t,0},q_{t,1}\), where \(q_{t,0}+q_{t,1}=\mu_t\). Its solution is a maximum-cardinality *mass matching*: nonnegative masses of compatible client pairs across the two sides, together with a distribution of hospital mass over maximum internal matchings. Each client slot’s total matched mass must not exceed its available mass. The objective is to maximize total matched-pair mass. For the mass version of Mix-and-Match, the natural split is \(q_{t,0}=q_{t,1}=\mu_t/2\).
I expect this problem to be tractable. With explicit type templates, the aggregate feasibility constraints form a linear optimization problem. The exponentially many choices of internal maximum matchings can be handled by pricing with maximum-weight matching, the same computational ingredient used in Theorem 5.2. The natural parameters are the number of types \(\tau\), total number of client slots, compatibility entries, and input bit length \(L\). This is a continuation of the paper’s actual allocation problem: the decision variable is still who gets matched to whom, now expressed as mass between repeated types.
The scope is just the computation in Theorem 5.2. It does not claim a continuous version of the paper’s full strategyproofness or approximation results. Further questions follow naturally: whether the mass mechanism can preserve individual strategyproofness, whether the 2-approximation guarantee of Theorem 6.1 survives aggregation, and whether tractability remains when the type templates are part of a succinct input.
My weakest point is that the scenario needs a genuinely small set of *complete* hospital types. Real compatibility can be highly individualized, making \(\tau\) approach \(n\). Also, serial priority among named hospitals does not directly become a tie rule over mass. So this is a credible mirror of the paper’s matching-computation subproblem in a structured high-multiplicity market, not a mirror of its entire mechanism-design result.
The only anchor is Theorem 5.2. It is a named polynomial-time result about computing \(\match_\Pi\), so “there is no computational result to mirror” is not available. The strongest objection is that the theorem’s input is an arbitrary labeled graph: matching feasibility depends on which particular client pairs are compatible. To preserve that information in a hospital type, the type may need to encode the hospital’s full client template and compatibility pattern with other hospitals. In a real exchange network, pairwise compatibility can be idiosyncratic; using complete profiles may therefore drive \(\tau\) close to the number of hospitals. Coarser types would replace exact compatibility with a structured approximation or a different model.
The theorem also concerns a particular mechanism: it requires each hospital’s internal matching to be maximum and uses serial tie-breaking among hospitals. A mass allocation over slot types does not directly reproduce the named hospitals’ tie priorities. These are real fidelity costs in the proposed mirror, especially if the claim is that the paper’s mechanism itself has been continuized.
But those points do not defeat the best version of the proposal. In a deliberately structured exchange network, suppose finitely many complete hospital templates determine internal client compatibility, and compatibility between client slots depends only on their templates. A distribution over those hospital types, split across the bipartition, gives a coherent population model. One can optimize mass matches subject to slot capacities and the distribution of each type’s maximum internal matchings. That is recognizably the same constrained-matching computation at high multiplicity; the identity-based tie rule can be replaced by a type-level tie rule if the authors accept that co-modification.
So the negative case is weak. It shows that Theorem 5.2 does not automatically give a useful mirror for an unrestricted, realistic compatibility graph, and that the proponent’s model is a structured regime rather than a continuation of arbitrary instances. It does not rule out a plausible finite-template regime. I cannot honestly argue that no worthwhile continuous mirror survives; on the grading criterion given, this anchor likely survives.
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.