MarketDesign en 最近の更新履歴 yyasuda's website

(1)

Introduc)on to Market Design

Yosuke YASUDA

Osaka University, Department of Economics Email: yosuke.yasuda@gmail.com

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

(2)

MARKET DESIGN FOR

ECONOMIC “ENGINEERING”

Putting Game Theory to Work

(3)

Nobel Prize in Economic Science 2012

- Roth and Shapley for Market Design!

(4)

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!

(5)

[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!

(6)

[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.

(7)

[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!

(8)

[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!

(9)

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

(10)

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

(11)

Lessons from Practices

- An Expert Says (in Roth, 2008)…

 

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.

(12)

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 other markets and institutions than perfectly competitive market.

  Game theoretical analysis.

  Try to fix market failure.

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

functioned is crucial.

(13)

MATCHING PROBLEM AND

ITS SOLUTION

Market Design in Practice (1)

(14)

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?

(15)

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

(16)

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?

David John Mark 1st Susan Susan Helen 2nd Linda Helen Susan

3rd Helen Linda Linda

Susan Linda Helen 1st Mark Mark John 2nd David David Mark 3rd John John David

(17)

Inefficient Matching

- Suppose Make Couples in Alphabetical Order…

 

Boys’ Preferences

 

Girls’ Preferences

 

David-Helen, John-Linda => worst partners

 

Switching partners makes them better off!

(18)

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.

(19)

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”…

(20)

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...

(21)

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.

(22)

Table made by Al Roth (2002, Econometrica)

(23)

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!

(24)

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

(25)

PRACTICE OF GS

MECHANISM

An Easy Way to Find Stable Matching

(26)

How to Use GS Mechanism

- 1

^st

Round: Boys’ Proposal

 

Boys’ Preferences

 

Girls’ Preferences

 

David and John propose to Susan.

 

Mark proposes to Helen.

(27)

How to Use GS Mechanism

- 1

^st

Round: Girls’ Rejection

 

Boys’ Preferences

 

Girls’ Preferences

 

Susan keeps David and rejects John.

 

Helen keeps Mark.

(28)

How to Use GS Mechanism

- 2

^nd

Round: Boys’ Proposal

 

Boys’ Preferences

 

Girls’ Preferences

 

John rejected in the 1

^st

round (by Susan)

proposes to Helen.

(29)

How to Use GS Mechanism

- 2

^nd

Round: Girls’ Rejection

 

Boys’ Preferences

 

Girls’ Preferences

 

Helen switches her tentative partner to John

and reject Mark.

(30)

How to Use GS Mechanism

- 3

^rd

Round: Boys’ Proposal

 

Boys’ Preferences

 

Girls’ Preferences

 

Mark rejected in the 2

^nd

round (by Helen)

proposes to Susan.

(31)

How to Use GS Mechanism

- 3

^rd

Round: Girls’ Rejection

 

Boys’ Preferences

 

Girls’ Preferences

 

Susan switches her tentative partner to Mark

and reject David.

(32)

How to Use GS Mechanism

- 4

^th

Round: Boys’ Proposal

 

Boys’ Preferences

 

Girls’ Preferences

 

David rejected by Susan proposes to Linda.

 

No further rejection => Mechanism finishes!

(33)

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.

(34)

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)

(35)

EXCHANGE PROBLEM AND

ITS SOLUTION

Market Design in Practice (2)

(36)

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)?

(37)

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

(38)

Inefficient Allocation

- Suppose Receive Item from the Next Person…

 

Members’ Preferences

 

B receives C (5

^th

) and D receives E (3

^rd

).

 

Exchanging the items makes them better off!

(39)

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.

(40)

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.

(41)

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.

(42)

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!

(43)

PRACTICE OF TTC

MECHANISM

An Easy Way to Find Core Allocation

(44)

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.

(45)

How to Use TTC Mechanism

- Everyone Points to his/her Best Item

A

C B

D

E

(46)

How to Use TTC Mechanism

- Transfer Realizes within Each Cycle!

A

C B

D

E

(47)

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!!

(48)

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

(49)

References

- The Papers Referred in Slides

  Gale and Shapley (1962), “College Admissions and the Stability of Marriage” American Mathematical Monthly, Vol.69: 9-15.

  Roth (2002), “The Economist as Engineer: Game

Theory, Experimentation, and Computation as Tools for Design Economics” Econometrica, Vol.70: 1341-1378.

  Roth (2008), “What Have We Learned from Market Design?” Economic Journal, Vol.118: 285-310.

  Shapley and Scarf (1974), “On Cores and Indivisibility” Journal of Mathematical Economics, Vol.1: 23-37.