Information Technology Reference
In-Depth Information
Proposition 4.
Given an SMW
P
,if
Linka
(
P
)=
c
(
P
)
(
Linkm
(
P
)=
c
(
P
)
),then
I
la
(
P
)=
I
(
c
(
P
))
(resp.,
I
lm
(
P
)=
I
(
c
(
P
))
).
If there are no ties in
Linka
(
P
)
(resp.,
Linkm
(
P
)
), then there is a unique link-additive-
stable marriage (resp., link-maximal-stable marriage) with the highest link.
Proposition 5.
Given an SMW
P
,if
Linka
(
P
)
(resp.,
Linkm
(
P
)
) has no ties, then
there is a unique link-additive-stable (resp., link-maximal-stable) marriage with the
highest link.
If we consider the definition of link-maximal-stability, it is possible to define a class of
SMWs where there is a unique link-maximal-stable marriage with the highest link.
Proposition 6.
In an SMW
P
where the preference values are all different, there is a
unique link-maximal-stable marriage with the highest link.
4.2
Finding Link-Additive-Stable and Link-Maximal-Stable Marriages with the
Highest Link
We now show that for some classes of preferences it is possible to find optimal link-
additive-stable marriages and link-maximal-stable marriages of an SMW by adapting
algorithm GS, which is usually used to find the male-optimal stable marriage in classical
stable marriage problems.
By Proposition 2, we know that the set of the link-additive-stable (resp., link-maximal-
stable) marriages of an SMW
P
coincides with the set of the weakly stable marriages of
the SMP
Linka
(
P
)
(resp.,
Linkm
(
P
)
). Therefore, to find a link-additive-stable (resp.,
link-maximal-stable) marriage, we can simply apply algorithm GS to a linearization of
Linka
(
P
)
(resp.,
Linkm
(
P
)
).
Proposition 7.
Given an SMW
P
, the marriage returned by algorithm
link-additive-
stable-GS
(
link-maximal-stable-GS
) over
P
,say
M
, is link-additive-stable (resp., link-
maximal-stable). Moreover, if there are not ties in
Linka
(
P
)
(resp.,
Linkm
(
P
)
),
M
is
link-additive-stable (resp., link-maximal-stable) and it has the highest link.
Algorithm 2.
Link-additive-stable-GS (resp., link-maximal-stable-GS)
Input
:
P
:anSMW
Output
:
μ
: a marriage
P
← Linka
(
P
) (resp.,
Linkm
(
P
));
P
←
a linearization of
P
;
μ ←
the marriage obtained by applying GS algorithm to
P
;
return
μ
When there are no ties in
Linka
(
P
)
(resp.,
Linkm
(
P
)
), the marriage returned by al-
gorithm
link-additive-stable-GS
(resp.,
link-maximal-stable-GS
) is male-optimal w.r.t.
the profile with links. Such a marriage may be different from the classical male-optimal
