KKY Slide201311 最近の更新履歴 yyasuda's website

Understanding Stable Matchings:

A Non-Cooperative Approach

KANDORI, Michihiro University of Tokyo

KOJIMA, Fuhito Stanford University

YASUDA, Yosuke National Graduate Institute for Policy Studies

interesting structures interesting structures Cooperative Game Theory

Stable Matchings

Existence of Stable Matching Best/worst Stable Matching

Non-Cooperative Game Theory

Strategic Complements

Existence of NE

Maximum/minimum NE

Cooperative Game Theory Non-Cooperative Game Theory

Strategic Complements

Nash equilibria of a game with

strategic complements

Stable Matchings

Existence of Stable Matching Best/worst Stable Matching

Existence of NE

Maximum/minimum NE

Review of Stable Matchings

Review of Strategic Complements

How to Bridge the Two

Review of Stable Matchings

Two-sided Matching Problem

One-to-one:

Men-Women (marriage markets)

One-to-Many:

Workers-Firms (labor markets)

Many-to-many:

Retailers-Suppliers

A general two-sided matching model

c ^∈ C a “college”

s has strict preference relation P_s over all C’ ^⊂ C.

Chosen set of s, Ch_s(C’)

C’

The (unique) most

preferred subset of C’

s ∈ S a “student”

Similar definitions for colleges

A matching _µ is a correspondence from

S

C to S

C where:

µ (s) ⊂ C is college(s) that s attends

µ ^{(c) ⊂} S is student(s) attending c

c ^∈ _µ (s) s ^∈ _µ (c) for all c, s

A matching _µ is (pairwise) stable if

(i) for all i, Ch

( _µ (i)) = _µ (i)

(ii) there is no unmatched pair (s,c) such that

c ^∈ Ch

( _µ (s)

c), and s ^∈ Ch

( _µ (c)

s)

S’

s

S”

not chosen in

_S’

not chosen in

_S”

substitutable

Substitutability FAILS when ….

S’

s

S”

chosen in S’

but not in S”

s’

Some

complementarities

When everyone has substitutable

preferences…

×

× ^×

× ^×

×

×

×

×

stable matchings

When everyone has substitutable

preferences…

×

× ^×

× ^×

×

×

×

×

stable matchings

best for all students

worst for all colleges worst for all students

best for all colleges

Review of Strategic Complements

≥ is a partial order on set X if

x ≥ y, y ≥ z x ≥ z

Examples:

(2) (x

,x

) ≥ (y

,y

) if x

≥ y

and x

≥ y

(3) ^≥ …. set inclusion ⊃

(1) ≥ …weak inequality in X=R

x ≥ y, y ≥ x x ₌ y

An ordered set (X, ≥) is a lattice if

for any x, y ^∈ X, inf {x, y} and sup {x, y}

exist.

Example:

X …. All subsets of C

Inf {x, y} = x ∩ y

≥ …. set inclusion ⊃

sup {x, y} = x ∪ y

A game has strategic complementarities if

x

x*

x* )

