1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
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>
|
