Information Technology Reference
In-Depth Information
Definition 6 (Link Maximal-strength).
Givenaman
m
and a woman
w
,the
link
maximal-strength
of the pair
(
m, w
)
, denoted by
lm
(
m, w
)
, is the value obtained by
taking the maximum between the preference value that
m
gives to
w
and the preference
value that
w
gives to
m
, i.e.,
lm
(
m, w
)=
max
(
p
(
m, w
)
,p
(
w,m
))
. Given a marriage
M
,the
maximal-link
of
M
, denoted by
lm
(
M
)
, is the maximum of the links of all its
pairs, i.e.,
max
{
(
m,w
)
∈M}
lm
(
m, w
)
.
Definition 7 (Link-maximal-Stability).
Given a marriage
M
,aman
m
, and a woman
w
, the pair
(
m, w
)
is a link-maximal-blocking pair for
M
if the following conditions
hold:
-
lm
(
m, w
)
>lm
(
m
,w
)
,
-
lm
(
m, w
)
>lm
(
m, w
)
,
where
m
is the partner of
w
in
M
and
w
is the partner of
m
in
M
. A marriage is
link-maximal-stable
if it does not contain link-maximal-blocking pairs.
4.1
Relations with Other Stability Notions
Given an SMW
P
, let us denote with
Linka
(
P
)
(resp.,
Linkm
(
P
)
) the stable marriage
problem with ties obtained from
P
by changing every preference value that a person
x
gives to a person
y
with the value
la
(
x, y
)
(resp.,
lm
(
x, y
)
), by changing the preference
rankings accordingly, and by considering only these new preference rankings.
Let us denote with
I
la
(
P
)
(resp.,
I
lm
(
P
)
) the set of the link-additive-stable mar-
riages (resp., link-maximal-stable marriages) of
P
and with
I
w
(
Linka
(
P
))
(resp.,
I
w
(
L
inkm
(
P
))
) the set of the weakly stable marriages of
Linka
(
P
)
(resp.,
Linkm
(
P
)
). It
is possible to show that these two sets coincide.
Theorem 2.
Given an SMW
P
,
I
la
(
P
)=
I
w
(
Linka
(
P
))
and
I
lm
(
P
)=
I
w
(
Linkm
(
P
))
.
Proof.
Let us consider a marriage
M
. We first show that if
M ∈ I
w
(
Linka
(
P
))
then
M ∈ I
la
(
P
)
.If
M ∈ I
la
(
P
)
,thereisapair
(
m, w
)
that is a link-additive-blocking
pair, i.e.,
la
(
m, w
)
>la
(
m, w
)
and
la
(
m, w
)
>la
(
m
,w
)
,where
w
(resp.,
m
)is
the partner of
m
(resp.,
w
)in
M
.Since
la
(
m, w
)
>la
(
m, w
)
,
m
prefers
w
to
w
in the problem
Linka
(
P
)
, and, since
la
(
m, w
)
>la
(
m
,w
)
,
w
prefers
m
to
m
in
the problem
Linka
(
P
)
. Hence
(
m, w
)
is a blocking pair for the problem
Linka
(
P
)
.
Therefore,
M
I
w
(
Linka
(
P
))
.
We now show that if
M
∈
I
w
(
Linka
(
P
))
,
there is a pair
(
m, w
)
that is a blocking pair for
I
w
(
Linka
(
P
))
, i.e.,
m
prefers
w
to
w
in
the problem
Linka
(
P
)
,and
w
prefers
m
to
m
in the problem
Linka
(
P
)
. By definition
of the problem
Linka
(
P
)
,
la
(
m, w
)
>la
(
m, w
)
and
la
(
m, w
)
>la
(
m
,w
)
.There-
fore,
(
m, w
)
is a link-additive-blocking pair for the problem
P
. Hence,
M
∈
I
la
(
P
)
then
M
∈
I
w
(
Linka
(
P
))
.If
M
∈
∈
I
la
(
P
)
.
It is possible to show similarly that
I
lm
(
P
)=
I
w
(
Linkm
(
P
))
.
When no preference ordering changes in
Linka
(
P
)
(resp.,
Linkm
(
P
)
)w.r.t.
P
,then
the link-additive-stable (resp., link-maximal-stable) marriages of
P
coincide with the
stable marriages of
c
(
P
)
.
