Transcription
Yeah. Um, okay. Hi everyone. Uh, we're gonna get started. This is going to be the last theory seminar of the semester. Um, I'm very excited today to introduce Rico. Rico is a good friend and was my postdoc host. Um, he is currently, uh, he's currently a professor in the department of mathematics at ETH Zurich. He previously held a position—Oh, see how good I can get on your history—He previously held a position in the department of applied math and statistics at Johns Hopkins. Um, two, and he has a PhD also from ETH Zurich, and he did postdocs at both a short one at EPFL and a longer one with Michelle Goemans at MIT, um, where he is right now on sabbatical. Um, I guess yeah, Rico holds the unusual distinction of being somebody that's done a lot of foundational work in theory and in particular in combinatorial optimization and network design and approximation algorithms. But he also has, like, uh, his foot strongly in the industry door and does a lot of more sort of like practical projects applying techniques from optimization and combinatorial optimization. I guess he's like the reason that Swiss trains run quickly. I'm told that's too much, Ellis, but thank you. That was probably true before we—um—and yeah, with that I'll let Rico get started.
Yeah, thanks Ellis. Thanks a lot, and yeah, thanks for being here. It's a pleasure to be here. So, um, let me talk about the—I would like to talk about the matrix secretary problem, that's—and the specific model thereof, but actually this talk it has two goals. In a one, is to talk about that specific model, but more importantly, I want to introduce you to the secretary problems and specifically the matrix secretary problem, to some challenges that we have there, and to give you a better global understanding of it and then actually show the specific model. There'll be a link to that, so it's less about uh, just that model, and that's joint work with Richard Santiago and Ivan 30th. And let me just start, and if you have questions, just just interrupt me. I think it's easiest to—
So what is the secretary problem? It's a it's a film that um, got quite popular in the 20th century, in the middle of the 20—in the 60s or 70s roughly—and uh, it's basic form is as follows. You have—you want to hire—and let me just stay in the terminology of the times—you want to hire a secretary, and you're going to—you interview a certain number of candidates. So say n candidates here, and they will be interviewed in uniformly random order. And the way it works is you want to hire a single one. When you hire—when you interview one of them, you will see how how strong that candidate is. And this will be revealed by what I call a weight. The higher the weight, the better. Now, the game is the following. You have to decide immediately, irrevocably, whether to hire that one or not. Of course, having seen the first—maybe not a good idea to hire that one. We have absolutely no idea what the weights are. So, we keep watching a little bit. Let's say number five. I mean, the only weight five probably also—we don't want to hire that one too. We keep going. Maybe at some point here we have a candidate with weight 11. We maybe say, okay, let's hire that one. Of course, you would have preferred to hire the one with weight 14, but that one passed, and as I said, decisions are irrevocable. So if you did not hire at that point, we cannot hire uh, in hindsight. Mhm. So far so good. Does the model make sense? So important is that—so the weights, they they're just hidden, but they're there, right? And so an adversary can—if you do a worst-case analysis—can choose those weights, but has to choose them up front, and then candidates are interviewed in random order. Random order is very important because it allows you to learn, right? By observing a constant fraction, you get an idea of the weights. If the order were like adversarial, it would be essentially impossible to learn, and an adversary could show you first weights that don't make any sense, and you would know nothing about what's happening later on. Okay, good. Oh, maybe let me start with the first observation. It's not so hard to find a strategy to hire the best secretary with constant probability. Let me give you a very easy strategy that does that. Let's do the follow—and and this reveals a general—a general theme in how people design algorithms in that context. Let's first do the following. Let's observe 50% of the of the candidates without doing anything. You don't even try to hire. It's just trying to learn. And then in the second phase—in the second 50%—let's try to hire the first one that is better than the best one you've seen so far. Okay. So you can imagine what happens is if you have the um, the second-best candidate—maybe I should just write things—say the second best one is here, and the first one—the best candidate—happens to be in the second half. Whenever this happens, you're going to hire the best one, right? Wrote it also again here. So this happens at least with probability of order—and it turns out that you can do—you can actually—this actually—the best strategy—but not by observing 50% first, but by observing a one over E fraction, and this is called Dinkelbach's algorithm and will lead to—so one over E fraction—this will lead to um, to hiring the best candidate with probability one over E. So maybe it's not so surprising—that's really a stopping time problem, right? I reveal random variables to you, and you have to stop at some point. That's why people at the beginning who studied that were mostly probabilists working on stopping times. Now, but then you have—one could say that the field was somewhat bit more quiet for a few decades, but later on people got more excited about it again, uh, but in variations of the problem where you can hire more than one secretary, and the problem—and the reason is that this is a lot of interesting links into mechanism design. Let me give you just one model that will—will be actually a special case of what I later introduce as the matrix secretary problem.
So here you see a network with a single—let's call it a server or a source—a single server, and we have different clients. The network has edge capacities, and let's assume that we want to—let me just uh, make up a story to explain the the setting here. Let's assume that we we're selling a service to our clients, and the service we sell is a is a unit connection to the server. So this will just be a single path. Let me do maybe do an example here. So I can serve that that one here, for example. Let me do something um, maybe slightly weird. Um, let's do it this way. I could serve that client that way with a with a unit path. This is a net—I can use three times with my path. But here the capacity is reached. I cannot use this edge anymore. So now I would have served that client. I could also serve this one as well, even both of them if I want to do so. Now I have to reroute the blue one, but that'll be okay, so I'm not—I don't really care how we serve them—I just have to make sure whenever whenever I accept two clients and tell them, oh, I can serve you—that there exists to path—to unit path from the source or the server to the clients—not exceeding the capacities—so don't think too much about the routing—important that the routing exists—and so now you can imagine that I will interview—or actually I will—I will talk to the clients in some random order and learn how much they're willing to pay, and I have to either accept or decline whether I want to serve them—so it's it's like the secretary problem from before, right? The only difference is that um, I can pick more than one under some constraints, and the network gives the constraints—doesn't make sense? Yeah, perfect. And of course, you can model the the problem from before this way, right? You could just have a server—a single edge of unit capacity—and all the clients being here, and then I have the problem you just saw right before. So it's a special case of this one.
So now what is this matrix secretary problem? And uh, I know some people get scared when they hear about matrices. So let me try to to lower that that shock a little bit. I'll actually mostly talk about one example of a matrix and explain everything using that example. But—but all whatever I do will work for any matroid. So let's still just try to understand what is a matrix—or maybe first try to maybe explain what is the matrix secretary problem, and then I explain to you what a matroid is. So here we—we can select—it's a again a secretary problem—we can select—with a ground set M—we want to select subsets—a subset thereof—the number of secretaries of that ground set before—and this used to be the the green little dudes I had everywhere, right?—and of total weight as high as possible. They reveal weights over time as as before; however, the set I'm selecting has to be an independent set in a matroid. So the matroid is just a constraint—before it was—oh, clients I can actually connect from the server with unit path without exceeding the capacities, right? This is the constraint here; it's a matroid now. Back to what is a matroid. A matroid. Now, depending where you talk to people in math or computer science, they may first say a matroid is a generalization of linear independence, or they may say a matroid is a generalization of forests. But let me just explain first the rules. So you have a finite ground set, and you have a—you subset there—I mean a family of subsets thereof. Think of those as the feasible sets—the ones you can pick. Right? So this family needs to fulfill two properties—to be a matroid—I mean strictly speaking actually three—it has to be non-empty—and this—to fulfill two more properties. One is that if something is feasible—for people in the matroid language like to call those sets independent—so if something is independent, any subset thereof is independent or feasible as well—makes sense beforehand, right? If I can serve a certain number of clients, I can also serve any subset thereof. It's good. If I have two sets that are feasible, and one is strictly bigger than the other one, then I can find an element in the in the bigger one that I can add to the smaller one and still have a bigger feasible set. So let me just do the two links from before—and that I mentioned before—the math and computer science kind of link. One is imagine that—maybe I can just write this on the on the slide—that's probably more uh, more helpful. Imagine that your set N is a set of vectors—let's say v1, v2 and so on—finite set of vectors—the subset in order—say to the n—and think of of I as being all the subsets thereof—where—of linearly independent vectors. Okay. So let's just check—they fulfill those properties here. They they form a matroid because it's a it's a non-empty family. It's always non-empty because it contains the empty set. By the way, it's also a candidate, right? Indeed, if you have a set of vectors that are linearly independent, you take a subset thereof, they're also linearly independent, and you have the—so-called augmentation property—of in linear algebra—where if you have two sets, subsets of vectors that are linearly independent, and one has more vectors in there than the other one. So, it spans a larger space, right? So, you can find a vector from the larger space, you can add to the smaller set of vectors and still get linearly independent vectors. It's one example. And the other one is that I would like to highlight—and I want to fix the other one for in what follows because we're here in computer science. So it's forests. Pick any graph and declare N to be the the edges of your graph, and I to be all the forests of your graph. Indeed, any subset of a forest is a forest. And also if I give you two forests, one with more edges than the other one, then you can always find an edge of the bigger one, you can add to the smaller one and still get a bigger forest. One way to see this is if you have more edges here in your forest, you have fewer connected components than you have in this forest. This means at least one of the edges over here will connect to different connected components over here. Just add that one, and you have a bigger forest. And that's the only slide where I torture you a little bit with matroid slang. And uh, and I hope you can then—I'm happy to to repeat things if anything is unclear later on. So—so again it's the it's the example of a graphic matroid. Here's a graph, and as I said, the ground set are the edges—independent sets are forests—and now I'd like to introduce what's the rank of a set. Let's pick any subset of the of the edges S—the red ones here—just an arbitrary subset. It's not a forest. It's not even connected also. So it's a it's a general subset. Then the rank of S is the largest forest you can find within that—the size of a largest forest you can find within the red. So here I can find a forest—the largest one is—let me pick one—largest one is this many—that's the largest forest I can find within the red edges. Um, it has—let's let's try to count that—it has 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 edges. So the rank of the red set—rank of S—is 10. What's the span? The span of that red set are all the edges that have both endpoints in the same connected component. What it means is if you add those, the rank is not going to change. Right? That's the way it's defined for a general matroid. Uh, the span is all the edges. If you add them, the rank is not going to change. Okay? Or think of—in this—in a graphic matroid—both endpoints in the same connected component. And what's a basis? A basis of your of your matroid is a largest set that's independent—in connected graphs. Those will be spanning trees. Okay.
So now—so what is now the—let's just look at an example of the matrix secretary problem for the graphic matroid. So you will see—is you will just see edges popping. Maybe this one is way nine. You have to decide—do I pick it? Yes or no? And you have to pick a forest. Let's pick it. Say red means I pick three. Let's not pick that one. Let's pick seven. I keep going. This one I cannot pick anymore. It will create a cycle, right? I have to pick a forest. And that's it. Let's say it's the end of the procedure. And of course, what I want to um, what I want to do is I would like to to find an algorithm that returns an expected weight as large as possible. And we will measure the quality of the algorithm in terms of its competitive ratio, meaning the expected weight of the algorithm we use divided by the max weight independence set—here the max weight spanning tree in that graph—so let me give you a procedure—it's a procedure by Krule and Paul—for getting a constant competitive—it's a constant competitive procedure for the matroid secretary problem—graphic matroid—and I think it's a beautiful procedure—it's a very elegant procedure—that's why it's nice to to get to warm up—it's a good one to to look at—meaning—let's say this is your graph, and you know the edges of that graph get revealed. You have no idea what the weights are. What you can do is just choose an arbitrary numbering of the vertices. Let's pick that one. Now look at two different orientations of the graph, and one of them—I directed all the edges from higher to lower labels—and then the other one—the other way around. So those graphs will naturally be acyclic. Make sense? And what you see here in this red arcs I show here, those are just all the arcs that are entering a certain vertex. Let's do a quick observation. What I could do is I could say—let's just focus on this left-hand side graph for time being—on this orientation. I could say—let's just pick for each vertex at the most one of the incoming arcs. It's not the problem I have to solve. I have to find a forest—of big forest, right?—but if I do so—that's just two observations I want to—I want to make about that—one is—if you have one incoming arc per vertex here, then that's definitely a forest—okay—so I'm restricting—I'm restricting myself—but any output I give here will actually be a a solution to the original problem—but now if I—what—what can I do if I say—I mean what is a natural strategy if I say, oh, I pick at most one of each of the of the of the red arcs here—I just run the classical Dinkelbach secretary algorithm on each of those bundles, right? So just just run it in parallel—for each vertex you have one algorithm running—whenever an an edge appears—or now would be an arc—it's a directed edge—I just look—oh, where is it—is it incoming or—incoming here—it's vertex 5—then I feed this into Dinkelbach for vertex 5—so Dinkelbach will guarantee—I'll actually get among those arcs the highest weight one with constant probability—remember one over E probability—but doesn't really matter—the constants don't matter that much—I just care about getting a constant for time being. So that sounds good. Now the question is—is this a good procedure? Of course, right? So far it's good. It's a procedure that will return a forest and to certain guarantees, but we don't know yet. But it's a good procedure. So it turns out this is not going to work out so easily that way. But what we're going to do is we'll actually—for probability 50%—run the algorithm on this graph and the probability 50% run it on that graph. And the idea is that—I think I have a line about that. The idea is that—no matter—think about any spanning tree—about the optimal spanning tree in the in the graph that you want to—so it's the max weight spanning tree that I'm drawing here. Let me—so I don't—you don't see the weights. I didn't didn't add weights here. I just want to make sure—I don't want to overload the picture—and let's make sure I I do something somewhat interesting. Let's say—let's say this is a max spanning tree. So let's—I have to compare against that spanning tree—my solution. What I can do is I can just—for analysis purposes—I can root it anywhere. Let's root it here. It works—number one—but it doesn't matter where you root it—and just direct everything away from the root. So that's the way it will look like. Now each of those arcs will be either here or there in one of the two graphs, right? Because every arc is directed both ways. Ones it's directed one way here and then the other way over here. Let's just look where they are in those graphs. So the the one from—sorry—from 1 to 4 is in this graph. Then we have 4 to 5. I hope it took something that—yeah—I have a little mix of things. 7 to 8 is here. And then 5 to 3 is over here. 5 to 2 is here. And we have uh, oh—8 to 6. I guess I forgot that one. Let's see. 1, 2, 3, 4, 5, 6, 7. Um, that looks good. But now remember—in—if I run my procedure here—I will get the heaviest arc among the incoming ones at constant probability for each of those vertices—even for the other ones—but for each of those. So this will—what I get here will compare against the weight of the green edges—the same over there—because if I mix 50/50%, I will actually get a constant factor. I lose a factor of two because I have to pick one of the two, and then I lose the Dinkelbach factor. So this is a one over 2e competitive procedure. I think it's beautiful. Oh, please.
Yes. Yeah. 421, 41. Exactly. It's a good point. So here, exactly. One—one could improve the analysis here, right? And say—actually—also—also for that edge—the one—the 14 uh, edge over there—I also would—would get it here with constant probability. My question is why? Yes. What could happen is that that maybe—so here it works nicely, but there could be another green edge that also links to one—and have to make sure that you're—you're not only allowed to pick one of them—and—and if you have more incoming here, then yeah, you may lose—it could be even potentially even a super constant number of of edges that are green and and the incident—want to have this with—yeah—maybe with with five, right? And here could not say that you can uh, uh, yeah, it would have an issue if you if you don't uh, do the analysis the way I did it. Yeah, that—that's the reason—it's a very good question. Thanks a lot for the question. Yeah. Oh, yes, Alex, please. Is it not the case that every vertex has a constant probability of getting its edge, in which case you're actually competitive of the constants with just like the largest? That's true. Excellent. Yeah, exactly. One can think of it that way. So essentially we're constant competitive against the harder objective and the one where every vertex gets the largest weight edge. Yeah, that's true. Yeah, good point. Very good point. Um, yeah, sure, sure. So in the original problem—it's—it's not really a weight—I guess you define a weight—I don't know if one is tight for the weighted version. It's also tight for the weighted one. It's a good question. So in the original problem, I just said, oh, what's the probability to pick the highest weight one. I didn't really care about—maybe I should have emphasized this better—I didn't really care about what the actual weight is. I just want to get the highest weight one. But then—but it turns out—it's also—here you want to get—you want to maximize the weight. Exactly. And uh, and it turns out also for the single secretary problem—one over E is the is optimal even for maximizing the weight. Yeah. And I assume eventually—are we getting to the—because you gave a great example of serving users, and yeah, one of the two major conditions for for that is—is that a matroid—oh, sorry—the one—oh, I should—oh, thanks—thanks so much for the question. So it turns out the um, the the server example I gave you—that's also a matroid. So the subsets of of of green clients you can pick—that that you can simultaneously serve—that's the family of independent sets of a matroid. Yeah, that's—that's called—to see that—that's called a gammoid. Yeah, it's—it's not easy—now you mean easy. I'm not sure—it's—it's um—imagine—let's let's check. So this like—so as I said—one property is easy, right? The one—um—I only verified just one—I think—if the easier one—I kind of—yeah—the other one under the rock. Exactly. Exactly. The other one is what I have to show is if you have um, two sets of clients you can simultaneously serve—one is bigger—one—say three up here—only two here—then what you can do is—so you can think—think of having a current flow that will actually serve—I mean serve these two clients—and now apply the—Phil said—apply the max flow algorithm—it will find an augmenting path—it has to be able to find one because there's an option to get three clients, right?—and the max flow algorithm will always in augment if it can—but what is another property of max flow is that it will actually not—anyone you serve now—you will still serve later after you augment along an augmenting path—and—and this shows the augmentation property—you need to know that—that property of augmenting—but thanks a lot for your question—that was just a gap in what I said before—perfect—so far so good—so what's the big conjecture—what people would like to prove is—they want to show—I mean people want to show that there's actually—there's a constant competitive procedure—sorry
Constant competitive procedure for any matrix for the matrix secretary problem. And this is wide open, and most experts believe that's true. The best it's known is a log rank procedure; log rank of the matrix. Um, so what else has been has been found? There's been quite some—I mean, massive—pro regime on restricted graph classes. I showed you the graphic matrix; there's many more where people know how to get constant comparative procedures. This includes like so-called laminar transversal regular matrix, max-flow matrix, and so on. We don't need to go into those details.
There's one more thing. There's certain different models where um, where actually constant competitive procedures have been found. Namely, for the free order model and the so-called random assignment model. The free order model means that you can choose which one is the next secretary that gets revealed, not knowing its weight, of course. And I will talk about random assignment in a moment. So let me skip that for a time being.
So what I would—having made the transition from at some point approximation algorithms to approximation schemes—what I would say is, under what restricted classes can yield better than order one, maybe a maybe a one plus epsilon? Very good point. We'll address that later. Yeah. So there's um, this has been studied for um, for picking k secretaries out of n. So, so it's kind of the easiest constraint for picking more than one secretary. And there you can get that you can get uh factors that improve it with increasing K. That's uh, it's not too hard to see. The question is what is the best dependence on K you can get.
Yeah. For other ones, it's um, for most of them, most of them include the um, the single secretary problem is a special case, or many of them include that. I guess I mean there's a one over e lower bound.
Yes. Yes. That's true. And it's probably for a very restricted class of matroids. It's already for the
Yeah, exactly. It's already for choosing a single secretary.
Yeah. So every matrix that that's that that generalizes that inherits that hardness.
Yeah. Okay. Yeah. It's kind of annoying.
Mhm. Kind.
Yeah. It's the reality.
Yeah. It's reality. We have to live with the reality, I guess.
Yeah. So um, but what's what's interesting, the aspect I want to highlight in this talk is all of these results; they heavily rely on this on on the following fact that you know the full matrix up front. Meaning I give you the ground set. I tell you what's already independent sets thereof. Remember the algorithm of of Poll and Kura? I showed to you this extremely nice procedure. I mean, I just said, oh, let's pick an arbitrary labeling of the vertices and then start orienting one or the other way, but I mean you can only do that if you actually know the graph, right? And that's that's a bit of a of a strange feature because for I mean this algorithm here, for example, the algorithms over here they don't need that. And now you may you may wonder, so why is that? Why is that the case? The thing is that there's a general belief—maybe should call it a belief or or just it feels weird—that knowing the matrix would help you for the general matrix secretary problem.
Why is it weird? Because let's assume I give you—so so assume you know the matrix for the general matrix secretary problem. Then what I could do is I could I could have my own matrix that I think is hard. I want to feed to your algorithm, but then I embed it in a much bigger matrix with a lot of of elements that, for example, have zero weight. So you have no impact, and you will learn a little—about knowing the matrix will probably give you a little information about the matrix I was I was hiding. It's it's not that's not a really formal argument because you can observe 50%, try to learn where it hides, but but somehow in a general—what I want to say is—in a general matrix it's much easier to hide stuff than in a specific matrix. In a graphic matrix, you can also say we can also hide a graph. I just always give it a complete graph, right, and hide things, but there's not that much you can hide. For example, the the Kruskal procedure from before still works no matter what you hide in there. It does it doesn't care whether you hide something bigger in a in a complete smaller in in a complete graph.
So I think I—you're thinking of an oracle model of access to the mat.
Yeah. Yes. Exactly. What would be the model? Yeah. What would be the model if you don't know it? I mean, so it's possible that to prove a potentially there's a lower bound, right? Uh, on is there is there a lower bound on queries? The oh, I see the number of—there's a lower bound on the competitive ratio. The best lower bound we know is still a one over e, even for a single secondary problem, so it's a same uh, okay. I guess I guess there would be the question would be a lower bound on the number of queries uh to achieve a given—oh, I see—I don't know of any such lower bound. It's a good question. Yeah, not sure about that. Yeah, I mean there must be some there must be a trade-off, right? The question is where does it lie? Yeah, I don't know where where it lies.
Yeah, I mean so far all those procedures that can be made in polynomial time. So I mean, of course there's those two questions, right? You can say—I mean, to some extent it's a stopping time problem. It's a purely um information theoretic question to some extent, right? How much can you get out of the information you gather? You could ask a question that way. Not even think about how many queries you you you make or or how much computational power you need, right? And and then you can of course also restrict the model and say, oh, actually I want to be polynomial time, and then you can restrict it even more and try to understand the trade-off between how many queries I need to get something. So so far I mean all of that is open. There's a general belief that probably you can do it at least polynomial time if you can do it if you can get a one that we—yeah, well, I don't know if you want to say anything about this uh, I mean I I'm I'm feel like I've been given permission to ask this question by Elsa's introduction uh point of view. I mean, other than this is maybe a beautiful conjecture.
Um, can you say anything about why we would care about such an abstract problem as all matroids?
Yeah, it's a good question indeed. I think it's just it's a nice abstraction that captures a lot of natural settings, but it's not—I mean, it's matrix is typically that you want to get a result for matroids, and then you want to apply it for special cases. That's normally the way it goes. It's not that that you don't you don't see a real-life general matroid. Uh, that that seems—that seems you're in a math department, so it's okay. But yeah, we see that in real life in the math department. I meant but I meant, you know, is is do do we do we think there'll be nice things that we'll learn from understanding this, you know, maybe we'll we'll—yeah, it's a medical question, I think. Exactly. I think what you can try to learn—I think that's that's a key question also we need to to think about that question, right? I think one of the main things you can learn is um that so most procedures work still like like Dinkin's procedure; they observe a constant fraction and then they take action. So I think the question is what can you learn—what can you learn from such a distrib—I mean from uh from seeing a random constant fraction of the elements—what kind of statistics can you can you make that will help you to to then make decisions based on those? And there's certain aspects you can learn also from a matrix. I will talk about that also also here about one thing you can learn. And I think the more we understand what we can learn, the more we can use that to maybe also in other settings to um, I mean, not sure whether it's really in practice, but at least in other settings to to apply that, Alice.
So I guess I I have a question about those questions, which is as far as number of like—I mean, I guess maybe rank or independence or model, but it seems to me like you need trivially at least linearly many—at least independence queries—just a partition matroid and like half of my elements or like say it's like a a two-partition matroid, half my elements can go to one, half my elements the other, the about zero elements or something like that, then anytime I see an element they need to decide whether I can actually like add it. Yes, and I need to decide between—fully agree. I think that that linear is a is a is a triple lower bound for getting any concept right because if you because you need at least before you pick an element you must check whether you preserve independence or you violate the—yeah, but it's a very—but but I fully agree with you, it's a good point. Yeah, so so even just to be able to to pick a linear number of elements you need to do linearly many queries. Super linear lower bound for queries case.
I don't think so. No.
Yeah. Yeah. I don't think so.
Yeah. You think that would be—I never really thought about it. So maybe—but it's it's a—
Yeah. Interesting. So let's talk a bit about um, so let me try to to go to one to one special model that already was was uh was mentioned at the very beginning of when people introduced the matrix secretary uh problem, namely this random assignment model that I also mentioned in the last slide and said we'll get back to it. So this moment is now. So how does that work? And so the adversary can still fix weights, but then the weights get assigned randomly to the elements. So let me let me give you an example. Let's look at our—and I said I will try to stick to graphic matrix. So here's our graph from before. So the adversary can fix an arbitrary graph. Let's say if it's a graphic matrix example, say that one. And now here we have eight edges. So the adversary will will define eight edge weights and only choose some distinct—but doesn't really make a big difference. Um, how many do I have now? I'm eight now. Good. And then what happens is those get assigned to the edges. But this process here—this is random, uniformly random. Okay. So the adversary is is weaker, right? Before you could choose weights, graph and and the assignment—that's a random assignment model. And what's interesting here is in that is on that model there people knew how to get this constant competitive procedure, but again they needed to know the matrix. And I will show you how—here you don't need to know the matrix—but I think again I think the main the the main message I want to convey or the main interesting part is not just the this model and the result, but there's a certain asp—But we can learn—going back essentially to Phil's question, right? So I want to show you without knowing the matrix how you can get constant competitive in that side.
Yes, please. Yes. Oh, very good point. So if you have um, if you if you pick a single secretary out of n secretaries, then there's no difference. Um, I mean it's a randomness in one of them—just just see randomly the weights. But uh, if you have another matrix like a like a graph—you have to pick a a forest—then there's a big difference because you cannot you cannot say—I mean you cannot decide on which—I mean certain—you cannot assign a certain weight to a particular edge, but it'll be randomly mixed. Yeah, that's a good point. Yeah, because there's a structural difference. The problem is in a single secondary problem all the elements are equivalent, right? In terms of of of the of what is feasible and what's not feasible. But that's not true for the for the other models. That makes a difference. Thanks for the question.
Okay, let me recap Zod's procedure. Zod is the one who got gave the first constant competitive procedure for that setting, but he had to know the matrix. Let's see about what he did, and let's just talk about let's just look at that example. Okay, let's assume I give you that graph and I tell you we on random assignment. What would you do? Where do you expect to have to find heavy edges? That's in a deep—exactly in a complete graph. Right. I mean it's just—I mean things get assigned randomly, uniform at random because there are way more edges in here. This is way more important that you're careful in that set here than outside. Right? So you kind of want to protect the dense area from the sparse area, right? You don't want—but what I mean with protect—I mean that what you don't want to do is you don't want to start picking edges outside here like this. If I pick these five edges, right, then actually these three vertices are already in the same connected components. So it can pick two edges less from the clique here. That's no good because the clique has so many edges. It's likely to have many of the heavy ones as well. So we don't want this to happen, right? And that's what Zod observed. You realize, okay, that's I have to I have to somehow shield the dense parts from the from the sparser parts. We want to protect denser parts. That's the message. How can we do that? And here he relied on a on a decomposition known in in matrix theory, but it's not it's not that complicated. It's just um, it's called the principal decomposition. And for this let's first just talk about let's just agree on what is density, right? Just to make sure we talk about the same thing when I say density. A density of a set—which a subset of the edges—is simply number of edges divided by the cardinality of the largest forest you can find in there. So if I pick a clique there, it's the density of that clique is number of edges. So let me try to do this live. Hope not embarrassing myself with eight vertices. So 8 * 7 divided by two is like 28 edges, right? And what is the um the largest force I can find in there? Have seven edges. So it has density four. That clique has density four. But you can define—you see that again the definition is for general matrix. It doesn't use anything about graphs. But you can just think of it that way.
Okay. So what's the decomposition? It does something very simple. It finds the densest subgraph first, then contracts it, finds again the densest subgraph and keeps going. Quick reminder: you can find dense subgraphs in polynomial time. K-dense subgraph is hard. If I tell you it has your densest subgraph needs to have k vertices, that's a very hard problem. But if I if I just want to find the densest subgraph, this can be find—this can be done efficiently. Finding the densest subgraph in a graph. In a graph. Well, in a matrix by the way. Okay. In a in a graph, you can do this with with with flow computations. In a matrix, it's uh you can do it with submodular minimization. That's a it's one of those classic optimization problems that can be solved in polynomial time, but it's it's it's non-trivial. You need to use separation oracle and ellipsoid type. There are other procedures now to minimize submodular functions. The first ones used the used ellipsoid—and yeah, this alternatives for that. Yeah, but the—again, one of those—maybe this links a bit to our discussion from before, Phil. So the the thing is that if I look at a general matrix then you need one of those heavy hammer things to do it, but for almost any special case there's much faster stuff you can do to actually get the—you're saying even for general matroids there's a there's a combinatorial algorithm.
Yes. Yes. You can use a combinatorial—some other function minimization procedure—to find the densest set.
Yeah. Exactly. So let's let's do it for this graph. So here I did it for you. So R1 is the is the densest set, then R2 and so forth. Let's just again think about that. So I said I will first find the densest one. I will contract it, and then the next densest one will be in the contracted graph, the light blue one. So—and I like to think of it as follows. So it consists of that graph, then because I contracted purple, I guess or violet. Yeah. So I get I get that graph here. Then I contract this, and the next one is green and so on and so forth. So what we're going to do is sort of—I mean, what what Zod then figured out is let's do the following, and now I will actually find—I will try to find a max weight forest in here, one in here, one in here independently for each graph—and actually if your first observation—and then you turn that—so what I wanted to do—again, first observation is if I pick a forest in each one of them—just look at the edges up there—that will be a forest up there—that's where—so that's good. Again, we're restricting ourselves—actually, one could think of it—we're restricting our problem to a to a more restricted matrix. So the the feasible sets are a subset of the ones we had before. But that's okay. That's one thing. Of course, the question is first, how do you solve those problems here? What did you win by actually going to those graphs? And even if you can solve them reasonably well, why is that good, right? Those are the two questions that remain. And and there we need one one main property, namely it turns out each of those graphs has a special property, and this is called being uniformly dense, and it's it's easy to state. It just means a graph is uniformly dense—let's look at this one here—if the densest subgraph therein is the full graph itself. And it's not hard to prove—if there were an even denser subgraph in here, you should have split that off first and then go to that one here—that's essentially the intuition behind it. This intuition really can be made formal quite quickly, but let me just let me just leave it at at the intuitive point here. So, and what is nice about uniformly dense graphs is here all the elements are kind of equally important. So, it's relatively easy to get a good matrix secretary procedure for such a graph. It behaves similar to to just having to pick K elements out of N. I mean, one has to think a bit more about it to be precise, but let's see.
Okay, so formally the key insights were—so we talked about that already. So it turns out for uniformly dense matrix—or here graphs—it's not so hard to get a constant comparative procedure. You still have to see whether that compares or what you get compares against the the best—the max weight spanning tree up here or max weight forest up here. And that's the first statement. One can also show that it turns out if you look at the expected optimum weights—with the sum of the expected of the of the max weight forest here plus here plus here—then that will be uh um that is the same as the uh the expected weight up here. So what what is—why why do we have an expectation? We have an expectation because the weights get assigned randomly to the edges. That's what we take the expectation over. Okay. So this just means okay, it's good, right? If you get constant comparative for each one of those because I return the union of them, so I get the sum of their of the profits, I will be constant competitive for the original problem. How am I doing with time? We'll skip some stuff, but that's okay. So here have a slide explaining why you can be—how it can be constant competitive on a uniformly dense matrix. Let me just give you an one quick. It's slightly different to what what Zod did, but doesn't doesn't really matter. It's just a slight—it's a variation. One could say essentially what you can do is you could just say if you have a clique, for example, you just look—what what do you say—28 edges, right? And I can pick seven of them. Essentially what you can do is you can batch the edges—say I will look at the first constantly many and try to pick the best one of those and then again and again and again. And of course I can only pick an edge if it doesn't create a cycle that I pick so far. And it turns out that is good enough; they will already give you a constant comparative procedure because things are assigned randomly. It's very unlikely that in the event that when first the heavy addresses will be spread among the buckets you make. So it's unlikely they're all in the same bucket, right? And second, it's unlikely that what you picked beforehand in in prior iterations will span precisely that heavy element that comes later. Essentially the two reasonings one has to make here. But let me skip this slide. I mean it's essentially a foolproof—almost foolproof—here I could go through, but let me skip that. It's it's not more than that. Yeah.
So now now let's go to um to trying not to use the the matrix. So it turns out that of course we cannot compute the principal decomposition. So this is this composition of densest, next densest, next densest. We cannot do that without knowing the the matrix or graph up front. And it's actually hard. So what would be nice is now we got back to the question what can you learn, right? What would be nice is if I gave you a match. If you could tell me it's pretty likely that one will be in the in the or in the green set, for example, in the third heaviest one. But this seems very hard to learn—at least I don't know how to how you could learn this. I still would like to use the same approach we saw at the very beginning for Dinkin's procedure. So I want to observe a constant fraction. So let's say 50%. The constant doesn't—I don't try to optimize constants here—and then try to see what I can learn and see how we use that. Right? So what can we learn from the first—from a random 50% of the elements? And what I suggest here is um we suggest that you try to learn—don't try to learn specific densities of of where specific edges lie—try to learn what we call the rank density curve. It is the following. Here's again the same graph from before. It's a graph that—so you look—it's it's a it's a plot—rank against density—where you look at the highest density and then you just draw a horizontal line for the rank it has. So the rank of that was uh seven, right? You can pick seven edges here—a forest of seven edges exists in that in a clique—so it should be seven, and then take the max dense set—so R2—the density seems to be two and a half—I didn't check, but just told it, right?—and then it's rank—so it's rank again—the rank in in in the graph—and you contract—contract the the purple part—so they would have one, two, three vertices—should have rank two, but this is two units, and so on and so forth. I want to learn that—just that curve—I don't want to learn specifics about which element lies in which part. I just want to learn the curve first. And so the way it's going to go is um we we showed two statements. First, it turns out that with the um that if you observe 50—a random 50%—that's the set S, right, up there—a random 50% of the elements—and this is just the graph restricted to those edges—so the matrix restricted to—so just look at the top graph, right?—and then you can—what you can do is you can look at the rank density curve for that graph—then it turns out that rank density curve is close to the one of the original graph. Let me be more precise what close means. Right? Of course you have a subgraph, so the density will be generally lower. Right? So it's definitely not—you will not find denser sets than what you had originally in the graph. This—so it has to lie below the other rank—the true rank density curve. And that's the same holds of course for the um for the
Compliment because that has the same distribution. I sample 50%. So what I don't see, and it's important to make statements about both, on one hand, because I mean what happens is I will run my procedure on this, and what's left. Right? So I have to make sure I learn something from here that I can use on what I have not seen so far. Right? That's important. So what I what we state here is that actually both of these rank density curves will be close to the original one. So they must be close to each other. So I can learn from here what I should do here. So what what does close mean? But what what do I mean by close? Um, so now I like to plot those rank density curves in in log scale because everything, the errors we have, are always constant factor errors, and then it's just like a constant a constant distance in the graph, right? It makes my life a bit easier. So it turns out that this is a a good chance um good probability, constant probability here, the rank density curve of of what you observed will be in in like a tube that goes a constant tube or a constant factor tube below the true rank density curve. So I may not be able to to understand what this density is or what the highest density is, but I get one that is a constant factor lower, C. And I may not get the true rank, but I will get one that's at least a constant factor lower than the true rank. There may be more steps as well. It doesn't need to have the same number of steps, right? This red curve can have more steps potentially, but um that's how it works.
And then once we have that, we can then we then we we learn that oh, BM, we also prove that oh, if we know actually an a good approximation of a density curve, then we can get a an constant comparative algorithm, and then you just have to combine: you first learn it, then you apply it on the on what you've not seen so far. About 10 more minutes, right? Get perfect, and uh this will lead to the result. Um, let's start with an instructive toy case. Um, um first, let's assume that the true rank density curve is well separated, meaning that the uh it steps are are large, so there's always constant factors here and here, so they don't have many small steps. The way we will then reduce to that case later is we just simplify: if you have a rank density curve that has many steps, it will simplify to to a coarser one. And let's assume for time being that we know actually the rank density curve of the matrix. So let's say let's just start with that problem. So we did the second part essentially: how do we get a good procedure if you know the rank density curve, and on top of that, I assume it is well structured. So that was a take a bit more. Yeah, it's a bit nicer assumption, but I actually have to show. So what you want to do is you want to learn a large fraction of each ring of this principal decomposition. Remember the different colors. And here we need um the notion of of the dens subset. Let me just do it on an example. You don't even need to read the whole part up there. Given, look at a at an instance of the graph here. For any subset of the edges, I will denote by DSH, let's say DS2, let's pick two for example, for H, that's the largest subgraph in black that contains two disjoint forests on the same vertex sets. Here it's essentially the largest two dense subgraph you can find in I just show you one thing. So this red set. So there's like orange and brown are each is a is a largest forest in the red set I picked. So two disjoint way, two dist of those, the disjoint largest forests, maybe even some extra edges that I, the dashed ones, I don't care about. I go back to the red set just to see it once more. So so DS2 is the largest subset of edges you can find. So that you can then you can in that in that subset of edges we can talk about the largest forest, and there are two of them that are disjoint. Okay. And with this problem, some other things and possibly some other things. Exactly. Yes. Exactly. Possibly some some more things. Exactly. Good.
So why is it useful? We show is that so essentially how should you think about that? Why why do we talk about that even so a random notion coming suddenly on a random slide. So the reason is that think of it as follows: with our original ma the original matrix, I would like to learn uh mean to I mean now so I would like to see only a 50% fraction of the original matrix first. Now what I want to do is having that 50% fraction, I want to I want to look at densities of what I have observed so far of the sampling phase, and this will be such sets essentially. I have a set s, and I look at what is what is the uh for for h equals 2 for example, what is the the largest two dense set, largest three dense set, and so on and so forth, essentially the dense sets of what I observe, that's why I define it that way. I just want to give the main ideas of what one can show here. So what one can show is one of the technical results and the that underlines the underlies the whole procedure. One can show that um if you have a matrix, let's so let's go back to what we actually want to what is what do we want to obtain. I want to be able to learn those steps. Remember so look at one step, maybe it's a big clique. If I see a constant fraction of a clique, right, it's pretty, let's say, 50%. It's likely that this is still a pretty dense set, right? The density should be in expectation is precisely half. The density I mean or or roughly half, depending whether I create more connected components, right? But you would expect to see a density of of about a half, right? So that sounds good. Now you could say, oh that's great. So it's easy to learn densities, right? If there's a density, you observe half of it, it will essentially be half dense, right? And there's a danger with the reasoning. The danger is that um I mean of course you will not not the full set will be half dense, only parts of it, there will be some less dense parts as well, and now what could happen that could a correlation could happen, namely the part the areas where you observed more elements that then look dense to you are those where there are fewer elements left to draw later on from, right? Remember that later on they have to have to draw elements, I mean they will see the remaining elements, and they want to pick the the remaining ones, but the worst that can happen to me is I have a one of the bad things can happen to me is I have for example the eight clique of our example in the sample. I see all of the eight clique, then I say oh let's protect all of it, that's great because there I found a dense set, but it helps nothing because there's no edge left to pick from, right? So somehow we have to prove a statement that says if you look at what you observe and there's a dense set in there that actually with high likelihoods there will be many elements that are spanned by that set, therefore if I protect the set I will actually protect a lot of stuff I can pick from later. That's what those statements say. It turns out that this these sets DSH have the property.
Turns out that the span what is spanned by such a set, if you for not what you have seen but among the remaining elements I I remove the sample set, is large or it's unlikely to be small, unlikely to be small. That's what that statement says. That's good. So it means if you observe a dense set, it's likely there's a lot of stuff you can pick within the span by that dense set. The second statement says oh also that d then set is likely to be large or unlikely to be small. I have a proof for that. I will not go through that proof, but essentially the toy case this would mean if you look at for example at um let's look at some density, say this density here, then there's a set that is has that rank actually of that density or higher, right? If some part is higher has in higher density, and then you have precisely that density here. So there's a set of that rank with that density. But this statement says oh actually if you now look at um think of this density, let's call this the density 3h, we use a factor of three here, 3h. If I look at a density that's factor of three lower, it's a log log graph. So a factor of three lower means it's it's just a constant below, say factor three, factor three, then actually you will see this set that that leads that is dense in the original matrix here will lead to a set that is dense for this density and still may not be not have that rank here but has a rank that's close to it, maybe up to here. So you will see something that looks like that may maybe it has some other some other steps up there, but but essentially on that segment you should be above; that's what the statement says. You can apply this to each of those corners, and this will give you um and you have to make sure you can use a union bound, but this works out because this channel of bound is extremely so bound you see here is very sharp, and you can show you can make sure you have concentration everywhere, and you will be close everywhere with with a good probability. I'll keep it short um so let me skip the proof for that; it's a I like the proof, but let's skip, and and then how do we go to the general case? Just one quick slide, how this can be generalized. So so let's try to put the pieces together here. So the way things work is we first observe a random 50% of all the the edges of our graph, right? Now quick reminder, the rank density curves, so rank RD of what you observed and what you did not observe again, they have the same distribution, what you observed because I observed 50%, they are good approximations of the one of the original matrix, so they are close to each other as well. That's what what I wrote here. The curve is the one that you observed is close to the one you did not, the one which you work on later on. That's good. Then what we do is so here we have now many steps. The reason from before, there I kind of like that steps are far apart, that things don't start to overlap, and I know that I can apply also get concentration by applying for only a few steps this turn of type results. Right? The problem would be also to get concentration here if you apply it to every little little kink here. Right? So what we then do is we then simplify the curve. We don't look at the actual curve but do as if the curve looks a bit different. This will lose a little factor, but it'll make make it have the shape essentially the shape you've seen before, one with the big steps. And then and then we just run the algorithm for the toy example. The toy example algorithm what it does is it just protects those um so it knows that if if we have a density here, so it tries to protect the densities that we observe in the in the sets s, essentially want to be a bit careful. I'm sweeping a few things under the rock, but essentially those are the ideas. Let me conclude. So I'm still just it's time. So the result is no one comparative procedure for uh the random assignment model without knowing the matrix. I think again the the model I think is is a nice model. It has been I mean it has been asked at the beginning. There have been papers on it later on. Um so it's nice to to solve I mean it was an open question. It was nice to solve that one. I think what's may probably more important is um densities is something we can we can learn reasonably well. So hopefully one can use that also for for the general conjecture. So up here it's maybe the from what I know it's the first well-known matrix secretary problem variant for which we now have an O1 procedure without knowing the matrix. But uh of course the big conjecture remains open. Now you may say so how can we use those facts for general the general matrix secretary problem because it's so different, right? Here used so heavily that rates get assigned randomly, how why should we even try to protect the dense area? It makes no sense because the adversary will choose the weights; there's no reason that the dense area is is useful, and indeed you should not apply it that way, but one what what one could for example do is and although this has been done in other procedures, you could observe a certain constant fraction, say um say a third for example, and then what you could do is you could say Now let's look at the max right spanning tree of what you observed. And now let's let's observe another third. But when I observe an element, if it does not improve on that spanning tree, I just ignore the element. Right? In anyway, it's not part of a max byite spanning tree. So people call the elements that do improve often improving elements. They could apply the result on just the improving elements for example. Right? So then I don't I don't suffer that adversary can of course completely fool me uh by just assigning the weights up front. But I'm not sure I mean it's not that easy to make it work. But just to give an idea of why I hope at least hopefully someone will be smart enough to see how to how to use that in a in a way as one of of many tools probably to resolve that conjecture, whether that will be the case. Uh I can't tell of course, but that's at least my hope. Okay. Thanks for your attention. Any questions? I'm happy. Yeah, there's also it turns out we have we also have a paper on that one. So one can um essentially for for most matrix we can uh for many if you can solve them separately we can also solve use soft intersection um under some certain properties that have to be fulfilled. Yeah, but it's Yeah, this certainly I mean but it's Yeah, exactly. But it's very little is um uh I mean yeah there's a lot to be explored there. This is a maybe just a first step. Yeah, thank you.