( ^∀

There is a maximum (pure) Nash equilibrium

_x

x

There is a minimum (pure) Nash equilibrium

Isn’t this similar to ….

• strategy spaces are (finite) lattices and

Then …

• the best replies are (weakly) increasing

×

× ^×

× ^×

×

×

×

×

Stable matchings

best for all students

worst for all colleges worst for all students

best for all colleges

Bridging Stable Matchings and

Games with Strategic Complements

Consider the following two-stage non-cooperative game, called students’ final offers game.

Students’ Final Offers Game

For simplicity, regard this as a game played

by students (college choices are automatic).

Each student applies to multiple colleges (or abstain), simultaneously with others. Each college chooses the best subsets of the applicants.

It is easy to check that,

Set of Nash equilibrium outcomes

||

Set of stable matchings

Students’ Final Offers Game

Each student applies to multiple colleges (or abstain), simultaneously with others. Each college chooses the best subsets of the applicants.

Three tricks to obtain a game with strategic complements

Allow overbooking by students

Multiple best replies → select the right one

Use substitutability of preferences

Allow overbooking by students

Strategy of student s: C_s ⊂ C

Ordering by set inclusion, i.e.,

larger set of colleges = larger strategy

Student can apply to any number of colleges.

If overbooked (e.g., one-to-many case),

student must compensate the colleges for any inconvenience and gets a very low payoff.

Three tricks to obtain a game with strategic complements

Multiple best replies → select the right one

A

(C

)

s, given other students’ applications C_-s . (1)

_Ch

_(A

_(C

₎₎

_{C - A}

_(C

₎

Three tricks to obtain a game with strategic complements

Multiple best replies → select the right one

A

(C

)

s, given other students’ applications C_-s . (1)

_Ch

_(A

_(C

₎₎

_{C - A}

_(C

₎

LBR

(C

)

Three tricks to obtain a game with strategic complements

Use substitutability of preferences

Largest best reply

LBR

(C

)

Starting with any Nash, add this part to the best reply of each player. Then…

We get another Nash with the same outcome. So, without loss of generality we can look at

Nash equilibria in the largest best replies.

Three tricks to obtain a game with strategic complements

Use substitutability of preferences

Largest best reply

LBR

(C

)

Three tricks to obtain a game with strategic complements

Use substitutability of preferences

Largest best reply

LBR

(C

)

= C - R_s(A_s(C_-s))

Colleges in A_s(C_-s) that s won’t choose

C_-s A_s(C_-s) R_s(A_s(C_-s)) LBR_s(C_-s)

Substitutability of

colleges’ preferences

Substitutability of s’ preferences

Three tricks to obtain a game with strategic complements

Use substitutability of preferences

Largest best reply

LBR

(C

)

Three tricks to obtain a game with strategic complements

C_-s LBR_s(C_-s)

We have obtained a game with strategic

complements, Nash = stable matching!

×

× ^×

× ^×

×

×

×

×

stable matchings

best for all students

worst for all colleges worst for all students

best for all colleges

“Smallest” Nash (students are applying to smallest sets of colleges)

The (“Cournot”) learning dynamic to reach the smallest equilibrium

C₁ C₂

BR₁ BR₂

(A version of) well-know algorithm to compute the student-optimal stable matching (Gale-Shpaley)

Assume one-to-one case: each student (/college) wants to match at most one college (/student).

A simple students’ offers game

Each student applies to one college (or abstain), simultaneously with others.

Each college chooses the best student from the applicants (could be empty).

Nash = stable matching (same as before)

How about “better college = higher strategy” ?

UT and KU.

Two Students: 1, 2

Both students like UT better than KU.

Both colleges like student 1 better than 2.

Best reply of 2: UT → KU

If Student 1: KU → UT

low high

low high

Example

If we have at least

THREE students and TWO colleges, there

is NO WAY to order students’ strategies to

make any simple students’ offers game to

be a game with strategic complements.

A simple students’ offers game

Each student applies to one college and then colleges respond.

Nash equilibria = Stable matchings

Impossibility Theorem:

More Results…

Small core (slope conditions):

Characterize # of stable matchings

Uniqueness, as a special case

Learning in supermodular game:

Compute median stable matchings

Micro-foundations:

T-mappings (Adachi, Ostrovsky, etc.)

Hatfield-Migrom mapping

Comparison to existing

monotone mappings to

compute stable matchings

Hatfield-Milgrom mapping

T-mapping (Adachi, Ostrovsky

and others)

In our students’ final offers game, another best

reply also “works”.

Largest best reply

LBR

(C

)

Best available

college All applications that are going to be rejected

Include only “good” colleges for s

Threshold best reply

TBR

(C

)

{c | c Ch ^≻ _∼

(A

(C

)) }

Offers by student s x_s ⊂ C, x_S = ( x_s )_s∈S Offers by college c x_c ⊂ S, x_C = ( x_c )_c∈C

Hatfield-Milgrom mapping

x_C’ = HM_C(x_S) = ( S – R_c({s | c∈x_s }))_c∈C

x_S’ = HM_S(x_C) = ( C – R_s({c | s∈x_c }))_s∈S

fixed points (x*

, x*

) ⇔ stable matchings

Offers by student s x_s ⊂ C, x_S = ( x_s )_s∈S Offers by college c x_c ⊂ S, x_C = ( x_c )_c∈C

T-mapping (Adachi, Ostrovsky and others)

x_S’ = T_S(x_C) = ( {c’ | c’ ∈ Ch_s({c | s∈x_c } U c’) } )_s∈S

fixed points (x*

, x*

) ⇔ stable matchings

x_C’ = T_C(x_S) = ( {s’ | s’ ∈ Ch_c({s | c∈x_s } U s’) } )_c∈C

T-mapping (Adachi, Ostrovsky and others)

T_C(x_S) = ( {s’ | s’ ∈ Ch_c({s | c∈x_s } U s’) } )_c∈C

s’ ∈ Ch_c({s | s^≠s’ c∈x_s } U s’)

s’ ∈ T

(x

)

Students who apply to college c under x

T

(x

)

LBR

(x

) = HM

(T

(x

))

Our largest best reply model:

x*

= HM

(T

(x*

))

x*

= HM

(x*

)

x*

= T

(x*

)

Our model of largest best replies in

students’ final offers game

effectively solves the mixture of

Hatfield-Milgrom and T-mappings

x*

= HM

(x*

)

x*

= T

(x*

)

TBR

(x

) = T

(T

(x

))

Our threshold best reply model:

x*

= T

(T

(x*

))

x*

= T

(x*

)

x*

= T

(x*

)

T

(x

)

Our model of threshold best replies

in students’ final offers game

effectively solves T-mappings

x*

= T

(x*

)

x*

= T

(x*

)

“Microfoundations” of T-mapping