pdf 公開中の記事 安田洋祐の研究室

1

Introduction to Market Design with

Practical Matching Mechanisms

Yosuke YASUDA

National Graduate Institute for Policy Studies (GRIPS) Email: yosuke.yasuda@gmail.com

Web: https://sites.google.com/site/yosukeyasuda/

2013 Winter

Outline of My Talk

- Survey + (Few) Theory + Practice

Frontier of Economics

Game Theory for Economic “Science”

Market Design for Economic “Engineering”

Market Design in Practice

Matching Problem and its Solution

Practice of GS Mechanism

Exchange Problem and its Solution

Practice of TTC Mechanism

GAME THEORY FOR

ECONOMIC “SCIENCE”

Frontier of Economics

2013 Winter 3

Traditional Economics

- Supply & Demand Analysis

Traditionally,

economics focused

(almost) only on ideal

market economy,

called “perfectively

competitive market.”

Supply and demand

is the main tool.

5

Silent Revolution in Economics

- Game Theory: New Mathematical Tool

Game theory makes it possible to study variety of social institutions other than the ideal market.

It dramatically changed economics since 80’s.

⇒ Is mathematics important in social science?

2013 Winter

Natural Science vs. Social Science

- Casual Comparison

Natural Science

Things follow consistent patterns: “natural laws.”

We cannot ask each object for the reason behind the event.

⇒ Mathematical models are necessary.

Social Science

Each person acts anyway she wants.

A person can explain why she took a specific action.

⇒ No mathematical model is needed?

Two Alternative Approaches

- Social Science alsoNeeds Math Model

2013 Winter 7

Institutional knowledge

Look into the “facts” in detail.

⇒ Superficial knowledge alone cannot explain economic movement.

Mathematical model (economic theory)

Look for the “laws” behind facts.

⇒ Two approaches complement each other. Q: What’s the fundamental economic law? A: Each person acts for her own interest.

A Genius Formulated Game Theory

- Seek for the ^“ Law ^” of Social Science

Von Neumann and Morgenstern (1944)

“We need essentially new mathematical theory to solve variety of problems in social science.”

They constructed the basic framework of game theory, but failed to establish a

general solution concept.

⇒ 6 year later, another young genius filled this gap…

9

A Beautiful Mind Discovered ^“ Law ^”

- Nash Equilibrium!

John Nash (1950) established THE solution concept:

In equilibrium, no one can benefit if she unilaterally changes her action.

The solution always exists.

John Harsanyi and Reinhard Selten significantly extended Nash equilibrium.

Triggered a thousands of applications of game theory.

⇒ Revolution by game theory!

2013 Winter

New Areas Pioneered by GT

- From Market Theory to Social Theory

How does economy function if market is immature or does not exist?

⇒ Economic History, Development Economics

How does government (politician, bureaucrat) behave?

⇒ Political Economics

What’s going on inside private companies?

⇒ Organizational Economics

How to compare different types of market economy?

⇒ Comparative Institutional Analysis

11

Three Fathers of Game Theory

- Nobel Prize (Economics) in 1994!

2013 Winter

Theoretical Revolution Continues ^…

- Nobel Prize for Game Theory since 1994

1996: Mirrlees, Vickrey

for their fundamental contributions to the economic theory of incentives under asymmetric information.

2001: Akerlof, Spence, Stiglitz

for their analyses of markets with asymmetric information.

2005: Aumann, Schelling

for having enhanced our understanding of conflict and cooperation through game-theory analysis.

2007: Hurwicz, Maskin, Myerson

for having laid the foundations of mechanism design theory.

13

The Last Year (2012) As Well

- Roth and Shapley for Market Design!

2013 Winter

MARKET DESIGN FOR

ECONOMIC “ENGINEERING”

Frontier of Economics

Market Design

- From Theory to Practice

Applying new insights in microeconomic

theory, market design tries to (re-)design

actual markets and to fix market failures.

Experiments and simulations are used to

check the performance. Engineering

New mechanisms proposed by economists

are implemented in real world. Practical

⇒

Let’s look at real life examples!

15 2013 Winter

[1] Spectrum Auctions

- The Greatest Auction Ever

The first spectrum auction was operated in New Zealand in 1990, which was not so successful.

