Our speaker today is Tim Ruffgaarden. Tim was a math major at Cornell. Then he got a PhD in computer science at Stanford, where he is today, associate professor of computer science at Stanford. He's gotten a lot of awards that are kind of name-checking a lot of pioneers. So he's got the Gertel Prize for his work on algorithmic game theory, the Kalei Prize, the Shapley Lectureship, the Tucker Prize, the Grace Murray Hopper Award, as well as also a Presidential Early Career Award. He's written a book on selfish routing and the price of anarchy, and he's got a book coming out soon, I guess, next month, next month being August, as I read, on 20 lectures on algorithmic game theory. So he's going to talk today about auctions and in particular about wireless auctions. So here he is. Oh, his greatest award, his finest achievement, his greatest accomplishment was he was a summer intern in K5-3 in 2001.  A great bunch of interns and a lot of the people at K5-3 were here then. Ron was here and Nimrod and many other people. So I learned a lot from them and so that's sort of, I haven't forgotten. So thanks for coming. Happy to be here. So over the past 15 years or so, a lot of computer scientists have started learning a lot about game theory and economics. And the original motivation was just to reason about the kinds of applications that were emerging early this century. So after the internet became widespread and increasingly commercialized, just a lot of applications that computer scientists started about involved interaction between a bunch of strategic participants. Of course, game theory and economics offer a lot of tools to think about those problems. But something interesting has happened over the past maybe seven years or so, which is the ideas are increasingly flowing in the opposite direction from computer science to game theory and economics. And so today I want to kind of highlight some of those ideas in the context of the design and analysis of auctions specifically with a case study of a particular really major auction involving tens of billions of dollars which is happening literally right now as we speak and where computer science has really brought a lot to the table, both in the design of the auction being run and also in just understanding when these types of auctions work well. So that's the plan. So let me tell you a little bit about this FCC incentive auction. The story begins about four years ago. Congress authorized the FCC to design and then run a novel auction for reallocating wireless spectrum. Now let me tell you what's not new about this proposal. What's not new is the idea of running an auction, the government running an auction to sell licenses for wireless spectrum to telecoms and other interested bidders. That idea has been around at least since the early 90s. So what's different now, a modern auction is necessary is because now all of the really juicy spectrum that people want for emerging wireless broadband technologies are pretty much already accounted for. All the spectrum is already owned by somebody. So to give someone new spectrum, you have to take it away from someone else. And that's exactly the purpose of this auction. It's to take spectrum away from people who are using it in a not very valuable way like say analog television broadcasting stations and reallocating it to people who can get much more value out of the spectrum like wireless telecoms. How do you compensate people who've got it taken away from you? That's what this is all about. That's what this auction is all about. Have your straight things. Exactly, thanks for the setup. Okay, so this is an auction that's really a double auction. It has what's called the reverse part and what's called the forward part. So a reverse auction, that's when you're running an auction to buy something.  Forward auction, that's when you're running an auction to sell something. When you put something on eBay, that's a forward auction. So the way this FCC incentive auction works is there's two stages, a reverse stage. This is where the government actually compensates people, buys back these licenses from current owners, again principally television broadcasters. And then there's a forward auction and you turn around and basically flip those licenses to people who can use them. So people like Verizon, AT&T, and so on. So there's the reverse stage and subsequently the forward stage where you sell. Now the numbers involved, our estimates are pretty big. So I'm listing some sort of old estimates here by the Congressional Budget Office. It's increasingly clear that the real numbers are going to be only higher than this. But the original estimates is that it would cost in total $15 billion to compensate television stations for enough licenses to be useful and that you could turn around and make $40 billion in the forward auction, selling them to telecoms and other interested parties. So that's a pretty big spread. That's a $25 billion spread. And so the hope was the bill proposed us to use that not just to cover the auction costs, but also to fund some new services and reduce the deficit, presumably part of why it was one of those rare pieces of legislation that had actually been passed by Congress in recent years. It probably didn't hurt that the bill was called the Middle Class Tax Relief and Job Creation Act. I mean this is a bill that just authorizes the FCC to do this double auction, that's what it's called. Who's going to vote against the Middle Class Tax Relief and Job Creation Act? Is it really any kind of tax relief or job creation? Presumably the deficit reduction feeds into that in some way. Okay, so the plan for the talk is I want to talk about each of these two stages in turn. So first the reverse auction, and reverse auction, let me emphasize this is the part that's totally new. There's literally never been an auction of this type in this domain and with spectrum licenses anywhere in the world. It's happening for the first time, actually just concluded about a month ago. And so here I'm going to show you how computer science has really directly influenced which auction was implemented. They really directly influenced the design that was developed over the past few years. The second half of the talk I'll move on to the forward auction where you're selling these licenses back to telecom companies. So like I said, these forward auctions have been being run for a long time since the early 90s before computer scientists were really engaging in computer science and economics and game theory. But still on the forward auction side I'll show you how the theoretical computer science toolbox is perfectly suited to make precise, to make rigorous, some rules of thumb about the practice options that have been known to practitioners, known to economists for years, but left unformalized until just the last few years. So let's begin with the reverse auction. Let me show you how computer science has contributed here. All right, so let me tell you how this works. This will be a few slides to tell you all the relevant details of how the reverse auction works. So again, remember what's the point? The point is the government is trying to buy licenses from those who already have them, principally television broadcasters. That's the point of this auction. Now, presumably the government on the one hand wants to buy up a lot of these licenses, so there's a lot of spectrum to resell. On the other hand, they don't want to pay an exorbitant cost, so the auction is meant to balance those two tensions. And so the auction design was proposed by two economist colleagues of mine, Paul Milgram and Ilya Sagal. And it's what's called a descending clock auction, and this can be thought of as an extension of previous work in both the economics and literature. And the main point of a descending clock auction is to make it as easy as possible to participate in the auction. So that if you're a bidder, if you're one of these television stations, it should be as obvious as possible how to participate in the auction. So how is this implemented? Well, if you're one of these bidders, if you're one of these TV stations in the auction, in a given round the auction will proceed in rounds. In a given round, you're going to be given an offer, a buyout offer. Would you be willing to accept $50 million in exchange for the license that you have? Yes or no? And in a given round this is the only question that a bidder has to answer. Yes or no at some given offer price like $50 million. So now if the bidder says no, I would not sell my license for $50 million, then that bidder is kicked out of the auction for the rest of time. So this station at the end of the day will not the government will not buy its license and it will not be compensated, it will have no payment. Question? You're not offering specifically that one person that it's... You are actually. No, this is an interesting point, it's actually personalized offer prices. Oh. And what basis do you decide to offer different amounts? Yeah, so we'll get to that. So there's this interesting, there's sort of an unusual price discrimination aspect. Which if you think about it it makes a lot of sense. Like CBS in New York is not going to be the same as some Podunk station in Wyoming. So you really it's kind of clear you need some way to do price differentiation. Well, I'll give you more details a little bit later. So that says the bidder you decide yes or no at a given offer price. If you say no then you're out. You just you get to keep your license and you don't participate at all in the reverse auction. Now if you say yes, I would be willing to sell for $50 million that doesn't necessarily mean that the government will buy your license and pay you $50 million. It just means you can continue in the auction. So in the next round it might well be that the auction comes back and says, well you know what we don't actually need your license that badly so we don't want to pay $50 million. Would you also be willing to accept $45 million? And again you can say yes or no. And again if you say no you're kicked out of the auction forever. If you say yes you get to stay in. So what's the motivation for somebody not to say yes all the time? Or at least for some time? Right so at some point the price will be so low it's just not, I mean you're not willing to sell. I mean you have some personal value for this license. So in the whole, and I said this auction was meant to be extremely easy to participate in. So the obvious way to participate is you just, so the hard part is you think about what is the lowest offer you'd be willing to accept. You know that's not an easy question but it's a well-defined question. You figure it out given that answer it's obvious what you do. You keep saying yes until the offer goes below that threshold and then you say no. He said you're kicked out for all time if for all time probably means today there may be a new auction. For this auction yeah it's not, there probably will be another auction like this sometime but it's probably also years. You know it's very uncertain when the next opportunity of this form will be. You know if you had a I think if you were happy to take a risk over five to tenured timeframe that would be a reasonable thing to do. It's not obvious you would be compensated more later than you would now but perhaps it would be scarcer the television spectrum. So you could do that. You could gamble on a better opportunity ten years from now but it would be risky. So I think the mental model you want to have is someone who maybe, so a lot of these broadcasters again this is this is analog we're talking about. So the reach of a lot of these broadcasters is very small. So when you're talking about you know millions or tens of millions of dollars it's pretty attractive. So there's a lot of interest. Good. Okay. So that's a high level bit of how it works. So each bidder sees a descending sequence of prices and you keep saying yes or no. When you say no you get kicked out. When the auction terminates and it's a little tricky to explain when it terminates, I'll talk about that in detail when it terminates at that point all of the bidders still in the auction the government will buy all of their licenses at the price equal to the most recently i.e. lowest accepted buyout offer. So that's what happens at the end. Buy that guy. Exactly. And so as was mentioned different people will face different prices. So in particular the beginning offer is wildly different for different participants. So it's all very high. The opening offers because for this to be successful you obviously need a lot of broadcasters to participate. So they begin with these very lucrative opening offers which basically everybody's happy to accept by participating in this auction you're under contract to sell your license if the price never drops below that opening offer. And the highest is in fact WCBS in New York. It was $900 million opening offer for WCBS which is kind of actually an insane amount of money. And again obviously ones in Wyoming are going to be offered much lower prices. And so at termination it's whatever your most recent offer price was. That's what you get paid for your license at termination. Just want to know for a particular piece of the spectrum how many it's different in New York and Wyoming some in Wyoming and some in New York have the same piece of the spectrum. Yes, we'll get to that. So basically a license is for a particular channel which is a particular block of spectrum for a particular region. So two broadcasters that have non-overlapping broadcast regions will have the same portion of the spectrum. And we'll see pictures of that in a couple of slides. Now you're going to also say how that initial price is set. I can say a little bit about it. So there is a formula and the formula is public. So basically there's two things which govern that price. The first is just the size of the market. So the extent of your reach. The second is a sort of rough proxy for how much your for how constrained you are. So think of it as like you look at the number of different people that you overlap with and so that means buying you out would give me a lot more flexibility with what I do with other people. So then I'll also give you a higher offer if somehow buying you out would just make my whole life easier because you conflict with so many different people. So imagine you conflicted with like 10 different stations. So all of you have to have a different channel from all of them. Then I'm also going to offer you a higher price. And there's some so called square root rule to kind of combine these two criteria. So the value of analog licenses probably goes down over time? So if everybody else sells and I keep my analog license probably not that many people are going to have a TV that's Possibly, yeah. So a big part of the value of these licenses is if you have an analog broadcasting license it actually forces cable to also carry your channel to carry your broadcast. So it has the value which is not necessarily obvious. I don't really know if the value is going to go up or down after this auction. I thought we shut down all the analog TV a couple of years ago. Only past channel 51. So we still have people 51 and below. Yeah. Digital is just a whole different story. There's no bidding, nothing. It just suddenly goes over the pipes. Digital stuff is totally orthogonal. All right. So this is totally orthogonal. So again, all these analog broadcasters in principle you could view them analog, but very few people do. So most people will see it through the digital signal. And again, if you have one of these analog licenses then you have to be granted to write. Here in the Bay Area all the major stations want offline. They're not there anymore. Okay. We talk about this offline. Good. Okay. So let me tell you more about how this stops. So what happens each round is you say yes or no and then in some sense the government wants to keep lowering these prices but it wants to clear enough spectrum. So what does it mean to clear enough spectrum? So getting back to Ron's question what does spectrum actually look like? This will help me sort of explain what the stopping rule is. So each of the channels and we're thinking of UHF channels here they occupy 6 megahertz of the spectrum and an item, a license that's the right to broadcast on a particular channel in a particular area. Okay. And so what does it mean to clear enough spectrum? So the goal is going to be to have some target number of channels and to do it nationwide. Okay. So for example channel 51 you want to buy out everybody on channel 51 nationwide. So you really want nationwide clearance for it to be as useful as possible to the potential bidders many of whom are thinking about implementing national plans with this new spectrum. Now, so the government's not just going to want to clear one channel it's going to want to clear many and so there's some it's unclear right now how many are going to get cleared. But for the sake of the talk let's imagine that they want to clear 10 channels. So 60 megahertz. And maybe they'd pick say the upper 14 channels 38 to 51. So it turns out the higher channels are the ones that are more useful for wireless broadband. So they might say okay out of these top 14 channels let's clear 10 of them nationwide that could just 60 megahertz to work with when we pass to the forward option and sell it back. So that's sort of how you should think of the goal. Okay, so from the top 14 channels you know let's free up 10 of them. Okay, so now we get to a really interesting part of the auction which is okay so again remember we're trying to clear nationwide but you know we're just we're decreasing prices in this auction at some point different people will drop out of the auction which means we don't get to buy the option. So that's how you should think of the goal. Okay, so from the top 14 channels you know let's free up 10 of them. We're going to drop out of the auction which means we don't get to buy their license means they keep their license and it seems very unlikely that these television broadcasters are going to neatly arrange dropping out in a way that just magically clears an entire channel nationwide and then the next channel nationwide that's not what's going to happen. Channel 49 in San Francisco will drop out then channel 39 in Austin will drop out then channel 42 in Boston and so on. So how do you deal with this? How do you deal with the fact that there's no spectrum? So here there's a major centralized step in the auction and it's really sort of the part of this process which you can't really imagine being done by a free market. It seems like you really need some kind of centralized coordination device like this option to do this is it's going to be a repacking i.e. a reassignment of channels. So if you're one of these television broadcasters and you have the right to channel 49 before the auction even if you drop out of the auction and you are not guaranteed to retain your license you are not guaranteed to retain your channel. You might be reassigned from say 41 to 49. So again even if you don't and there's sort of minimal compensation if you have a channel reassignment but it's at a much lower level than for buying out your license. Okay? If I'm channel 5 and I give up my spectrum I still want to keep channel 5 I still want to keep channel 5 but just I get assigned to a new spectrum and people's TV sets will somehow magically know the new spectrum I don't quite get how that works. So I mean there'd be a new so I mean there'd be a new list of channels basically so you know who's on a given channel would just be different. So me as a consumer I would notice a difference then I would notice that. Yeah you would be told that here's the new assignment of channels. I see. Some channels are disappearing. Right. It's not like all of them are being reassigned. That's right. So there's going to be a mixture. Some of these channels really will disappear some of them really will be reassigned. There's actually some intermediate options that bidders can take which I'm not going to really mention which is they can share channels two stations can share a channel or you can just agree to have other types of partial service but let's just think of it as binary. You either keep your license or not. I mean let's say I'm the guy in Wyoming and you're the guy in New York with the same spectrum and the guy in my only wish to drop out I can imagine the guy in New York saying look don't drop out I'm going to keep this whole thing alive I'll give you some money to stay alive. Sure so there's an issue of collusion which so it's illegal so it's not illegal. Yeah so if you engage in it you know and the government finds out they'll prosecute you for it. There's some degree of collusion does happen and it's in auction design there's basically no reasonable auction design which is fully robust to collusion with side payments. So the usual way you handle this is you do the auction format as best you can and then you use the legal system to really sort of try to prevent large scale collusion. Okay so when I say clear 10 channels out of the top 14 I really mean something a little more subtle nationwide so what I mean is you want to buy back enough licenses from the top 14 channels so that the stations you did not buy back buy out can be repacked reassigned on just four channels okay nationwide. So you want 10 clear nationwide four can be full nationwide after you do a suitable channel reassigned okay repacking problem so given that there's a collection of stations that you have not bought out that keep their licenses reassigned them to channels so they use as few channels as possible and if you think about it let me just point out you're going to have to solve these kinds of repacking problems over and over and over again in this auction design. Let's go back to you know we talked about how you know at some point if you're a bidder your offer might be lowered from 50 million to 45 million at which point you can now say no and be kicked out of the auction and if you think about it from the auction's perspective that means you got to be a little careful before you lower anybody's buyout offer right so suppose you're offering someone 50 million they're willing to be bought out and there's some collection of stations which are not bought out which you can successfully repack in your target say four channels. Now if you drop this guy's offer from 50 to 45 he might drop out so that's one more station you have to repack and this could be the pivotal station which suddenly causes you to need five channels to reassign everybody rather than four and if your target's four that's not going to be acceptable okay so the auction's going to maintain the invariance that the stations which have dropped out can be repacked into a target number of channels if there's any station which whose dropout would violate that invariance their price is frozen until the end of the auction okay so dropping you would violate my repacking invariance you'll have this 50 million offer on the table until the end of the auction at that point you basically know you are going to get bought out for 50 million okay so now every time you do this this is a repacking problem right so every thought experiment where you say if this person dropped out would I no longer be able to pack everybody that's an instance of this repacking problem. There could be two two what? Not just this one guy who drops out screws up a repacking but be either A or B and you want to keep either A or B but so you want it's not clear you'll be happy if either A or B were going to sell right but not necessarily A not necessarily B so if you stop if you give them the money you didn't need them both and we needed one of them. That's right so there's a question of right so the way the auction works is they literally just go through the bidders one by one so at any given time the auction is deciding on only one bidder and it's basically doing kind of worst case analysis over what might happen in the future but I mean but to be clear stations are only dropping out so your repacking problem is only getting harder you know so once someone is critical they're really critical no matter what happens for the rest of the auction you're going to need to buy them out no matter what else happens okay so that's the repacking problem and it's happening literally every round of this auction okay so thousands of these need to be done every day so let me give you a picture of this repacking problem just to make sure it's clear so here each circle here represents one particular broadcaster the circle is the area of their coverage the colors here correspond to channels okay the current channels you'll notice that no two overlapping circles share a color okay and that's because you know no two stations which overlap in their broadcasting area can share a channel actually they can't even share an adjacent channel let's leave that aside okay so you could ask okay three channels could be repacked them in only two channels well definitely not because over here we have three mutually overlapping stations so we really need three different channels to have none of them interfere with each other on the other hand imagine that we bought out this big station on the upper right now it's still the case that all three channels are being used but now we can actually reassign them on to only two channels so that there's still no interference okay so that's the repacking problem in picture alright you want to buy out you want to make enough of these circles disappear buy out enough people so that the remaining circles the stations keeping their license can be colored in the target number of colors say four so that's the repacking problem I said that we had to do the auction has to do thousands of these every day and this is obviously an NP-hard problem this is basically exactly the graph coloring problem you could just plop this into an algorithms course as a real life application of graph coloring which it is okay so how are we going to solve thousands of graph coloring problems a day so Milgram and Seagal they recruited a computer scientist Kevin Layton Brown at UBC to lead this effort and something really cool turned out to be true which is that state-of-the-art techniques for solving NP-complete problems specifically SAT problems turned out to be sufficient and also sort of necessary to make this a viable format to solve these repacking problems sufficiently quickly that you can actually implement the auction in a reasonable amount of time so the approach was first you formulate these graph coloring type problems as SAT problems if you just use the state-of-the-art off-the-shelf solvers they do reasonably well so they already kind of solved maybe say 90% of the relevant instances in a second or less that was roughly the amount they were willing to tolerate computation for one of these problems but by leveraging the domain-specific structure of this problem Layton Brown and his team was able to get it up to more like 99% of these repacking problems that come up get solved in a second or less there's still a few of these repacking problems that come up where they time out the specialized SAT solver doesn't solve it in one second in that case you just sort of pretend as if it's unsatisfiable which it may or may not be because remember what is a repacking problem you're asking can you or can you not successfully reassign all of these stations that have dropped out to a given number of channels and it's not okay to make a mistake in the direction of saying yes when the answer is actually no so what's funny here is that I've never seen a more direct link between the running time performance of an algorithm and the money which gets made or lost it's like a literally super direct connection because every time the SAT solver fails to find a satisfying assignment to a satisfiable SAT instance that is a case where the auction is unable to lower somebody's offer price usually by millions of dollars when if only they had found the satisfying assignment they could have lowered their offer price by millions of dollars therefore paying less at the end of the auction so every SAT instance every satisfiable SAT instance that you failed to solve in one second kind of directly leads to corresponding millions of dollars of loss or increase in cost just one second after all such lowering you have to give that person time to decide on their offer or is it like is the decision instantaneous do they just keep their minimum price no they're around so in a given day there will be two or three rounds each lasting two to three hours and as a bidder you go once per round but you have to cover all the bidders in a given round and so every bidder has their own repacking problem and so that's why you have lots of these that need to be solved so you need to solve the order of thousands of them in a couple hours basically for every bidder you have to compute the repacking order they certainly experimented with different thresholds because you can play with how many rounds you have a day all these parameters you can play with they wound up deciding on a second but certainly like a minute would certainly not have been okay that would not have been enough two seconds so they were getting sort of diminishing returns I think so if you didn't solve it in a second their SAT solver would often take much longer than a second say it again they could also use maybe some foster hardware they're kind of maxed out yeah that was the easiest part was to buy a whole bunch of machines then you have to do the other ones good okay so again I want to emphasize this auction format would literally not be viable you literally could not run this auction which just finished last month without the state-of-the-art technology for solving NP-complete problems are SAT solvers public or do you go buy a SAT solver and I say I've got even better many of these are public it's not like C-Plex so they started from so they have these SAT competitions and those are generally most of those you can just work with it varies but there are good ones which are which are you can just use it's not a good business to go into making rules for a SAT solver to sell it to people I could imagine if you had a one particularly good for some important domain like model checking or chip verification maybe you could do something but just for a general purpose I wouldn't necessarily recommend it okay so let me just mention one other thing quickly a little bit more on the theoretical side around the reverse auction before I move on to the forward auction part so there's still flexibility in the auction format as I've described it namely what are these opening prices, who do you decrease next by how much do you decrease them and so Milgram and Segal proved a really nice theorem which maps out that design space exactly you know what are the different ways you could implement this descending clock option and what they proved is they essentially correspond to all possible reverse greedy algorithms so let me talk about what I mean by reverse greedy algorithm I could give you a formal definition I'm not going to it's just easier to think of an example so as an example think about the minimum spanning tree problem you want to graph with edge costs you want the spanning tree to graph with the cheapest possible sum of edge costs you've all seen Kruskal's algorithm at some point in your life this is the MST algorithm where you sort the edges from cheapest to most expensive you do a single pass through the edges and you keep including an edge as long as it doesn't destroy feasibility as long as it doesn't create a cycle and Kruskal's algorithm is correct it's guaranteed to give you an MST so that's what I mean by a normal greedy algorithm you go from the edges in one pass from cheapest to most expensive you go the opposite direction you go from most expensive to cheapest and now you think about starting with all of the edges and deleting an edge unless it destroys feasibility or until you get feasibility back so as long as an edge is on a cycle you delete it and you continue and turns out you may have never thought about this algorithm but this algorithm is equally correct it has the same output as Kruskal's algorithm or reverse and there's some other examples where it doesn't matter whether you do forward or reverse so at the moment maybe it doesn't sound like that interesting a question we understand a lot about greedy algorithms Milgram and Seagal prove that it's these reverse greedy algorithms probably it's the same as greedy algorithms so we kind of know what's up actually not so much so this is with Paul Dutting and Basilis Gazelis we studied the power and limitations of reverse greedy algorithms and what we discovered is actually if you just take the obvious normal greedy algorithm and reverse it in this way it's a total disaster for example matching, even bipartite matching okay so you can solve matching with a normal greedy algorithm a forward greedy algorithm you go through the edges from highest weight to lowest weight you always pick an edge if it doesn't violate the fact that it's a matching that's well known to give a one half approximation in the worst case what would be the reverse version of that greedy algorithm you'd start with all the edges go from the worst to the best and delete an edge as long as, sorry, until you recovered feasibility until you wound up with a matching and that can be a disaster even in a very simple case so imagine you have an eighth cycle and all the edges had weight one so you start with all the edges this is not a matching, this eighth cycle it's an edge if everything has the same weight you're going to delete some arbitrary edge you don't know which one so now you're left with this path of length 7 it's still not a matching so you're still going to go and delete an edge and again you give it no guidance about which edge to delete so maybe that's the next edge you delete and you keep going you still don't have a matching you delete again, you still don't have a matching etc, etc, etc so the reverse greedy algorithm actually doesn't terminate and obviously this is very far from the max weight matching so this just shows that MST is the happy case where Ford and reverse is the same there are other problems where the reverse version of the natural greedy algorithm is terrible and remember the point of the Milgram-Sagall theorem says that descending clock options really require reverse greedy algorithms alright so I won't go into too much detail here so what we thought about was could you have a more clever reverse greedy algorithm which matches the performance of the normal greedy algorithm for let's say matching problems both in graphs and in hypergraphs and the answer is yes so the obvious reverse greedy algorithm does not get within a constant factor approximation but if you work harder if you do kind of a two phase approach then there are techniques that will get you within a constant factor approximation growing linearly with the hypergraph ranking D and what I think is cool here is reverse greedy algorithms have been studied before but barely a handful of papers kind of scattered through the literature and I understand why so reverse greedy algorithms seem harder they seem less intuitive, harder to design than normal greedy algorithms they seem to often have worse performance so why would you ever bother why not just do a normal greedy algorithm but here coming from this auction application we see that because reverse greedy algorithms are the ones that fit in to this descending clock auction format it's actually the first extrinsic motivation to study this class of algorithms reverse greedy algorithms and I think there's some nice theory problems there ok so I want to move on to the forward auction any questions on the reverse part you can't you're doing kind of worst case analysis you thought experiment what if they dropped out would I be screwed would I no longer be able to repack everybody exactly now in the implementation there's a lot of actually really nice caching ideas so that you wind up getting a lot of SAT problems where you can just look up do table look up on the solution but still there's a lot of cache misses too which they have to solve that's where the one second comes from you really have to solve tons of these problems to what extent can the bidders the companies be strategic deciding whether to accept the bidder or not rather than just the obvious thing to do is they have a simple threshold in mind I want to get at least 30,000 dollars just wait until then but can they be more strategic than that good question so it sort of depends on you know space of strategies you're thinking about I mean thinking about just the strategies where you're saying yes or no with different points then there's nothing there's really no reason to not do it and it's very strong sense there's no reason not to do the obvious thing right because what are the two what are the two things that could happen if you deviate either you could say no you know too early in which case you might have missed out on the opportunity to get a ton of money for your license or you stayed in too long on the risk of actually getting bought out for this amount which is less than what you're willing to pay for it is now if you zoom out a little bit and you're like well maybe there's ways of strategizing kind of outside the box of the auction then certainly there are opportunities and people are you know you can see people strategizing for example you could buy a different station okay and so then in effect you get to place bids there's people in the auction so it's somehow implicit collusion to buy a second station you can try to coordinate how those two things work with each other that's legal it's also a collusion but it's a legal collusion it's kind of a legal workaround I mean there are regulations on sort of how many stations any one entity can own in a given geographic region it's often only one or sometimes maybe two so that limits it to some degree but there have been I think some strategic sort of mergers and buyouts in advance of the auction and frankly there's also just like been just a ton of lobbying for example someone asked about how are these opening offers calculated I mean there was just huge arguments over that there's a strong lobby group for the television broadcaster so they of course wanted higher offer prices and the government was trying to push back lower offer prices so all that kind of negotiation in advance of the auction was also going on so there's lots of strategy but if you narrow in just a limited enough range of things then this auction actually is very good in set of properties you really should just do the obvious thing and of course the hope is that the ultimate outcome will be dominated by television broadcasters that just kind of participate in the obvious way that's the hope okay, other questions? so the forward auctions remember this is what happens second where we're at so the reverse auction or at least the first stage of the reverse auction concluded about a month ago and the forward auction is starting literally a week from today so that's where they're going to start taking bids I think there's 62 qualified bidders or something like that participating in the forward auction bidding on licenses okay, as I said these auctions have been around for a long time early 90s and they work pretty well so no one's really looking to do much with the design mostly people have just been using the standard workhorse for auction after auction over the last 20 years but so here where computer science has contributed is really in the analysis in taking rules of thumb which are widely believed in practice but had not been formalized and it turns out the theoretical computer science toolbox is perfect for turning these rules of thumb into translating them into precise guarantees precise theorems alright so a little bit about how these forward auctions work so we've been mentioning that there's big numbers involved tens of billions of dollars in these things and then what makes it kind of even more scary is that the design really matters so if you use a bad auction design it can perform extremely poorly so there's a cautionary tale from the early days, New Zealand in 1990 so here the New Zealand government was selling the rights for 10 different television channels interchangeable and they decided to sell these 10 channels using 10 simultaneous second price auctions so a single second price auction is like what happens on eBay the winner is the highest bidder and the selling price is the second highest bid so that's a second price auction so they decided to just do a sealed bid second price auction simultaneously sell 10 of these channels so as a participant in this auction you will write down 10 numbers what is your bid for each of the 10 channels and then each channel is just awarded independently so you just look at the highest bidder on that channel and the second highest bid on that channel and that determines the winner and the price you don't want to win twice though generally not and in this case the bidders didn't really want to win more than one so that would suggest you write down 9 zeros but it's under your control to not win more than one exactly so this is exactly where I'm going so if you think about it imagine you were a participant in this auction it's actually not super obvious what you should do especially if you knew there were only about 20 participants in this auction so it's actually not very competitive as far as the ratio of bidders to channels so maybe the simplest thing you might try to do is to suppose you only wanted one channel like Ron said let me just pick my favorite channel channel number 7 and go all in I'm just going to bid my willingness to pay on the one channel and hope I get it it's not the only strategy you can also say well there's only 20 people after these 10 channels so if they're kind of randomly picking different channels to bid on maybe there's going to be some channel that's the one people who are bidding on it and so maybe I should just bid super low on multiple channels hoping I get one of them for a bargain and hoping that I don't win all of them and have to pay for all of them exactly depending on where the price is for your value so that could be a legitimate strategy bidding low on lots of presumably you could then sell it to somebody else and you get an extra channel possibly, yeah there's issues around that okay right so it's not clear how to bid and a good rule of thumb is in an auction where it's not clear what you should do as a bidder has very high variability and unpredictability in the outcome and you can suffer a lot both in terms of the revenue and in terms of just the quality of the allocation that you attain so in this New Zealand auction for example they were hoping to make a quarter of a billion dollars they made less than that was the estimate they made less than 15% of that 6 million instead of 250 million and you know when you sort of look into the details of this auction it's really kind of cringe entusing to see the details like there was one channel where the high bid was 250,000 that's already like really bad news because you notice they're hoping to make 25 mil per channel so I'm telling you the highest bid was 250,000 on this channel the second highest bid was 6 $6 $6 and I don't know why but they didn't use a reserve price oh my gosh the guy got it for 6 bucks yeah the guy got it for 6 bucks there's another channel where the high bid actually was 25 million but the second highest bid was sort of you know 50,000 something like that it was worth 250,000 so I made a profit it was worth 250,000 and you had to pay 6 by the way excuse me 6 dollars was going to be 250,000 right maybe each means that's how much money was left on the table the highest bid was 250,000 right no that I agree so it's clear there's a lower bound certainly on how much money was left on the table and right this is what I was getting at so at insult to injury the contract of this auction required the government to report both the high bid and the selling price on every one of the auctions so these spreads were just obvious to the whole world after this happened so it's kind of a high stakes thing big numbers and bad designs are really problematic and of course in the US auctions we're scaling these numbers up by 2 orders of magnitude alright so people don't use the sealed bid simultaneous format so what do they use well they use kind of a simple twist on it simultaneous ascending auctions so what's a single ascending option that's what you'd see at Christie's or Sotheby's where the some auctioneer maintaining a price the price only goes up you raise your hand as long as you want it and as soon as there's only one person who's still raising their hand they're the winner at the most recently announced price by the auctioneer so for simultaneous ascending auctions you just have one of these running in parallel on each of the items that's being sold so in a spectrum auction you're going to have one price per license and all of these prices are only going up and as a bidder you can stay in on whatever subset of these licenses you see fit okay and again they're just allocated separately so when there's only one person left interested in a license it gets allocated at the most recent price so this does much better in practice than sealed bid formats you know basically because there's room for bidders to coordinate implicitly as the auction proceeds and of course you can have mid-course corrections as if you realize the competition is sort of higher or lower in certain parts than what you thought so the thinking is these work pretty well but they're not perfect they do have a couple of vulnerabilities so let me tell you the two biggest vulnerabilities in simultaneous ascending auctions the first is called demand reduction and so this is where a bidder will ask for fewer licenses than it actually wants in order to depress the competition of the market clearing prices so let me tell you a specific example so suppose there's just two items two licenses suppose you're bidder number one you're willing to pay six per license so you're willing to pay six for one license twelve for both suppose I really only want one license I don't want them both I'm willing to pay five for either of the two licenses now on something like moral level you should get both of the licenses your value for each six is more than my value for either five so that's sort of what we want to have happen in some sense but how would that actually happen in this ascending auction? for me to get nothing why would I ever drop out in this ascending auction? again I'm willing to pay five for either one I'm only going to drop out when the price for both of the items is five or more if either item has priced below five I'm going to stay in and be like I want that so I only drop out when both of the prices hit five so at that point you win both items and you have value twelve six for each but you pay ten five for each so you have a net utility of two okay it's better than nothing but here's the incentive for demand reduction imagine that instead of insisting on going for both licenses imagine you just bid only on license one and you never bid on license two I would then say okay fine I'll take license two for free thank you very much I won't bother competing with you on license one and you'll get license one for free so you only get one license instead of two but because the prices drop from five to zero your net utility has gone up from two to six okay so that's why decreasing the amount of licenses that you target can decrease competition leading to lower prices and therefore higher utility okay that's demand reduction okay so the second vulnerability second price of these simultaneous ascending auctions known as the exposure problem and the exposure problem comes up when there are so-called complementarities between items so now imagine that you're still bidder number one but now you really want both of the licenses for example maybe one is northern California and one is southern California and you really want to roll out a statewide plan you really do not want just one license you really want both imagine you're willing to pay six for both okay total imagine I'm the same as before I'm willing to pay five for either one both okay so again you know morally you should win right because your value if it is license to six is more than mine five but again if you think about these ascending auctions I'm not going to drop out until the price of both hits five and if you stay in that long to force me out of the auction think about where things stand you're going to get both items you have value six but you pay five for each you pay ten okay so your utility is minus four you're worse off than if you'd never showed up to the auction in the first place okay so that's the exposure problem if you're a bidder with these complementarities between items where you really want a whole package and not a subset then you have to either bid aggressively and risk you know paying more than your value or bid tentatively and then risk you know not winning what you rightfully deserve okay so that's the exposure problem and so these are well known issues with simultaneous ascending auctions so I told you some toy examples do these things actually happen yeah they do happen so you know let's see what the experts say about this issue so Peter cramped in he's an economics professor at University of Maryland and he's been very active both in the design of these forward spectrum auctions and he also does a lot of work consulting for people who bid in these auctions and so he's written a number of things about how you know how they've worked in practice so he starts with an interesting statement which just says look first of all you know it's a complex allocation problem we're dealing with allocating licenses to bidders you're not going to have full efficiency you're not going to get the best possible allocation with any reasonable auction format so in some sense what he's saying is the best you could hope for is some kind of near optimal near optimality some kind of approximation guarantee he goes on to say you know demand reduction definitely happens he cites a particular company page net and he was actually consulting for page net during this auction so he was well positioned to know that they were engaging in demand reduction and further he says that you know there is inefficiency arising from demand reduction but at least you know in this particular auction it didn't seem very severe there was inefficiency but still the quality of the outcome was not too far away from the best you could hope for from an optimal allocation the demand reduction seems to definitely exist but seems to not be such a big deal the exposure problem by contrast seems like kind of a deal breaker for simultaneous ascending auctions this quote's referring to you know field lab experiments rather than field experiments but still most people believe that if you have these strong complementarities between items where a bidder really wants a bundle and not the individual items then you're vulnerable to very poor outcomes with simultaneous ascending auctions so demand reduction exists but it's not a deal breaker if you have complementarities the exposure problem does seem like a deal breaker for this workhorse auction format of simultaneous ascending auctions so here's how I would summarize the discussion so far so if you talk to people who work in the trenches of these forward auctions there's maybe a little bit of debate but for the most part there's a consensus of the following two rules of thumb so first of all if there aren't strong complementarities between items then you can get away with a simple auction format like simultaneous ascending auctions it should be fine it's not going to be 100% efficient nobody's claiming that but it should be good enough in some sense on the other hand if there are strong compliments then you really have to add more complexity to the auction beyond just these simultaneous ascending auctions if you want to have any kind of reasonable outcome so more complexity here might mean something like adding package bidding or in addition to bidding separately on each item you can also submit a bid that says I really want items 1, 3 and 5 and I'm willing to bid 100 for it that would be an example of adding complexity to an auction in order to let bidders express any complementarities they might have between the items so for the rest of this talk I want to say at least a little bit about each of these and I want to show you how in theoretical computer science we naturally lens the vocabulary to translate these rules of thumb into totally precise guarantees totally precise theorems these have been known to economists those working in the trenches for many many years but it's been left essentially totally unformalized in the economics literature and if I had to speculate I would say it's really because I can't imagine any way of turning these beliefs into theorems which don't involve talking about approximation and economists just historically have not really thought about approximation guarantees it's just not been something they do and so that's why there's been sort of a mismatch between traditional economic theory and kind of theory that would be relevant for understanding these rules of thumb okay so let me say a little bit about each one so first we want a positive result we want to say that if there aren't these between items then a simple auction works pretty well so what would a theorem look like okay so I want to think about the case that Crampton was talking about where you have demand reduction there is strategic behavior but somehow the efficiency still seems pretty high so fundamentally what the theorem is going to be about it's going to be talking about the result of strategic behavior it's going to be talking about the equilibria of some auction this was some simple auction format and the conclusion should be that the equilibria the result of strategic behavior is close to optimal with respect to some objective function okay so approximation guarantees for equilibria is actually something that computer scientists have been thinking a lot about over the past 15 years there's even a catchy name for it the price of anarchy hopefully a few of you have heard about this at some point if you haven't thought about the price of anarchy in like five years or more maybe the first picture that comes into your mind is a network maybe there's selfish routing maybe there's network formation something like this because in the early days of algorithmic game theory this is what the work on price of anarchy was it was sort of a collection of sort of model specific analyses for lots of different usually network related settings last five years something really cool has happened which is there's really now a very coherent theory of price of anarchy balance and there's a powerful and easy to use improving in many different types of games including relevant for us auctions that equilibria are guaranteed to be near optimal so what I want to do next is I want to tell you there's a bunch of results of this form that use the price of anarchy to formalize that folklore belief I'm going to single out one specific one just to make it more concrete so in these last few slides I'm not going to do any proofs or anything like that but I do want to be somewhat precise about the statements so let me tell you a little bit more formally about the model I'm talking about and the objective function we're approximating and so on so there's n-bitters, m-items think of them as telecoms and spectrum licenses and we need to have a notion of the best allocation the way to allocate the items to the bitters so that it's most valuable to everybody so how do we make that precise well we need to have a notion of a bitters value for one or more items so we have this notion of evaluation i has a valuation which specifies and this is sort of just in their mind it specifies for each subset of licenses they might receive what would be their maximum willingness to pay for that particular subset so for licenses 1, 3, and 5 maybe you're willing to pay 12 at most notice evaluation specifies 2 to the m different numbers one for each subset of items for sale one for each bundle that it might receive so the notion of the best allocation is just going to be the one that maximizes what's known as the social welfare which is just the sum of the values of all of the bitters of the items that they receive so in a perfect world we would love to distribute, partition the items in a way to make that social welfare as high as possible that's kind of our utopian benchmark a bidder, what it wants to do is it wants to maximize its utility so it's value minus the price it has to pay for the items that it receives and so the question then to prove a price of anarchy down what it means is to prove that the equilibria of some game, of some auction game are close to the maximum possible in social welfare that's what it means to prove that the price of anarchy is good that the price of anarchy is close to one so let me tell you what this is to tell you what auction format the theorem is going to be about so we're going to talk about for simplicity first price auctions we could use second price there'd be analogous results it's just simpler to work with the first price case so this is where the items are sold separately sealed bids winter pays their bid and then the question I want to ask is when does simultaneous first price auctions have equilibria with nearly the maximum possible welfare welfare almost as high as if we could just have a centralized optimization of all of the items so folklore beliefs would suggest that the answer might work well if there are not compliments but it shouldn't work well in general if there are compliments but again there are no theorems about this until a few years ago so the positive result so now I need to say what do I mean formally by there are no complementarities between items there's several ways of making this precise one thing that's cool about this theorem is it works with the weakest of all of the definitions people think about compliments which is just having a sub-added evaluation so the only assumption here is that a bidder's value for the union of two bundles is at most the sum of their values for each bundle by itself so that's a sub-added evaluation that's one way of saying there's no compliments and a really great theorem by Feldman, Fou, Graven and Lucier show that as long as you have sub-added bidder valuations so no compliments in that sense and under no other assumptions any equilibrium so the result of strategic behavior is going to be within a constant factor of the maximum possible welfare so you have this auction it's a very simple lightweight auction people reach some equilibrium and it's going to be guaranteed to be near optimal in this sense so in this case it's 50% in the worst case and as usual in many cases you expect to do better than the worst case but you can strengthen the assumption from sub-additivity to sub-modularity which is a stronger version of having no compliments than actually even the worst case value improves from 50% to 1-1 over E which is roughly 63% so this is a sense in which remember that first folklore belief without strong compliments i.e. with sub-added valuations simple auctions work pretty well i.e. every equilibrium of simultaneous first-press auctions of the maximum possible so it's really a direct translation of this belief using the price of the energy as a tool so that's the formal version of the first rule of thumb that without compliments simple auctions do well let me conclude by talking about the second one so the second one says if there are complementaries between items so again people want bundles and not the individual items then you really need to add complexity to the auction because simple auction is going to be good enough so let's again ask what would a theorem look like here so here it's a little different it's a lower bound, it's a negative result we want to prove that for every single simple auction it's not going to be good i.e. there will be equilibria with very poor welfare so we need to rule out the entire class of simple auctions simultaneously which if you weren't a computer scientist might sound pretty intimidating but of course it's right in the wheelhouse of theoretical computer science to have techniques that rule out any possible solution to some problem we have lots of tools for proving that solutions of a certain form do not exist for different problems that's basically what we need here the solution space being simple auctions and then the problem to be attaining a near optimal outcome of the items so let's just start by revisiting the auction about simultaneous first price auctions let's just check they got within a constant factor without compliments the folklore relief suggests that they shouldn't without compliments or with compliments with general valuations and that was shown by Hasidim Kotlin, Mansur and Nisa so in fact that constant factor we saw for the sub-additive case it really needs the sub-additive assumption it is just really badly false for general valuations as you scale the number of items we are guaranteed to get 1% of the maximum welfare in an equilibrium with simultaneous first price auctions it's something that should be easy to show you say it's a big deal wouldn't that be easier to show some simple example show that? I wasn't trying to say this is a big deal this is the first standard you showed so we want to show that all simple auctions are bad let's start with the specific simple auctions and improve good results about it at least that doesn't work but now as Ron is suggesting it's more clever maybe we change first price to second price or all pay or maybe we let people bid on pairs of items and not just single items but why wouldn't one of these perhaps work but in fact it can't so you can really prove this is unconditional that when bidders have general valuations when they have compliments actually every single simple auction I'll have to tell you what I mean by that but every single simple auction there is no possible welfare there is no simple auction that guarantees a constant fraction of the optimal welfare when you have compliments in this sense simple auctions perform poorly with complementarities so what do I mean by simple by simple I just mean that there aren't too many bidding parameters per bidder so let's think about this for a second so let's say it's simultaneous first price auctions how many bidding parameters are there on each of the M items so those M bidding parameters and simultaneous first price auctions if I could also submit on pairs of items then it would be M squared and so on on the other hand what's the biggest number of bidding parameters you could possibly imagine well I kind of only have two to the M things to say but I have this valuation which specifies how I value each of the possible bundles I guess in the extreme case I could tell you all two to the M numbers if you did that then there's an analog of the second price auction which actually would get full efficiency so once you get exponential it's not going to be the case that things don't work well they can work well it's not going to be implementable for modest M but in principle it does get full efficiency so simple here just means you're not at this extreme case of having an exponential number of bidding parameters if you have M parameters, M squared parameters two to the root M parameters whatever it's not going to be good enough so the question with just a sub exponential just a sub exponential number of bids per player is going to suffer from arbitrarily poor equilibria that sounds hard to prove it's not too hard to prove I'll give you a sketch I'll give you one slide plus about the argument yeah, Vitaly so why having some equilibria which are bad this is the kind of result why does it mean that necessarily whatever I'll run when I run those auctions I'll reach those bad equilibrium so it actually says suppose you have any special case of an equilibrium which is tractable to verify so this is sort of the property of an equilibrium that I need for the theorem I needed that if you wrote down an alleged equilibrium I could in say polycommunication or something like that verify it as such so a non-example would be if you said this is the maximum welfare equilibrium how would I know that? how do I know there isn't one that's bigger? I just can't find it so I would argue that any kind of useful equilibrium concept if I equate certifiability as a necessary condition for relevance we are talking about the solution which result from some process exactly would it necessarily I mean why would we be using the process which result in solutions which have some very viable properties? I wouldn't say it's not a case that I'm not assuming any process for reaching an equilibrium I'm saying if people reach an equilibrium no matter how they do it with exponential amount of communication and time and all this kind of stuff it's still going to be the case that it's not going to achieve good welfare so that's kind of the strength of it so if I was somehow assuming that bidders were only doing polycommunication to get wherever they get then these results would be much more immediate so the point of the main result is even if I allow you the power to magically jump to an equilibrium still there's still not going to get an approximation anyway so before I say maybe just a minute about the argument let me just point out I think this is a quite direct translation to that second folklore belief that without strong compliments you really have no choice but to add complexity to the auction format if you want good welfare guarantees at least in the good case at least in the worst case okay so let me just say kind of one word about how it goes because in particular this result piggybacks on some really nice work that's been done in communication complexity last decade I think a lot of people who don't work in complexity think of communication complexity as sort of this kind of very esoteric difficult strand of theoretical science and there are aspects which are but it's actually exactly what you need to turn this empirical rule of thumb into a theorem it's actually exactly the right tool it's really cool actually so my theorem which is more general in the following sense it's a translation of lower bounds for communication protocols to lower bounds for equilibria so whenever you can prove that there's no communication protocol with certain properties for obtaining a near optimal allocation of the items it will automatically follow from this theorem so this theorem will say it will automatically follow that that same lower bound you prove for protocols also holds for equilibria the reason this is non-trivial is because I'm not assuming that the equilibrium is computed by some low cost protocol so even if you magically get to an equilibrium it's still the case that the lower bound that we prove for protocols applies for equilibria equilibrium of simple auctions I should say so the lower bound applies for auctions that have a sub-exponential number if they don't play in it and so then I just use the fact that actually last decade there's a lot of nice work that really do say there are not low cost communication protocols for these welfare maximization problems even approximately so for example with general evaluations you cannot in a reasonable amount of communication even non-deterministic communication achieve any kind of constant factor approximation if you combine that lower bound on protocols with my theorem on the translation it tells you then that no simple auction can get a constant fraction of the optimal welfare at equilibrium is 2 to the m minus 1 sub-exponential? no it's there's some constant there the proof works up to 2 to the cm for some constant c my guess is it's like a quarter or something like that but I didn't try to optimize that constant so it's possible you might be able to compress it a little bit I don't know but certainly you can't there's some constant c such that you can't do better than 2 to like less than 2 to the cm is not good enough we'll not be good enough so anyways the high order of it here is there's nice work by other people done last decade saying communication protocols cannot with minimum cost with a low cost compute near optimal allocations and therefore by this general translation theorem equilibria can't do that so that's how you prove it so you know wrapping up I think this is a very exciting time reworking in this area the interface of economics and computation I mean for 15 years there's been really cool research going on but really this decade I think we're starting to see kind of a major impact out in the real world from the ideas that have been coming out from this community so I just picked one case study I just picked the 2016 FCC incentive auctions obviously there's other case studies I could have chosen as well and here I tried to highlight two things so first of all in the reverse auction which is the new part which got actually there was freedom to design over the past few years computer science played a crucial role in what auction was chosen to implement and how it was implemented and how computer science techniques some other auction would have been run a few months ago and then on the forward auction side there aren't a lot of opportunities these days to influence design but still there are these 20 year old rules of thumb for people who work in the trenches lacking formalization and the price of anarchy for the upper bounds and communication complexity for the lower bounds is exactly the right language to turn those into rigorous guarantees so I'm very optimistic about the exact applications of the field in the years to come thanks very much I know economists feel about computer scientists are they eternally grateful or are they using this in a lot of things I would say in general I've been extremely impressed with how collegiate economists and game theorists have been especially in the early days computer scientists kind of really we were making a lot of blunders we were kind of reinventing the wheel periodically in the early days of the game theory and rather than the usual hostility and disdain that I think you get from some other field my experience has been very open, very patient saying maybe you should read chapter 4 of this textbook and then come talk to me again and they were right and so I think they're I think they've been in general very open minded they're actually the best economists that I've met I think they've been especially open minded and you know some of the stuff that we do they like some of it they don't like but they're fine with that and they cherry pick the parts that they do like and incorporate into their own research and I think that's a healthy relationship I mean we do the same thing with economics literature they're parts that computer scientists sort of reject for various reasons totally more or less totally unrelated fields you know John Von Neumann not outstanding you know I think it's been unusually successful collaboration unusually friction free actually do you write papers for economics? I so I don't write very many with economists I mean I'll you know so you know I'll send them my papers for comments and vice versa but we tend to ask different questions so anybody else have a question? I have a non-computer scientist do you comment on the role of technology in timing of the auctions? in timing of the auctions how often do the auctions happen depending on what you're talking about in the proper place? oh I see I you know my sense was I mean I think this may change but my sense was historically it's been more logistical and economic drivers determining the timing of these forward auctions when they were just doing forward auctions over and over again you know it seemed like it was a roughly regular schedule of how often they do it you know you could imagine this came up earlier you could ask is there ever going to be another double auction of this form if so when what will be the stakes then will they be higher or lower so certainly I wouldn't be surprised if the cost of buying back spectrum keeps going up because there's kind of less of it and so then it would suggest that you need on the buyer side you need to have that much more value you can extract from it which presumably would be enabled by some kind of new technologies so on that level again this is just speculative but I could imagine new technologies being the essential motivation for doing this again five years from now or eight years from now this is a little outside my expertise but I haven't seen evidence that that's been what's driving it thus far as much so thanks again ok


