Abstract Gale-Shapley 2 (1) 2 (2) (1)

( ) 2011 3

Abstract Gale-Shapley 2 (1) 2 (2) (1)

1 1 1.1........................................... 1 1.2......................................... 2 2 4 2.1................................... 4 2.1.1 Gale-Shapley.......................... 4 2.1.2............................ 6 2.2................................... 9 2.2.1.............................. 9 2.2.2.............................. 10 2.2.3................................. 12 3 14 3.1.............................. 14 3.2........................................ 17 4 20 4.1.................................... 20 4.2........................................ 23 4.2.1 Knuth (1976).............................. 23 4.2.2............................. 24 5 27 A 28 A.1 3.2........................................ 28 A.2 4.1........................................ 29 Acknowledgements 32 i

References 33 ii

1 1.1 2 two-sided matching Gale and Shapley (1962) deferred acceptance *1 Roth and Vande Vate (1990) Gale-Shapley *1 Roth (1991) 1

2 Gale-Shapley 2 3 (1) (2) (3) Gale-Shapley (1) (2) strategy-proof 1 (1) (2) (3) Roth (1989) 1.2 2 Gale-Shapley Gale-Shapley Gale-Shapley 2

3 4 Roth and Vande Vate (1990) 5 2 3

2 Gale-Shapley Roth and Vande Vate (1990) Roth and Vande Vate (1990) Adachi (2000) Adachi (2000) 2.1 2.1.1 Gale-Shapley 1 1 2 Gale-Shapley Gale-Shapley Gale-Shapley (M, W; P) 2 M W M = {m 1, m 2,..., m p } p 4

W = {w 1, w 2,..., w q } q m M W {m} m w W M {w} w rational *1 completeness *2 transitivity {{ m } m M } {{ w } w W } 2 {{ m } m M, { w } w W } P Gale-Shapley 1 outcome Definition 2.1 matching µ µ µ(x) = x M W M W µ(m) m µ(m) W µ(w) w µ(w) M Definition 2.2 µ stable µ µ (IR) (S) (IR) (S) µ(m) m m for all m M and µ(w) w w for all w W; and (m, w) M W such that w m µ(m) and m w µ(w). 2.2 (S) (m, w) blocking pair Gale and Shapley (1962) *3 Gale-Shapley (1) Gale-Shapley *4 (2) (3) *1 m W x y x m y y m x *2 m W x y z x m y y m z x m z *3 *4 strategy-proof Gale-Shapley 5

Gale-Shapley (1) 2.2 Gale-Shapley 2.1.2 Roth (1989) Gale-Shapley (M, W; P) Gale-Shapley P = {P(m 1 ),..., P(m p ), P(w 1 ),..., P(w q )} *5 P(m) m Q(m) w P(w) Q(w) Q = {Q(m 1 ),..., Q(m p ), Q(w 1 ),..., Q(w q )} *6 h Q µ Q µ = h(q) Q h h(q) Q *7 h (N = M W, Q, h, P) i M W Q (i) Q i µ = h(q (i), Q i ) µ(i) ν = h(q(i), Q i ) ν(i) i M W Q (i) *5 P *6 P Q *7 2 µ ν µ ν 1 ν µ ν 6

Q (i) Q i Theorem 2.1 (Roth (1982)) Gale-Shapley 2 Theorem 2.2 (Dubins and Freedman (1981)) (N = M W, Q, h, P) Q = (Q(m 1 ),..., Q(m p ), Q(w 1 ),..., Q(w q )) i M W Q(i) Q i 2.1 Corollary 2.1 (Roth and Sotomayor(1990)) 2.2 *8 2.1 Theorem 2.3 (Roth (1984)) h (N = M W, Q, h, P) P = (P (w)) w W P 1 *8 Gale and Sotomayor (1985) 7

*9 Γ = (N = M W, Q, h, U = U i, F). h : Q L[M] M L[M] U i u = {u i } i N U F F F σ i U i σ = {σ} i N Q = σ(u) h(σ(u)) u i i u i (σ) = p i (u i u i )u i [h(σ(u i, u i ))]. u i U i p i (u i u i ) i F Γ σ i N u i U i i σ i u i (σ ) u i (σ i, σ i ) h Q h(q) 1 2.3 i N Theorem 2.4 (Roth (1989)) Gale-Shapley 2 Γ h(σ (u)) 1 σ 1 h *9 Roth (1989) i Q(i) D i 8

