One key reason why the stable matching problem admits an efficient solution is
that you can, in principle, match any node to any other node on the opposite
side. Sure the nodes have preferences, and
might not want to be matched to certain nodes, but there's no hard constraints
preventing certain pairings. When you do have such hard constraints,
we wind up with the classical, bipartite matching problem.
So the input to the bipartite matching problem is a bipartite graph, so remember
what that means. That means you can take the vertices and
put them into two groups. Let's call one of them capital U, the
other one capital V, and every single edge has exactly one endpoint in each of
the two groups. Put differently, there exists a cut of
the graph that cuts every single edge. The goal is to compute the matching.
Remember a matching is a sub-set of edges that are pair wise disjoint, no pair of
edges can overlap at an endpoint. And to compute the matching that has the
largest possible size. So, for example, in this pink graph on
the right, there are various matchings consisting of 3 edges.
And I'll leave it for you to check that there is no perfect matching.
There's no way to have a matching of 4 edges.
So, bipartite matching is a totally fundamental problem.
There are constraints on which objects you can pair up and you want to pair up
as many objects as possible. I'm happy to report that the maximum
matching problem is solvable in polynomial time.
In fact its poly time servable not just in bipartite graphs which is what I'm
discussing here but even in general non-bipartite graph.
So non-bipartite graphs you have to work pretty hard to solve the problem in
polynomial time. The bipartite case that I'm talking about
here reduces easily to another problem you should know about, called the maximum
flow problem. So I'll now move on to describing the
maximum flow problem. I'll leave it as a good exercise for you
to do why bi partied matching reduces to maximum flow.
You can study maximum flow in either un-directed or directed graphs.
The directed graph case is in some sense the more general one.
Let me state that here. The input is directed graph, one special
vertex is called the source vertex s, and another vertex t, is called the sync
vertex. Finally, each edge e has a capacity, u
sub e, which is the maximum amount of flow, or traffic, that the edge can
accommodate. Informally, the goal is to push as much
stuff as possible. From the source vertex s to the sync
vertex t respecting the capacities of the various lengths.
So you should think of examples as electrical current being generated from s
and flowing to t or you can think of water being injected into the network at
s flowing through these edges representing pipes and then being drained
out at t. The point is, you have a conservation of flow at every vertex
other than s and t. That is, the amount of stuff coming in
has to equal the amount of stuff coming out, except for s, where stuff gets
generated and at t, where stuff gets drained.
As a simple example, suppose in this pink network on the right, I give each edge a
capacity of 1. the maximum amount of stuff you can push
from s to t in this network is 2 units. The way to do that is you spend one unit
of stuff over the top path. From S to V to ^.
And you send a second unit on the bottom path, using W as an intermediate stop.
So I'm happy to report that The Maximum Flow Problem can be solved exactly, in
polynomial time. There are many ways of doing it, many
different cool algorithms that solve the max flow problem.
But the simplest ways are, in effect, greedy algorithms, where you route flow
one path at a time. One thing worth pointing out, is the most
obvious greedy approach to the maximum flow problem doesn't work.
The most obvious thing to do, is to just find the path where there's residual
capacity along every edge, send flow along that path, and repeat.
So, the sub-optimality of the naive greedy algorithm is already evident in
the 4 vertex network that I've shown you on this slide.
Suppose in the first generation, to find your first path to push flow along, you
wind up choosing the path that goes from s, to v, to w, to t.
So, that has three edges on it. All of those edges have capacity one, so
your free to push one unit of flow. Along this exact path.
But, if you do that, you've now blocked up the other paths as well, the s u v and
the s w t path. There is no way to send further flow
along any of those three paths. So this naive greedy algorithm, only
compute a flow of value one whereas we know the max flow value is equal to 2.
So instead you have to allow a more generous notion of an augmenting path,
where you can send the flow in reverse, in effect undoing augmentations of
previous iterations. But, with this more generous definition
of augmenting paths, the resulting greedy algorithm is indeed guaranteed to compute
a maximum flow. Moreover if you're smart about which
augmenting path you use in each iteration of greedy algorithm, you can proof a
running time bound which is polynomial. There's also a number of non-augmenting
path based polynomial time algorithm's for the maximum flow problem as well.
In fact, this diversity of solutions for the maximum flow problem makes it a
little hard for me to give you a succinct bottom line about what running time we
can get for this problem. But roughly speaking, we don't have
algorithm which are near linear time. But we have plenty of algorithm which are
not much worse than that, like quadratic regime.
Think about, you know, Bellman-Ford like running time bounds of m*n and a lot of
these algorithms to better than quadratic in practice.
And one thing that's cool, is that even though this maximum flow problem is
totally classical, these augmenting path algoritms where first studied in the
1950s by Foren Folkenson even in the 21st century we've been seeing some really
nice new developments with maximum flow. Cool new algorithms based on things like
either random sampling, or connections to electrical networks.
In some applications of flow networks, you want to think about flows as not
being computed by some centralized algorithm but rather as arising from the
behavior of a number of participants. Think for example when you get in a car
and drive from say Home to work. Nobody's telling you which route you have
to take, rather you choose what route you want to take from home to work, based on
your own preferences. For example, perhaps you take the
shortest route available. Such self interested behavior in networks
has been a major research topic in the 21st century.
Let me just show you one acute cocktail party ready example of that called braces
paradox. So imagine we have a flow network.
And again you might want to think about road traffic as being a simple example.
Let's focus on a case where a bunch of morning commuters are leaving a common
suburb, represented by a vertex s, destined for a nearby city, let's call it
a vertex t, all leaving at roughly the same time and all of them get to pick
whichever routes they want through the network to get from s to t.
So to better represent issues in transportation networks, let's, instead
of thinking of links as having capacities, let's think of them as having
delay functions. So for each edge, there's going to be a
function, which describes. As a function of how much traffic uses
that edge, what is the resulting travel time that all of that traffic endures? So
as you know from your own experiences, the more congested a road is, the longer
it takes you to get across that road. So as an illustration in this pink
network on the right, let's give two of the roads the constant delay function
always equal to one. So these would be roads that have, in
effect, an infinite number of lanes but they're also pretty long.
So no matter how much traffic is using it, it always takes you an hour to
traverse one of these two roads. The other two roads, by contrast, are
going to have the travel time increase with the congestion.
And just to keep things really simple, let's use the identity function so that
if 100% of the traffic uses one of these roads, then it takes an hour.
If 50% of the traffic uses one of these roads, all of that traffic takes a half
an hour to traverse the road, and so on. So let's now look at this pink network.
Remember, we have this one unit of selfish traffic, which is representing
hundreds, or thousands of drivers, that are picking their own routes from s to t.
Let's assume that drivers just want to get to t as quickly as possible.
They just want to minimize their travel time.
And then the question is, which flow is going to arise from this aggregate,
self-interested behavior. Well, the two routes are exactly the
same. Each one has one road that always takes
an hour, and it has a se-, and also has a second road which takes time proportional
in hours to the fraction of traffic that uses it.
So because of this symmetry, once things settle down into a steady state We expect
half of the traffic to be using the top path, half of the traffic to be using the
bottom path. With a 50/50 split of the traffic, each
of the two routes takes an hour and a half overall.
Now, I mentioned something called, Bracer's paradox.
So what's the paradox? Well, imagine that we view this hour and a half commute time
time was totally unacceptable. Moreover, imagine that we have a new
technology. Someone just invented a teleportation
device and we want to install it in this network so that.
People can get to their workplace faster than before.
So let's install one of these teleporters, at the vertex v, to allow
people to travel instantaneously, to the vertex w.
So we're, we'll represent that by adding to this pink network, a fifth link from v
to w, with a constant delay function always equal to zero.
So what are the ramifications of adding this teleportation device allowing you to
go from V to W instantaneously. Well suppose you were one of those
drivers, stuck with your current commute time of an hour and a half, no surprise
you wouldn't want to ditch your old route, to make use of this new teleport.
So you would want to switch from your old path, whether it was s v t or s w t to
the new zigzag path, s v w t. It's looking like then, it would, you'd
get to work in only an hour. You'd spend half an hour on the edge s v
instantaneous teleportation and another half an hour on the edge w t.
But, here's the catch, not only are you going to switch your path to use the
teleportation device, so are the thousands of other drivers.
So in the new steady state, after we've augmented the network with this
teleportation device, everybody's going to be using the zig zag path s v w t.
And now that everybody is doing exactly the same thing, all of the traffic uses
the edge s v, driving it's travel time up to an hour.
Everybody's using the edge w t driving it's travel time up to an hour.
So now, depsite the fact that we've made the network intuitively only better, In
the unique new steady state, assuming everybody selfishly chooses their minimum
travel time path, the commute time has actually gotten worse.
It's jumped from an hour and a half for everybody, to two hours for everybody.
That is Braess' paradox, improvements to networks where you have selfish users,
can make the outcome worse for everybody. Wow.
So that's Braess's Paradox, discovered by, you guessed it, Braess, a German
mathmatician, back in 1968. Amaze your friends and colleagues at the
next nerdy cocktail party you find yourself at.
Actually, there's a physical realization of Braess' Paradox you might find more
useful For that purpose. Here's the idea, the idea is your going
to take as ingredients, strings and springs.
The strings are meant to perform the function of constant delayed functions.
Strings of course being in-elastic objects, that the length of teh string is
independant of the amount of force you apply.
Springs, on the other hand, are elastic. That is, their length is proportional to
the force applied to the spring. So those play a role analogous to the
linear delay functions in this network. So Braess' Paradox shows that there
exists a way to wire strings and springs brings together.
And then hang this contraption of strings and springs from a fixed base say the
underside of a table. You hang a weight from the bottom of
these strings and springs, so that naturally stretches it out.
Now, in general, when you have a contraption that's holding some weight
and you start chopping, you Take a pair of scissors and cut things off in the
middle of this contraption. You expect the contraption to be weaker
and therefore the weight is going to sag further toward the ground.
But in the same way Braess's Paradox shows that we're moving a supposedly
helpful teleportation device from a network can actually improve, can
actually shorten, selfish commute times. That shows that cutting out top strings
from the middle of the contraption, can actually get a weight to levitate further
off of the ground. And this is not just hypothetical.
Students in my classes have built these strings and springs contraptions, and
have demonstrated this levitation. If you search YouTube I'll bet you could
find some videos. Try it at home.