Projekt:Einführung Marktdesign/Übungsaufgaben

Übungsblatt 2: Matching Market Algorithm

Aufgabe 1: One-to-One Matching und Stabilität

a) Wann ist ein Matching $\mu$ stabil ?

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

Pseudocode des Gale-Shapley Algorithm

/**
function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman who he has not proposed to yet
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}
*/

manPref:

1 0 3 2 4

0 2 1 3 4

1 0 4 3 2

2 4 1 0 3

1 2 0 3 4

womanPref:

4 3 0 2 1

2 3 0 1 4

2 0 4 1 3

4 1 2 3 0

3 2 4 0 1

Married couples (woman + man):

0 + 0

1 + 2

2 + 4

3 + 1

4 + 3

Gale-Shapley Algorithmus Animation

Aufgabe 2: One-to-One Matching und DAA

Betrachten Sie den folgenden Heiratsmarkt, in dem die Agenten strikte Präferenzen haben:

P( $m_{1}$ ) = $w_{1}$ , $m_{3}$ , $w_{4}$ , $w_{2}$

P( $m_{2}$ ) = $w_{3}$ , $w_{2}$ , $w_{1}$ , $w_{4}$

P( $m_{3}$ ) = $w_{3}$ , $w_{4}$ , $w_{2}$ , $w_{1}$

P( $m_{4}$ ) = $w_{4}$ , $w_{3}$ , $w_{1}$ , $w_{2}$

P( $w_{1}$ ) = $m_{4}$ , $m_{2}$ , $m_{3}$ , $m_{1}$

P( $w_{2}$ ) = $m_{4}$ , $m_{2}$ , $m_{3}$ , $m_{1}$

P( $w_{3}$ ) = $m_{3}$ , $m_{1}$ , $m_{4}$ , $m_{2}$

P( $w_{4}$ ) = $m_{2}$ , $m_{1}$ , $m_{3}$ , $m_{4}$

a) Wenden Sie den Gale-Shapley-Algorithmus an, in dem immer die Männer vorschlagen. Was sind die resultierenden Zuordnungen?

b) Wenden Sie den Gale-Shapley-Algorithmus an, in dem immer die Frauen vorschlagen. Was sind die resultierenden Zuordnungen?