3 3 2.2 2.2.1 Roth and Vande Vate (1990) Gale-Shapley Theorem 2.5 (Roth and Vande Vate (1990)) µ (M, W; P) µ = µ 1 µ k µ 1,..., µ k i = 1,..., k 1 µ i (m i, w i ) µ i+1 µ i (m i, w i ) Knuth (1976) 2.2 (S) (S) (S) * 10 Gale-Shapley (1) (1) (3) Gale-Shapley (1) (3) Roth and Vande Vate (1990) *10 Roth and Sotomayor (1990) 9

2.5 Corollary 2.2 (Roth and Vande Vate (1990)) µ 1 1 1 Knuth (1976) 4 Adachi (2000) 2.2.2 Adachi (2000) * 11 2.1 µ M W M W 3 (1) x M W µ µ(x) = x (2) µ(m) m µ(m) W (3) µ(w) w µ(w) M (1) 1 1 (2) (3) 3 (1) Definition 2.3 v M : M M W v W : W M W 2 *11 Gale and Shapley (1962) Tarski Adachi (2000) 10

v = (v M, v W ) v M (m) m v M (m) W; v W (w) w v W (w) M. (2.2.1) 1 1 1 m w w w w w m w 2.3 1 Adachi (2000) v M (m) = max m {w W : m w v W (w)} {m} for all m M; v W (w) = max w {m M : w m v M (m)} {w} for all w W. (2.2.2) (2.2.2) (2.2.2) (2.2.2) 1 (2.2.2) v M v W v W v M 11

Adachi (2000) 2.2.3 Roth and Vande Vate (1990) 2 Blair (1988) Alkan (2001, 2002) Alkan and Gale (2003) Alkan (2001, 2002) 2 3 2.1.2 12

4 Roth and Vande Vate (1990) 4 13

3 2.2 Roth and Vande Vate (1990) 2 2 3.1 Gale-Shapley Roth and Vande Vate (1990) W P(W) P(W) K W K W K W K = M K W K (M, W; P, K) K- 2.2 2 Assumption 3.1 Assumption 3.2 14

3.1 3.2 2.2 (IR) 3.2 *1 Definition 3.1 K-GS µ K- K-stable µ (KS) (KS) (m, w) M K W such that w m µ(m) and m w µ(w). K- K- Example 3.1 M = {m 1, m 2, m 3 } W = {w 1, w 2, w 3 } *2 m1 : w 1, w 2, w 3, m 1, w1 : m 1, m 2, m 3, w 1 ; m2 : w 1, w 2, w 3, m 2, w2 : m 1, m 3, m 2, w 2 ; m3 : w 1, w 3, w 2, m 3, w3 : m 1, m 2, m 3, w 3. K = {m 1, m 2, m 3, w 2, w 3 } w 2 w 3 w 1 µ 1 K- µ 2 *1 K- 3.1 3.1 K- K- K- µ 1 w 2 w 3 w 1 µ 1 m 2 w 1 m 2 w 1 *2 15

(m 1, w 2 ) K- *3 µ 1 = ( ) m1 m 2 m 3, µ w 2 w 1 w 2 = 3 ( ) m1 m 2 m 3. w 3 w 1 w 2 K-GS K K- Lemma 3.1 K-GS (M, W; P, K = M K W ) K = M K W (M, W; P, K ) K- M M K W K W M M K W K W µ M K- µ w m µ(m) m w µ(w) M K W (m, w) K W = K W µ K K- K W K W w w K W w K W W µ K K- w m µ(m) m w µ(w ) M K W (m, w ) w w K W w K W W (m, w ) M K W w m µ(m) m w µ(w ) M K W (m, w ) K W K W µ K K- K W K W µ M µ M 3.1 Proposition 3.1 K-GS K- Gale and Shapley (1962) 3.1 K = M W M W K W M Roth and Vande Vate (1990) K-GS Proposition 3.2 K K-GS (M, W; P, K) µ (M, W; P, K) µ = µ 1 µ k K- µ 1,..., µ k i = 1,..., k 1 µ i (m i, w i ) µ i+1 µ i (m i, w i ) *3 16

K-GS Roth and Vande Vate (1990) A.1 3.2 * 4 K- Roth and Vande Vate (1990) (M, W; P) p q Gale-Shapley Gale- Shapley K K-GS (M, W; P, K) K W = K = M = M K- M = {µ 1,..., µ n } 3.1 M Gale-Shapley 3.2 3.1 K M W K-GS M K- G = (W, { w } w W, {S w } w W ; M, { m } m M ), (1) W = {w 1,..., w q } (2) w W w (3) S w = {r w, n w } w r w reveal n w *5 (4) M = {m 1,..., m p } (5) m M m *4 Fishburn (1978) Perea et al. (2006) *5 2 17

