WEBVTT 1 00:00:00.160 --> 00:00:04.799 So what if I told you there's an inescapable mathematical 2 00:00:04.839 --> 00:00:08.560 proof explaining why the person who makes the first move 3 00:00:08.599 --> 00:00:11.240 in a relationship or you know, like the opening offer 4 00:00:11.279 --> 00:00:14.000 and a negotiation almost always comes out ahead. 5 00:00:14.080 --> 00:00:17.000 And to be clear, it is not about psychology at. 6 00:00:16.879 --> 00:00:20.079 All, Right, it's actually hardwired into the math of how 7 00:00:20.239 --> 00:00:24.600 systems organize themselves. So welcome to this deep dive, custom 8 00:00:24.640 --> 00:00:27.600 tailored just for you. Today. We're opening up a really 9 00:00:27.600 --> 00:00:32.079 fascinating source, the authoritative text book called Algorithm Design by 10 00:00:32.119 --> 00:00:35.840 John Kleinberg and Epit Tardos. And I mean our mission 11 00:00:35.840 --> 00:00:38.079 today is not about writing lines of code or anything 12 00:00:38.119 --> 00:00:38.320 like that. 13 00:00:38.399 --> 00:00:40.640 No, not at all. It's really about looking at algorithms 14 00:00:40.679 --> 00:00:44.679 as a powerful lens to view human behavior. You know, 15 00:00:44.719 --> 00:00:48.520 we're taking these messy, chaotic, totally real world situations and 16 00:00:49.280 --> 00:00:51.600 stripping them down to their mathematical cores to see what's 17 00:00:51.600 --> 00:00:52.960 actually going on beneath the surface. 18 00:00:53.079 --> 00:00:56.159 Yeah, and that leap, like from human chaos to mathematical 19 00:00:56.200 --> 00:00:59.079 certainty is just profound. But to get to that proof 20 00:00:59.119 --> 00:01:01.240 about why the first wins, we first need to look 21 00:01:01.320 --> 00:01:05.719 at a classic problem that perfectly illustrates unregulated human self interest. 22 00:01:05.959 --> 00:01:08.560 Right, the classic stable matching problem. 23 00:01:08.120 --> 00:01:12.959 Exactly, originally posed by two mathematical economists, David Gale and 24 00:01:13.040 --> 00:01:17.719 Lord Shapeley, way back in nineteen sixty two. And the 25 00:01:17.760 --> 00:01:21.560 textbook sets this up with a highly relatable summer internship scenario. 26 00:01:21.680 --> 00:01:25.439 Oh yeah, the internship one. So picture your friend Roj 27 00:01:25.879 --> 00:01:28.879 rog goes through this grueling interview process and finally accepts 28 00:01:28.879 --> 00:01:32.879 a summer job at this massive, totally stable telecom company 29 00:01:32.879 --> 00:01:33.640 called Cleanet. 30 00:01:34.239 --> 00:01:36.159 The ink is dry, he set, right. 31 00:01:36.040 --> 00:01:38.680 You'd think so. But a few days later, a hip 32 00:01:38.719 --> 00:01:42.519 little startup called web Exodus, who had completely ghosted him previously, 33 00:01:42.959 --> 00:01:45.120 suddenly calls up and offers him the position, and. 34 00:01:45.120 --> 00:01:48.239 Roj obviously prefers the startup. I mean it's a cooler vibe, 35 00:01:48.280 --> 00:01:51.200 probably better long term prospects, So, acting in his own 36 00:01:51.200 --> 00:01:54.480 pure self interest, he just retracts his acceptance from Clunet 37 00:01:54.519 --> 00:01:56.599 and bails to go to web Exodus exactly. 38 00:01:56.640 --> 00:01:59.159 And now Clunet is down an intern so they panic. 39 00:01:59.200 --> 00:02:01.719 They go to their weightlist and call another applicant, but 40 00:02:02.560 --> 00:02:06.719 that applicant has already accepted an offer at a third company, Babblesoft. 41 00:02:06.439 --> 00:02:09.360 Right, so that person bails on Babbelsoft to go to Clunet. 42 00:02:09.639 --> 00:02:12.439 The disruption just cascades through the entire industry. 43 00:02:12.800 --> 00:02:15.360 Yeah, and the instability flows in the other direction as well. 44 00:02:15.599 --> 00:02:18.960 Like I suppose a student named Chelsea is scheduled to 45 00:02:18.960 --> 00:02:22.159 go to Baiblsoft mm hm. She hears about rog is 46 00:02:22.199 --> 00:02:25.719 maneuvering and decides to just call up web Exodus herself. 47 00:02:25.840 --> 00:02:28.479 Bold move, very bold. Yeah. She tells them she'd rather 48 00:02:28.520 --> 00:02:32.439 work there. Web Exodus looks at her resume, realizes they 49 00:02:32.439 --> 00:02:36.479 actually prefer Chelsea over one of the students they already hired, 50 00:02:36.719 --> 00:02:40.120 and they just ruthlessly retract an earlier offer to hire 51 00:02:40.159 --> 00:02:40.919 Chelsea instead. 52 00:02:41.240 --> 00:02:44.319 So agreements mean absolutely nothing because people are constantly looking 53 00:02:44.319 --> 00:02:47.639 for a side deal. Gail and Shapley basically realize that 54 00:02:47.680 --> 00:02:49.840 to stop the spiral, you need a system that is 55 00:02:49.879 --> 00:02:51.560 fundamentally like self. 56 00:02:51.360 --> 00:02:53.400 Enforcing a stable outcome, yeah, where. 57 00:02:53.240 --> 00:02:56.439 Individual self interest actually prevents any of these behind the 58 00:02:56.439 --> 00:02:58.280 scenes deals from happening in the first place. 59 00:02:58.439 --> 00:03:02.000 Right. And to study this, the economists stripped away all 60 00:03:02.039 --> 00:03:05.319 the complexities of the corporate world, you know, the different salaries, 61 00:03:05.360 --> 00:03:09.039 the unequal numbers of applicants and jobs, and they abstracted 62 00:03:09.080 --> 00:03:11.080 it into a classic marriage model. 63 00:03:11.280 --> 00:03:14.280 Okay, let's unpack this bare bones model because it's key. 64 00:03:14.719 --> 00:03:18.000 We have n men and n women. Each man has 65 00:03:18.039 --> 00:03:20.680 a ranked preference list of all the women from his 66 00:03:20.800 --> 00:03:25.240 absolute favorite to his least favorite, with no ties allowed, and. 67 00:03:25.240 --> 00:03:27.919 Each woman has a similarly ranked list of all the men. 68 00:03:28.120 --> 00:03:31.479 Right, So the goal is a perfect matching. Everyone gets 69 00:03:31.479 --> 00:03:35.000 married to exactly one person. No one is single. But 70 00:03:35.080 --> 00:03:38.159 the real objective here is finding a stable. 71 00:03:37.759 --> 00:03:42.120 Matching, and stability here is defined specifically by the absence 72 00:03:42.120 --> 00:03:43.919 of an instability. 73 00:03:43.240 --> 00:03:45.159 Which means what exactly in math terms. 74 00:03:45.360 --> 00:03:48.319 An instability formally exists if there's a man or a 75 00:03:48.319 --> 00:03:50.400 woman who are not married to each other, but who 76 00:03:50.439 --> 00:03:53.960 actually prefer each other over their current assigned partners. 77 00:03:54.120 --> 00:03:58.280 Okay, I picture an instability like a precarious house of cards, 78 00:03:58.360 --> 00:04:01.159 or maybe a tightly woven fabric. If even one pair 79 00:04:01.199 --> 00:04:02.879 of people look at each other across the room and 80 00:04:02.919 --> 00:04:05.280 both realize, like, hey, I'd rather be with you than 81 00:04:05.280 --> 00:04:07.919 the person I was assigned to, they just bypass the rules. 82 00:04:07.960 --> 00:04:10.680 They do. They act in their own self interest exactly. 83 00:04:10.840 --> 00:04:13.800 They pull that thread, run off together, and the entire 84 00:04:13.840 --> 00:04:18.839 fabric unravels because their abandoned partners are suddenly single, forcing 85 00:04:18.879 --> 00:04:21.720 them to find new matches, displacing others in an endless 86 00:04:21.800 --> 00:04:22.439 chain reaction. 87 00:04:22.639 --> 00:04:26.360 What's fascinating here is that Gail and Shapley proved mathematically 88 00:04:26.639 --> 00:04:30.319 that a completely stable matching, a fabric that absolutely will 89 00:04:30.319 --> 00:04:35.319 not unravel, always exists. I wait, always, always, for literally 90 00:04:35.360 --> 00:04:38.959 any set of preferences, no matter how conflicting, contradictory, or tangled, 91 00:04:39.399 --> 00:04:41.959 you can always pair people up so that no two 92 00:04:42.040 --> 00:04:44.000 people want to abandon the system for each other. 93 00:04:44.040 --> 00:04:47.199 Okay, but knowing a stable outcome exists hovering out there 94 00:04:47.240 --> 00:04:51.360 in the ether is one thing. Human preferences are impossibly complex. 95 00:04:51.439 --> 00:04:53.879 How do you actually find that stable state without just, 96 00:04:53.959 --> 00:04:57.079 I don't know, trying millions of combinations until you get lucky. 97 00:04:57.199 --> 00:04:59.680 Well, you use the Gail Shapley algorithm. It's a h 98 00:05:00.000 --> 00:05:03.519 It's a step by step mechanical process. Initially, everyone is 99 00:05:03.560 --> 00:05:08.120 completely free. The algorithm dictates that an unengaged man looks 100 00:05:08.120 --> 00:05:11.199 at his preference list and proposes to the absolute highest 101 00:05:11.240 --> 00:05:13.240 ranked woman. He hasn't asked yet, so. 102 00:05:13.160 --> 00:05:14.600 He starts right at the top of his. 103 00:05:14.639 --> 00:05:17.399 List, exactly. He starts at the top. If that woman 104 00:05:17.439 --> 00:05:20.040 is free, she accepts, and they become engaged. 105 00:05:20.439 --> 00:05:22.079 But the text is clear that this is only an 106 00:05:22.120 --> 00:05:24.759 intermediate state, right, Like they aren't fully married yet. 107 00:05:24.920 --> 00:05:27.800 Right. It's at the native engagement because if she receives 108 00:05:27.800 --> 00:05:30.000 a proposal later from a man she ranks higher than 109 00:05:30.000 --> 00:05:33.439 her current fiance, she immediately breaks the engagement to trade up. 110 00:05:33.800 --> 00:05:34.279 Ouch. 111 00:05:34.399 --> 00:05:38.000 Yeah, brutal for the guy. The rejected man becomes free again, 112 00:05:38.360 --> 00:05:40.639 moves down to the next woman on his list, and 113 00:05:40.680 --> 00:05:41.600 proposes to her. 114 00:05:41.839 --> 00:05:44.839 The mechanics are relentless. I mean, the men are constantly proposing, 115 00:05:44.920 --> 00:05:47.920 getting rejected, and working their way down their preference lists, 116 00:05:47.959 --> 00:05:51.199 so their choices are getting progressively worse. 117 00:05:51.000 --> 00:05:53.040 Over time yep, moving down the ranks. 118 00:05:53.199 --> 00:05:57.040 Meanwhile, the women are holding these tentative engagements, essentially keeping 119 00:05:57.120 --> 00:05:59.680 a safety option on the hook, just waiting for a 120 00:05:59.720 --> 00:06:02.920 better offer to come along. They break hearts to trade up, 121 00:06:02.920 --> 00:06:06.160 meaning their situations are getting progressively better. And this runs 122 00:06:06.199 --> 00:06:09.720 until no man is free, the music stops, all engagements 123 00:06:09.720 --> 00:06:12.920 become final marriages, and the system terminates. 124 00:06:13.319 --> 00:06:14.879 That's the algorithm in a nutshell. 125 00:06:15.040 --> 00:06:17.439 Okay, but here's where it gets really interesting to me. 126 00:06:18.439 --> 00:06:22.800 Looking at the sheer mechanics of that process. Logic dictates 127 00:06:22.800 --> 00:06:25.800 that the women must get the absolute best end of 128 00:06:25.839 --> 00:06:27.800 the deal. I mean they're holding all the cards. You'd 129 00:06:27.800 --> 00:06:30.959 think so yah, right, They sit back, hold onto a 130 00:06:31.000 --> 00:06:35.079 safety net, and continually trade up for better offers. The 131 00:06:35.160 --> 00:06:38.519 men are facing constant brutal rejection and moving further and 132 00:06:38.560 --> 00:06:41.759 further down their lists. So clearly the women have all 133 00:06:41.800 --> 00:06:42.480 the power here. 134 00:06:42.839 --> 00:06:46.279 That is the intuitive leap almost everyone makes. It completely 135 00:06:46.319 --> 00:06:48.639 looks like the women are in the power position, but 136 00:06:49.879 --> 00:06:53.240 in a massive twist of mathematical irony, that assumption is 137 00:06:53.360 --> 00:06:57.800 entirely wrong. Seriously, Yeah, the algorithm is heavily fundamentally biased 138 00:06:57.839 --> 00:07:00.800 in favor of the proposers in this specific model. 139 00:07:00.879 --> 00:07:03.560 The men, wait, how is that mathematically possible when the 140 00:07:03.600 --> 00:07:05.279 women are the ones doing all they're rejecting. 141 00:07:05.600 --> 00:07:07.839 It comes down to the difference between playing on offense 142 00:07:07.879 --> 00:07:11.879 and playing on defense. The textbook proves this beautifully. Remember 143 00:07:11.879 --> 00:07:15.160 there could be multiple valid stable matchings for any given 144 00:07:15.199 --> 00:07:17.879 group of people. Okay, but when you run this algorithm, 145 00:07:17.879 --> 00:07:20.720 the side that does the proposing is systematically testing the 146 00:07:20.720 --> 00:07:23.800 waters from the top down. The very first woman who 147 00:07:23.879 --> 00:07:27.120 accepts a man and stays with him represents the absolute 148 00:07:27.199 --> 00:07:30.680 highest possible match he could achieve in any stable universe. 149 00:07:31.160 --> 00:07:33.680 He hits the ceiling of his potential. He never even 150 00:07:33.720 --> 00:07:34.959 has to ask anyone lower. 151 00:07:35.120 --> 00:07:39.120 Oh wow. While the receiving side, the women who felt 152 00:07:39.120 --> 00:07:42.360 like they were in total control, are purely playing defense. 153 00:07:42.600 --> 00:07:45.639 Exactly. A woman might desperately want the man at the 154 00:07:45.680 --> 00:07:48.360 top of her list, but if he never proposes to her, 155 00:07:48.759 --> 00:07:51.879 she can never get him. She is entirely dependent on 156 00:07:51.920 --> 00:07:52.959 who approaches her door. 157 00:07:53.160 --> 00:07:55.000 That makes so much sense. She only gets to filter 158 00:07:55.120 --> 00:07:58.399 a limited, self selecting pool of candidates. 159 00:07:57.839 --> 00:08:01.319 Precisely by constantly try rating up among the people who 160 00:08:01.360 --> 00:08:05.000 do propose. She isn't achieving her dream scenario. She's just 161 00:08:05.120 --> 00:08:08.040 elevating herself from the absolute bottom of her potential options. 162 00:08:08.680 --> 00:08:12.600 The algorithm mathematically ensures that every single woman ends up 163 00:08:12.639 --> 00:08:15.040 with the lowest ranked man she could possibly end up 164 00:08:15.079 --> 00:08:17.240 with while still maintaining a stable system. 165 00:08:17.360 --> 00:08:20.199 So she catches the floor while the proposer hits the ceiling. 166 00:08:20.319 --> 00:08:20.800 You got it. 167 00:08:21.079 --> 00:08:24.519 That is staggering the illusion of choice. You know, the 168 00:08:24.560 --> 00:08:27.759 ability to sit back and reject people actually results in 169 00:08:27.800 --> 00:08:31.800 the worst possible stable outcome for you. The side facing 170 00:08:31.839 --> 00:08:35.399 constant rejection ends up with the optimal outcome. And why 171 00:08:35.440 --> 00:08:38.519 does this matter to you the listener? Because this exact 172 00:08:38.559 --> 00:08:41.120 algorithm governs massive parts of our lives. 173 00:08:40.879 --> 00:08:44.799 Oh totally. The National Resident Matching Program, which places thousands 174 00:08:44.840 --> 00:08:48.639 of medical students into hospitals every year, uses a variation. 175 00:08:48.279 --> 00:08:51.679 Of this School placements use this too. Understanding the math 176 00:08:51.759 --> 00:08:54.879 proves that being the proposer or the initiator in any 177 00:08:54.960 --> 00:09:00.759 system isn't just psychologically empowering, it provides a mathematically guaranteed advantage. 178 00:09:00.960 --> 00:09:04.679 It's a profound structural reality hidden inside a matching algorithm. 179 00:09:05.360 --> 00:09:08.320 But as algorithm designers know, the textbook version of the 180 00:09:08.320 --> 00:09:12.480 Gail Shaply model assumes a perfect vacuum like everyone ranks everyone, 181 00:09:12.600 --> 00:09:13.720 no one has deal breakers. 182 00:09:13.759 --> 00:09:17.720 But the real world is infinitely messier. What happens when, say, 183 00:09:17.759 --> 00:09:21.000 our friend Raj simply lacks the legal certification to work 184 00:09:21.039 --> 00:09:23.120 at what bex it is? Or what if two specific 185 00:09:23.120 --> 00:09:26.519 people absolutely refuse to be paired together under any circumstances. 186 00:09:26.679 --> 00:09:28.399 Doesn't the whole algorithm just break down? 187 00:09:28.679 --> 00:09:31.919 You'd think it might, but the text actually anticipates this 188 00:09:32.399 --> 00:09:36.159 by introducing the concept of forbidden pairs. The Gaale Shaply 189 00:09:36.279 --> 00:09:40.639 algorithm is remarkably robust. It adapts to this messy reality 190 00:09:40.960 --> 00:09:44.000 without breaking a sweat. How so you simply cross the 191 00:09:44.000 --> 00:09:48.080 forbidden pairs off the preference lists, the men only proposed 192 00:09:48.080 --> 00:09:51.639 to non forbidden women, the women only accept non forbidden men, 193 00:09:52.279 --> 00:09:55.679 and the math holds up perfectly. It still guarantees a 194 00:09:55.720 --> 00:09:59.159 stable matching where no two people who are legally allowed 195 00:09:59.159 --> 00:10:01.080 to match to abandon the system. 196 00:10:01.159 --> 00:10:04.120 Okay, but that leads to an even bigger human complication 197 00:10:04.639 --> 00:10:05.799 because humans cheat. 198 00:10:06.039 --> 00:10:06.519 They sure do. 199 00:10:06.679 --> 00:10:10.519 If the math legally mathematically guarantees that the receivers get 200 00:10:10.600 --> 00:10:13.600 their worst valid outcome, can a receiver just lie on 201 00:10:13.639 --> 00:10:16.159 her preference list to trick the algorithm into giving her 202 00:10:16.159 --> 00:10:17.000 a better match. 203 00:10:17.360 --> 00:10:20.080 Ah, so you've hit on the truthfulness dilemma, which is 204 00:10:20.200 --> 00:10:24.440 honestly a major headache and algorithm design. The text explores 205 00:10:24.440 --> 00:10:26.759 the scenario where a woman realizes she's going to get 206 00:10:26.759 --> 00:10:28.759 a low tier match because she's on the receiving end, 207 00:10:29.159 --> 00:10:32.679 so she decides to artificially swap the ranking of two 208 00:10:33.279 --> 00:10:37.440 low tier men on her submitted list. She essentially rejects 209 00:10:37.440 --> 00:10:40.399 a man she actually likes slightly better, forcing a breakup 210 00:10:40.440 --> 00:10:42.240 and sending him back into the proposing pool. 211 00:10:42.320 --> 00:10:45.080 Oh, I see the strategy. Yeah, because that rejected man 212 00:10:45.120 --> 00:10:47.360 is back in the pool, he bumps into another woman 213 00:10:47.399 --> 00:10:50.440 and proposes to her. That might cause a cascade of 214 00:10:50.480 --> 00:10:54.679 broken engagements across the whole system, which maybe, just maybe 215 00:10:54.759 --> 00:10:57.320 knocks a top tier man out of his current engagement 216 00:10:57.600 --> 00:11:00.480 and sends him proposing down his list until he reaches 217 00:11:00.519 --> 00:11:01.519 the woman who lied. 218 00:11:01.840 --> 00:11:05.600 You just trace the exact cascade perfectly. By lying about 219 00:11:05.639 --> 00:11:08.159 her preferences at the bottom of her list, she alters 220 00:11:08.200 --> 00:11:10.519 the entire sequence of proposals happening above her. 221 00:11:10.639 --> 00:11:11.279 That's wild. 222 00:11:11.480 --> 00:11:14.639 The textbook proves it's entirely possible for a receiver to 223 00:11:14.720 --> 00:11:18.639 improve their final outcome by falsely reporting their preferences, and 224 00:11:18.720 --> 00:11:21.840 this is a critical lesson. Algorithm designers can't just stop 225 00:11:21.840 --> 00:11:24.639 at the elegant math. They have to constantly analyze the 226 00:11:24.679 --> 00:11:28.000 boundaries of the rules, human behavior, and whether the players 227 00:11:28.039 --> 00:11:31.600 are economically or psychologically incentivized to lie to the system. 228 00:11:31.879 --> 00:11:34.600 Designing an algorithm is basically designing a game where you 229 00:11:34.679 --> 00:11:37.279 have to assume the players will actively try to break it. 230 00:11:37.480 --> 00:11:38.000 Pretty much. 231 00:11:38.080 --> 00:11:42.279 Yeah, so we've successfully navigated stable matching. We found a clean, 232 00:11:42.480 --> 00:11:46.080 efficient mechanism for a chaotic problem. But as we try 233 00:11:46.080 --> 00:11:48.960 to model more complex human behaviors, the math starts to 234 00:11:49.039 --> 00:11:52.039 really push back. The textbook zooms out here to look 235 00:11:52.039 --> 00:11:56.039 at the entire landscape of computational difficulty using what they 236 00:11:56.080 --> 00:11:59.360 frame as a staircase of five representative problems. 237 00:11:59.840 --> 00:12:02.639 Five problems serve as milestones for the rest of the 238 00:12:02.679 --> 00:12:06.120 study of algorithms, because not everything is as solvable as 239 00:12:06.159 --> 00:12:09.320 matching interns to jobs. Let's look at what happens when 240 00:12:09.320 --> 00:12:13.360 a problem goes from easily solvable to practically impossible. 241 00:12:13.559 --> 00:12:17.039 Okay. Step one on this staircase is interval scheduling. You 242 00:12:17.080 --> 00:12:20.919 have a single resource, like an expensive electron microscope, and 243 00:12:21.159 --> 00:12:24.120 a bunch of researchers want to reserve it for overlapping times. 244 00:12:24.559 --> 00:12:27.679 You want to accept the maximum number of requests. The 245 00:12:27.720 --> 00:12:30.840 intuitive human approach might be to pick the shortest requests first, 246 00:12:30.919 --> 00:12:33.440 or maybe the ones that start the earliest, right, But the. 247 00:12:33.360 --> 00:12:38.879 Textbook shows the most efficient way is a pure greedy algorithm. 248 00:12:39.440 --> 00:12:43.639 The mechanism is incredibly simple, almost myopic. You just look 249 00:12:43.679 --> 00:12:46.639 at the pile of requests, pick the single request that 250 00:12:46.679 --> 00:12:48.799 finishes the earliest and book it. 251 00:12:48.840 --> 00:12:50.720 Just the earliest finished time yep. 252 00:12:51.120 --> 00:12:53.679 Then you cross out anything that overlaps with it and 253 00:12:53.759 --> 00:12:57.000 pick the next available request that finishes earliest. You don't 254 00:12:57.000 --> 00:13:00.559 look ahead, you don't strategize, You just greedily the next 255 00:13:00.600 --> 00:13:05.919 finishing task for this specific problem, that simple mechanism mathematically 256 00:13:05.960 --> 00:13:08.399 guarantees an optimal solution every time. 257 00:13:08.639 --> 00:13:11.159 Okay, but that works when every request is considered equal. 258 00:13:11.559 --> 00:13:14.039 Let's step up the staircase to weight at interval scheduling. 259 00:13:14.600 --> 00:13:17.559 What if we attach money to this, Say a massive 260 00:13:17.559 --> 00:13:20.440 pharmaceutical company will pay ten thousand dollars to rent that 261 00:13:20.480 --> 00:13:23.639 microscope for the whole day, while five smaller researchers will 262 00:13:23.639 --> 00:13:25.919 pay one thousand dollars each for two hour slots. That 263 00:13:26.039 --> 00:13:29.320 changes everything, right, because the greedy rule picking the earliest 264 00:13:29.320 --> 00:13:32.159 finishing tasks would grab the small researchers and make five 265 00:13:32.200 --> 00:13:34.840 thousand dollars but completely miss the ten thousand dollars payout. 266 00:13:35.360 --> 00:13:37.399 The greedy mechanism just totally breaks. 267 00:13:37.799 --> 00:13:41.679 It fails completely because the simple rule cannot account for value. 268 00:13:42.799 --> 00:13:45.960 So to solve this, the text introduces a technique called 269 00:13:46.039 --> 00:13:47.120 dynamic programming. 270 00:13:47.519 --> 00:13:48.440 How does that work? 271 00:13:49.039 --> 00:13:52.519 The mechanism here is essentially having the algorithm keep a 272 00:13:52.639 --> 00:13:56.919 highly detailed scorecard. Instead of deciding blindly in the moment, 273 00:13:57.200 --> 00:14:01.240 it calculates the maximum possible profit for every single overlapping 274 00:14:01.279 --> 00:14:04.519 scenario saves those answers in a massive table and then 275 00:14:04.559 --> 00:14:05.279 works backward. 276 00:14:05.399 --> 00:14:06.159 Oh clever. 277 00:14:06.279 --> 00:14:08.399 Yeah. By the time it reaches the first request, it 278 00:14:08.480 --> 00:14:10.879 just looks at its table to trace the absolute most 279 00:14:10.879 --> 00:14:14.360 profitable path through the whole day. It requires more memory 280 00:14:14.360 --> 00:14:16.960 and calculation, but it is still highly efficient. 281 00:14:17.080 --> 00:14:19.879 Got it. So the third step on the staircase scals 282 00:14:19.879 --> 00:14:23.559 things up even more bipartite matching. We aren't just scheduling 283 00:14:23.639 --> 00:14:27.279 one microscope anymore. We're trying to assign dozens of professors 284 00:14:27.279 --> 00:14:31.519 to dozens of courses based on their specific overlapping qualifications. 285 00:14:31.600 --> 00:14:33.840 And for this you need a technique called network flow. 286 00:14:34.519 --> 00:14:37.919 The mechanism treats the connections between professors and classes like 287 00:14:38.000 --> 00:14:41.879 water pipes. You push water, which represents the assignments through 288 00:14:41.919 --> 00:14:43.919 the pipes from the professors to the classes. 289 00:14:44.000 --> 00:14:47.240 Okay, I can visualize that the magic of this algorithm 290 00:14:47.600 --> 00:14:50.200 is that if you hit a bottleneck, say you assign 291 00:14:50.279 --> 00:14:53.840 Professor X to calculus, but later realize Professor Y can 292 00:14:53.879 --> 00:14:58.080 only teach calculus, the algorithm can actively push water backward. 293 00:14:58.519 --> 00:15:01.720 It unassigns Professor X, re ruts them to algebra, and 294 00:15:01.759 --> 00:15:04.840 opens up the calculus capacity. For a professor y. It 295 00:15:04.919 --> 00:15:07.840 systematically builds and reroutes the optimal flow. 296 00:15:07.759 --> 00:15:10.759 That is genuinely brilliant. But this is where the staircase 297 00:15:10.799 --> 00:15:15.279 gets incredibly steep. Step four is called independence set, and 298 00:15:15.360 --> 00:15:17.480 I like to think of this as the dinner party. 299 00:15:17.200 --> 00:15:19.200 Problem, a very stressful dinner party. 300 00:15:19.240 --> 00:15:22.279 Extremely you want to invite as many friends as possible 301 00:15:22.320 --> 00:15:25.320 to a dinner party, but certain pairs of friends absolutely 302 00:15:25.399 --> 00:15:28.240 despise each other. You map this out by drawing a 303 00:15:28.240 --> 00:15:30.799 graph where your friends are dots and their conflicts are 304 00:15:30.840 --> 00:15:34.000 lines connecting them. You need to find the largest possible 305 00:15:34.000 --> 00:15:36.679 group of dots with absolutely no lines between them. 306 00:15:36.960 --> 00:15:41.039 This problem introduces a massive paradigm shift. Independent set belongs 307 00:15:41.039 --> 00:15:44.240 to a class of problems called NP complete. There is 308 00:15:44.320 --> 00:15:47.559 no known efficient algorithm for it. No greedy rule, no 309 00:15:47.679 --> 00:15:49.320 dynamic table, no flowing water. 310 00:15:49.440 --> 00:15:50.639 None of the tricks work. 311 00:15:50.559 --> 00:15:52.919 None of them. If you want to find the absolute 312 00:15:53.000 --> 00:15:56.559 largest complict free dinner party, you basically have to use 313 00:15:56.600 --> 00:16:01.799 brute force search, meticulously checking every possible combination of guests. 314 00:16:02.399 --> 00:16:04.919 Finding the answer is agonizingly hard. 315 00:16:05.159 --> 00:16:08.159 Okay, if it's so incredibly difficult to solve, why is 316 00:16:08.159 --> 00:16:11.240 it such a famous milestone in computer science. 317 00:16:10.960 --> 00:16:14.399 Because of a fascinating asymmetry. Finding the answer is practically 318 00:16:14.399 --> 00:16:17.320 impossible as the group gets larger, but checking the answer 319 00:16:17.399 --> 00:16:19.720 is trivially easy. What do you mean if I hand 320 00:16:19.759 --> 00:16:21.879 you a list of a hundred friends and claim here 321 00:16:22.000 --> 00:16:24.919 is a massive conflict free dinner party. You can just 322 00:16:25.000 --> 00:16:27.440 check that specific list against your conflict graph in a 323 00:16:27.440 --> 00:16:31.559 matter of seconds. NP complete problems are defined by this asymmetry. 324 00:16:31.799 --> 00:16:34.600 Finding the solution is a nightmare, but verifying a proposed 325 00:16:34.600 --> 00:16:36.519 solution is incredibly fast. 326 00:16:36.399 --> 00:16:38.720 Which brings us to the terrifying top of the staircase. 327 00:16:39.200 --> 00:16:40.720 Competitive facility location. 328 00:16:40.960 --> 00:16:41.879 This one is intense. 329 00:16:42.240 --> 00:16:46.240 Imagine two giant coffee chains, right, Let's call them Java 330 00:16:46.240 --> 00:16:49.039 Planet and quek Wakes Coffee. They're locked in a turf 331 00:16:49.039 --> 00:16:52.559 war taking turns opening cafes in a city, but local 332 00:16:52.639 --> 00:16:56.480 zoning laws state no two cafes can be adjacent. Java 333 00:16:56.519 --> 00:17:00.519 Planet opens a store, then Quekwigs, then Java Planet. Strategic 334 00:17:00.600 --> 00:17:04.720 board game, the question is does the second player have 335 00:17:04.799 --> 00:17:09.640 a mathematically guaranteed winning strategy to hit a specific revenue target. 336 00:17:09.799 --> 00:17:13.559 This problem is categorized as pspace complete. This is a 337 00:17:13.599 --> 00:17:16.960 whole different universe of difficulty. It is not just hard 338 00:17:17.000 --> 00:17:20.799 to solve. It is practically impossible to even check the answer. 339 00:17:20.519 --> 00:17:23.079 Because there's no single list of friends to verify. Like 340 00:17:23.119 --> 00:17:25.359 if you hand me the answer and say yes, quekwigs 341 00:17:25.400 --> 00:17:27.960 has a winning strategy, I can't just quickly check a graph. 342 00:17:27.960 --> 00:17:30.119 I basically have to argue with you exactly. I have 343 00:17:30.119 --> 00:17:31.920 to say, okay, but what if Java Planet opens on 344 00:17:31.920 --> 00:17:33.640 fifth Street? Then what do you do? Okay, but what 345 00:17:33.680 --> 00:17:35.759 if they open on sixth Street? Instead? I have to 346 00:17:35.799 --> 00:17:40.240 analyze a vast, endlessly branching game board of alternating future moves. 347 00:17:40.440 --> 00:17:44.799 The gulf between NP complete and P space complete is profound. 348 00:17:45.519 --> 00:17:50.000 NP is about finding a single static configuration. Psbas is 349 00:17:50.039 --> 00:17:54.000 about planning, game playing, and navigating a massive tree of 350 00:17:54.079 --> 00:17:55.160 hypothetical futures. 351 00:17:55.319 --> 00:17:58.400 Wow. Okay, so we keep throwing around the word efficient. 352 00:17:59.000 --> 00:18:02.119 We say stable matching is efficient, but finding the optimal 353 00:18:02.119 --> 00:18:04.799 dinner party is not. Since some of these problems are 354 00:18:04.839 --> 00:18:08.440 so wildly difficult, how do computer scientists actually draw the line, 355 00:18:08.480 --> 00:18:11.880 Like why not just use massive warehouse sized supercomputers to 356 00:18:11.920 --> 00:18:14.920 brute force check every possibility for the dinner party? 357 00:18:15.039 --> 00:18:16.559 To answer that, you really have to look at the 358 00:18:16.640 --> 00:18:20.279 terrifying numbers behind brute force algorithms. Let's look at an 359 00:18:20.279 --> 00:18:23.640 algorithm that takes n factorial steps to check every combination, 360 00:18:24.079 --> 00:18:28.079 and let's ground this in reality. Imagine your GPS app 361 00:18:28.079 --> 00:18:30.920 trying to find the fastest route home by literally checking 362 00:18:31.000 --> 00:18:33.680 every single combination of streets. Okay, let's say they're only 363 00:18:33.720 --> 00:18:36.359 thirty street segments to choose from, just thirty items. 364 00:18:36.400 --> 00:18:38.720 Well, thirty items doesn't sound too bad, and my phone 365 00:18:38.759 --> 00:18:41.480 has a really powerful processor. Let's say it can perform 366 00:18:41.519 --> 00:18:44.720 a million high level instructions every single second. That should 367 00:18:44.720 --> 00:18:47.440 burn through thirty items instantly, right. 368 00:18:46.960 --> 00:18:50.240 You'd think. But to check every combination of those thirty 369 00:18:50.279 --> 00:18:54.200 street segments using a brute force factorial algorithm, your phone's 370 00:18:54.240 --> 00:18:56.720 processor would take ten to the twenty fifth years to 371 00:18:56.759 --> 00:18:57.559 give you the route. 372 00:18:57.599 --> 00:18:59.960 Ten to the twenty fifth years. Wait, our entire universe 373 00:19:00.119 --> 00:19:02.559 is only about thirteen point eight billion years old. It 374 00:19:02.559 --> 00:19:05.160 hasn't even been around for ten to the tenth years exactly. 375 00:19:05.559 --> 00:19:08.359 My phone would be calculating that route until the stars 376 00:19:08.480 --> 00:19:09.640 literally burn out. 377 00:19:09.799 --> 00:19:12.160 That is the brute force trap. It does not matter 378 00:19:12.200 --> 00:19:15.880 how fast your hardware is, exponential growth will always always 379 00:19:15.880 --> 00:19:19.240 outrun it. This is why computer scientists define an efficient 380 00:19:19.319 --> 00:19:23.240 algorithm strictly is one that runs in polynomial time. We 381 00:19:23.279 --> 00:19:25.759 write this as big O of N to the power 382 00:19:25.799 --> 00:19:28.599 of D, where n is the input size and D 383 00:19:28.880 --> 00:19:29.920 is a constant power. 384 00:19:30.359 --> 00:19:31.759 So it scales gracefully. 385 00:19:31.960 --> 00:19:34.599 Right, If you double the number of streets on your GPS, 386 00:19:34.839 --> 00:19:36.799 the time it takes to find their route only slows 387 00:19:36.839 --> 00:19:40.240 down by a predictable constant factor, not a universe ending 388 00:19:40.279 --> 00:19:41.200 exponential one. 389 00:19:41.319 --> 00:19:44.319 I like to visualize this concept of asymptotic order of 390 00:19:44.359 --> 00:19:49.079 growth what computer scientists call big O notation, like looking 391 00:19:49.079 --> 00:19:51.759 out the window of an airplane flying high over a forest. 392 00:19:51.759 --> 00:19:52.960 Oh, that's a great way to put it. 393 00:19:53.160 --> 00:19:55.640 Yeah, when you look down from thirty thousand feet, you 394 00:19:55.680 --> 00:19:57.759 do not care about the exact number of leaves on 395 00:19:57.799 --> 00:20:00.359 a specific oak tree. You don't care if the highly 396 00:20:00.400 --> 00:20:03.480 specific mathematical function of an algorithm's running time is like 397 00:20:04.000 --> 00:20:06.519 one point six to two n squared plus three point 398 00:20:06.519 --> 00:20:09.519 five n plus eight. Right, the details fade away exactly. 399 00:20:09.559 --> 00:20:11.559 You just care about the sweeping shape of the forest. 400 00:20:11.880 --> 00:20:15.839 The end squared bi go notation strips away the hardware quirks, 401 00:20:15.880 --> 00:20:19.519