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.