| paper | d4-conf-sagt-2020-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
Given finite applicant types \(I\) and position types \(J\), rational supplies \(\alpha_i,\beta_j\), and incomplete weak preference orders with tie classes of at most \(L\) opposite-side types, determine whether a polynomial-time algorithm can return a stable assignment \(x_{ij}\ge 0\) with total matched mass at least \(\frac{2L-1}{3L-2}\) times the maximum stable matched mass. Here \(\sum_j x_{ij}\le\alpha_i\), \(\sum_i x_{ij}\le\beta_j\), and stability means that for every acceptable type pair, at least one side has zero mass that is unmatched or strictly prefers that pair to its current assignment.
A two-sided nonatomic matching market with finitely many applicant and position types, rational type supplies, shared incomplete weak preference orders, and divisible assignment mass \(x_{ij}\). A type pair blocks when positive mass on both sides is unmatched or strictly prefers to match across that pair; the objective is to maximize total matched mass.
The theorem’s original bound applies to ties among individual partners; although the proponent acknowledges redefining \(L\) over partner types, the distinctive guarantee would need a new proof for that model.
fatal: False
The mirror covers Theorem 1’s approximation guarantee for maximum-cardinality stable matching with incomplete lists and bounded ties. It leaves the paper’s exact optimization question and its analysis of individual-level proposals unestablished in the mass model.
The strongest eligible anchor is Theorem 1, the paper’s main theorem, proved here. It says that for every bipartite stable matching instance with incomplete preference lists and ties of size at most \(L\), the paper’s polynomial-time algorithm returns a stable matching \(M\) with \(|M|\ge \frac{2L-1}{3L-2}|\mathrm{OPT}|\), equivalently an approximation ratio of \(\frac{3L-2}{2L-1}\). The authors note that this matches a known lower bound on the integrality gap, citing Iwama et al. (2014). The introduction also mentions NP-hardness and inapproximability, but those are cited results, not numbered results of this paper, so I would not use them as anchors.
A plausible regime is a large centralized hiring or placement round with many applicants and positions but relatively few repeated profiles. An applicant type records the attributes and priorities that determine how its members rank position types; a position type records its role and how its members rank applicant types. Each type has many interchangeable units of mass, and the number of agents is large compared with the number of types. Mass measures headcount or positions in a common unit.
Here is the mirror I would hand to a prover. Call it Ties-\(L\) Maximum Stable-Mass Approximation. An instance consists of applicant types \(I\), position types \(J\), rational supplies \(\alpha_i,\beta_j\), and each type’s incomplete, possibly tied preference order over acceptable types on the other side. All members of a type share that description. The tie bound \(L\) counts partner *types* in a tie class; it does not count the continuum of interchangeable agents within a type.
A solution is a rational matrix \(x=(x_{ij})\), where \(x_{ij}\ge 0\) is the mass of type \(i\) assigned to type \(j\), and \(\sum_jx_{ij}\le\alpha_i\), \(\sum_ix_{ij}\le\beta_j\). Its value is \(\sum_{i,j}x_{ij}\). To define stability, let \(u_i=\alpha_i-\sum_jx_{ij}\) and \(v_j=\beta_j-\sum_ix_{ij}\) be unmatched mass. For an acceptable pair \((i,j)\), let \(w_{i,j}=u_i+\sum_{j':\,j\succ_i j'}x_{ij'}\) be the mass of type \(i\) that is unmatched or strictly prefers \(j\) to its current partner; define \(w_{j,i}\) symmetrically. The assignment is weakly stable if, for every acceptable pair, \(w_{i,j}=0\) or \(w_{j,i}=0\). That is, no positive mass on both sides could form a blocking pair. The computational question is whether, in time polynomial in the number of supported types, the preference data, and the input bit length, one can return a stable \(x\) with \(\sum_{i,j}x_{ij}\ge\frac{2L-1}{3L-2}\mathrm{OPT}_{\mathrm{mass}}\), where \(\mathrm{OPT}_{\mathrm{mass}}\) is the greatest value of any stable assignment.
I would tentatively expect this approximation problem to be Class A: the theorem’s guarantee suggests that a type-level proposal and assignment method may preserve the same charging argument while working with masses. That is a research conjecture, not a consequence of Theorem 1. Further questions include whether divisible mass improves the guarantee, whether the bound is tight for this model, and whether exact maximum stable mass is tractable.
The mirror covers the maximum-cardinality stable matching problem and Theorem 1’s approximation guarantee; it does not claim that the paper’s exact optimization problem becomes easy, or that its proof directly transfers. The soft spot is substantial: the paper’s algorithm works with individual agents, and expanding binary-rational masses into individuals could take time exponential in the input bit length. Also, its \(L\) bounds ties among people, whereas this mirror bounds ties among partner types. The authors might accept the typed market as a natural version of their problem, but a compressed algorithm and a clear account of that tie-bound change would be needed to establish the result.
Theorem 1 is a real computational anchor, and the hiring-market scenario is plausible. The objective is aggregate cardinality, so identity alone does not rule out a type-based model. The strongest case against the mirror is narrower: the theorem’s useful parameter \(L\) does not survive the population limit in its original sense.
In the paper, \(L\) bounds the number of individual partners in a tie. Suppose each type instead ranks partner types, as in the proposed mirror. Expanding a positive-mass partner type into \(N\) people makes its members indistinguishable to the opposite type. A tie spanning that type then contains \(\Theta(N)\) individuals, so the paper’s \(L\) grows with the population. Its guarantee consequently tends to
\[
\frac{3L-2}{2L-1}\longrightarrow \frac32,
\]
the general-case benchmark the paper already describes. The theorem’s improvement for bounded ties—the distinctive content of this anchor—has no fixed-\(L\) population limit.
The best repair is to redefine \(L\) as the number of partner *types* in a tie, or to introduce a parameter based on tied mass. Both yield coherent questions, but they change what the theorem measures. A type tie could cover an arbitrarily large population while counting as one; a mass-based parameter has no direct counterpart in the paper’s proposal and charging scheme. Either route asks for new results about a newly parameterized mass-matching problem. The proposed positive-mass blocking condition is a sensible way to define stability there, but it is also a substantive choice: it ignores blocking pairs whose mass is zero, as a nonatomic model must.
So the negative case is that Theorem 1 does not provide a clean or especially promising continuous mirror: preserve its original \(L\), and its bounded-tie advantage washes out; preserve a nontrivial typed market, and the theorem’s parameter and analysis no longer transfer. That is not enough to rule out a worthwhile new question. The typed mass-matching model remains plausible, and the paper’s result could motivate it. I cannot honestly defend the universal claim that no scenario makes a continuous mirror worthwhile; the strongest objection is to this theorem as evidence for one.
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.