s w1 S w1,..., s wq S wq (s w1,..., s wq ) S w1 S wq K K-GS K-GS K- M p M p M (M) f : S w1 S wq (M) K- w i W M w i M(w i ) M(w i ) = {m 1,..., m k,..., m l,..., m p } 1 k < l p k l m k wi m l K- M p M w i p M(wi ) (M(w i )) p M K- µ j M p M (µ j ) p M(wi ) m M(w i ) p M(wi )(m) m M(w i ) p M(wi )(m) = j { j : µ j (w i ) = m } p M (µ j ). g wi : (M) (M(w i )) f g wi h wi = g wi f : S w1 S wq (M(w i )) (s w1,..., s wq ) S w1 S wq M(w i ) p M(wi ) p M(wi ) = h wi (s w1,..., s wq ) H wi : M(w i ) [0, 1] m k M(w i ) H wi (m k ) = m k m = m 1 p M(wi )(m). M(w i ) h w i H w i Definition 3.2 M wi 2 h wi h w i h wi h w i h wi first degree stochastically dominates h w i ; h wi D 1 h w i m M wi H wi (m) H w i (m) 1 18

w i Definition 3.3 w i s wi S wi s wi = (s w1,..., s wi 1, s wi+1,..., s wq ) best response under first degree stochastic dominance; FSD- h wi (t wi, s wi ) D 1 h wi (s wi, s wi ) t wi S wi Definition 3.4 G s = (s w 1,..., s w q ) first degree stochastic dominance equilibrium w i W s w i s w i FSD- K- K- 1 FSD- K- 2 19

4 4.1 Roth and Vande Vate (1990) 3 M = {m 1, m 2, m 3 } 3 W = {w 1, w 2, w 3 } Gale-Shapley 3.1 m w w w w w m w Definition 4.1 µ C : M W M W (4.1.1) C max{w W : i w µ(w)} {i} if i M; C(i) = i (4.1.1) max{m M : i m µ(m)} {i} if i W. i (4.1.1) i µ i µ µ(w) w i µ w = µ(i) *1 {w W : i w µ(w)} i {w W : i w µ(w)} {i} i 1 C(i) i (4.1.1) Adachi (2000) (2.2.2) (4.1.1) µ C 3 3 Gale-Shapley µ *1 µ i = µ(w) w = µ(i) 20

2.2 (IR) *2 3 (1) µ C (m, w) C(m) = w C(w) = m (m, w) ν (m, w) µ 1 i M W C(i) = i i ν (2) (1) µ(w) µ(m) µ 2 ν (1) (3) µ ν (1) 3 C µ ν Example 4.1 M = {m 1, m 2, m 3 } W = {w 1, w 2, w 3 } m1 : w 2, w 1, w 3, m 1, w1 : m 1, m 3, m 2, w 1 ; m2 : w 1, m 2, w 3, w 2, w2 : m 3, m 1, m 2, w 2 ; m3 : w 1, w 2, w 3, m 3, w3 : m 1, m 3, m 2, w 3. µ µ = ( ) m1 m 2 m 3. w 1 w 2 w 3 C *2 21

C(m 1 ) = max m1 {w 1, w 2, w 3 } {m 1 } = w 2 ; C(m 2 ) = max m2 {w 2 } {m 2 } = m 2 ; C(m 3 ) = max m3 {w 2, w 3 } {m 3 } = w 2 ; C(w 1 ) = max w1 {m 1, m 2, m 3 } {w 1 } = m 1 ; C(w 2 ) = max w2 {m 1, m 3 } {w 2 } = m 3 ; C(w 3 ) = max w3 {m 3 } {w 3 } = m 3. C m 1 m 3 w 2 w 2 w 3 m 3 3 ν (1) (m 3 = C(w 2 ), w 2 = C(m 3 )) ν (m 3, w 2 ) µ (2) m 2 w 3 m 2 w 3 2 3 m 1 w 2 w 1 m 1 (m 1, w 1 ) ν ( ) m1 m ν = 2 m 3. w 1 w 2 w 3 4.1 ν ν C C(m 1 ) = max m1 {w 1, w 3 } {m 1 } = w 1 ; C(m 2 ) = max m2 {w 3 } {m 2 } = m 2 ; C(m 3 ) = max m3 {w 2, w 3 } {m 3 } = w 2 ; C(w 1 ) = max w1 {m 1, m 2, m 3 } {w 1 } = m 1 ; C(w 2 ) = max w2 {m 1, m 3 } {w 2 } = m 3 ; C(w 3 ) = max w3 {w 3 } = w 3. ν C C 22

