Information Technology Reference
In-Depth Information
2.3
Stable Marriage Problems with Weighted Preferences
In classical stable marriage problems, men and women express only qualitative prefer-
ences over the members of the other sex. For every pair of women (resp., men), every
man (resp., woman) states only that he (resp., she) prefers a woman (resp., a man) more
than another one. However, he (resp., she) cannot express how much he (resp., she)
prefers such a woman (resp., a man). This is nonetheless possible in stable marriage
problems with weighted preferences.
A
stable marriage problem with weighted preferences
(SMW) [12] is a classical SM
where every man/woman gives also a numerical preference value for every member of
the other sex, that represents how much he/she prefers such a person. Such preference
values are natural numbers and higher preference values denote a more preferred item.
Given a man
m
and a woman
w
,the
preference value
for man
m
(resp., woman
w
)of
woman
w
(resp., man
m
) will be denoted by
p
(
m, w
)
(resp.,
p
(
w,m
)
).
Example 3.
Let
{w
1
,w
2
}
and
{m
1
,m
2
}
be respectively the set of women and men. An
instance of an SMW is the following:
-
m
1
:
w
[9
1
>w
[1
2
(i.e., man
m
1
prefers woman
w
1
to woman
w
2
, and he prefers
w
1
with value
9
and
w
2
with value
1
),
-
m
2
:
w
[3
1
>w
[2
2
,
-
w
1
:
m
[2
2
>m
[1
1
,
-
w
2
:
m
[3
1
>m
[1
2
.
The numbers written into the round brackets identify the preference values.
In [12] they consider stable marriage problems with weighted preferences by looking
at the stable marriage that maximizes the sum of the preference values. Therefore, they
use the classical definition of stability and they use preference values only when they
have to look for the optimal solution. We want, instead, to use preference values also to
define new notions of stability and optimality.
We will introduce new notions of stability and optimality that are based on the
weighted preferences expressed by the agents and we will show how to find them by
adapting the classical Gale-Shapley algorithm [4] for SMs described in Section 2.
3
α
-Stability
A simple generalization of the classical notion of stability requires that there are not two
people that prefer
with at least degree
α
(where
α
is a natural number) to be married to
each other rather than to their current partners.
Definition 1 (
α
-stability).
Let us consider a natural number
α
with
α
1
. Given a
marriage
M
,aman
m
, and a woman
w
, the pair
(
m, w
)
is an
α
-blocking pair for
M
if the following conditions hold:
≥
-
m
prefers
w
to his partner in
M
,say
w
,byatleast
α
(i.e.,
p
(
m, w
)
p
(
m, w
)
−
≥
α
),
