-2 4 This paper proposes a new approach to the Stable Marriage Problem. In the famous Gale-Shapley algorithm, the situation is highly asymmetric and in favor of the proposers. The goal of this new approach is to address this asymmetry by having both sides taking turns proposing. The original Gale-Shapley is modified to accommodate the fact that the proposing side alternates: when a party sees their engagement broken by some person b, they start proposing again starting from the person below b in their preference list. The performance of the algorithm is measured in terms of the egalitarian cost and the sex equality cost, two criteria trying to capture whether or not the algorithm is fair to both sides. Theory: * the problem was well-formulated. The algorithm, even if a straightforward variant of the original Gale-Shapley algorithm was well-motivated by examples. * the main theoretical result is: if the algorithm terminates, then it finds a stable matching. As far as I can tell, this proof is correct. * no formal guarantees are given on the termination of the algorithm, or on its performance with respect to the two criteria defined above. * the choice of the PickProposer function (the function which decides, given an iteration number k, which side should be proposing) was somewhat weakly justified: - I agree with the authors that this function should be balanced and state-independent - the justification for choosing a deterministic function was not very convincing: if the goal is simply to have reproducible results, then using a PRNG with a fixed seed is probably as good. - in fact I think the choice of sin(x^2) can easily lead to issues: as x grows, the frequency increases, making the problem of finding the sign of sin(x^2) a fight against machine accuracy. - the justification for aperiodicity was also not clear to me: it seems that a function with an irrational period would also prevent the issue of a resonance phenomenon between the period of the function and cycles in the proposal patterns. In particular, I wonder whether or not the authors tried the simple sin(x) function. Experiments: * the code is publicly available which makes the experiments easily verifiable and reproducible. * the suggested algorithm is only compared to the Gale-Shapley algorithm and the recent SWING algorithm from Everaere et al. I wish it were also compared to other heuristics. * I think a comparison between different PickProposer functions would make the experimental part more convincing. What is special about sin(k^2)? Is it the only function which performs well? * on a side note: I wonder why ESMA and SWING always seem to perform equally well for the egalitarian cost criterion. Writing: The paper was well-structured and well-articulated overall. There were however local inaccuracies and inconsistencies which made the reading harder than one could expect: - page 5: n_a = m_a +1 = pr_a[b] +1 : I think this (C-style) double assignment is hard to read and understand. Splitting it in two would be better. - page 5: pr_a is the inverse of l_a (not its reverse) - page 6: function evaluate line 7, this is inconsistent with the definition given on the previous page because a.n can be strictly greater than a.m. I think a.n should be set to pr_a[b] to be consistent with the previous page (at the cost of one extra useless proposal). - page 6: maybe you could define evaluate(b, a) instead of evaluate (a, b) (I was confused at first because the a in evaluate (a, b) is the b in propose(a) - page 6, algorithm 1: PickProposer has not been defined yet at this point. Make clear what the purpose of PickProposer is and that it will be defined later. It should also be clear that the theorem holds for any PickProposer function. - the proof of Theorem 1 could be written in a clearer way by making the timeline explicit: - a_i and b_j were both rejected at least once by the other - assume wlog that a_i was the last to reject - then it was matched at this point to someone higher than b_j. Since he ended up with someone lower than b_j, he must have proposed and be rejected by b_j afterwards. A contradiction. Thibaut Horel thorel@seas.harvard.edu