1 00:00:00,012 --> 00:00:04,231 One key reason why the stable matching problem admits an efficient solution is 2 00:00:04,231 --> 00:00:08,314 that you can, in principle, match any node to any other node on the opposite 3 00:00:08,314 --> 00:00:10,663 side. Sure the nodes have preferences, and 4 00:00:10,663 --> 00:00:14,873 might not want to be matched to certain nodes, but there's no hard constraints 5 00:00:14,873 --> 00:00:18,654 preventing certain pairings. When you do have such hard constraints, 6 00:00:18,654 --> 00:00:22,218 we wind up with the classical, bipartite matching problem. 7 00:00:22,218 --> 00:00:26,747 So the input to the bipartite matching problem is a bipartite graph, so remember 8 00:00:26,747 --> 00:00:29,961 what that means. That means you can take the vertices and 9 00:00:29,961 --> 00:00:33,498 put them into two groups. Let's call one of them capital U, the 10 00:00:33,498 --> 00:00:37,866 other one capital V, and every single edge has exactly one endpoint in each of 11 00:00:37,866 --> 00:00:40,956 the two groups. Put differently, there exists a cut of 12 00:00:40,956 --> 00:00:45,657 the graph that cuts every single edge. The goal is to compute the matching. 13 00:00:45,657 --> 00:00:51,164 Remember a matching is a sub-set of edges that are pair wise disjoint, no pair of 14 00:00:51,164 --> 00:00:56,236 edges can overlap at an endpoint. And to compute the matching that has the 15 00:00:56,236 --> 00:01:01,167 largest possible size. So, for example, in this pink graph on 16 00:01:01,167 --> 00:01:04,951 the right, there are various matchings consisting of 3 edges. 17 00:01:04,951 --> 00:01:09,078 And I'll leave it for you to check that there is no perfect matching. 18 00:01:09,078 --> 00:01:11,661 There's no way to have a matching of 4 edges. 19 00:01:12,753 --> 00:01:16,286 So, bipartite matching is a totally fundamental problem. 20 00:01:16,286 --> 00:01:20,907 There are constraints on which objects you can pair up and you want to pair up 21 00:01:20,907 --> 00:01:24,967 as many objects as possible. I'm happy to report that the maximum 22 00:01:24,967 --> 00:01:27,897 matching problem is solvable in polynomial time. 23 00:01:27,897 --> 00:01:32,367 In fact its poly time servable not just in bipartite graphs which is what I'm 24 00:01:32,367 --> 00:01:35,777 discussing here but even in general non-bipartite graph. 25 00:01:35,777 --> 00:01:40,222 So non-bipartite graphs you have to work pretty hard to solve the problem in 26 00:01:40,222 --> 00:01:43,722 polynomial time. The bipartite case that I'm talking about 27 00:01:43,722 --> 00:01:49,679 here reduces easily to another problem you should know about, called the maximum 28 00:01:49,679 --> 00:01:54,269 flow problem. So I'll now move on to describing the 29 00:01:54,269 --> 00:01:58,572 maximum flow problem. I'll leave it as a good exercise for you 30 00:01:58,572 --> 00:02:02,345 to do why bi partied matching reduces to maximum flow. 31 00:02:03,581 --> 00:02:07,825 You can study maximum flow in either un-directed or directed graphs. 32 00:02:07,825 --> 00:02:11,618 The directed graph case is in some sense the more general one. 33 00:02:11,618 --> 00:02:16,735 Let me state that here. The input is directed graph, one special 34 00:02:16,735 --> 00:02:21,512 vertex is called the source vertex s, and another vertex t, is called the sync 35 00:02:21,512 --> 00:02:26,904 vertex. Finally, each edge e has a capacity, u 36 00:02:26,904 --> 00:02:34,080 sub e, which is the maximum amount of flow, or traffic, that the edge can 37 00:02:34,080 --> 00:02:39,371 accommodate. Informally, the goal is to push as much 38 00:02:39,371 --> 00:02:43,884 stuff as possible. From the source vertex s to the sync 39 00:02:43,884 --> 00:02:47,831 vertex t respecting the capacities of the various lengths. 40 00:02:47,831 --> 00:02:52,764 So you should think of examples as electrical current being generated from s 41 00:02:52,764 --> 00:02:57,725 and flowing to t or you can think of water being injected into the network at 42 00:02:57,725 --> 00:03:02,489 s flowing through these edges representing pipes and then being drained 43 00:03:02,489 --> 00:03:07,400 out at t. The point is, you have a conservation of flow at every vertex 44 00:03:07,400 --> 00:03:11,317 other than s and t. That is, the amount of stuff coming in 45 00:03:11,317 --> 00:03:16,439 has to equal the amount of stuff coming out, except for s, where stuff gets 46 00:03:16,439 --> 00:03:19,615 generated and at t, where stuff gets drained. 47 00:03:19,615 --> 00:03:25,172 As a simple example, suppose in this pink network on the right, I give each edge a 48 00:03:25,172 --> 00:03:29,482 capacity of 1. the maximum amount of stuff you can push 49 00:03:29,482 --> 00:03:35,497 from s to t in this network is 2 units. The way to do that is you spend one unit 50 00:03:35,497 --> 00:03:38,907 of stuff over the top path. From S to V to ^. 51 00:03:38,907 --> 00:03:45,202 And you send a second unit on the bottom path, using W as an intermediate stop. 52 00:03:45,202 --> 00:03:50,402 So I'm happy to report that The Maximum Flow Problem can be solved exactly, in 53 00:03:50,402 --> 00:03:54,077 polynomial time. There are many ways of doing it, many 54 00:03:54,077 --> 00:03:58,077 different cool algorithms that solve the max flow problem. 55 00:03:58,077 --> 00:04:03,352 But the simplest ways are, in effect, greedy algorithms, where you route flow 56 00:04:03,352 --> 00:04:07,317 one path at a time. One thing worth pointing out, is the most 57 00:04:07,317 --> 00:04:11,512 obvious greedy approach to the maximum flow problem doesn't work. 58 00:04:11,512 --> 00:04:16,322 The most obvious thing to do, is to just find the path where there's residual 59 00:04:16,322 --> 00:04:20,721 capacity along every edge, send flow along that path, and repeat. 60 00:04:20,721 --> 00:04:25,267 So, the sub-optimality of the naive greedy algorithm is already evident in 61 00:04:25,267 --> 00:04:28,691 the 4 vertex network that I've shown you on this slide. 62 00:04:28,691 --> 00:04:33,538 Suppose in the first generation, to find your first path to push flow along, you 63 00:04:33,538 --> 00:04:37,162 wind up choosing the path that goes from s, to v, to w, to t. 64 00:04:37,162 --> 00:04:41,498 So, that has three edges on it. All of those edges have capacity one, so 65 00:04:41,498 --> 00:04:45,498 your free to push one unit of flow. Along this exact path. 66 00:04:45,498 --> 00:04:51,183 But, if you do that, you've now blocked up the other paths as well, the s u v and 67 00:04:51,183 --> 00:04:54,643 the s w t path. There is no way to send further flow 68 00:04:54,643 --> 00:04:59,496 along any of those three paths. So this naive greedy algorithm, only 69 00:04:59,496 --> 00:05:05,495 compute a flow of value one whereas we know the max flow value is equal to 2. 70 00:05:05,495 --> 00:05:09,713 So instead you have to allow a more generous notion of an augmenting path, 71 00:05:09,713 --> 00:05:13,969 where you can send the flow in reverse, in effect undoing augmentations of 72 00:05:13,969 --> 00:05:17,558 previous iterations. But, with this more generous definition 73 00:05:17,558 --> 00:05:22,419 of augmenting paths, the resulting greedy algorithm is indeed guaranteed to compute 74 00:05:22,419 --> 00:05:25,810 a maximum flow. Moreover if you're smart about which 75 00:05:25,810 --> 00:05:30,512 augmenting path you use in each iteration of greedy algorithm, you can proof a 76 00:05:30,512 --> 00:05:35,461 running time bound which is polynomial. There's also a number of non-augmenting 77 00:05:35,461 --> 00:05:39,732 path based polynomial time algorithm's for the maximum flow problem as well. 78 00:05:39,732 --> 00:05:43,824 In fact, this diversity of solutions for the maximum flow problem makes it a 79 00:05:43,824 --> 00:05:48,059 little hard for me to give you a succinct bottom line about what running time we 80 00:05:48,059 --> 00:05:51,393 can get for this problem. But roughly speaking, we don't have 81 00:05:51,393 --> 00:05:55,662 algorithm which are near linear time. But we have plenty of algorithm which are 82 00:05:55,662 --> 00:05:58,331 not much worse than that, like quadratic regime. 83 00:05:58,331 --> 00:06:02,650 Think about, you know, Bellman-Ford like running time bounds of m*n and a lot of 84 00:06:02,650 --> 00:06:05,912 these algorithms to better than quadratic in practice. 85 00:06:05,912 --> 00:06:09,945 And one thing that's cool, is that even though this maximum flow problem is 86 00:06:09,945 --> 00:06:14,198 totally classical, these augmenting path algoritms where first studied in the 87 00:06:14,198 --> 00:06:18,669 1950s by Foren Folkenson even in the 21st century we've been seeing some really 88 00:06:18,669 --> 00:06:23,090 nice new developments with maximum flow. Cool new algorithms based on things like 89 00:06:23,090 --> 00:06:26,937 either random sampling, or connections to electrical networks. 90 00:06:26,937 --> 00:06:31,557 In some applications of flow networks, you want to think about flows as not 91 00:06:31,557 --> 00:06:36,337 being computed by some centralized algorithm but rather as arising from the 92 00:06:36,337 --> 00:06:41,147 behavior of a number of participants. Think for example when you get in a car 93 00:06:41,147 --> 00:06:45,663 and drive from say Home to work. Nobody's telling you which route you have 94 00:06:45,663 --> 00:06:50,494 to take, rather you choose what route you want to take from home to work, based on 95 00:06:50,494 --> 00:06:53,871 your own preferences. For example, perhaps you take the 96 00:06:53,871 --> 00:06:58,898 shortest route available. Such self interested behavior in networks 97 00:06:58,898 --> 00:07:02,011 has been a major research topic in the 21st century. 98 00:07:02,011 --> 00:07:07,192 Let me just show you one acute cocktail party ready example of that called braces 99 00:07:07,192 --> 00:07:09,746 paradox. So imagine we have a flow network. 100 00:07:09,746 --> 00:07:14,217 And again you might want to think about road traffic as being a simple example. 101 00:07:14,217 --> 00:07:18,624 Let's focus on a case where a bunch of morning commuters are leaving a common 102 00:07:18,624 --> 00:07:23,081 suburb, represented by a vertex s, destined for a nearby city, let's call it 103 00:07:23,081 --> 00:07:27,460 a vertex t, all leaving at roughly the same time and all of them get to pick 104 00:07:27,460 --> 00:07:31,907 whichever routes they want through the network to get from s to t. 105 00:07:31,907 --> 00:07:36,617 So to better represent issues in transportation networks, let's, instead 106 00:07:36,617 --> 00:07:41,167 of thinking of links as having capacities, let's think of them as having 107 00:07:41,167 --> 00:07:44,712 delay functions. So for each edge, there's going to be a 108 00:07:44,712 --> 00:07:48,880 function, which describes. As a function of how much traffic uses 109 00:07:48,880 --> 00:07:53,861 that edge, what is the resulting travel time that all of that traffic endures? So 110 00:07:53,861 --> 00:07:58,613 as you know from your own experiences, the more congested a road is, the longer 111 00:07:58,613 --> 00:08:03,051 it takes you to get across that road. So as an illustration in this pink 112 00:08:03,051 --> 00:08:07,778 network on the right, let's give two of the roads the constant delay function 113 00:08:07,778 --> 00:08:11,324 always equal to one. So these would be roads that have, in 114 00:08:11,324 --> 00:08:15,389 effect, an infinite number of lanes but they're also pretty long. 115 00:08:15,389 --> 00:08:19,758 So no matter how much traffic is using it, it always takes you an hour to 116 00:08:19,758 --> 00:08:24,350 traverse one of these two roads. The other two roads, by contrast, are 117 00:08:24,350 --> 00:08:28,275 going to have the travel time increase with the congestion. 118 00:08:28,275 --> 00:08:33,395 And just to keep things really simple, let's use the identity function so that 119 00:08:33,395 --> 00:08:37,908 if 100% of the traffic uses one of these roads, then it takes an hour. 120 00:08:37,908 --> 00:08:42,976 If 50% of the traffic uses one of these roads, all of that traffic takes a half 121 00:08:42,976 --> 00:08:47,252 an hour to traverse the road, and so on. So let's now look at this pink network. 122 00:08:47,252 --> 00:08:51,260 Remember, we have this one unit of selfish traffic, which is representing 123 00:08:51,260 --> 00:08:55,663 hundreds, or thousands of drivers, that are picking their own routes from s to t. 124 00:08:55,663 --> 00:08:59,376 Let's assume that drivers just want to get to t as quickly as possible. 125 00:08:59,376 --> 00:09:01,759 They just want to minimize their travel time. 126 00:09:01,759 --> 00:09:06,240 And then the question is, which flow is going to arise from this aggregate, 127 00:09:06,240 --> 00:09:09,971 self-interested behavior. Well, the two routes are exactly the 128 00:09:09,971 --> 00:09:12,589 same. Each one has one road that always takes 129 00:09:12,589 --> 00:09:17,352 an hour, and it has a se-, and also has a second road which takes time proportional 130 00:09:17,352 --> 00:09:20,187 in hours to the fraction of traffic that uses it. 131 00:09:20,187 --> 00:09:24,904 So because of this symmetry, once things settle down into a steady state We expect 132 00:09:24,904 --> 00:09:29,155 half of the traffic to be using the top path, half of the traffic to be using the 133 00:09:29,155 --> 00:09:32,312 bottom path. With a 50/50 split of the traffic, each 134 00:09:32,312 --> 00:09:35,032 of the two routes takes an hour and a half overall. 135 00:09:35,032 --> 00:09:38,456 Now, I mentioned something called, Bracer's paradox. 136 00:09:38,456 --> 00:09:43,435 So what's the paradox? Well, imagine that we view this hour and a half commute time 137 00:09:43,435 --> 00:09:47,693 time was totally unacceptable. Moreover, imagine that we have a new 138 00:09:47,693 --> 00:09:50,904 technology. Someone just invented a teleportation 139 00:09:50,904 --> 00:09:54,522 device and we want to install it in this network so that. 140 00:09:54,522 --> 00:09:58,237 People can get to their workplace faster than before. 141 00:09:58,237 --> 00:10:02,924 So let's install one of these teleporters, at the vertex v, to allow 142 00:10:02,924 --> 00:10:06,485 people to travel instantaneously, to the vertex w. 143 00:10:06,485 --> 00:10:12,094 So we're, we'll represent that by adding to this pink network, a fifth link from v 144 00:10:12,094 --> 00:10:16,372 to w, with a constant delay function always equal to zero. 145 00:10:16,372 --> 00:10:21,182 So what are the ramifications of adding this teleportation device allowing you to 146 00:10:21,182 --> 00:10:25,042 go from V to W instantaneously. Well suppose you were one of those 147 00:10:25,042 --> 00:10:29,757 drivers, stuck with your current commute time of an hour and a half, no surprise 148 00:10:29,757 --> 00:10:34,382 you wouldn't want to ditch your old route, to make use of this new teleport. 149 00:10:34,382 --> 00:10:39,173 So you would want to switch from your old path, whether it was s v t or s w t to 150 00:10:39,173 --> 00:10:43,643 the new zigzag path, s v w t. It's looking like then, it would, you'd 151 00:10:43,643 --> 00:10:48,089 get to work in only an hour. You'd spend half an hour on the edge s v 152 00:10:48,089 --> 00:10:52,862 instantaneous teleportation and another half an hour on the edge w t. 153 00:10:52,862 --> 00:10:58,192 But, here's the catch, not only are you going to switch your path to use the 154 00:10:58,192 --> 00:11:02,627 teleportation device, so are the thousands of other drivers. 155 00:11:02,627 --> 00:11:07,697 So in the new steady state, after we've augmented the network with this 156 00:11:07,697 --> 00:11:13,282 teleportation device, everybody's going to be using the zig zag path s v w t. 157 00:11:13,282 --> 00:11:18,817 And now that everybody is doing exactly the same thing, all of the traffic uses 158 00:11:18,817 --> 00:11:22,460 the edge s v, driving it's travel time up to an hour. 159 00:11:22,460 --> 00:11:27,417 Everybody's using the edge w t driving it's travel time up to an hour. 160 00:11:27,417 --> 00:11:33,103 So now, depsite the fact that we've made the network intuitively only better, In 161 00:11:33,103 --> 00:11:38,095 the unique new steady state, assuming everybody selfishly chooses their minimum 162 00:11:38,095 --> 00:11:41,931 travel time path, the commute time has actually gotten worse. 163 00:11:41,931 --> 00:11:46,708 It's jumped from an hour and a half for everybody, to two hours for everybody. 164 00:11:46,708 --> 00:11:51,818 That is Braess' paradox, improvements to networks where you have selfish users, 165 00:11:51,818 --> 00:11:54,812 can make the outcome worse for everybody. Wow. 166 00:11:54,812 --> 00:12:00,012 So that's Braess's Paradox, discovered by, you guessed it, Braess, a German 167 00:12:00,012 --> 00:12:04,687 mathmatician, back in 1968. Amaze your friends and colleagues at the 168 00:12:04,687 --> 00:12:07,912 next nerdy cocktail party you find yourself at. 169 00:12:07,912 --> 00:12:13,412 Actually, there's a physical realization of Braess' Paradox you might find more 170 00:12:13,412 --> 00:12:17,274 useful For that purpose. Here's the idea, the idea is your going 171 00:12:17,274 --> 00:12:19,817 to take as ingredients, strings and springs. 172 00:12:19,817 --> 00:12:24,107 The strings are meant to perform the function of constant delayed functions. 173 00:12:24,107 --> 00:12:28,361 Strings of course being in-elastic objects, that the length of teh string is 174 00:12:28,361 --> 00:12:30,912 independant of the amount of force you apply. 175 00:12:30,912 --> 00:12:35,646 Springs, on the other hand, are elastic. That is, their length is proportional to 176 00:12:35,646 --> 00:12:39,612 the force applied to the spring. So those play a role analogous to the 177 00:12:39,612 --> 00:12:43,994 linear delay functions in this network. So Braess' Paradox shows that there 178 00:12:43,994 --> 00:12:47,547 exists a way to wire strings and springs brings together. 179 00:12:47,547 --> 00:12:52,052 And then hang this contraption of strings and springs from a fixed base say the 180 00:12:52,052 --> 00:12:55,197 underside of a table. You hang a weight from the bottom of 181 00:12:55,197 --> 00:12:58,677 these strings and springs, so that naturally stretches it out. 182 00:12:58,677 --> 00:13:02,627 Now, in general, when you have a contraption that's holding some weight 183 00:13:02,627 --> 00:13:06,653 and you start chopping, you Take a pair of scissors and cut things off in the 184 00:13:06,653 --> 00:13:10,031 middle of this contraption. You expect the contraption to be weaker 185 00:13:10,031 --> 00:13:13,380 and therefore the weight is going to sag further toward the ground. 186 00:13:13,380 --> 00:13:16,999 But in the same way Braess's Paradox shows that we're moving a supposedly 187 00:13:16,999 --> 00:13:20,514 helpful teleportation device from a network can actually improve, can 188 00:13:20,514 --> 00:13:24,590 actually shorten, selfish commute times. That shows that cutting out top strings 189 00:13:24,590 --> 00:13:29,141 from the middle of the contraption, can actually get a weight to levitate further 190 00:13:29,141 --> 00:13:32,169 off of the ground. And this is not just hypothetical. 191 00:13:32,169 --> 00:13:36,586 Students in my classes have built these strings and springs contraptions, and 192 00:13:36,586 --> 00:13:40,879 have demonstrated this levitation. If you search YouTube I'll bet you could 193 00:13:40,879 --> 00:13:42,679 find some videos. Try it at home.