NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:243
Title:Equitable Stable Matchings in Quadratic Time

Reviewer 1

The authors propose a novel algorithm for stable matching problem in a two-sided market. This algorithm is a cute extension of the classical DA (Deferred Acceptance) algorithm. The modification includes three important components: - Monotonic Deferred Acceptance - Strongly Deferred Acceptance - local search steps (resulted in Deferred Local Search) The paper is well written and structured. The technical presentation is clear with a good balance between formal notations and informal explanation. The core contribution of the paper is the novel algorithm that achieves O(n^2) complexity (w.r.t. the number of participants in the two-sided market). It would be great to see an evaluation or application of the proposed algorithm in practice (real example). //After rebuttal: thank you for clarification on practical evaluation. Please, make sure to include it in the next version of your paper

Reviewer 2

Originality: This method is a novel extension of existing work. Quality: There are no obvious technical issues with the submission, however, some parts of the writing are unclear and I had to make my own guesses about what authors mean in some places (see Improvements section for suggestions). Clarity: The introduction is clear but the main text is not very clear. In particular, it was hard to understand how the proposed algorithms actually work. Significance: In theory DA produces unfair matchings. In many practical applications there is only a few stable matchings anyway so the unfairness doesn't really matter. This algorithm may be important for cases where indeed there are many stable matchings and we care about fairness.

Reviewer 3

Comments: The problem being addressed is a nice twist on a classical combinatorial optimization problem, and focusing on the fairness aspects of the famously-not-fair stable matchings that pop out of standard DA is a good thing. I found the paper extremely readable, and the authors clearly know the related literature and state of the art in stable matching. Still, some minor comments regarding language/notiation/citations/etc follow: * Was there a reason to use M instead of the standard \mu to represent the matching function/matching? (In fact, \mu is used to denote a matching in Algorithm 1 instead of M.) * It would be good to define a few terms more formally and stick to them. For example, at various times, couples "break up" (L121) or are "abandoned" (L125, L133), there can be "divorcees" (L127) afterward, and so on. * "Idle" in Theorem 3.1 should not be italicized. * I'd be careful about the wording used in the Conclusions, where "finding an equitable stable matching" is NP-hard and then a polytime algorithm for finding "stable matchings of good equity" is proposed. I get what you're saying, but you don't want somebody to write the paper off because of what that might seem to imply. * L220, ``all agents to an idle state'' not ``all agents in an idle state'' * n isn't defined in the Algorithm 1 block * The cost of a matching also isn't defined in the algorithm block, not clear if this refers to regret cost, egalitarian cost, balance cost, or some other cost. (And, those costs haven't been discussed for a few pages by the time the reader hits Algorithm 1, so it'd be good to add a sentence near the algorithm block in general.)