How can we appropriately sell spectrum licenses with potentially highly interdependent values?

In 1994, on the advice of economists, the U.S.

Federal Communications Commission (FCC) started the simultaneous multi-rounds ascending-bid

(SMRA) auctions:

“The Greatest Auction Ever” (NY Times, 1995)

The British spectrum auction of 2000 designed by economists raised about 22.5billion pounds!

[2] Markets for New Doctors

- Economics Changes Labor Markets

In each year, around 20000 new American doctors are assigned to their hospitals via a centralized

clearinghouse: National Resident Matching Program.

Both students and hospitals submit their ranking

orders, and assignments are made based on these reported preferences.

This matching program was re-designed in 1998: (student-proposing) deferred acceptance algorithm.

Japan (2003-) and some regions in UK adapted the same resident matching program.

2013 Winter 17

[3] Kidney Exchange

- Economics Saves Lives

The shortage of transplantable kidneys is a serious problem: 11000 transplants / 70000+ waiting list.

A live-donor may want to donate her kidney to a

particular patient, say to her husband, but often it is biologically incompatible.

Economists provided a way to resolve this mismatch problem in 2004: pooling incompatible patient-donor pairs and appropriately exchange their partners.

This kidney exchange mechanism is implemented in New England, and started to save patients’ life!

[4] School Choice Program

- Economics Improves Education

School choice, which enables students to choose public schools beyond their residence area, is

implemented in many countries.

Its idea has broad public support, but how to

operate school choice remains actively debated.

Based on economists’ advise, NYC and Boston redesigned their mechanisms in 2003 and 2005.

Both practically and theoretically important issues remain to be solved: frontier of market design!

2013 Winter 19

Real Life Applications

- There are Many Success Stories!

Auction Design

Radio spectrum

Treasury bills

AdWords (Google)

Matching Mechanisms

Medical residency

Kidney exchange

Public school choice

21

Real Life Applications

- There are Many Success Stories!

Use “Money”

Radio spectrum

Treasury bills

AdWords (Google)

No “Money”

Medical residency

Kidney exchange

Public school choice

2013 Winter

Real Life Applications

- There are Many Success Stories!

Auction design

Radio spectrum

Treasury bills

AdWords (Google)

Paul Milgrom (Stanford)

Matching mechanisms

Medical residency

Kidney exchange

Public school choice

Alvin Roth (Harvard)

23

More on Public School Choice

- Institutional Background

Traditionally, students are assigned to public schools according to where they live.

Starting with school districts in the U.S. during 1980’s, several countries have adopted school choice programs.

In Japan, it was officially introduced in 1998.

Around 20% of the cities employ the system.

2013 Winter

Trend of School Choice in Japan

- Number of Adapting Cities is Increasing!

25

Why does Game Theory Matter?

- Choose Schools Wisely!

Seats are limited!

It is impossible to assign each student to his/her best school.

Need to (strategically) think which schools to apply / avoid.

Mechanism matters, because

Students’ assignments and incentives will vary.

General idea of school choice gaining political support, but the exact method is debated.

Game theory is used to tackle this issue.

2013 Winter

Lessons from Practices

- An Expert Says…

Prof. Alvin Roth lists three key factors for

successful market design:

 Marketplaces need to

1. Provide thickness, that is, they need to attract a sufficient proportion of market participants.

2. Overcome congestion that thickness brings, by making it possible to consider enough alternative transactions to arrive.

3. Make it safe and sufficiently simple to participate in the market.

27

Traditional Econ. vs. Market Design

- What’s New for Market Design?

Traditional Economics

Markets/institutions are exogenously given.

Mainly focuses on ideal markets, i.e., perfectly competitive market.

Supply & demand analysis.

Rely on market mechanism.

⇒ Importance of laws, custom, and the role of government are often under evaluated.

Market Design

Markets/institutions can be constructed.

Analyze also markets and institutions other than

perfectly competitive market.

Game theoretical analysis.

Try to fix market failure.

⇒ Institutional (re-)design that makes markets well-

functioned is crucial.

2013 Winter

MATCHING PROBLEM AND

ITS SOLUTION

Market Design in Practice

What is “Matching Problem”?

- Matching over Individuals between 2 Groups

Each member in one

group is matched

with a member in

