Information Technology Reference
In-Depth Information
overall score that each man (resp., woman) receives: men (women) that receive higher
overall scores are more preferred. The overall score of a man
m
(resp., woman
w
), say
s
(
m
)
(resp.,
s
(
w
)
), is computed by summing all the preference values that the women
give to him (the men give to her). If two candidates receive the same overall score,
we use a tie-breaking rule to order them. If we apply this voting rule to the preference
valuesgivenbythewomenin
P
, then we obtain
-
s
(
m
1
)=8+3=11
,
-
s
(
m
2
)=5+1=6
,
and thus the ordering
o
m
is such that
m
1
o
m
m
2
. If we apply the same voting rule to
the preference values given by the men in
P
,
-
s
(
w
1
)=3+4=7
,
-
s
(
w
2
)=2+2=4
,
and thus the ordering
o
w
is such that
w
1
o
w
w
2
. The lex-male-optimal
α
-stable mar-
riage w.r.t.
o
m
and
o
w
is the marriage
M
1
=
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
}
.
3.3
-Stable Marriage
It is possible to find optimal
α
-stable marriages by adapting the GS-algorithm for clas-
sical stable marriage problems [4].
GivenanSMW
P
and a natural number
α
, by Theorem 1, to find an
α
-stable mar-
riage it is sufficient to find a weakly stable marriage of
α
(
P
)
. This can be done by
applying the GS algorithm to any linearization of
α
(
P
)
.
Given an SMW
P
, a natural number
α
, and two orderings
o
m
and
o
w
over men
and women computed by applying a voting rule to
P
as described in Definition 3, it
is possible to find the
α
-stable marriage that is lex-male-optimal w.r.t
o
m
and
o
w
by
applying the GS algorithm to the linearization of
α
(
P
)
where we order incomparable
pairs, i.e., the pairs that differ for less than
α
in
P
, in accordance with the orderings
o
m
and
o
w
.
Finding the Lex-Male-Optimal
α
Algorithm 1.
Lex-male-
α
-stable-GS
Input
:
P
:anSMW,
α
: a natural number,
r
: a voting rule
Output
:
μ
: a marriage
o
m
←
the strict total order over the men obtained by applying
r
to the preference values
given by the women over the men
o
w
←
: the strict total order over the women obtained by applying
r
to the preference
values given by the men over the women
P
←
the linearization of
α
(
P
) obtained by ordering incomparable pairs of
α
(
P
) in
accordance with
o
m
and
o
w
;
μ ←
the marriage obtained by applying the GS algorithm to
P
;
return
μ
Proposition 3.
Given an SMW
P
, a natural number
α
,
o
m
(resp.,
o
w
) an ordering over
the men (resp., women), algorithm
Lex-male-
α
-stable-GS
returns the lex-male-optimal
α
-stable marriage of
P
w.r.t.
o
m
and
o
w
.
