| paper | Two-sided matching with partial information |
| authors | B. Rastegari, A. Condon, N. Immorlica, Kevin Leyton-Brown |
| venue | SIGECOM 2013 |
| filed under | coalition · matching |
| judged by | gpt-5.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: The ordinary problem is $\mathrm{coNP}$-complete under polynomial many-one reductions, even with unit applicant masses, employer masses in $\{1,2\}$, complete acceptability, and zero budget. The diligent variant is in $\mathrm{P}$ with running time polynomial in $m,\tau,L$. The ordinary problem is in $\mathrm{P}$ exactly if $\mathrm{P}=\mathrm{NP}$, and is $\mathrm{NP}$-hard exactly if $\mathrm{NP}=\mathrm{coNP}$. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given finite employer types \(E\) and applicant types \(A\) with rational masses \(w\) and \(v\), partial orders, admissible type-level strict refinements, a realized refinement profile \(\rho\), batch interview costs \(c_{ea}\), and budget \(B\), does there exist an interview-mass allocation \(q\) of cost \(\sum_{e,a} c_{ea}q_{ea}\le B\) whose revealed comparisons certify that the employer-optimal stable mass matching \(x^\rho\) remains employer-optimal for every compatible refinement? In the diligent variant, every positive edge of \(x^\rho\) must be covered by an interview.
A high-multiplicity cohort market with finite employer and applicant types, rational population masses, shared latent preference refinements within each type, type-level batch interviews, a mass matching flow \(x\), and minimum interview mass as the objective.
The paper does not establish that type-level batch interviews with mass-proportional costs are the canonical high-multiplicity limit of its individual interview histories rather than a new information-acquisition primitive.
fatal: False
The mirror securely covers Theorem 4.4 and its Feedback Arc Set hardness; it leaves the MDP result, nonexistence theorems, and the polynomial policy of Theorem 5.2 without a comparably justified continuous analogue.
The strongest mirror is a high-multiplicity matching market in which agents are replaced by cohorts, while the uncertainty, interviews, stability requirement, and employer-optimality objective remain intact.
Let \(E\) and \(A\) be finite sets of employer and applicant types. Type \(e\) has mass \(w_e\), type \(a\) has mass \(v_a\), with rational masses summing to one on each side. A type records its acceptable counterpart types, partial preference ordering, support or distribution of compatible strict refinements, and interview costs. Thus agents of one type are genuinely interchangeable for everything the model uses.
A matching is now a mass flow \(x=(x_{ea})\), where \(x_{ea}\) is the mass of type-\(e\) employers matched to type-\(a\) applicants. Its row and column sums are \(w_e\) and \(v_a\). Each individual still receives one integral match; \(x_{ea}\) is fractional only because it is the aggregate of a continuum. Stability and employer-optimality are defined in the standard nonatomic way: there must be no positive mass of a pair of types who both prefer one another to their assigned partners.
The natural regime is a market with \(Nw_e\) employers and \(Nv_a\) applicants of each type, where \(N\gg |E|+|A|\), represented compactly by the masses. A plausible example is a large market of applicants from finitely many degree-region cohorts and many hiring slots or branches using finitely many recruitment templates. Their coarse rankings are known as equivalence classes; exact rankings within those classes are learned through interviews. This is not simply fractional matching: the continuous object is the population, while the mass matching is the aggregate consequence.
My lead anchor is Theorem 4.4, proved in this paper. It states that the paper’s Optimality Certificate decision problem is NP-hard, even when every partial preference ordering is an equivalence-class ordering. The input consists of a matching instance \((E,A,p_{E,A})\), a strict preference profile \(\succ\) refining the partial profile, and an integer \(K\). The question is whether there is an information state \(I\) containing at most \(K\) interviews such that the specified matching \(\mu\), which is employer-optimal under \(\succ\), remains employer-optimal under every strict preference profile consistent with \(I\) and \(p_{E,A}\). The paper proves this by reduction from Feedback Arc Set; the FAS result itself is cited to Karp (1972), but Theorem 4.4 and its reduction are proved here.
I would state the continuous counterpart as follows.
\(\mathrm{Mass\text{-}OC}_\infty\): an instance consists of finite employer and applicant type sets, rational masses \(w\) and \(v\), initial partial orders, compatible strict refinements, interview costs \(c_{ea}\), a realized refinement profile \(\rho\), and a budget \(B\). An interview action selects type pairs \(Q\subseteq E\times A\) and reveals the corresponding type-level comparisons. The question is whether there exists \(Q\) with
\[ \sum_{(e,a)\in Q} c_{ea}\le B \]
such that the employer-optimal stable mass matching \(x^\rho\) is also the employer-optimal stable matching for every refinement compatible with the initial information and all comparisons revealed by \(Q\). A solution is the interview certificate \(Q\), together with the certified mass matching \(x^\rho\). For a diligent version, every positive matching edge must also be interviewed.
This is recognisably the authors’ problem: it retains partial preferences, hidden strict refinements, adaptive information acquisition, stability, employer-optimality, and minimum interviews. The only co-modification is that interviews and matches operate on exchangeable cohorts. In the natural shared-cohort setting, a type-level interview is a batch interview whose cost is proportional to the mass contacted; a partial interview cannot certify the unqueried part of a cohort.
I would expect \(\mathrm{Mass\text{-}OC}_\infty\) to be Class B: hardness transfers. The FAS reduction is driven by the directed graph of employer and applicant types, not by the number of individually named agents. Replace every agent in the reduction by a large cohort of identical agents and scale the certificate budget by the common cohort mass. The fixed \(2n\) interviews and the selected graph arcs remain exactly the same type-level choices, so a certificate still exists precisely when the graph has a feedback arc set of the required size. This is the useful kind of negative result for ChoCo: continuization removes irrelevant multiplicity but does not remove combinatorics living in the type graph.
A secondary, positive anchor is Theorem 5.2, also proved in this paper. Under the restriction that all applicants have identical equivalence-class orderings, with employers otherwise unrestricted and matching required to be diligent, Algorithm 1 (“Lazy Gale–Shapley”) executes a very weakly dominant, diligent policy in polynomial time. In full, the algorithm alternates between interviewing an employer’s highest-ranked achievable applicant class and running tentative employer proposals. It always returns the employer-optimal stable matching, interviews matched agents, terminates after polynomially many interviews, and— for every underlying strict preference profile—uses no more interviews than any other diligent sound policy. Consequently it is also Pareto optimal and optimal in expectation for every full-support prior.
The corresponding continuous problem is \(\mathrm{Mass\text{-}LazyGS}_\infty\). Its input is a finite typed market with masses, common applicant-side equivalence classes, arbitrary employer-side equivalence classes, compatible strict refinements, and the diligent requirement. A policy may interview mass, make tentative offers, reject inferior offers, and terminate with a stable employer-optimal matching flow. It must be sound for every compatible refinement, and its cost is total interview mass. The question is to compute a policy that is pointwise minimal among diligent policies: for every realization, no other diligent policy uses less interview mass.
The natural expectation is Class A in the cohort version. Lazy Gale–Shapley can be compressed by processing type masses, residual capacities, and class transitions rather than individual agents. Rational masses merely change the arithmetic; the structural proof—interview only achievable applicants in the highest relevant class, then make employer-optimal proposals—survives. The richer version with independently varying hidden rankings inside each mass type would be a worthwhile further problem rather than something I would claim Theorem 5.2 already solves.
The weakest point is the interview semantics. If “continuum” is interpreted as infinitely many independently idiosyncratic agents, with interviews occurring only at individual resolution, then a finite type-level certificate may cease to exist or may require interviewing essentially all mass. My mirror instead uses a legitimate high-multiplicity scenario in which cohorts share the information structure and interview outcomes are meaningful at cohort level. That is a real modelling choice, but it is not a trivialisation: the hard FAS structure remains, and the question still asks for a robust employer-optimal stable matching under partial information.
The resulting programme would ask at least three further questions: whether the hardness survives with genuinely fractional interview decisions; whether expected rather than worst-case mass certification yields a continuous dynamic programme; and whether the boundary between the hard general model and the polynomial common-equivalence-class model is itself a Class C phenomenon.
The strongest negative case is not that the paper lacks computational results: it does not. Theorem 4.4 is a genuine NP-hardness result, and Theorem 5.2 is a genuine polynomial-time policy theorem. The problem is that both results compute over information attached to named agent–agent pairs, whereas a population continuum erases precisely that information.
Theorem 4.4 is about a set \(I\) of individual interviews. Its certificate must rule out every completion of every named agent’s partial preference ordering. The Feedback Arc Set reduction relies on this locality: an arc \((v_i,v_j)\) is represented by the particular interview \(e_i:a_j\), and an unqueried edge permits a particular employer in a particular alternating cycle to change its preference. This is not merely a population-size issue.
There is no satisfactory cohort quotient. If all members of a cohort share the same hidden strict preference, then one representative or one batch interview reveals the relevant information for the whole cohort. Normalized interview cost tends to zero, or the model introduces a new batch-interview primitive whose cost is proportional to cohort mass. The latter is not derived from the paper.
If, more realistically, members of a coarse cohort have independently varying hidden preferences, then they are not one type for this problem. Two such members can produce different interview outcomes, receive different proposals, and participate in different blocking pairs. Interviewing a fraction of the cohort leaves an unqueried positive-mass set capable of witnessing a different employer-optimal matching. Exact soundness therefore forces an all-or-nothing decision: interview essentially the whole relevant mass, or do not obtain a certificate. The continuous variable has collapsed back to a discrete choice of type-pairs.
One can repair this by adding latent preference types, correlations, and batch observations. But then the object is a new stochastic or nonatomic information-acquisition problem. Its state is a measure over latent preference profiles and interview histories, not the society distribution used by the continuization programme. The proposed \(\mathrm{Mass\text{-}OC}_\infty\) also adds interview costs and type-level observations absent from the theorem. Re-encoding Feedback Arc Set on the resulting type graph may be interesting, but it would establish a new graph-query problem, not a population relaxation of the paper’s optimality-certificate problem.
Theorem 5.2 has the same obstruction in a more exposed form. Lazy Gale–Shapley exploits individual applicants’ revealed strict rankings and individual proposal chains. The common equivalence-class ordering is only coarse information; the paper explicitly permits the applicants’ underlying strict preferences to differ. A positive-mass cohort with that property cannot be represented by one matching-flow variable \(x_{ea}\): the policy needs to know which submass accepts which employer and which submass remains achievable. Splitting the cohort by every latent strict order restores the information, but then the alleged compression is gone and the number of relevant types can be factorial or worse in the market description. Forcing all cohort members to share their hidden strict order makes interviews batch observations and changes the policy problem.
The diligent requirement makes the mismatch unavoidable. In the paper, every matched pair must actually interview. In a mass model, if \(x_{ea}>0\), does that require interviewing all of that mass? If not, the un interviewed portion can contain the preference realization that invalidates stability or employer-optimality. If yes, interview cost is again an all-or-nothing mass charge, and the claimed continuous policy is only a finite type-level policy with weights attached.
Even the dominance objective does not survive innocently. Theorem 5.2 compares interview counts pointwise for every individual preference profile. In an atomless society, changing one agent’s preference has zero mass and no effect on aggregate cost or matching. Replacing pointwise dominance by dominance up to null sets, expected mass cost, or worst-case positive-mass deviations is a substantive new objective, not a harmless limit convention.
Thus the proponent’s mirror has a forced trilemma. Common hidden preferences make information acquisition collapse; heterogeneous hidden preferences destroy exchangeability; and a batch-query model avoids both only by introducing a new problem whose central primitives are not those of the paper. A cohort hiring story may be plausible, so this is not an airtight impossibility claim. But under ChoCo’s requirement that the population itself be the continuous object while the computational question remains recognisably the paper’s, neither Theorem 4.4 nor Theorem 5.2 supplies a worthwhile mirror.
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.