Database Reference
In-Depth Information
besteht nun darin, alle Frauen aus W und alle Manner aus M stabil miteinander
zu verheiraten.
Um ein solches SMP formal darzustellen, nehmen wir an, dass fur jede Frau
w
∈
W die Relation
w
⊆
M
×
M
ihre Praferenzen bzgl. aller Manner angibt, d.h., m
1
w
m
2
druckt aus, dass w den
Mann m
1
dem Mann m
2
vorzieht. Entsprechend druckt fur jeden Mann m
∈
M die
Relation
m
⊆
W
×
W
die Vorlieben von m bzgl. der Frauen in W aus. Eine
Losung des SMP
ist eine
bijektive Abbildung S : M
W angibt,
dass m mit S(m) und w mit S
−1
(w) verheiratet ist. Weiterhin muss gelten, dass
kein Paar (m, w)
→
W ,diefur alle m
∈
M und fur alle w
∈
∈
M
×
W existiert, so dass
w
S
−1
(w)
w
m
S(m)
und
m
gilt, d.h., dass der Mann m die Frau w seiner Ehefrau S(m) vorzieht und w den
Mann m ihrem Ehemann S
−1
(w) vorzieht. Dann werden alle Ehen als stabil be-
trachtet.
Ein solches SMP kann auch durch das Argumentationssystem
AS
SMP
mit den
folgenden Komponenten reprasentiert werden:
AS
SMP
=(A
SMP
,→)
A
SMP
= M
×
W,
→⊆A
SMP
×A
SMP
(m
1
,w
1
)
→
(m
2
,w
2
)gdw.
m
1
= m
2
und w
1
m
1
w
2
oder
w
1
= w
2
und m
1
w
1
m
2
Wie das folgende Theorem aufzeigt, besteht zwischen den (im oben ausgefuhrten
Sinn) stabilen Eheverbindungen des SMP und den stabilen Extensionen des Argu-
mentationssystems
AS
SMP
ein eineindeutiger Zusammenhang.
Theorem 10.80 (SMP und stabile Extensionen)
Eine Menge
S⊆A
SMP
ist
genau dann eine Losung des SMP, wenn
S
eine stabile Extension von AS
SMP
ist.
Beweis:
Wir nehmen zunachst an, dass
eine Losung
des Heiratsproblems wie oben angegeben ist. Zu zeigen ist dann, dass
S
=
{
(m, S(m))
|
m
∈
M
}
S
konflikt-
frei und eine stabile Extension von
AS
SMP
ist. Wenn
S
nicht konfliktfrei ware,
musste es (m
1
,S(m
1
)), (m
2
,S(m
2
))
(m
2
,S(m
2
)) geben.
Dies stunde aber im Widerspruch zur Definition von
AS
SMP
,daS eine Bijektion
ist und S(m
1
)
∈S
mit (m
1
,S(m
1
))
→
m
1
S(m
1
)bzw.m
1
S(m
1
)
m
1
gilt.
Um zu zeigen, dass
S
eine stabile Extension von
AS
SMP
ist, sei (m, w) /
∈
und (S
−1
(w),w)
S
.Dannist(m, S(m))
∈S
∈S
, und es gilt S(m)
m
w oder
S
−1
(w)
w
m,sonstwaren die Ehen (m, S(m)) und (S
−1
(w),w) nicht stabil. Also
gilt nach Definition von
AS
SMP
(m,
(m, w)
und damit S → (m, w). S greift also jedes Paar außerhalb von S an und ist daher
eine stabile Extension.
S
(m))
→
(m, w)oder(S
−1
(w),w)
→