Proposition 4.1 µ µ C C C(i) = i for all i M W. (4.1.2) Proof: A.2 4.2 C (3) (1) C Knuth (1976) 4.2.1 Knuth (1976) M = {m 1, m 2, m 3 } W = {w 1, w 2, w 3 } m1 : w 2, w 1, w 3, m 1, w1 : m 1, m 3, m 2, w 1 ; m2 : w 1, w 3, w 2, m 2, w2 : m 3, m 1, m 2, w 2 ; m3 : w 1, w 2, w 3, m 3, w3 : m 1, m 3, m 2, w 3. µ 1 µ 6 6 µ 5 µ 6 ( m1 m µ 1 = 2 m 3 µ 4 = w 1 w 2 w 3 ), µ 2 = ( ) m1 m 2 m 3, µ w 3 w 2 w 5 = 1 ( ) m1 m 2 m 3, µ w 2 w 1 w 3 = 3 ( ) m1 m 2 m 3, µ w 2 w 3 w 6 = 1 ( ) m1 m 2 m 3 ; w 3 w 1 w 2 ( ) m1 m 2 m 3. w 1 w 3 w 2 Knuth (1976) µ 1 µ 2 µ 3 µ 4 µ 1. (4.2.1) 23

4.2.2 C Knuth (1976) µ 1 C 3 C(m 1 ) = max m1 {w 1, w 2, w 3 } {m 1 } = w 2 ; C(m 2 ) = max m2 {w 2 } {m 2 } = w 2 ; C(m 3 ) = max m3 {w 2, w 3 } {m 3 } = w 2 ; C(w 1 ) = max w1 {m 1, m 2, m 3 } {w 1 } = m 1 ; C(w 2 ) = max w2 {m 1, m 2, m 3 } {w 2 } = m 3 ; C(w 3 ) = max w3 {w 2, w 3 } {w 3 } = m 3. (1) C(m 3 ) = w 2 C(w 2 ) = m 3 (m 3, w 2 ) (2) (1) m 2 = µ 1 (w 2 ) w 3 = µ 1 (m 3 ) (3) (m 1, w 1 ) µ 6 µ 2 C 3 C(m 1 ) = max m1 {w 1, w 2, w 3 } {m 1 } = w 2 ; C(m 2 ) = max m2 {w 1 } {m 2 } = w 1 ; C(m 3 ) = max m3 {w 1, w 2, w 3 } {m 3 } = w 1 ; C(w 1 ) = max w1 {m 2, m 3 } {w 1 } = m 3 ; C(w 2 ) = max w2 {m 1, m 3 } {w 2 } = m 3 ; C(w 3 ) = max w3 {m 3 } {w 3 } = m 3. (1) C(w 1 ) = m 3 C(m 3 ) = w 1 (m 3, w 1 ) (2) (1) m 2 = µ 2 (w 1 ) w 3 = µ 2 (m 3 ) (3) (m 1, w 2 ) µ 5 24

µ 3 C 3 C(m 1 ) = max m1 {w 1, w 3 } {m 1 } = w 1 ; C(m 2 ) = max m2 {w 1 } {m 2 } = w 1 ; C(m 3 ) = max m3 {w 1, w 2 } {m 3 } = w 1 ; C(w 1 ) = max w1 {m 1, m 2, m 3 } {w 1 } = m 1 ; C(w 2 ) = max w2 {m 1, m 3 } {w 2 } = m 3 ; C(w 3 ) = max w3 {m 1 } {w 3 } = m 1. (1) C(m 1 ) = w 1 C(w 1 ) = m 1 (m 1, w 1 ) (2) (1) m 2 = µ 3 (w 1 ) w 3 = µ 3 (m 1 ) (3) (m 3, w 2 ) µ 6 µ 6 µ 4 C 3 C(m 1 ) = max m1 {w 1, w 2, w 3 } {m 1 } = w 2 ; C(m 2 ) = max m2 {w 2 } {m 2 } = w 2 ; C(m 3 ) = max m3 {w 1, w 2 } {m 3 } = w 1 ; C(w 1 ) = max w1 {m 1, m 2, m 3 } {w 1 } = m 1 ; C(w 2 ) = max w2 {m 1, m 2 } {w 2 } = m 1 ; C(w 3 ) = max w3 {m 1, m 2 } {w 3 } = m 1 (1) C(w 2 ) = m 1 C(m 1 ) = w 2 (m 1, w 2 ) (2) (1) m 2 = µ 4 (w 2 ) w 3 = µ 4 (m 1 ) (3) (m 3, w 1 ) µ 5 (4.2.1) C C Knuth (1976) µ 1 w 2 w 2 C(w 2 ) = max w2 {m 1, m 2, m 3 } {w 2 } = m 3 25

