Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: OK, on Tuesday we talked about sex,

so today we're going to talk about marriage.

Now, in terms of graph theory, marriage

is expressed as a matching problem,

and today we're going to talk about a matching algorithm that

is used in all sorts of applications.

It's used by online dating agencies

to match compatible people together.

It's used for assignment problems,

for example, matching interns to hospitals on match day.

It's used for resource allocation problems,

for example, load balancing traffic on the internet.

And we'll talk about the applications

at the end of class.

In its simplest form of a matching problem,

you have a graph where the edges represent compatibility.

Two nodes can be paired together, or married,

and the goal is to create the maximum number

of compatible pairs.

So let's define a matching, given a graph, G,

with nodes, V, and edges, E. In matching,

you can think of it as a collection of edges,

or a subgraph of G where every node has degree 1.

So everybody can be married just to one person.

So let's draw an example, maybe not put that edge in.

And let's label these nodes x1, x2, x3, x4, x5, x6, x7, and x8.

Now x1, x6 and x2, x5 is a matching, so x1, x6 and x2,

x5 is a matching with two edges, so we say it has size two.

All right, so I can pair these guys up and pair these guys up.

Is there any bigger matching in this graph?

So I found one with two marriages, here

and here, two edges.

Yeah?

AUDIENCE: x1, x7.

PROFESSOR: x1, x7.

AUDIENCE: x2, x6.

PROFESSOR: x2, x6.

AUDIENCE: [INAUDIBLE].

PROFESSOR: Good.

All right, that's a matching of size three.

So I got three couples together.

Good.

Can I make a bigger matching, one with size four--

four marriages here?

No.

Why not?

Can anybody give me a reason why it can't be done?

Yeah?

AUDIENCE: x8 and x7 would have to be matched with someone.

PROFESSOR: Yeah, so if-- Yeah?

AUDIENCE: They could only be paired with x1,

but x1 can't be paired with both.

PROFESSOR: Good.

If I were to have a matching with four edges,

well, there's only eight nodes, so I'd

have to have all eight nodes involved in the matching.

And that means x7 and x8 would have to be in the matching,

but they could only be paired with x1,

and so it's not possible to do that.

All right, so there is no matching

of size four in this graph.

Three is the best I can do.

Now, when you get every node in a matching,

then it's called a perfect matching.

And so in this case, it doesn't exist, but sometimes it does.

So a matching is perfect if it has

size half the number of nodes.

In other words, if the number of edges is v over 2,

then every node is in the matching.

All right, so that one doesn't have a perfect matching.

What about this graph?

So I got b1, b2, b3, b4, g1, g2, g3, g4,

and I'll put in the compatibility edges here.

OK, Does that graph have a perfect matching?

Can you pair up every boy with a girl

here so that everybody is compatible with their mate,

and you have just one spouse?

Can you do that?

AUDIENCE: Yes.

PROFESSOR: Yeah?

All right, who do I start pairing up?

AUDIENCE: 1, 1.

AUDIENCE: 1, 1.

AUDIENCE: b2, g3.

PROFESSOR: b2, g3.

AUDIENCE: b3, g2.

PROFESSOR: b3, g2

AUDIENCE: b4, g4.

PROFESSOR: There we go.

All right, so there is a perfect matching in this graph.

Very good.

Now, in some cases, some pairings

are more desirable than others, and this can

be represented with a weight.

And so you might have a weighted graph where

every edge has a weight on it.

For example, we might weight b1, g2 with 5,

and b1, g1 gets a 10.

And usually when you see weighted graphs

in the matching context, a lower weight

means it's more desirable, so that b1 and g2 would get along

better than b1 and g1.

And then the goal is to find a matching with minimum weight.

Now, the weight of a matching, call it M,

is the sum of the weights on the edges of M. Now,

usually when you're looking at weighted matchings,

you require yourself to have a perfect matching so

that everybody gets paired up.

And often in that case, you'll see all the edges present,

some of them with very big weights, maybe even infinity

if they just can't be put together.

Because otherwise you just say, don't match anybody together,

and you have weight zero.

So for when you look at minimum weight matchings,

you're looking for the perfect matching with minimum weight.

So we say a min-weight matching for a graph, G,

is a perfect matching for G with the minimum weight,

overall perfect matchings.

Let's try an example.

Say I've got this graph, and call this node Brad,

here's Billy Bob, here's Jennifer, and then Angelina.

And the weights are as follows-- I put a 10 here,

a 10 down here, a 5 here, because Brad really

likes Angelina and vice versa, and a 16 between Jennifer

