Information Technology Reference
In-Depth Information
free. When all men are engaged, the engaged pairs form the male optimal stable match-
ing. It is female optimal, of course, if the roles of male and female participants in the
algorithm were interchanged.
This algorithm needs a number of steps that, in the worst case, is quadratic in
n
(that is, the number of men), and it guarantees that, if the number of men and women
coincide, and all participants express a strict order over all the members of the other
group, everyone gets married, and the returned matching is stable.
Example 1.
Assume
n
=2
.Let
be respectively the set of
women and men. The following sequence of strict total orders defines a profile:
-
m
1
:
w
1
>w
2
(i.e., man
m
1
prefers woman
w
1
to woman
w
2
),
-
m
2
:
w
1
>w
2
,
-
w
1
:
m
2
>m
1
,
-
w
2
:
m
1
>m
2
.
For this profile, the male-optimal solution is
{
w
1
,w
2
}
and
{
m
1
,m
2
}
. For this specific
profile the female-optimal stable marriage coincides with the male-optimal one.
{
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
2.2 Stable Marriage Problems with Partially Ordered Preferences
In SMs, each preference ordering is a strict total order over the members of the other sex.
More general notions of SMs allow preference orderings to be partial [14,11,10,7,6].
This allows for the modelling of both indifference (via ties) and incomparability (via
absence of ordering) between members of the other sex. In this context, a stable mar-
riage problem is defined by a sequence of
2
n
partial orders,
n
over the men and
n
over
the women. We will denote with SMP a stable marriage problem with such partially
ordered preferences.
Given an SMP, we will sometimes use the notion of a
linearization
of such a problem,
which is obtained by linearizing the preference orderings of the profile in a way that is
compatible with the given partial orders.
A marriage
M
for an SMP is said to be
weakly-stable
if it does not contain blocking
pairs. Given a man
m
and a woman
w
, the pair
(
m, w
)
is a blocking pair if
m
and
w
are
not married to each other in
M
and each one
strictly prefers
the other to his/her current
partner.
A weakly stable marriage
M
dominates a weakly stable marriage
M
iff for every
man
m
,
M
(
m
)
M
(
m
)
or
M
(
m
)
M
(
m
)
(
means incomparable) and there is a
man
m
s.t.
M
(
m
)
>M
(
m
)
. Notice that there may be more than one undominated
weakly stable marriage for an SMP.
Example 2.
Let
≥
{
w
1
,w
2
}
and
{
m
1
,m
2
}
be respectively the set of women and men. An
instance of an SMP is the following:
-
m
1
:
w
1
> w
2
,
-
m
2
:
w
1
>w
2
,
-
w
1
:
m
1
m
2
,
-
w
2
:
m
1
>m
2
.
For this instance, both
M
1
=
{
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
and
M
2
=
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
}
are weakly stable marriages and
M
1
dominates
M
2
.