µ 1 m 2 = µ 1 (w 2 ) m 1 m 3 w 2 m 3 µ 1 w 3 = µ 1 (m 3 ) w 2 m3 w 3 = µ 1 (m 3 ) w 2 {m 1, m 2, m 3 } {m 1, m 2 } C C(w 2 ) = max w2 {m 1, m 2 } {w 2 } = m 1 C µ 2 (4.2.1) µ 1 µ 2 m 3 µ 2 w 3 = µ 2 (m 3 ) w 1 w 2 m 3 w1 m 2 = µ 2 (w 1 ) m 3 {w 1, w 2, w 3 } {w 2, w 3 } C C(m 3 ) = max m3 {w 2, w 3 } {m 3 } = w 2 µ 3 (4.2.1) µ 2 µ 3 w 1 w 1 m1 w 3 = µ 3 (m 1 ) C C(w 1 ) = max w1 {m 2, m 3 } {w 1 } = m 3 µ 4 µ 4 m 1 w 2 m 1 w2 m 2 = µ 4 (w 2 ) 1 C C(m 1 ) = max m1 {w 1, w 3 } {m 1 } = w 1 µ 1 (4.2.1) Knuth (1976) 26

5 Roth and Vande Vate (1990) Roth and Vande Vate (1990) Gale and Shapley (1962) Roth and Vande Vate (1990) 2.5 Gale-Shapley C 4 3 3 Gale-Shapley 4 4 27

A A.1 3.2 3.1 (KS) µ 1 µ 1 (m 1, w 1 ) µ 1 k = 1 µ 2 µ 2 (m 1 ) = w 1 µ 1 (m 1, w 1 ) A(1) = {m 1, w 1 } A(1) (m 2, w 2 ) µ 2 {m 2, w 2 } A(1) µ k i = 1,..., k 1 A(i) 2 (A1) A(i) A(i + 1); (A2) A(i). {A(i) : i = 1, 2,... } i A(i) = M W A k A(i) = M W (A2) µ k (A1) (A2) {A(i) : i = 1,..., k} i = q A(q) 2 (MI1) (MI2) A(q) µ q+1 ; µ q+1 A(q) A(q). (MI1) (A2) (A1) A 28

i = 1 A(1) = {m 1, w 1 } µ 2 µ 2 A(1) m 1 A(1) w 1 = µ 2 (m 1 ) A(1) i = 1 2 (MI1) (MI2) i = k + 1 µ q+1 (MI1) m q+1 w q+1 A(q) (m q+1, w q+1 ) µ q+1 3 (i) (ii) (iii) m q+1 A(q) w q+1 A(q); m q+1 A(q) w q+1 A(q); m q+1 A(q) w q+1 A(q). (i) µ q+2 (m q+1, w q+1 ) w q+1 = µ q+2 (m q+1 ) A(q + 1) = A(q) {w q+1 } µ q+1 m q+1 A(q + 1) µ q+2 (MI1) (MI2) m q+1 µ q+1 w q+2 = µ q+1 (m q+1 ) µ q+2 A(q+1) m q+2 w q+2 = µ q+1 (m q+1 ) (m q+2, w q+2 ) µ q+3 (m q+2, w q+2 ) µ r+1 r + 1 q + 2 A(r) µ r+1 A(r) A(q + 1) A(q + 1) (MI1) (MI2) A(q + 1) = A(q) {w q+1 } r q + 1 A(r) A(q) (A1) (ii) (i) (iii) µ q+1 (m q+1, w q+1 ) µ q+2 A(q + 1) = A(q) {m q+1, w q+1 } A(q + 1) A(q) A(q + 1) µ q+2 (MI1) (MI2) 3 i = q + 1 A(q + 1) 2 (MI1) (MI2) A.2 4.1 µ µ C (4.1.2) m i (1) µ m i w i = µ(m i ) C(m i ) = w i µ 2.2 (S) m j wi m i m j M µ(m j ) m j w i {m M : w i m µ(m)} 29

