- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper proposes a method to decide if a given two-sided matching is stable or not when each side provides utilities that are smeared by Gaussian noise. The primary insight is spelt out early and clearly: if one agent's gain is quite negative then it rules out a blocking pair without even considering the gains of the other agent. Both individual utility queries and deployments of whole matchings that return feedback from both sides are considered. The authors derive exact information limits for each and show that (section 3.3) deployment constraints can change which blocking pair is easiest to certify. An adaptive guard algorithm is proposed and it is shown to achieve finite-sample cost bounds on stable instances. A separate tracking algorithm achieves asymptotically optimal efficiency for a fixed market as the required confidence increases. The authors also provide sampling-design certificates and synthetic experiments showing savings over uniform auditing. While I find the theory to be sound and the adaptive sampling to be interesting, I also think the paper is too dense and notation-heavy to read, the Gaussian model could be somewhat restrictive and some simulations in section 6 are small-scale with no comparison to existing stable-matching learning methods.
Critical strengths
In my own reading the papers main strength is how it connects matching-specific insight with rigorous guarantees. I find the key insight mentioned above to be intuitive and appreciate the theoretical results built around it. The theory also accounts for deployment constraints that can change which blocker is cheapest to certify. I particularly value the clear connection between the information limits and the algorithms’ guarantees (Sections 3–4). I find this convincing because it explains both where savings in observations arise and how to achieve them. This is why I support weak acceptance however its more on the borderline due to the issues I raise next.
Critical weaknesses
-
My main concern is that I am not yet convinced of the practical significance, despite the intuitive main result/insight. The authors deal with only Gaussian noise. A more severe practical question is how the auditor can repeatedly deploy arbitrary matchings, including unstable ones, when they only have a limited budget. In the simulations, the tracker is only tested for n = 3 and 6, so it is hard to see what happens for larger n. Moreover, there is no comparison with other state-of-the-art methods. These concerns keep me close to borderline.
-
I find the paper hard to read in its current form. Section 2 spends over two pages introducing notation before the first main theorem appears, including supplementary quantities mainly used in the appendices. The guard, one of the main algorithms in my view, is described in Section 4, but its pseudocode appears only in Appendix B. The writing feels quite choppy and often feels severely suppressed to accommodate page limits.I had to move between the main text and appendices many times to understand and assess the contributions.
Questions for authors
-
if the auditor cannot afford the next doubling stage what happens to the main algo guard? More fundamentally, what if some required pairs cannot be observed under the permitted deployments? I asked about n being small above already and consistent to that, I think when n is even moderately large, it is quite practical that not all deployments will be possible. It is perfectly acceptable to me if the budget does not allow resolution of stability but a quantification on that note will make the paper even more interesting and practical
-
Are the methods truly scalable for larger market? Note there is cost associated with deploying and repeated matching as well. Also there are other well-established matching methods available so the authors should try to adapt those fixed-confidence methods and see if the savings are still persistent.
-
What if the markets are many-to-one? I can think of many such practical examples and honestly these examples are more natural to me than perfect one-on-one matching.
Thank you for your responses. I am keeping my original score. I still believe that the paper’s current presentation is below the ICLR bar.