From 3fbb69842a86af665d95bc3778c9b35f957d99ee Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 16 May 2015 17:42:18 +0200 Subject: Adding esa review --- esa-2015-40.txt | 185 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 185 insertions(+) create mode 100644 esa-2015-40.txt diff --git a/esa-2015-40.txt b/esa-2015-40.txt new file mode 100644 index 0000000..a37ad0d --- /dev/null +++ b/esa-2015-40.txt @@ -0,0 +1,185 @@ + + + + +-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 + + -- cgit v1.2.3-70-g09d2