☉Preference List

Male

　

Female

　

A

2

5

1

3

4

1

E

A

D

B

C

B

1

2

3

4

5

2

D

E

B

A

C

C

2

3

5

4

1

3

A

D

B

C

E

D

1

3

2

4

5

4

C

B

D

A

E

E

5

3

2

1

4

5

D

B

C

E

A

☉Matching(Marriage):1-1,onto mapping

☉Unstable marriage: a 1,b 2 s.t. a:2_1,2:a b

☉Example:A1,B3,C2,D4,E5 is unstable

☉Goal: Find a stable matching

☉Algorithm

Each man M in turn becomes suitor, proposes to each W on his list:

(1)W is free=> MW engaged

(2)For W,M>>current fiancee M' =>MW engage, M' becomes suitor

(3)M'>>M=> M proposes to next W on his list

☉Analysis

(1)Program terminates?

(2)Generate a Matching?

(3)Stable?

(4)Male optimal: No man does better in other stable matching

(5)Female pessimal: No woman does worst in other stable matching