diff options
| -rw-r--r-- | esa-2015-40.txt | 185 |
1 files changed, 185 insertions, 0 deletions
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 @@ +<!-- + == For your convenience, this form can be processed by EasyChair + == automatically. You can fill out this form offline and then upload it + == to EasyChair. Several review forms can be uploaded simultaneously. + == You can modify your reviews as many times as you want. + == + == When filling out the review form please mind the following rules: + == + == (1) Blocks such as this are comments. EasyChair will ignore them. + == Do not write any text into these blocks as it will be ignored. + == You can add comments to the review form or remove them. + == (2) Write only into the tags where instructed. Do not modify any + == tags and attributes, or the review will become unusable and will + == be rejected by EasyChair. + --> +<review id="2320262::1073196" + submission="40" + title="An Equitable Solution to the Stable Marriage Problem" + authors="Ioannis Giannakopoulos, + Panagiotis Karras, + Dimitrios Tsoumakos, + Katerina Doka, + Nectarios Koziris" + pc_member="Charalampos Tsourakakis"> +<score id="261808" name="Overall evaluation"> +<!-- + == Select your choice from the options below and write its number below, + == before the </score> tag. + == + == 3 strong accept + == 2 accept + == 1 weak accept + == 0 borderline paper + == -1 weak reject + == -2 reject + == -3 strong reject + --> +-2 +</score> +<score id="261809" name="Reviewer's confidence"> +<!-- + == Select your choice from the options below and write its number below, + == before the </score> tag. + == + == 5 (expert) + == 4 (high) + == 3 (medium) + == 2 (low) + == 1 (none) + --> +4 +</score> +<!-- ======== Review ======== --> +<text id="261811" name="Review"> +<!-- + == Please provide a detailed review, including justification for your + == scores. This review will be sent to the authors unless the PC chairs + == decide not to do so. This field is required unless you have an + == attachment.. + --> +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. +</text> +<text id="261812" name="Confidential remarks for the program committee"> +<!-- + == If you wish to add any remarks intended only for PC members, please + == write them below. These remarks will only be seen by the PC members + == having access to reviews for this submission. They will not be sent to + == the authors. This field is optional.. + --> + + + + + + +</text> +<reviewer> + <!-- + == If the review was written by (or with the help from) a subreviewer + == different from the PC member in charge, add information about + == the subreviewer below. Write subreviewer's first name, last name + == and email between the tags below. + --> + <first_name> Thibaut </first_name> + <last_name> Horel </last_name> + <email> thorel@seas.harvard.edu </email> +</reviewer> +</review> |