Advertisement
English transcript
MALE SPEAKER: Hi, everyone.
Thanks for coming out this afternoon.
So we have two special speakers today as you can see,
one guest and one fellow Googler.
Hal Varian immediately to my right
is Google's chief economist and has worked with Google
since 2002.
Hal has contributed to Google projects
on auction design, econometric analysis, finance,
corporate strategy, and public policy.
He's also an Emeritus Professor in Business and Economics
and Information Management at the University of California
Berkeley.
That's also where he earned his PhD.
Before coming to Google, Hal taught
at some of the world's most prestigious universities,
including the University of Michigan, MIT, Oxford,
Stanford, and of course, Berkeley.
Alvin Roth, our special guest, is the Craig and Susan McCaw
Professor of Economics at Stanford University
and the Gund Professor of Economics
and Business Administration Emeritus at Harvard.
Professor Roth is an expert in game theory,
experimental economics, and market design.
In 2012, he and Lloyd S. Shapley were awarded the Nobel Memorial
Prize in Economics for their contributions
to stable allocations and market design.
And their work isn't just theory.
It's been put to real world use in areas ranging
from health care to education as Professor Roth discusses
in his new book, which we're here to talk about today, "Who
Gets What-- and Why."
So without further ado, please give a warm welcome
to Dr. Hal Varian and Dr. Alvin Roth.
HAL VARIAN: Welcome to the Hal and Al show.
By the way, I didn't tell you, but since Jon Stewart's retired
there is an opening.
And I thought maybe we could do a little rehearsal--
ALVIN ROTH: Good idea.
HAL VARIAN: --for that position.
And one of us will be the interviewer.
And one of us will be the guest.
ALVIN ROTH: We can figure out afterwards.
HAL VARIAN: We'll let the audience vote afterwards
on which role is appropriate.
But as you just heard, Al is here today
because he wants to talk about his new book, "Who Gets What--
and Why."
And I have to say, it's a pretty broad title.
Right?
You could say, that's all of economics should exist
[INAUDIBLE].
So tell me what's unique about your book.
ALVIN ROTH: Well, it has a subtitle,
which is "The New Economics of Matchmaking and Market Design."
And so I try to talk about matching markets and markets
more broadly.
A little bit, I think of it as a field guide the markets the way
you'd use a field guide to birds to let
you know that there are more than red breasted robins
in the world.
I think that outside of Silicon Valley people
have a very different view of markets
than we have in the Valley.
Because of course, markets are ancient human artifacts
probably older than agriculture.
But often, we tend to think of markets the way
we think of languages, which are also human artifacts,
but which we can't intervene in very much.
You know, we speak English.
But we speak it the way we received it pretty much.
But of course, companies like Google make markets.
There are a lot of market making companies.
And there are a lot of markets in the world.
So markets, unlike languages, have proprietors,
have interested active groups of users,
and are susceptible to design.
We can change markets when they're not
working the way we want.
And we can invent new ones when we
see markets that are missing.
HAL VARIAN: And just to fill in the little for the audience
is this idea that you could design economic mechanisms,
like markets, and like matching and other processes.
I guess Lyle Hurwitz was really the guy who
first promulgated that, at least in current times.
ALVIN ROTH: I think that's right.
Although, my guess is the guy who first promulgated
it was trading in stone tools back before the beginning.
HAL VARIAN: Yes.
And a very interesting development
in the last 10 or 15 years has been the development
of algorithmic mechanism design, which
is a way to combine computer science
considerations like computability and so
on with the economic considerations which
are incentives.
And this has actually, I think, been very, very stimulating
to both fields.
And as an economist, you focused a lot on the incentive issues.
But have you also dealt with the computational side of things?
Or is that--
ALVIN ROTH: Oh, no, no.
I have.
One of the chapters in the book is devoted to kidney exchange.
And as that market has developed,
we're looking more and more at long chains and things
that turn out to be computationally
difficult problems.
So they're incomplete problems.
They are also just hard, even though solvable,
because you're dealing with integer programs that
have more constraints than you can write down.
So you have to generate them on the fly.
And when you try calling things like CPLEX,
you run into memory problems.
So you have to do column generation or a row generation.
So yes, we think a lot about the computational problems that
arise in organizing some of the markets we deal with.
HAL VARIAN: Yeah.
It's been a very stimulating field
for both sets of researchers.
In fact, there's a conference, a whole fall specialization
at the Math Sciences Research Institute at Berkeley,
which is devoted to exactly this topic,
getting the computer engineers, computer sciences,
together along with economist to study a lot of these markets,
both the theory of what can be done and what can be achieved
and the practice of actually implementing some of the stuff.
ALVIN ROTH: You know, again I hardly have to say here,
but as markets have moved more and more to the internet,
the problem just to implementing them
often falls to computer engineers or various sorts.
And so there's going to be natural, inevitable contact
between people who think of how the participants in the market
will use it and the engineers who
think how to make it happen on the internet.
HAL VARIAN: So how did you get into this area?
When you started, there really weren't many people.
I guess, it was the original Gale, Shapley paper
the lot has subsequently been built on.
But it wasn't something that was in every curriculum the way
it is now.
ALVIN ROTH: Well, I started by thinking
about particular markets.
And the first one that I studied for many years
before I got an opportunity to redesigned
it was the market for new doctors in the United States.
And that market had a lot of market failures
prior to the 1950s when they invented
a centralized clearinghouse that essentially anticipated
the paper that Gale and Shapley wrote 10 years later.
That market worked very well for reasons
that we now understand much better.
But over the years, it developed problems.
Because in the 1950s, when it began,
it was a sort of simple market.
Simple in part, because just about every graduate
of an American medical school in 1950 was a man.
But by 1970s, there were 10% women graduates.
And today, there are 50%.
And so medical graduates, they're very busy.
And one of things they can do is marry each other.
And they started looking for two jobs, not just for one.
It turns out looking for two jobs is
a theoretically and computationally more difficult
problem than looking for one job.
So matching married couples to pairs of jobs
became the question I was asked to help
when I was asked to direct a redesign of that marketplace.
HAL VARIAN: The grand challenge.
ALVIN ROTH: It was a challenge.
HAL VARIAN: So why don't you outline,
let's say, the Gale Shapley example just
as a very simple case, a starting problem,
so people can get an idea of what this matching process
looks like.
And then maybe say a word or two about how it
can be extended to other cases.
ALVIN ROTH: OK.
Well, Gale and Shapley wrote a prescient paper
called "College Admissions and the Stability of Marriage."
So it had a funny title.
And what they said is they said, think of a problem of marriage
where-- they didn't quite put it this way, but supposing you're
trying to organize a centralized clearinghouse to marry people.
And you're not a central planner.
You can't simply decide who marries whom.
You can only make suggestions about who should marry whom.
And what will ultimately determine
who marries whom are the preferences
of the married people, who each have the right to marry
each other if they so choose.
They said what you would like to do
then is you'd like to create a stable matching if you could,
which is a matching that has the property that there are no man
and woman not married to each other who would both prefer
to be married to each other.
So your aim is to suggest a stable matching.
Because if you suggest an unstable matching,
they'll be a blocking pair.
They'll be a man and a woman not married to each other
who would prefer to marry each other
and who won't have to accept your suggestion.
Instead of doing what you propose,
they could marry each other.
HAL VARIAN: So in other words, anybody that I would rather
have wouldn't want me.
ALVIN ROTH: That's a characteristic
of a stable matching.
And they constructed an algorithm
that produces a stable matching no matter
what the preferences of the men and the women are.
And there are two versions of the algorithm.
One has the men proposing.
And one has the women proposing.
And so the man proposing algorithm goes like this.
At the first step of the algorithm,
each man proposes to his first choice woman.
And every woman who has received acceptable proposals--
if you receive an unacceptable proposal that
is someone who you would rather not be married to.
You'd rather be single.
You reject them.
But also if you've received multiple acceptable proposals,
you hold onto the one you like best,
the one you prefer the most and reject the rest.
But you don't immediately accept the proposal
that you don't reject.
This is a deferred acceptance algorithm.
Acceptance will only happen at the end.
So what happens?
All the men who have just been rejected,
they propose to their next choice woman, their next most
preferred woman.
And every woman who's gotten the proposal,
now looks at the new proposals that she gets together
with any proposal, which she may have held previously,
keeps the one she likes best, rejects the rest.
And this continues until no more rejections
are issued, which it must do.
Because it's a finite problem.
And no man proposes twice to the same woman.
And when no more rejections are issued,
now the proposals are accepted.
And each woman is married to the man, if any, whose proposal she
has not rejected.
She might be holding on to one proposal.
And what Gale and Shapley observed is that that matching,
regardless of what the preferences were
that were the input, is stable.
It can't be that there are a man and a woman who
would prefer to each other to who they're matched to.
And the reason, of course, is that if a man is matched
to his third choice woman, he knows that his second choice
woman doesn't prefer him.
Because he already proposed to her.
And she rejected him when she got a proposal
that she preferred.
So that was where they left it.
And later, when we started to think
about this as centralized clearinghouses,
we said, you know, this really depends
on knowing the preferences--
HAL VARIAN: Right.
ALVIN ROTH: --of the men and women.
And one of the things that you can show
is that the men can do no better than to state
their true preferences.
But that the women situation, when the men are proposing,
is more complicated.
HAL VARIAN: I think, isn't there a Jane Austen
novel with that plot?
ALVIN ROTH: Several, I believe.
HAL VARIAN: Something along that line, at least,
I think I've encountered before.
But Gale and Shapley, to my recollection,
did not cite Jane Austen in that paper.
ALVIN ROTH: Well, they didn't deal
with the incentive problem.
They took what, for better or for worse,
for many years became the computer science approach--
HAL VARIAN: Right
ALVIN ROTH: --which is that the person organizing the market
knows the preferences.
HAL VARIAN: And many of you may know
that a very common exercise in your first computer science
or programming class is to write the code for this algorithm.
But without looking at the incentives-- [INAUDIBLE].
Before we talk about the incentives,
give us a few more examples of where
this two-sided matching market or multi-sided matching market
might be relevant.
ALVIN ROTH: Well, so as I said, we've
helped build clearinghouses for a variety of medical and health
care marketplaces.
But my colleagues and I are also helping reform school choice
in a number of American cities.
And you can easily have school choice mechanisms that
don't work as well as a deferred acceptance algorithm
clearinghouse.
And so in recent years, we've helped redesign the processes
for putting children into schools in New York
and in Boston and New Orleans and in Denver
and some other cities.
And a clearinghouse that operates
like a deferred acceptance algorithm
solves a couple of problems that school choice systems often
have.
One is making it safe for children and their families
to reveal their preferences to the school district.
For many years, New York City, the way
you applied for a school was you who
submitted to rank order list.
This is my first choice, my second choice, my third choice.
And then that list was Xeroxed and sent to the schools.
And that was your application.
What that meant was if I applied to your school,
you might be able to see that I had applied
and you are my third choice.
And you could, as a school principal,
adopt an admissions policy that says, we're a popular school.
We're only going to admit people who
list us as their first choice.
So that would mean that, although it appeared
that I had lots of choices of schools,
I might really have very few.
Because of the schools I wanted, only the ones
that I listed first would consider me.
Similarly, Boston had a system of school choice
where they tried to give as many people as possible
their first choice.
And when more people wanted a particular school
as their first choice than they could fit in,
they used a priority system to break ties.
If an older sibling went to the same school, you could go.
But the trouble with that mechanism-- which
was very benign in intent, they'd give as many people as
possible their first choice, then
as many people as possible their second choice and so forth--
was if you didn't get your first choice,
your second choice might already have all its seats
filled with people who had listed it
as their first choice.
So that even though you had high priority
at your second choice-- an older child who already went
to the school, which means if you had listed it
as your first choice-- you would've gotten in.
If you listed it as your second choice, you wouldn't.
So when we use the deferred acceptance algorithm
with students proposing, that solves that problem.
Because if you don't get into your first choice, when
you apply to your second choice, they
haven't filled all their seats yet.
They've rejected some applications and kept others.
But they haven't accepted those.
And if you have very high priority at your second choice
school, you go right to the top of their list.
And they reject someone else.
So it's safe for you to tell the city what your choices are.
Your chance of getting your second choice school
if you get rejected by your first choice
is just as large as it would have
been if you had listed that school as your first choice.
HAL VARIAN: And it's interesting.
Both of these examples, the school admission problem
and the residence assignment problem,
have this side constraint that it's
good to have husband and wife in the same location.
It's good to have older siblings and younger
siblings in the same school.
So the same complications presumably
arise if you're trying to solve that full problem.
ALVIN ROTH: So not quite.
In most cities, the school choice problem
is simpler than the couples problem.
HAL VARIAN: I see.
ALVIN ROTH: Because we're dealing with older siblings who
are already in place.
HAL VARIAN: Ah, OK.
ALVIN ROTH: Now twins are a problem.
HAL VARIAN: Yup.
ALVIN ROTH: And in New Orleans, it's common for people
to change schools at every grade.
In most cities, you change schools
at kindergarten, sixth grade, and ninth grade.
So the couple's problem for siblings isn't so bad.
But in New Orleans, you might have a first and third grader
and you want to move them both to a different school.
So they look like the couples problem.
HAL VARIAN: So the stable marriage idea
is very attractive.
But it doesn't always exist.
In the two-sided case it exists.
But tell us about the roommate problem.
ALVIN ROTH: Well, in the roommate problem
and in the couples problem it might not exist.
HAL VARIAN: And the couples.
Yes, right.
ALVIN ROTH: But Gale and Shapley, in their '62 paper,
they said, you know, there's a big difference
between defining what's a stable matching
and knowing that one exists.
And what the deferred acceptance algorithm
allowed them to prove was in two-sided matching, when you
know who are the men and who are the women
and who are the doctors and who are the hospitals,
you can always find a stable matching.
But they gave an example to show that it wouldn't always
be so easy.
And they said think of the problem of matching roommates.
So you have a bunch of people, any of whom
can be a roommate with any other.
This, incidentally, is a little bit
like the problem we face with kidney exchange.
But that's a different problem.
And we face it in a different way.
But what they said about roommates is so your job,
you're the housing office at some university.
You get preferences for roommates.
You have to fill double rooms.
And consider the case of four people,
where person one's first choice roommate is person two.
Person two's first choice roommate is person three.
Person three's first choice roommate is person one.
And person one, two, and, three, their last choice
is person four.
And it turns out in this example it's not
going to matter what person--
HAL VARIAN: He was my roommate in college.
I remember him.
ALVIN ROTH: That's funny.
He told me the same thing.
But what you can see is there's no stable matching.
Because whoever you match with person four,
that person, the person who is the roommate of person four,
is the first choice of someone else.
And so whoever is roomed with person four,
together with whoever regards that person
as his first choice, they're a blocking pair.
They would both rather be rooming
with each other than the matching that you've designed.
So that shows that stable matchings might not always
exist.
And, indeed, one of the first things
I observed about the problem with couples
was that when you have couples in the medical labor market,
stable matching might not always exist.
And one of the differences between being
an economic theorist and being a market designer
was when I first observe this, I was still a game theorist
just observing the market.
And it was enough for me to observe
that therefore the problem of matching couples
was a hard problem.
And that made for a great paper and full stop.
So when one day my phone rang and on the other end
was the Director of the National Resident Matching Program
and he said, we're having these problems,
would you redesign the match for us,
I knew that it was no longer going
to be enough to say that's a hard problem.
It was going to become my hard problem.
And so designing markets has changed my taste
in economic theory in much the way, I think,
that it's going to change the taste of computer scientists
in algorithmic theory.
HAL VARIAN: It's like, you proved the bumblebee couldn't
fly, now what?
ALVIN ROTH: Yeah.
HAL VARIAN: But it's got to fly.
Actually another paper of yours that I handled
when I was editor of "The American Economic Review"
that really appealed to me was a sorority paper.
Right?
Because there was a very explicit algorithm
that was used to match sororities and pledges.
But it had some really fundamental faults.
Maybe you could say a word or two about that.
ALVIN ROTH: Well, so let me actually
take that as an oppor
…
Thanks for coming out this afternoon.
So we have two special speakers today as you can see,
one guest and one fellow Googler.
Hal Varian immediately to my right
is Google's chief economist and has worked with Google
since 2002.
Hal has contributed to Google projects
on auction design, econometric analysis, finance,
corporate strategy, and public policy.
He's also an Emeritus Professor in Business and Economics
and Information Management at the University of California
Berkeley.
That's also where he earned his PhD.
Before coming to Google, Hal taught
at some of the world's most prestigious universities,
including the University of Michigan, MIT, Oxford,
Stanford, and of course, Berkeley.
Alvin Roth, our special guest, is the Craig and Susan McCaw
Professor of Economics at Stanford University
and the Gund Professor of Economics
and Business Administration Emeritus at Harvard.
Professor Roth is an expert in game theory,
experimental economics, and market design.
In 2012, he and Lloyd S. Shapley were awarded the Nobel Memorial
Prize in Economics for their contributions
to stable allocations and market design.
And their work isn't just theory.
It's been put to real world use in areas ranging
from health care to education as Professor Roth discusses
in his new book, which we're here to talk about today, "Who
Gets What-- and Why."
So without further ado, please give a warm welcome
to Dr. Hal Varian and Dr. Alvin Roth.
HAL VARIAN: Welcome to the Hal and Al show.
By the way, I didn't tell you, but since Jon Stewart's retired
there is an opening.
And I thought maybe we could do a little rehearsal--
ALVIN ROTH: Good idea.
HAL VARIAN: --for that position.
And one of us will be the interviewer.
And one of us will be the guest.
ALVIN ROTH: We can figure out afterwards.
HAL VARIAN: We'll let the audience vote afterwards
on which role is appropriate.
But as you just heard, Al is here today
because he wants to talk about his new book, "Who Gets What--
and Why."
And I have to say, it's a pretty broad title.
Right?
You could say, that's all of economics should exist
[INAUDIBLE].
So tell me what's unique about your book.
ALVIN ROTH: Well, it has a subtitle,
which is "The New Economics of Matchmaking and Market Design."
And so I try to talk about matching markets and markets
more broadly.
A little bit, I think of it as a field guide the markets the way
you'd use a field guide to birds to let
you know that there are more than red breasted robins
in the world.
I think that outside of Silicon Valley people
have a very different view of markets
than we have in the Valley.
Because of course, markets are ancient human artifacts
probably older than agriculture.
But often, we tend to think of markets the way
we think of languages, which are also human artifacts,
but which we can't intervene in very much.
You know, we speak English.
But we speak it the way we received it pretty much.
But of course, companies like Google make markets.
There are a lot of market making companies.
And there are a lot of markets in the world.
So markets, unlike languages, have proprietors,
have interested active groups of users,
and are susceptible to design.
We can change markets when they're not
working the way we want.
And we can invent new ones when we
see markets that are missing.
HAL VARIAN: And just to fill in the little for the audience
is this idea that you could design economic mechanisms,
like markets, and like matching and other processes.
I guess Lyle Hurwitz was really the guy who
first promulgated that, at least in current times.
ALVIN ROTH: I think that's right.
Although, my guess is the guy who first promulgated
it was trading in stone tools back before the beginning.
HAL VARIAN: Yes.
And a very interesting development
in the last 10 or 15 years has been the development
of algorithmic mechanism design, which
is a way to combine computer science
considerations like computability and so
on with the economic considerations which
are incentives.
And this has actually, I think, been very, very stimulating
to both fields.
And as an economist, you focused a lot on the incentive issues.
But have you also dealt with the computational side of things?
Or is that--
ALVIN ROTH: Oh, no, no.
I have.
One of the chapters in the book is devoted to kidney exchange.
And as that market has developed,
we're looking more and more at long chains and things
that turn out to be computationally
difficult problems.
So they're incomplete problems.
They are also just hard, even though solvable,
because you're dealing with integer programs that
have more constraints than you can write down.
So you have to generate them on the fly.
And when you try calling things like CPLEX,
you run into memory problems.
So you have to do column generation or a row generation.
So yes, we think a lot about the computational problems that
arise in organizing some of the markets we deal with.
HAL VARIAN: Yeah.
It's been a very stimulating field
for both sets of researchers.
In fact, there's a conference, a whole fall specialization
at the Math Sciences Research Institute at Berkeley,
which is devoted to exactly this topic,
getting the computer engineers, computer sciences,
together along with economist to study a lot of these markets,
both the theory of what can be done and what can be achieved
and the practice of actually implementing some of the stuff.
ALVIN ROTH: You know, again I hardly have to say here,
but as markets have moved more and more to the internet,
the problem just to implementing them
often falls to computer engineers or various sorts.
And so there's going to be natural, inevitable contact
between people who think of how the participants in the market
will use it and the engineers who
think how to make it happen on the internet.
HAL VARIAN: So how did you get into this area?
When you started, there really weren't many people.
I guess, it was the original Gale, Shapley paper
the lot has subsequently been built on.
But it wasn't something that was in every curriculum the way
it is now.
ALVIN ROTH: Well, I started by thinking
about particular markets.
And the first one that I studied for many years
before I got an opportunity to redesigned
it was the market for new doctors in the United States.
And that market had a lot of market failures
prior to the 1950s when they invented
a centralized clearinghouse that essentially anticipated
the paper that Gale and Shapley wrote 10 years later.
That market worked very well for reasons
that we now understand much better.
But over the years, it developed problems.
Because in the 1950s, when it began,
it was a sort of simple market.
Simple in part, because just about every graduate
of an American medical school in 1950 was a man.
But by 1970s, there were 10% women graduates.
And today, there are 50%.
And so medical graduates, they're very busy.
And one of things they can do is marry each other.
And they started looking for two jobs, not just for one.
It turns out looking for two jobs is
a theoretically and computationally more difficult
problem than looking for one job.
So matching married couples to pairs of jobs
became the question I was asked to help
when I was asked to direct a redesign of that marketplace.
HAL VARIAN: The grand challenge.
ALVIN ROTH: It was a challenge.
HAL VARIAN: So why don't you outline,
let's say, the Gale Shapley example just
as a very simple case, a starting problem,
so people can get an idea of what this matching process
looks like.
And then maybe say a word or two about how it
can be extended to other cases.
ALVIN ROTH: OK.
Well, Gale and Shapley wrote a prescient paper
called "College Admissions and the Stability of Marriage."
So it had a funny title.
And what they said is they said, think of a problem of marriage
where-- they didn't quite put it this way, but supposing you're
trying to organize a centralized clearinghouse to marry people.
And you're not a central planner.
You can't simply decide who marries whom.
You can only make suggestions about who should marry whom.
And what will ultimately determine
who marries whom are the preferences
of the married people, who each have the right to marry
each other if they so choose.
They said what you would like to do
then is you'd like to create a stable matching if you could,
which is a matching that has the property that there are no man
and woman not married to each other who would both prefer
to be married to each other.
So your aim is to suggest a stable matching.
Because if you suggest an unstable matching,
they'll be a blocking pair.
They'll be a man and a woman not married to each other
who would prefer to marry each other
and who won't have to accept your suggestion.
Instead of doing what you propose,
they could marry each other.
HAL VARIAN: So in other words, anybody that I would rather
have wouldn't want me.
ALVIN ROTH: That's a characteristic
of a stable matching.
And they constructed an algorithm
that produces a stable matching no matter
what the preferences of the men and the women are.
And there are two versions of the algorithm.
One has the men proposing.
And one has the women proposing.
And so the man proposing algorithm goes like this.
At the first step of the algorithm,
each man proposes to his first choice woman.
And every woman who has received acceptable proposals--
if you receive an unacceptable proposal that
is someone who you would rather not be married to.
You'd rather be single.
You reject them.
But also if you've received multiple acceptable proposals,
you hold onto the one you like best,
the one you prefer the most and reject the rest.
But you don't immediately accept the proposal
that you don't reject.
This is a deferred acceptance algorithm.
Acceptance will only happen at the end.
So what happens?
All the men who have just been rejected,
they propose to their next choice woman, their next most
preferred woman.
And every woman who's gotten the proposal,
now looks at the new proposals that she gets together
with any proposal, which she may have held previously,
keeps the one she likes best, rejects the rest.
And this continues until no more rejections
are issued, which it must do.
Because it's a finite problem.
And no man proposes twice to the same woman.
And when no more rejections are issued,
now the proposals are accepted.
And each woman is married to the man, if any, whose proposal she
has not rejected.
She might be holding on to one proposal.
And what Gale and Shapley observed is that that matching,
regardless of what the preferences were
that were the input, is stable.
It can't be that there are a man and a woman who
would prefer to each other to who they're matched to.
And the reason, of course, is that if a man is matched
to his third choice woman, he knows that his second choice
woman doesn't prefer him.
Because he already proposed to her.
And she rejected him when she got a proposal
that she preferred.
So that was where they left it.
And later, when we started to think
about this as centralized clearinghouses,
we said, you know, this really depends
on knowing the preferences--
HAL VARIAN: Right.
ALVIN ROTH: --of the men and women.
And one of the things that you can show
is that the men can do no better than to state
their true preferences.
But that the women situation, when the men are proposing,
is more complicated.
HAL VARIAN: I think, isn't there a Jane Austen
novel with that plot?
ALVIN ROTH: Several, I believe.
HAL VARIAN: Something along that line, at least,
I think I've encountered before.
But Gale and Shapley, to my recollection,
did not cite Jane Austen in that paper.
ALVIN ROTH: Well, they didn't deal
with the incentive problem.
They took what, for better or for worse,
for many years became the computer science approach--
HAL VARIAN: Right
ALVIN ROTH: --which is that the person organizing the market
knows the preferences.
HAL VARIAN: And many of you may know
that a very common exercise in your first computer science
or programming class is to write the code for this algorithm.
But without looking at the incentives-- [INAUDIBLE].
Before we talk about the incentives,
give us a few more examples of where
this two-sided matching market or multi-sided matching market
might be relevant.
ALVIN ROTH: Well, so as I said, we've
helped build clearinghouses for a variety of medical and health
care marketplaces.
But my colleagues and I are also helping reform school choice
in a number of American cities.
And you can easily have school choice mechanisms that
don't work as well as a deferred acceptance algorithm
clearinghouse.
And so in recent years, we've helped redesign the processes
for putting children into schools in New York
and in Boston and New Orleans and in Denver
and some other cities.
And a clearinghouse that operates
like a deferred acceptance algorithm
solves a couple of problems that school choice systems often
have.
One is making it safe for children and their families
to reveal their preferences to the school district.
For many years, New York City, the way
you applied for a school was you who
submitted to rank order list.
This is my first choice, my second choice, my third choice.
And then that list was Xeroxed and sent to the schools.
And that was your application.
What that meant was if I applied to your school,
you might be able to see that I had applied
and you are my third choice.
And you could, as a school principal,
adopt an admissions policy that says, we're a popular school.
We're only going to admit people who
list us as their first choice.
So that would mean that, although it appeared
that I had lots of choices of schools,
I might really have very few.
Because of the schools I wanted, only the ones
that I listed first would consider me.
Similarly, Boston had a system of school choice
where they tried to give as many people as possible
their first choice.
And when more people wanted a particular school
as their first choice than they could fit in,
they used a priority system to break ties.
If an older sibling went to the same school, you could go.
But the trouble with that mechanism-- which
was very benign in intent, they'd give as many people as
possible their first choice, then
as many people as possible their second choice and so forth--
was if you didn't get your first choice,
your second choice might already have all its seats
filled with people who had listed it
as their first choice.
So that even though you had high priority
at your second choice-- an older child who already went
to the school, which means if you had listed it
as your first choice-- you would've gotten in.
If you listed it as your second choice, you wouldn't.
So when we use the deferred acceptance algorithm
with students proposing, that solves that problem.
Because if you don't get into your first choice, when
you apply to your second choice, they
haven't filled all their seats yet.
They've rejected some applications and kept others.
But they haven't accepted those.
And if you have very high priority at your second choice
school, you go right to the top of their list.
And they reject someone else.
So it's safe for you to tell the city what your choices are.
Your chance of getting your second choice school
if you get rejected by your first choice
is just as large as it would have
been if you had listed that school as your first choice.
HAL VARIAN: And it's interesting.
Both of these examples, the school admission problem
and the residence assignment problem,
have this side constraint that it's
good to have husband and wife in the same location.
It's good to have older siblings and younger
siblings in the same school.
So the same complications presumably
arise if you're trying to solve that full problem.
ALVIN ROTH: So not quite.
In most cities, the school choice problem
is simpler than the couples problem.
HAL VARIAN: I see.
ALVIN ROTH: Because we're dealing with older siblings who
are already in place.
HAL VARIAN: Ah, OK.
ALVIN ROTH: Now twins are a problem.
HAL VARIAN: Yup.
ALVIN ROTH: And in New Orleans, it's common for people
to change schools at every grade.
In most cities, you change schools
at kindergarten, sixth grade, and ninth grade.
So the couple's problem for siblings isn't so bad.
But in New Orleans, you might have a first and third grader
and you want to move them both to a different school.
So they look like the couples problem.
HAL VARIAN: So the stable marriage idea
is very attractive.
But it doesn't always exist.
In the two-sided case it exists.
But tell us about the roommate problem.
ALVIN ROTH: Well, in the roommate problem
and in the couples problem it might not exist.
HAL VARIAN: And the couples.
Yes, right.
ALVIN ROTH: But Gale and Shapley, in their '62 paper,
they said, you know, there's a big difference
between defining what's a stable matching
and knowing that one exists.
And what the deferred acceptance algorithm
allowed them to prove was in two-sided matching, when you
know who are the men and who are the women
and who are the doctors and who are the hospitals,
you can always find a stable matching.
But they gave an example to show that it wouldn't always
be so easy.
And they said think of the problem of matching roommates.
So you have a bunch of people, any of whom
can be a roommate with any other.
This, incidentally, is a little bit
like the problem we face with kidney exchange.
But that's a different problem.
And we face it in a different way.
But what they said about roommates is so your job,
you're the housing office at some university.
You get preferences for roommates.
You have to fill double rooms.
And consider the case of four people,
where person one's first choice roommate is person two.
Person two's first choice roommate is person three.
Person three's first choice roommate is person one.
And person one, two, and, three, their last choice
is person four.
And it turns out in this example it's not
going to matter what person--
HAL VARIAN: He was my roommate in college.
I remember him.
ALVIN ROTH: That's funny.
He told me the same thing.
But what you can see is there's no stable matching.
Because whoever you match with person four,
that person, the person who is the roommate of person four,
is the first choice of someone else.
And so whoever is roomed with person four,
together with whoever regards that person
as his first choice, they're a blocking pair.
They would both rather be rooming
with each other than the matching that you've designed.
So that shows that stable matchings might not always
exist.
And, indeed, one of the first things
I observed about the problem with couples
was that when you have couples in the medical labor market,
stable matching might not always exist.
And one of the differences between being
an economic theorist and being a market designer
was when I first observe this, I was still a game theorist
just observing the market.
And it was enough for me to observe
that therefore the problem of matching couples
was a hard problem.
And that made for a great paper and full stop.
So when one day my phone rang and on the other end
was the Director of the National Resident Matching Program
and he said, we're having these problems,
would you redesign the match for us,
I knew that it was no longer going
to be enough to say that's a hard problem.
It was going to become my hard problem.
And so designing markets has changed my taste
in economic theory in much the way, I think,
that it's going to change the taste of computer scientists
in algorithmic theory.
HAL VARIAN: It's like, you proved the bumblebee couldn't
fly, now what?
ALVIN ROTH: Yeah.
HAL VARIAN: But it's got to fly.
Actually another paper of yours that I handled
when I was editor of "The American Economic Review"
that really appealed to me was a sorority paper.
Right?
Because there was a very explicit algorithm
that was used to match sororities and pledges.
But it had some really fundamental faults.
Maybe you could say a word or two about that.
ALVIN ROTH: Well, so let me actually
take that as an oppor
…