m m i = µ(w i ) m C C(w i ) = max wi {m M : w i m µ(m)} {w i } = max wi {µ(w i ) w i } µ (IR) µ(w i ) wi w i C(w i ) = max wi {µ(w i ) w i } = µ(w i ) = m i. C(m i ) = w i C(w i ) = m i C C(m i ) = C(w i ) = m i (2) µ m i µ (S) w j mi m i w j W µ(w j ) w j m i {w W : m i w µ(w)} w W m i mi w j C (4.1.1) C(m i ) = max mi {w W : m i w µ(w)} {m i } = m i. C C(m i ) = C(m i ) = m i w i W C C(w i ) = w i µ C (4.1.2) µ µ (4.1.2) 4 (1) m i M w i = µ(m i ) W C(m i ) = w i C(w i ) = m i (2) m i M m i = µ(m i ) C(m i ) = m i (3) w k W m k = µ(w k ) M C(w k ) = m k C(m k ) = w k (4) w k W w k = µ(w k ) C(w k ) = w k (3) (1) (4) (2) m i (1) (2) (1) (2) (4) µ (1) C(m i ) = w i C (4.1.1) w i 30

{w W : m i w µ(w)} {m i } mi m i w j µ(w j ) w j w i = µ(m i ) mi w j (A.2.1) w i = µ(m i ) mi m i (A.2.2) C(w i ) = m i (4.1.1) m i {m M : w i m µ(m)} {w i } wi w i m j µ(m j ) m j m i = µ(w i ) wi m j (A.2.3) m i = µ(w i ) wi w i (A.2.4) (2) C(m i ) = m i (4.1.1) m i {w W : m i w µ(w)} {m i } mi m i w j µ(w j ) w j m i = µ(m i ) mi w j (A.2.5) (4) (2) C(w k ) = w k w k ml µ(m l ) m l w k = µ(w k ) wk m l (A.2.6) (A.2.2) (A.2.4) µ 2.2 (IR) (A.2.1) (A.2.3) (A.2.5) (A.2.6) (S) 31

Acknowledgements 2011 3 32

References Adachi, H. (2000): On a Characterization of Stable Matchings, Economics Letters, 68, 43 49. Alkan, A. (2001): On Preferences over Subsets and the Lattice Structure of Stable Matchings, Review of Economic Design, 6, 99 111. Alkan, A., Gale, D. (2002): A Class of Multipartner Matching Markets with a Strong Lattice Structure, Economic Theory, 19, 737 746. Alkan, A. (2003): Stable Schedule Matching under Revealed Preference, Journal of Economic Theory, 112, 289 306. Blair, C. (1988): The Lattice Structure of the Set of Stable Matchings with Multiple Partners, Mathematics of Operations Research, 13, 619 628. Dubins, L. E., Freedman, D. A. (1981): Machiavelli and the Gale-Shapley Algorithm, The American Mathematical Monthly, 88, 485 494. Fishburn, P. C. (1978): Non-cooperative Stochastic Dominance Games, International Journal of Game Theory, 7, 51 61. Gale, D., Shapley, L. (1962): College Admissions and the Stability of Marriage, The American Mathematical Monthly, 69, 9 15. Gale, D., Sotomayor, M. A. O. (1985): Ms. Machiavelli and the Stable Matching Problem, The American Mathematical Monthly, 92, 261 268. Knuth, D. E. (1976): Mariages Stables, Montreal, Les Presses de l Universite de Montreal. Perea, A., Peters, H. Schulteis, T. Vermeulen, D. (2006): Stochastic Dominance Equilibria in Two-person Noncooperative Games, International Journal of Game Theory, 34, 457 473. Roth, A. E. (1982): The Economics of Matching Stability and Incentives, Mathematics of Operations Research, 7, 617 628. Roth, A. E. (1984): Misrepresentation and Stability in the Marriage Problem, Journal of Economic Theory, 34, 383 387. Roth, A. E. (1989): Two-Sided Matching with Incomplete Information about Others Preferences, Games and Economic Behavior, 1, 191 209. Roth, A. E. (1991): Incentives in Two-Sided Matching with Random Stable Mechanithms, Economic Theory, 1, 31 44. 33

Roth, A. E., Sotomayor, M. A. O. (1990): Two-sided Matching: A Study in game-theoretic modeling and analysis, Cambridge, Cambridge University Press. Roth, A. E., Vande Vate, J. H. (1990): Random Paths to Stability in Two-Sided Matching, Econometrica, 58, 1475 1480. 34