We're going to speak about some varieties of auctions to get a sense for the richness of this base. Because we often think about auctions about something very specific, but in fact auctions are very broad. And auction is any mechanism that allocates resources, typically scarce resources among agents who have their own interests, and we know of many examples. The governed sale of whether the electromagnetical spectrum or mineral rights, drilling rights for oil, what have you privatization of national assets. Those are all typically put to bid in one way or another. Stock markets are very famous two-sided auction where there are many buyers and sellers. RFQs, or requests for quotes, are a standard mechanism for a company or a government to solicit offers to supply them with goods and services at the most attractive terms. These are often called reverse auctions. We already mentioned the FCC's spectrum auction by way of sale of natural resources. Real estate sales are often conducted on some kind of tender or bid basis where multiple people make offers according to certain rules and certainly consumer based auctions such as the one that come back at an Ebay are very famous, where everything from cars to old CDs are sold. There are many other examples and we should bare in mind that often the goods being sold are not necessarily the standard one to think of in auctions. As a computer scientist, I should point out, many applications are auctioned in competing environments. So for example, metric bandwidth is a scant resource and there is an opportunity to auction off the right to use bandwidth to highest bidders. In advertising auctions, famously on Google and other advertising platforms, advertises bid for the right to present us with certain offers when we search for certain keywords, or even when we just browse certain web pages there are display advertising. And they, too, are open for bid. There are peer to peer networks and many other applications in the computing environment. So what are the kind of auctions we see? In fact, the space of auctions is infinite. Here are some examples that begin to illustrate the richness of the space. So we'll go over those in order English auction, the Japanese, the Dutch, the First-Price CO bid auction, at the Second-Price CO bid auction, and finally the All-Pay auction. So lets go over those in turn. The English Auction is probably the most submitted format. This is the sort of thing that in art auction houses, a mechanism used there. So auctioneer starts with some initial price, often called the reservation or the reserve price. And bidders in the auction shout ascending prices. And at some point they stop shouting, the auctioneer may try to cajole them into suggesting higher prices, but at some point, nobody says anything at that point, the auction is closed, and the highest bidder wins the good at that price. The Japanese Auction is less common term but it's similar to the English Auction. In that, it's an open outcry auction and the price ascends. Except here's the auctioneer that calls out the prices, whether explicitly or by some mechanism like a clock that just continuously rises. And think of all the bidders as being in to begin with. They're all standing there, and maybe the auction starts at zero dollars for a television, and everybody says, I'm in. And then, the price starts to rise slowly and at some point bidders decide the price is too high for them and they sit down, they are out of the auction. And this is irrevocable. Once they sit down, they cannot stand back up. And when you have only one bidder left standing, they get the good at that price. This is very similar to the English Auction. It's a little easier to analyze among other things, because the price does rise continuously, and you don't have what you call jump bids, where somebody suddenly offers a price that's much higher than the current price. And if you want to think about it in terms of a game representation, you can imagine that in the English Auction, every point of the game you have many branches corresponding to the different sort of increases or the jump bids one can give, whereas here the game involves in a single predictable way. That is the auction that's often called the Japanese Auction. And staying on the international theme, we have the Dutch Auction. This is a more standard term, and it's so called because this is in fact the mechanism that, to this day, is used in the Dutch flower markets. So how does the Dutch Auction work? This is a descending auction. Like in the Japanese Auction, it's the auction near that cause that prices. Again, whether explicitly or by a mechanism and in fact, in the Dutch flower market, it's a clock that starts at, that everybody can look at and starts at a high price and gradually goes down. And at some point the bidder claims the object, say the flower palette by shouting mine or as is the case in the Dutch flower market hitting a buzzer and when they hit it they get that goods for that price. So you can think of it as a game of chicken, obviously everybody would like to get the good at the lowest possible price but if you wait too long somebody could beat them to the punch. This is a Dutch Auction Moving on to sealed bid auctions. We get off the international theme. These are called sealed bid auctions, because unlike the ones we've discussed so far, there's no open outcry. But imagine that every bidder writes an offer, a bid, on a piece of paper and seals it in an envelope and hands it to the auctioneer, and the auctioneer opens the envelope at the same time and then decides what the outcome of the auction is. And here are two examples of how this might happen. The most common auction is the First-Price Auction, or First-Price sealed bid auction. So in this case, the auctioneer picks the bidder with the highest price as a winner and have them pay their price. Seems very straightforward, and a very common mechanism. Second-Price Auction is almost the same. It's, again, the highest person who bid who wins the auction, but they don't pay what they wrote down. They pay what's the highest rejected bid, what the second highest bid is. And you might scratch your head for a moment to say, why would I want to do this? For example, if I want to maximize my revenue as a seller, should have give us money if I did the Second-Price? But when you think about it, the answer isn't so simple because by changing the rules of auction, people would bid differently. In fact, there's a famous result called the revenue theorem that shows that under certain conditions, many auction formats look very different. In particular, the first and second-price seal bid auctions actually in expectation fetch the same price. Here for varieties of very different sort of auction, and it's the All-Pay Auction. And so, you have a good for sale and maybe the good is a $20 bill. Now, imagine that I auction off this $20 bill. And here are the rules. If you bid at the auction, you can write down any amount you want, on a piece of paper, and the highest guy will win the auction. So if you write down $3 and you're the highest guy, you'll get this $20 bill for $3. If you lost, you will still have to pay your bid. That's why it's called an All-Pay Auction. And now, think for a moment, what would you bid in such an auction? Surely, so tempting, you'd want to bid something. Wouldn't you bid at least $1 for the right to win this $20 bill? What happens if this wasn't a seal bid option but an ascending auction? And people could bid $1, and then somebody could bid $2. How would you bid in this auction? So we've seen several auction type now, the English, Japanese, the Dutch, still bid auctions, the all-pay auction. And this might suggest to understand this base of auctions you should enumerate the different auction types and study them. But in fact, space of auctions is infinite. An auction is simply a negotiation mechanism. That is first market-based. So that means that there's some set of rules that govern it and typically involve some sort of currency of the marketplace, for example money. It's mediated by a central authority, the auctioneer, and it has very well-defined rules that everybody goes by and everybody knows that everybody goes by. They're common knowledge. And there are three kind of rules that we need to specify an auction. There are the bidding rules, there are the information rules, and there are the market clearing rules. And if you specify those, you specify the auction. So what we mean by bidding rules? We really mean who can bid, when they bid, what they can bid, and some restrictions. There are, for example, in an ascended bid auction, I have to bid the current highest price. In other auctions, I have to bid my own price. We may not allow people to bid arbitrarily high. We may put some budget constraints. Bids may have expiration dates. They may be subject to withdrawals or not, and so on and so forth. So these are all the bidding rules. Very importantly are the information disclosure rules. And for example, in a sealed bid auction we, when I bid you don't see my bid. But do you know that I bid already? That is a very important information from you. Do you know who are the set of people who might be bidding? So information dissemination here is very critical to the marketplace and has to be explicitly specified. And finally, when all is said and done, the bidding is done, based on information that the agents do or don't have, you need to clear the market. And the market clearing rules are also multifaceted. There's a question on when to clear. So for example, we might clear the markets many times. If we have multiple goods we may clear the market once and a certain set of goods will be sold and clear again and another set and so on. You might for example, decide when to clear based on activities. And so, in some of the online auctions you'll see that the auction ends at noon or after a period of ten minutes of inactivity. That is, ten minutes during which nobody place any bid, whichever is later. It's a very interesting market clearing rule. So that's regarding the timing, then the allocation and the payment, in other words we've the market to say, who got what. Who got for example, in case of single good, who got the wango and who pays what. And we think it may not only be the person who won who pays. For example, in an all-pay auction, everybody that bid pays. Once we specify all of that, we specify the auction, and we're done.