the other group.

How can we achieve

desirable matching

outcomes?

2013 Winter 29

Variety of Matching Problems

- From the Simplest to the Most Complicated

One-to-One

 ^【Marriage Market^】 Men and Women

One-to-Many

 ^【Labor Market^】 Workers and Firms

 ^【School Choice^】 Students and Schools

Many-to-Many

 ^【Business^】 Upstream and Downstream Firms

A Simple Matching Problem

- 3 Boys and 3 Girls

Boys’ Preferences

Girls’ Preferences

How can/should we make partners in order to

achieve efficient or fair outcomes?

2013 Winter 31

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Inefficient Matching

- Suppose Make Couples in Alphabetical Order…

Boys’ Preferences

Girls’ Preferences

David-Helen, John-Linda => worst partners

Switching partners makes them better off!

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Pareto Improvement is Possible

- Clearly Superior to the Original Matching

Boys’ Preferences

Girls’ Preferences

Make all 4 better off while the other 2 same.

The original matching was Pareto inefficient.

2013 Winter 33

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Unstable Matching

- Suppose Boys Can Choose Girls in Order…

Boys’ Preferences

Girls’ Preferences

The outcome is always Pareto efficient!

But Mark-Susan has “justified-envy”…

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Pair Can “Block” the Outcome

- Mutually Preferable Pair Failed to be Matched

Boys’ Preferences

Girls’ Preferences

Mark-Susan can improve their situation.

The original outcome was unstable...

2013 Winter 35

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Theory of Stable Matching

- What is so Surprising?

Stable Matching _： No pair (or individual)

cannot become better off if they deviate.

 Everyone is matched with the best partner available to him/her! (given other pairs)

 Unstable mechanisms tend to be abandoned.

Properties of Stable Matching:

 Exists for ANY one-to-one matching problems.

 Every stable matching is Pareto efficient.

 Can be found by Gale-Shapley(GS) mechanism.

37

Table made by Al Roth (2002, Econometrica)

2013 Winter

How to Find Stable Matching

- (Boys-Proposing) GS Mechanism

1.

Everyone submits preference (ranking).

2.

Clearing house operates as follows:

1. Every boy proposes to his top ranked girls.

2. Each girl keeps the favorite boy among those who propose to her and reject all other boys.

3. Boy whenever gets rejected proposes to the girl who is ranked one below (on his ranking).

4. Girl switches tentative partner whenever more favorite boy proposes to her (and reject others).

3.

Outcome finalizes when no boy is rejected!

Remarks on GS Mechanism

- Which Side Makes Proposal Does Matter.

In general there are many stable matchings.

 Our example happens to have exactly one.

Two procedures produce different outcomes.

 Boys prop. _⇒ Best stable matching for ALL boys

 Girls prop. _⇒ Best stable matching for ALL girls

 This time, both derive the same (stable) outcome.

What is boys/girls best or optimal Stability?

 Every boy/girls is matched with the most favorite partner among the girls/boys who will become a partner in some stable matching.

2013 Winter 39

PRACTICE OF GS

MECHANISM

An Easy Way to Find Stable Matching

How to Use GS Mechanism

- 1

Round: Boys’ Proposal

Boys’ Preferences

Girls’ Preferences

David and John propose to Susan.

Mark proposes to Helen.

2013 Winter 41

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 1

Round: Girls’ Rejection

Boys’ Preferences

Girls’ Preferences

Susan keeps David and rejects John.

Helen keeps Mark.

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 2

Round: Boys’ Proposal

Boys’ Preferences

Girls’ Preferences

John rejected in the 1

round (by Susan)

proposes to Helen.

2013 Winter 43

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 2

Round: Girls’ Rejection

Boys’ Preferences

Girls’ Preferences

Helen switches her tentative partner to John

and reject Mark.

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 3

Round: Boys’ Proposal

Boys’ Preferences

Girls’ Preferences

Mark rejected in the 2

round (by Helen)

proposes to Susan.

2013 Winter 45

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 3

Round: Girls’ Rejection

Boys’ Preferences

Girls’ Preferences

Susan switches her tentative partner to Mark

and reject David.

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

How to Use GS Mechanism

- 4

Round: Boys’ Proposal

Boys’ Preferences

