Information Technology Reference
In-Depth Information
4
Stability Notions Relying on Links
Until now we have generalized the classical notion of stability by considering separately
the preferences of the men and the preferences of the women. We now intend to define
new notions of stability that take into account simultaneously the preferences of the
men and the women. Such a new notion will depend on the strength of the link of the
married people, i.e., how much a man and a woman want to be married with each other.
This is useful to obtain a new notion of stable marriage, that looks at the happiness of
the pairs (man,woman) rather than at the happiness of the members of a single sex.
A way to define the strength of the link of two people is the following.
Definition 4 (Link Additive-strength).
Givenaman
m
and a woman
w
,the
link
additive-strength
of the pair
(
m, w
)
, denoted by
la
(
m, w
)
, is the value obtained by
summing the preference value that
m
gives to
w
and the preference value that
w
gives
to
m
,i.e.,
la
(
m, w
)=
p
(
m, w
)+
p
(
w,m
)
.Givenamarriage
M
,the
additive-link
of
M
,
denoted by
la
(
M
)
, is the sum of the links of all its pairs, i.e.,
{
(
m,w
)
∈M}
la
(
m, w
)
.
Notice that we can use other operators beside the sum to define the link strength, such
as, for example, the maximum or the product.
We now give a notion of stability that exploit the definition of the link additive-
strength given above.
Definition 5 (Link-additive-Stability).
Givenamarriage
M
,aman
m
, and a woman
w
, the pair
(
m, w
)
is a link-additive-blocking pair for
M
if the following conditions
hold:
-
la
(
m, w
)
>la
(
m
,w
)
,
-
la
(
m, w
)
>la
(
m, w
)
,
where
m
is the partner of
w
in
M
and
w
is the partner of
m
in
M
. A marriage is
link-additive-stable
if it does not contain link-additive-blocking pairs.
Example 8.
Let
be, respectively, the set of women and men.
Consider the following instance of an SMW,
P
:
{
w
1
,w
2
}
and
{
m
1
,m
2
}
-
m
1
:
w
[30]
>w
[3]
2
,
1
-
m
2
:
w
[4
1
>w
[3
2
,
-
w
1
:
m
[6]
2
>m
[5]
1
,
-
w
2
:
m
[10
1
>m
[2
2
.
In this example there is a unique link-additive-stable marriage, that is
M
1
=
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
, which has additive-link
la
(
M
1
)= 35+5= 40
. Notice that such a marriage
has an additive-link higher than the male-optimal stable marriage of
c
(
P
)
that is
M
2
=
{
}
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
which has additive-link
la
(
M
2
)=13+10=23
.
The strength of the link of a pair (man,woman), and thus the notion of link stability, can
be also defined by considering the maximum operator instead of the sum operator.