and Billy Bob.

What is the weight of the min weight matching in that graph?

20.

And who gets paired with who there?

Who does Brad get hooked up with?

AUDIENCE: Jan.

PROFESSOR: Jan, and that leaves Billy Bob with Angelina,

and the weight is 20.

So even though Brad really likes Angelina, if I go that route,

my weight is 21, which is not as good.

So the min-weight matching would be this one.

OK.

Now, it turns out that finding the maximum matching--

the maximum number of edges you can put together--

or finding the minimum weight perfect matching,

those are both solvable, tractable problems.

You don't get a million dollar prize for solving that.

The algorithm is run in quadratic to cubic time,

so not terrible, but they're not NP-complete,

so people know how to do it.

Now, they are pretty complicated,

so we're not going to cover them in 6042.

What we're going to do is look at a slightly different version

of the problem that actually turns out

to be more useful in practice, because there's

a very nice algorithm for it.

Now, in the version of the problem that we're

going to look at, everybody has preferences-- a preference

list.

It's not weighted, but it's a priority order

of who they want to get mated to, or matched up with.

So it would look not quite like that,

but it would look like this.

So Brad, Billy Bob, Jennifer, and Angelina-- same players,

but what we do is we know that Brad really likes Angelina,

and Angelina really likes Brad, so they are first choices,

at least was.

Number two for Brad is Jennifer, but Jennifer really likes Brad

first, and Billy Bob second.

Billy Bob likes Angelina first, then Jennifer.

Angelina thinks Billy Bob is number two.

So it's not necessarily symmetric.

Jennifer has Brad as the first choice.

Brad has Angelina as the first choice.

All right?

So it's an asymmetric situation.

Now, what would happen if we set up our marriages so that Brad

is married to Jen, and Billy Bob is married to Angelina?

What might happen if we made those as our pairings,

and we put them on a desert island, all four of them?

What's likely to happen there?

AUDIENCE: Brad and Angelina are going to cheat on each other.

PROFESSOR: Yeah, we're going to have a problem.

Because Brad and Angelina have the hots for each other here,

and they like each other better than their spouse.

So before you know it, they're going

to be doing their 6042 homework together late at night.

All right?

Now, when this happens, we have what's called a rogue couple.

Given a matching, x and y, a boy and a girl,

say, form a rogue couple if they prefer each other

over their mates in M. All right.

So here, if we married Brad to Jennifer,

and Billy Bob to Angelina, Brad and Angelina

form a rogue couple, because they

like each other better than who they were hooked up with.

And that's sort of a bad thing.

It creates instability if you were

to make the matchings that way.

In fact, we say that a matching is stable

if there aren't any rogue couples.

And now, one thing to make clear is that your preferences

can't change over time.

So it's not a situation where you get bored with your spouse,

and you change your mind, and then

you go off and create a rogue couple.

You're fixed in your preferences over all time,

no playing the field, none of that stuff here, OK?

So it's fixed once and for all, and your goal, of course,

is to create or find a perfect matching that's stable.

That's the goal.

So get everybody married up and make it stable.

All right, is it doable in that example?

If I put those four people on a desert island,

could I make a stable matching?

Yeah, who would I match Brad to?

AUDIENCE: Angelina.

PROFESSOR: All right.

Good, and then Billy Bob gets Jennifer.

Now, I'm not saying that you make everybody happy,

because Billy Bob and Jennifer are probably not happy there.

They each got their number two choice.

But it's stable, because Brad and Angelina

aren't going anywhere.

They are going to stay together because they

like each other best, and so there's no chance that Jennifer

is going to-- that Angelina is going to sneak off, sorry,

with Billy Bob, or that Brad's going

to sneak off with Jennifer.

All right?

So it's stable.

Not everybody's happy, but it's a stable set of marriages.

OK.

Any questions about what we're trying to do here now?

Yeah?

AUDIENCE: [INAUDIBLE] the edges?

PROFESSOR: That's a great question.

You'll see it referred to both ways.

Technically, it's a subgraph, so it has nodes and edges,

but you'll see me, and you'll see everybody say, oh, it's

a bunch of edges that don't share any nodes,

and you'll see them refer to it as the edges.

But really, underlying that, it's a subgraph, technically.

Any other questions about what we're

trying to do here to find stable, perfect matching?

All right.

Well, in this example, there was a stable, perfect matching.

But what about in general?

If I have a lot more people, and they

have arbitrary preferences, how many people

think you can always find a stable perfect matching?

There's one optimistic person.

How many people think there's some cases where you're just