Girls’ Preferences

David rejected by Susan proposes to Linda.

No further rejection => Mechanism finishes!

2013 Winter 47

David John Mark

1^位位位位 Susan Susan Helen 2^位位位位 Linda Helen Susan 3^位位位位 Helen Linda Linda

Susan Linda Helen

1^位位位位 Mark Mark John 2^位位位位 David David Mark 3^位位位位 John John David

Properties of GS Mechanism

- Simple yet Powerful System of Matching

Incentive Problem

 No proposer has incentive to manipulate.

 Receiver may have such incentive…

There exist NO incentive compatible (strategy-proof) mechanism that implements stable matching.

Extension of GS Mechanism

 Allowing “unacceptable” is straightforward.

 Need to break “ties” if preferences are weak.

 Naturally extends to one-to-many problems.

Applications of GS Mechanism

- Let’s Make Use of GS Mechanism in Real Life!

Actual Examples in Practice

 Medical Residency Matching (Japan, US, UK)

 Attorney Training (Canada)

 Public School Choice (NYC, Boston)

 College Admission (Hong Kong)

Potential Applications

 Matching over students and research laboratories.

 Assignment of new employees (to division)

2013 Winter 49

EXCHANGE PROBLEM AND

ITS SOLUTION

Market Design in Practice

What is “Exchange Problem”?

- Exchange among Objects

Agents in a group try

to exchange their

items among them.

How can we achieve

desirable exchange

(assignment)?

2013 Winter 51

A Simple Exchange Problem

- 5 Members Exchanging Their Items

Members’ Preferences

How can/should we make transfers in order

to achieve efficient or fair allocation?

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Inefficient Allocation

- Suppose Receive Item from the Next Person…

Members’ Preferences

B receives C (5

) and D receives E (3

).

Exchanging the items makes them better off!

2013 Winter 53

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Pareto Improvement is Possible

- Clearly Superior to the Original Allocation

Members’ Preferences

Make B&D better off while other 3 the same.

The original allocation was Pareto inefficient.

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Receiving Worse Item than His/Hers

- Suppose Members can Select Items in Order…

Members’ Preferences

The outcome is always Pareto efficient.

B receives a worse item than his endowment.

2013 Winter 55

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Individual Can “Block” the Outcome

- B is not Willing to Exchange his Item…

Members’ Preferences

B prefers NOT to follow his assignment (E).

The allocation was not individually rational.

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Theory of (Strict) Core

- What is so Surprising?

Strict Core: No group (or individual) cannot

become better off if they jointly deviate.

 Exchange within sub-group is not profitable.

 Everyone obtains the best item available to him/her! (given other members’ preferences)

Properties of (Strict) Core Allocation

 Exist exactly one for ANY exchange problem.

 Always Pareto efficient and individually rational.

 Top Trading Cycles(TTC) mechanism finds it!

2013 Winter 57

PRACTICE OF TTC

MECHANISM

An Easy Way to Find Core Allocation

How to Find Core Allocation

- TTC Mechanism

1.

Everyone submits preference (ranking).

2.

Clearing house operates as follows:

1. Everyone points to his/her best ranked item.

2. If cycle is formed, its members transfer their

items accordingly and exit (from the procedure).

3. Remaining members points to their best ranked item (among remaining items)

4. Continue this process until everyone exits.

3.

Exit members receive their assignment.

2013 Winter 59

How to Use TTC Mechanism

- Everyone Points to his/her Best Item

A

C B

D

E

How to Use TTC Mechanism

- Transfer Realizes within Each Cycle!

2013 Winter 61

A

C B

D

E

How to Use TTC Mechanism

- A Pointing to Himself Finalizes Mechanism

Members’ Preferences

It is Pareto efficient and Individually rational!

No one has incentive to manipulate!!

A B C D E

1^st B B E C D

2^nd C E D D A

3^rd A A C E E

4^th E D B A C

5^th D C A B B

Applications of TTC Mechanism

- Let’s Make Use of TTC Mechanism in Real Life!

Closely Related Examples in Practice

 Kidney exchange (US)

 Public school choice (San Francisco)

Potential Applications

 Office room re-allocation

 Exchange of used items (books, clothes, DVD…)

 Re-allocation of relief supplies

2013 Winter 63