Hey Mustangs, my name is Dr. I, and I am the Vice Provost for Student Success and your Faculty Athletic Representative for the NCAA. My advice to you, if you wanna pass, you gotta get to class. The same way you can't expect to be your best self on the field, you can't expect to do your best in the classroom if you don't show up. So, you gotta get to class. That's where you meet your faculty, connect with your classmates, engage in all of the material. It's where all the good stuff happens. So, if you wanna pass, you gotta get to class. Have a great season and a great semester.


فشرف بالاشتغالي بالعلم ولا تبغي به ما عشت يا دا دا دا وياله من شراف عظيم الحمد لله رب العالمين له الحمد الحسن والثناء الجميل واشدوا الله إلا الله وحده لا شريك له يقول الحق وهو يهدي السبيل واشدوا أن سيدنا ونبينا محمد صلى الله عليه وعلى آله وأصحابه والتابعين لهم بإحسان إلى يوم الدين أما بعد سورة النبأ بسم الله الرحمن الرحيم عما يتسألون عن النبأ العظيم الذيهم فيه مختلفون كلا سيعلمون ثم كلا سيعلمون ألم نجعل الأرض مهادا والجبال أو تادا وخلقناكم أزواجا وجعلنا نومكم سباتا وجعلنا الليلة لباسا وجعلنا النهار ما عاشا وبنينا فوقكم سبعا شدادا وجعلنا سراجا وهاجا وأنزلنا من المعصرات ما أنت الجاجا لنخرج به حبا ونباتا وجنات ألفافا إن يوم الفصل كان مقاتا يوم ينفق في الصور فتأتون أفواجا وفتحت السماء فكانت أبوابا وسيرت الجبال فكانت سرابا إن جهن مكانت مرصادا للطاغين مآبا لا بثين فيها أحقابا لا يذوقون فيها بردا ولا شراب الساقا جزا حسابا وكذبوا بآياتنا كذابا وكل شيء أحصيناه كتابا فدوقوا فلن نزيدكم إلا عذابا وكأسا جزا حسابا رب السماوات والأرض وما بينهما يوم يقتصفا لا يتكلمون إلا من أدن له لك اليوم الحقا فمن شاءت تخذ إلى ربه ما يقول الكافر صورة النبأ صورة النبأ بإتفاق المفصيرين بمجموعة من التفصير صورة النبأ لا يوجد تفكير من العلم الله سبحانه وتعالى عما يتسألون ما يتسألون عما يتسألون عما يتسألون عما يتسألون هذا هو ما يكون عما صورة النبأ صورة حديثة صورة صورة صورة التفصير صورة على what صورة صورة صورة فالنون اضافت لذلك فقط اصبحت عم ماء عين و مين وهذا يشهد في القرآن و يشهد في العربية و إن شاء الله و تعالى سنرى بإذن الله الكريم في صورة النازيات و الله سبحانه وتعالى يقول في ماء ففي ماء هو استخدام مين ماء هو استخدام و لذلك لأنه اضافت لأنه يمكن أن يكون هناك سؤال الله سبحانه وتعالى يقول عم ماء عن اي شيء يسألوا كفار مكة ماذا are the disbelievers of Maka asking about هذا one قول هذا one opinion the second opinion regarding the scholars of Tafsir is the ones that are asking this question are not the مشركين they are not the pagans they are everybody so there are two views about who is asking the question the first opinion is the ones that are asking the question are the مشركون the pagans and the polyethists are asking this question إن شاء الله و تعالى we are going to see what the question is and their argument is because the reason why they believe that the ones that are asking the questions are the polyethists and the pagans is because the context restricts that meaning after that Allah is going to be saying and this is only referring to the pagans that's one view the second view is that the ones who are asking the question are all of the people the reason why they believe that is because as you are going to see later the surah is talking about resurrection and the disbelievers already have made their decision regarding the resurrection they don't believe in it and they don't differ regarding the resurrection they already believed that there is no such a thing as a resurrection that's why they said if we die and we become dust and we become bones and flesh are we going to be brought back? that's something that's not going to happen so they already made their minds up the other group of scholars are saying that this is everybody's going to ask the question and the reason why they believe everyone's going to ask is because the muslim also asks questions so his iman increases الله سبحانه وتعالى he says عما what are they asking about عنين نبع العظيم the second verse Allah سبحانه وتعالى says they are asking about the great news the scholars they differ regarding the great news and their differences is three opinions and we can emerge them into two opinions what's this great news in which they are asking about each other the first view is that what they are asking one another is the Qur'an and the affairs pertaining to the Qur'an this opinion is held by مجاهي ديبنو جبر they are asking about the great news the scholars they differ regarding the great news who is the student of Abdullah ibn Abbas he believes that what these people are asking one another is the Qur'an what is this and this is what Allah is referring to as النبع العظيم the great news the second view of the scholars is the great news in which they are asking about one another is an Ba'a the resurrection and this is the view held by قتادة بن دعامة السدوسي and ابنو زيد and ابنو جلين الطبلي رحمه الله he strengthens both of those opinions to the people who are attributed it to so he is saying it is authentically transmitted from قتادة that it's the Qur'an according to him and it's correctly transmitted from sorry مجاهد that it's the Qur'an and that قتادة and ابنو زيد their opinion are authentically transmitted so we have two opinions regarding what they are asking about الله says عما يتسأل what is it that they are asking about عنين النبع العظيم the great news the great news is how many things it's either one of two opinions either the Qur'an or it's either the resurrection and there's a third opinion which is that it's the Prophet ﷺ but it doesn't show so and the strongest opinion from the two is that they are asking about the resurrection but the difference here is not a contradiction meaning anyone who is asking about the Qur'an they are also asking about resurrection because the resurrection is mentioned in the in the Qur'an so this اختلاف is called اختلاف التلوء and the sebab of this اختلاف is called التواطق في الكلام because Allah ﷻ he removed the sifa and the most of from its sifa and this is something we have already spoken about مقدمة فقصورة ترسير على كل حال what is it that they are discussing and they are asking about is the resurrection الله سبحانه وتعالى he then says اللذي هم the resurrection in which they are فيه مختلفون in disagreement اللذي هم and if you look at it here Allah doesn't mention what they are disputing but Allah left it vague and ambiguous الله says اللذي هم فيه مختلفون about which they are in disagreement they became parties and they became groups regarding the resurrection and its affairs if we take the opinion of those who said that this is meant by resurrection then the parties broke into two parties a group that believes in the resurrection and a group that don't believe in the resurrection the groups that are believing in it are the believers and the ones who don't are the disbelievers if we take the great news النبأ العظيم is the Quran then they are differing in three the first group are saying إنه قولوا شاعر this Quran is the speech of a poet the second is they are saying that this man is a fortune teller and the third one is they are saying so the people are differing so whichever the view that we take if we say that النبأ العظيم the great news is the Quran then those who are disagreeing are disagreeing in three views the first view is they are saying إنه قولوا شاعر the other party are saying إنه قولوا شاعر and the third one they are sayingákلاء الله and another group are saying Suiteر العولين these are the stories of the early people محمد has been told stories تدرا munah فيتم Brea morning and evening somebody is dictating the Quran and writing it so we say إذا كنا نقول ما يفعله بالنسبة للنسبة للنسبة then there's a party who are accepting the resurrection and a party who's disagreeing the existence of the resurrection. الله سبحانه وتعالى هيدا يقول كلا سيعلمون ثم كلا سيعلمون كان Pourkalla in the Quran are only there and they only have two meanings, they only have two meanings. The first meaning is to stay away from something or to scold. الثالث هو أنه يأتي في الثالث يعني كما حقاً حقاً الثالث في القرآن فقط يعني هذه الثالث والذين are the only two meanings in which it holds and it is found in the Qur'an 33 times and it is only in the first half of the Qur'an الله.. so here what does it mean here ابن جليل الطابري رحمه الله he took the opinion that the kalla here is يعني الله سبحانه وتعالى يسيد ليس الأمر و الماته is not as these disbelievers are claiming and rejecting that الله سبحانه وتعالى is going to resurrect his slaves the question here is what are they going to know they are going to know that the resurrection is true and that every single body is going to be resurrected and that there's no way out of it those who say know that this is not talking about resurrection it's talking about the Qur'an they say سيعلمونه means they are going to know the day of judgment and now Qur'an حقاً that the Qur'an is true and everything that the Qur'an has told us is the truth وسيعلمونه and they are also going to know the outcome of their lying and their making up stories when are they going to know this and when are they going to find out the scholars they said that they're going to find out عِنَّ مُوتِهِمُ when death comes to them and the soul is taken out of their body and they're also going to know when they're going to their graves and the angels come to them and they're also going to know the day when they stand in front of الله سبحانه وتعالى they're going to know resurrection does exist and they're also going to know that the Qur'an is the speech of Allah and it tells the truth that day they will come to know الله سبحانه وتعالى it says then الله سبحانه وتعالى he tells us he says to us and I want you to ponder here الله سبحانه وتعالى is now going to start talking about the universal signs he's going to talk about the things that he has blessed us with and the things that he has done and there's a reason why he does this and I'll explain later when I finish all of the universal signs the things that Allah has favoured us with brothers and sisters everything Allah is saying here has a powerful meaning ponder Allah says have we not made the earth as a bed the word mihad it means a place like a bed we spread the earth out for them did we not do this in the Arabic language this is called الله is asking a question but he's actually asserting information he's actually establishing something against you this question that he's asking you سبحانه وتعالى is a question within it is yes of course oh الله you have and he wants you to wake up because when a person is asked a question generally it's a way to get his attention so الله is asking you have we not made and this نجع is we and it's out of royalty because the نحن in the Qur'an when it's used it is used as المعظم the one who speaks out of royalty المعظم نفسه the one who speaks out of royalty because we in the Arabic language is used as one of two one who is speaking and then somebody else is speaking with him and it's also used as a person who's speaking out of royalty so الله says ألم نجع هل لدينا المعظم المعظم المعظم as a bed we flattened it for you you are walking on it you are going and you're doing what you want هل لدينا this for you سبحانه وتعالى say to you then الله says and have we not made the mountains أو تا دن as pegs the word أو تا د is جمع وتد and the وتد in the Arabic language is what you use for a tent when you want to hold a tent when الله created this earth when الله created this earth this earth started to move so الله سبحانه وتعالى pegged the mountains on it so that the earth doesn't move and if you look at the world today the places that have more mountains generally don't have earthquakes الله has made this earth mountains on it for it not to move and not to shade on its people سبحانه وتعالى so الله is saying ألم نجعل have we not made الأرض مهادن have we not made this earth as a bed والجبالة and have we not made the mountains أو تا دن as pegs on this earth the answer again here is what of course سبحانه وتعالى you are the one who made this earth a bed for us a place we can walk on and spread it out for us and you are the one who pegged these mountains on this earth سبحانه وتعالى and I want you all to ponder here these mountains that are pegged on this earth what is Allah going to say about it later in the same surah how does Allah speak about the mountains you're going to see إن شاء الله وتعالى هنالك then Allah سبحانه وتعالى He says وَالجِبْ وَجَعْ وَخَلَقْنَاكُمْ Allah says we have created you وخلقناكم we have created you all as wajj in pairs the مفصرين they differed here what is meant by وخلقناكم as wajj and they differed in two views the first view they said as wajj in here means males and females that's one Allah created a man and then he created for every man a woman to fulfill his desires for the offspring of mankind to carry on Allah said I mean men and women that's one view the other view of scholars they say وخلقناكم as wajj in here means we have made you in different types one that's tall one that's short one that's good looking one that's not good looking one that's dark one that's light one that's a male one that's a female I have created you in different types so the scholars they differ what is meant by as wajj Allah says am I not with the previous question that's asked وخلقناكم we have created you as wajj in pairs or we created you male and female then Allah subhanahu و تعالى he says وجعنة and we have made no mat from your sleep but we have made your sleep سباةان as a thing for us the word سباةان the word سباةان here actually means in the arabic language in its linguistic meaning it means in this connection that's what it linguistically means like in ibn Faris in his معجم مقايس اللغة he defined it not according to his linguistic meaning but according to what would come out from its linguistic meaning in other words الله is saying I have made sleep a disconnection of tiredness in other words you relax I have made the sleep in your sleep سباةان means اقتع it means disconnection امال قطع something to cut what is it that's cutting from you the tiredness and the fatigue that you were enduring the whole day قطع and get disconnect from you what happens here الراحة والسكينة tranquility calm relaxation because who's the one who's giving you this you look at a person sleeping at night his mouth is open he doesn't know what's happening who's protecting him who's looking after him the minute he sleeps he wakes up and he's fresh his mind his head everything الله is saying I am the one who has made for you a sleep for you to find from that sleep a rest الله is saying سبحانه وتعالى then الله سبحانه وتعالى he says وجعلنا we have made for you الليلة the night we have made the night as a covering لباس and it means covering what is it that the night covers you from the night it covers you from the sun the ray that comes from the sun if it was 247 day time you wouldn't be able to sleep the sun would be in your eyes when you want to sleep you switch off the lights you make the room dark الله سبحانه وتعالى he says I have made the night to cover you so when you sleep and you relax you can properly sleep also I have also blessed you with this night that if you want to hide from the people's eyes because you have to remember back at those times the people they wanted to leave if they were scared of an enemy at night time I have made this dark pitch black a time for you to run away from your enemies so they won't be able to see you also this night and this dark I have covered it so the one who wants to stand up in the last day of the night and wants to come with sincerity so nobody sees him he's also able to stand up and الله says in the Qur'an and the people of Lord نجيناهم بصحب we saved them at night time سورة القمر آية 34 at night time الله saved them so when was it they traveled to get away from the enemy at night time so this is what I have done for you he says then الله سبحانه وتعالى he says we have made for you النهارة we have made the day for you الله is saying we have made it for you وقت لتعيشي a time for you to live and to get up and to go and to look for a livelihood to look for your risk it's made bright for you so you can drive so you won't hit somewhere so you don't need lights I am the one who provided you with a day where you can go and you can look for your risk and you can look for the blessings الله سبحانه وتعالى has given you طلبوا المعاش it's a time for you to get up and to live and to look for your livelihood I am the one who has done this for you الله سبحانه وتعالى he says and then الله goes on to saying we have built over you الله سبحانه وتعالى he says وبنينة we have built بنينة here means رفعنا we have placed over you محمد and all you believers and all of mankind سبع سماوات seven layers of سماوات why did Allah use the word شدادا شدادا here means محاكمة محاكمة this سماوات has actually been solidified look what Allah says هل ترى من فطور برجع البصرة look at the سماوات do you see any cracks in it no there's no cracks there's no cracks that are done to it الله سبحانه وتعالى has solidified it made sure that it's smooth and that it is there's no deficiency or cracks in the سماوات pay attention the samaوات that is like this at this particular moment what is it going to turn out to be later at the end of the surah and how is Allah going to speak about it سبحانه وتعالى