Game Theory Lecture: Clinching Auctions & TTC Algorithm

[00:00:00]all right so welcome to what's gonna be the last lecture on mechanism design of the course next week we're going to start studying games that are more appear in the wild and talking about their equilibria and when they are close to optimal for this last week of mechanism design I want to study problems where there are constraints on payments so I'm going to be moving beyond the quasi-linear utility model that we've been studying thus far what do I mean by constraints on payments well one type of constraint is when players have budget constraints a maximum amount that they can pay another type of constraint is there's simply no money at all for applications where it's illegal or otherwise inappropriate and so this type of mechanism design is quite a bit harder in some sense there's not as much you can do but the other hand some of the greatest hits of mechanism design Theory do come from these kinds of problems as you'll see so let me just remind you about the quasi linear assumption we've been making thus far we've been assuming that every player strives to maximize the difference between its value for whatever outcome is chosen I'm using the multi parameter notation here so little Omega is just some possible outcome from capital Omega so it strives to maximize its value valuation for the outcome chosen - whatever it has to pay okay so its utility is linear in money okay so in particular at no point have we really imposed constraints on the payments beyond just the baseline constraints that we're thinking of them always being non-negative and always being at most the bid of the player okay so the first reason that we might want to consider situations where the payments are not quite so unrestricted or budget constraints so this just means that for a given player I there's a maximum amount it's kit could possibly pay now your first reaction to me saying this might be that this is kind of a weird extra constraints so like if you think about something like a single item auction then budget constraints usually you don't really need to include them in the model that's just sort of part of somebody's valuation remember when I very for the first time introduced evaluation I said think of it as a maximum willingness to pet so for if you're only selling one good you know if you can only pay so much feasibly you know presumably that's a cap on your valuation on how much you'd be willing to pay and so the budget we can string the valuation anyways but there are other applications where this makes tons of sense in particular situations where you might wind up buying lots and lots of things hundreds of goods and maybe you want some overall cap on the total amount of payment that you make for everything that's you buy and the application so you know economist auction theorists have thought about budgets a little bit over the decades but the application that really forced people to start taking budget constraints much more seriously start trying to develop better models better analyses of them was our old friend keyword auctions so some of the few of you may have done this but if you actually go and enter some bids on a search engine for various keywords you will be asked for among other things certainly the following two parameters so first of all you'll be asked for your value that is how much you're willing to pay for each click that you get on your sponsored link so this might be ballpark 25 cents something like that on the other hand depending on the popularity of the key burden question there might be tons of these search options in a given day a thousands or even millions and your so your ad might get shown your sponsored link might get shown a lot of times and if it gets clicked on a lot that's 25 cents times a very large number so you do want as many clicks as possible but you also want some control over your maximum expenditures this is the way in which most people reason about these kinds of decisions about their preferences over buying a larger number of in this case especially identical goods so by popular demand you know the search engines are happy to have this parameter and the advertisers are generally happy to have this parameter you're asked for a daily budget so maybe you're willing to pay 25 cents per click up to maybe a maximum of 100 dollars in a day up to 400 clicks okay or whatever it is that you're paying per click divided by a hundred dollars so some applications you don't really need them but some you really do so the simplest way to incorporate budgets into our vanilla quasi linear model is the following and this is somewhat extreme but it's still a useful guide so if your payment is at most your budget then like before you'll have quasi linear utility your value for the outcome - what you pay so I'm going to use the notation capital bi for eyes budget and it's just not okay to go over budget let's sit so your utility is minus infinity if you're asked to pay more than your budget it's easy to think of smooth versions of these where you just pay some penalty depending on the extent to which you go over your budget people have thought about those models but we're gonna stick with a simple one for lecture today okay all right and again the way I'd like you to think about this the new feature or the new sort of aspect of this mechanism design is a new set of constraints and mechanism design we've had constraints all along we've had our incentive compatibility constraints that's what gives mechanism design its flavor that often compiles down to some kind of monotonicity condition on the allocation rule we've had allocation constraints you know simple things like you can't allocate a good to more than one different person those are the two types of constraints we've had so far now there's a third okay the payments can only be a certain amount so limiting of the power of the designer also limits what you can do and mechanism design with constraints on payments is generally harder than in the models we've seen so far there's impossibility results things you can't do that previously we could with money okay without budgets so we develop your intuition for this so I guess we've seen one example of this already so we talked about how surplus was special okay so we had this VCG mechanism which maximizes surplus even ex-post so that as you do as well with respect to your performance measure with a prospective surplus as if all of the information was known to you in advance and so what was really special about surplus was two things basically we didn't have to worry about payments except in as much to get the DSi C property they weren't in the objective function all we wanted to do is maximize surplus we didn't care about revenue and they weren't in the constraints okay so when we lifted the payments to be into the objective function we had the week on revenue maximization and as we saw that required some modeling and technical innovations beyond surplus maximization we're going to continue to think about surplus roughly this week but now payments instead of being in the objective in the constraints and again that makes our lives more complicated okay for example we no longer have the VCG mechanism or the even the victory option in our toolbox so we can't maximize surplus in the ex post sense that we could with the VCG mechanism okay so we're not gonna get surplus as high as if we knew everybody's valuations of funds through telepathy this is gonna be true even in a single item auction if you think about it for a little bit so imagine we're just selling off one thing to say you know ten potential bidders and imagine bidders do have budgets and let's even imagine that we do have to let the thief or the budgets we know what they are let's say everybody has unit budget I argued that single item auctions aren't the best motivation for budgets but I'm going to use it anyways just to prove a point in this part of the lecture okay the point I'm trying to make holds very generally so but the valuations are private as usual okay so maximizing surplus in the ex post sense that we got spoiled with through the Vickrey auction and then the VCG mechanism extension for a single item auction that just means you always successfully award the good to the highest the bitter with the highest valuation okay so everybody has unit budget the evaluations can be all over the map we have no idea and we have to identify who the highest valuation person is okay and at this point you know we basically hopefully already see impossibility right so first of all what if we ran the victory option okay we know what the winner pays in the Vickrey auction as stated is the second highest bid second highest valuation no reason that to expect that to be at most one could be anything okay so maybe there's some other option that will get us full surplus but that does respect budgets what do you think we've got exercises to sort of talk about this point why not that's right so one of the main conceptual points of meyerson's lemma was that once you fix the allocation rule for example surplus maximization you have you have no remaining free parameters okay the payments are determined ok so we lose the Vickrey auction and therefore we lose the ability to maximize surplus even a single item option so the point of this example is that we got to do something different ok so then the question of course is what should we do so that's the subject of this lecture what should we do and so to handle budgets I'm gonna I'm only going to tell you you know basically one auction format but it's a very nice one it's called the clinching option the reason for the name clinching auction will be clear once we describe it so the original version of the clinching auction stood as a bell and the original version all asked you to go through in the third problem set the original clinching auction actually was not intended to deal with budgets it was intended to be an ascending implementation of the VCG mechanism for a special problem for so-called multi-unit auctions so the it was then adapted to the case of budgets and that's what I'll talk about today by Dobbs insky at all about five years ago so that's the that's the history lesson let me tell you the model so in lecture I'm only going to talk about the case of identical goods that was the subject of both of these papers that since Pitt extended but I'm just going to stay with the basic setting identical goods a lot of the times when we talked about identical goods I've also made the assumption that each bidder only wants one that is not the assumption today it bidders in general want as many of these goods as they can get their grubby little hands on okay again think about clicks or you just really want it you're happy to have as many as possible alright so as far as each bidder I well there's gonna be a private valuation and we're just gonna have a very simple model like our single parameter problems like our keyword auctions where your evaluation is just linear in the amount of stuff that you get things so if I give you K goods then your value for those K goods is VI times K so you're happy to have another good as many as you want to give me I get VIX for each time to give me another good in addition each eye each bitter eye has a budget VI and I will be assuming that these budgets are public by which I mean they are known to the mechanism of fronts then the budgets by assumption cannot be manipulated by the bidders only the valuations can okay now it would of course be better to have an auction which did not make this assumption which elicited the budgets from the bidders and was incentive compatible that you incentivize the videos to give you truthful valuations and truthful reports of the budgets and did the right thing that problem turns out to be harder if there's some impossibility results saying that things don't work the clinching auction is not incentive compatible I'll ask you to work that through an exercise okay so we're gonna make you something of public budgets it makes the the problem remains non-trivial but tractable and by solving it we'll get some will be guided toward you know interesting auction formats which is the point of this theory in the first place yep so public budgets so though what I'm going to do is I'm going to first describe an auction which is not the clinching option which is more naive but very natural and we'll look at how it fails and then a revision of that initial attempt will be the clinching option so we're going to do it in two steps question I'm sorry so as usual the bid will be the alleged valuation yeah but they do not have a second report for the budget that's the key thing so there's two parameters associated with the agent one we don't know so we don't one we do know so we don't have to ask them when we don't know so we have no choice but to ask them yes it's going to be dominant strategy so it will not be relevant okay so like I said so first I'm going to give you something which is not the clinching auction but it's more naive and so the initial idea is basically to use a market clearing price to allocate the goods okay one thing you know just to reiterate with the public budget assumption remember that our non example with the Vickrey auction the budgets were public there as well okay so the difficulty of budgets is present even when when budgets are known okay so what do I mean by using market clearing price so I'm going to describe I'm just gonna describe you the allocation rule and the payment rule at the same time I'm gonna describe this as a direct revelation mechanism but as should be clear from the description it's very naturally implemented as an ascending option last week we talked about some of the benefits of ascending auctions over direct revelation mechanisms and indeed I'll the balls original motivation was really to have an ascending of lamentation he wanted an analog of the English auction when you were selling many goods rather than just one but for simplicity in lecture I'm going to describe the direct revelation version okay all right so market clearing price that means we should somehow equalize supply and demand the supply is evident it's here on the board there's M goods so let me tell you about the demand - how much people want now that's of course going to be a function of the price the lower the price the higher the demands so to find the eyes demand at price P denoted di of P well there's going to be two cases okay so remember what bitter eye is like it has this simple valuation where every good you give it it has value VI for okay I'm going to write this down as zooming truthful bid so I'll go back to the convention of interchangeably talking about bids or valuations assuming that the truthful so first of all suppose the price is bigger than I value VI how many does it want none that's right the reason is because it's going to increment the value part by VI and it's going to increment the payment part by more than VI so that leads to negative utility alright good so how about that it's not what I meant to do how about of the price is less than the per unit value well let me give you a simple case so what if the budget was plus infinity what if there was no constraints on how much better I could pay will be its demand at a price P less than its valuation how many does it want all and there's no diminishing returns here every good you give it it gets a VI so if the price is cheaper than that give them all to me so the only thing constraining also those two things constraining I guess how many Goods I could possibly get the first is just how many goods are available so I'll cap this at M the number of goods the other is how much it can pay okay so the amount it can pay is this budget VI it has to pay that per good so bi divided by P is the number of items at price P it can afford okay this might not be an integer so let's also round down for good P is per good so that's the demand of avatar iit given price P so the higher the price the less the demand as you'd expect what's the demand at price zero you'd happily take them all and the demand at ends let's say an infinite price for a sufficiently high price it's gonna be zero actually just so you have good intuition for these demand functions let's think about this little bit more carefully exactly how it decreases okay so I'm raising the price P slope on this bidder okay this demand is only gonna drop there's actually two ways it could drop okay so the first way it could drop is if the price hits the bidders value okay let's say the demand is currently 10 at the current price and all of a sudden the price hits the value what the demand decreases by what from 10 to what it's a zero okay it's suddenly evaporates okay so it was some number some positive integer now it's zero what about the other kind of decrease they're gonna decrease is where the price is still well below the value okay but obviously with a fixed budget the amount you can afford is dropping as the price goes up so to suppose the demand drops for that reason at a given price but when it drops from 10 to something what's going to drop to not okay there'll be some price at which you can afford strictly exactly one less good than you could before okay so as we increase P the demand dropped either by a single unit or it suddenly goes to zero I guess I didn't quite specify the demand function when the price equals VI I didn't say what it was and that's because you know both in the auction itself and in our analysis we get to be flexible okay when VI equals P you know the bidder could care less how many items you give it at that price it's totally indifferent so we'll define when P equals VI di FP to be whatever's convenient for for the what's under discussion okay again as usual we can't violate bitters budgets alright alright so now what does it mean to choose the market clearing price it just means we're gonna sell items at the price which makes supply and demand the same you know what supply is it's just M we know what the demands are they're just as di of peace so but P star be the smallest price P so that supply equals total demand so if you want to be nitpicky there need not be any prices where this holds with an equality and that's because as we just observe demands can suddenly drop by like 10 so then we have to look at the point where everywhere to the left of that point all smaller prices the demand strictly bigger than M and all prices a little bit bigger the demand strictly less than it and there will be something such a point and then what do we do just for all I we give di of P star goods to I at the market clearing price P star so that's the first cut of the mechanism and I've defined for you both the allocation rule and the payment questions well I mean we need to prove aesthetic compatibility right so guided by all the way back to the Vickrey auction we're sort of amongst prices where someone would accept that good you always take the smallest one it seems like the right thing to do questions all right so the good news is in contrast to the Vickrey auction or the more general VCG mechanism budgets are going to be respected by this mechanism we go user error okay so recall the definition of demand I guess this is where you see right so if we allocate to a bitter I D I of P goods at a price of P then by the definition of D I of P the amount that it pays is at most V sub I right we defined B sub I of P to be the largest number of goods that the bidder could afford at that price P actually the minimum of that or 0 if the price is bigger than the value okay so just by definition of demand budgets are going to be respected the bad news is and when I guess the bad news yeah not DSi see okay since the bad news I'll give you an example essentially the problem here is something that plagued us on Wednesday with simultaneous ascending options as well which was a form of demand reduction so in effects a bitter preferring to get more Goods sorry a shooing getting more Goods at a high price opting instead to get fewer Goods at a lower price okay and bidding in a non truthful way to make that happen so here's an example and hopefully this will also kind of make sure that we all understand how the clinching auction works so just two Goods and two bidders let's say and again remember budgets are known so let's say we're well aware that the first bidder can't afford an arbitrarily large amount of payment but we don't know its value let's say it's private value turns out to be six okay the second bidder let's value in there its budget are both five okay so what's the market clearing price assume for the moment the bidders bid truthfully so bids equal values what market clearing price would we then compute so remember the market clearing price is the smallest price at which supply equals demand and prices don't have to be integers so what are like five point five what's the demand at five point five total that's also Elite ooh right we only need a price of five plus epsilon for the second bidder to have demands zero okay at which point the for the first bidder has demand two which clears the market so the smallest of all prices that equalize the supply and demand would be five plus epsilon for some arbitrary small epsilon so we'll call it five among friends so suppose number two bids five number one bid six so we agree that the price will be five so who gets the goods so bitter one gets both so it's the utility of bitter one with this allocation payment combo that's right so you get a utility have one for each good for a total of two so the risk of plunging my foots into a bucket of water let me work out the rest on this part of this part of the board there's a bucket of water right there does it make sense given all the rain we've been having okay so demand reduction remember the idea is it can be better in a poorly designed auction or a manipulable auction to get fewer Goods at a low price as opposed to more goods at a high price so imagine that it's a bitter one a can't-miss report it's demand per say all I can do is say it has a different value at a lower value so suppose number one bids three instead of five and said six excuse me all right so let's think this through so let's think about bidder number two for a second okay so when the price is zero we're very close to zero what is bitter two's demand it's to its habitat both okay what's the price at which bitter twos demand drops below two two point five as soon as the price exceeds two point five it still wants goods as many as you give it like only afford one of them okay so the price two point five we have a demand of two from bidder number one and a demand of one from bidder number two so we're not at a market clearing price yet but something interesting has happened now once we get to the price of three remember bidder number one falsely bid three okay so that's the point at which we're on the verge of kicking bidder number one out okay and so that's the point at which the auctions going to stop okay so again remember when P equals VI and I define the demand according to my convenience so let's just I'm gonna set the demand equal to 1 for bidder number one when the price equals its false bid three okay the demand from bidder number two is still one so that's where the market clears okay at the price of three now the bad news for video number one is instead of getting two goods like before now it only gets one the good news is the price for that good is no longer five now it's three so what's the utility of bitter number one with this false boot of three three six minus three its value minus the price so that's a concrete demonstration that's with the market clearing price based auction it's not D si si so it's been a while since we talked it since we've put on the mechanism on the board any auctions that were not incentive compatible okay we sort of had a rich enough toolbox this had stopped happening to us okay so what happened here well we went back to the approach of designing the allocation and payment rules together and evidently we did it incorrectly okay notice this is totally a single parameter problem okay budgets are known that's just a private VI for each bidder so this allocation rule I'll let you check this the allocation rule is monotone so by meyerson's lemma there are payments that would make it a DSi C mechanism evidently we got them wrong so we could go back and derive the DSi C payments the meyerson's lemma would give you but I'm not going to do that turns out a different allocation rule well it's smarter allocation was going to work better okay so this is going to be the clinching option so again I'll describe this in its direct revelation form what I encourage you how to think about how this might be implemented in ascending form again that was the original motivation for this clinching auction technology so we're not gonna have a price which inside our algorithm we think of ascending at some steady rates rather than allocating all the goods in one shot at the end we're going to allocate them piecemeal at different prices so I'm going to keep track of this current supply s which is of course initialized to em while goods remain while they're still demand I'm going to raise the price I'm going to raise the price until demand falls and by demand falling what I mean is I wait until there's some bitter eye so that if I let the other end -1 bidders take what they want at the current price there'd still be some left over for bitter eye ok so maybe there's 10 Goods left there's 20 bidders out there in the world and if I just let these 19 bidders take what they want the price is actually high enough that some of these 10 Goods still remain on the shelf so s minus some of the other bidders of their demand at the current price remember as we increase P these are dropping this is staying fixed this is how many goods are left this is what people want at this price this goes down as the price goes up so once this is positive let's call this number K I guess I should also remind you what these demands are is it up there oh good its deliverer okay the demands are defined in the same way once this happens once there these K good left over even if you're the one and minus one better to take what they want I let bidder I have these K goods at this current price of at this current price of P so these are goods that these are called clinched this is the name of the clinching auction okay so these Goods that you get that I gets at this point these are its goods forevermore and the prices that it pays for them are fixed right now this price will go up later on in the algorithm doesn't matter for these particular K Goods that I gets right now P is what it has to pay for them and maybe the main thing that the clinching auction does differently than the market clearing price auction is that it go ahead and keeps track of the reduction in budget with a couple things so first of all it promises goods at relatively low prices early on in the auction and then second of all to make sure that all the prices come out correct at the end it keeps track of bidders reduc keeps track of bidders budgets and reduces them as they clinch goods so it decreases the supply by the amount that it should namely K it's a decrease s by K and bitter eyes budget by the amount that it's now committed namely the K goods that it's clinched times the price that it's going to have to pay for them okay so unlike the first auction based on the market clearing price a bidder will not necessarily pay the same price for all of the goods that it acquires the price it pays for the goods will get higher and higher as the auction proceeds so I'll go through an example go through the same example in fact but any questions about the auction before I hide the pseudocode for a minute you can afford it you're gonna afford the goods by the definition of DJ other questions that's a good question so it turns out arbitrarily arbitrarily works fine yeah so you can even do them simultaneously so arbitrarily yeah so just to be just to be clear with respect to the demands remember the demand of a bidder at a given price part of that definition is how many you can afford at the given price the price is increasing as always so that makes the demands drop but remember the clinching auction is keeping track of the past expenditures of a bitter eye okay so you decrease the review you really tracking residual budgets not original budgets and so of course when you compute demands it's with respect to residual budgets not with respect to original budgets yep as I said you break ties arbitrarily let's revisit the example so let me remind you the example it's up there perfect two goods first bidder has infinite budget value six that was the one who had an incentive to reduce its value previously to get one good at price three instead of two goods at price five each bitter two has budget equal value equal five so what happens with truthful bids now so initially what are the demands initially when the price is zero they're both two right so from each bidders perspective the other one doesn't leave any on the shelf so we need to look at the first price point at which somebody's demand goes down we already talked about what that was that was a price 2.5 once it's 2.5 bit or number 2 cannot only afford one okay so again bitter twos demand drops to one at the price of 2.5 leaving one on the shelf okay so this condition is triggered with bitter number one at the price of 2.5 k is equal to two minus one there's a one good left on the shelf we go ahead and give it to bidder number one at the current price which is two point five now there's only one good remaining okay so for this for there to be something left on the shelf when everybody else goes it has to be we have to wait until the price is so high that one of the bidders demand drops to zero okay so that happens once it's equal to five the valuation of the second bidder at that point the second bidder is kicked out and that's the price at which bidder one gets its second good so the prices are less than with truthful book bids in the nandi si si market clearing mechanism and the truthful bids bidder one paid five for both that's why it had an incentive to do demand reduction you might hope and we'll prove a more general statement you might hope that getting the prices right in this sense would take away that's and send it for demand reduction so theorem indeed the clinching option is d s ice now you know one way we could prove this again this is a single parameter problem so in some way the the way that I've trained you to prove this is to write down the allocation will formally compute the matter of some payments and then check that we got the payments right check that the payments here are actually the Morison lemma payments you could do that it would work turns out in this case I think it's easier to just verify directly so that's what I'm going to do okay so proof so I fix some bitter fix bids by the others so a sort of a trivial observation the one that kind of helps you orient you for this proof right so don't forget that your value per unit of good is always the same whether it's the seventh good that you get or the 20th good you get it's always a VI okay so what would any point in the auction if you pay less than VI you're happy if you pay more than VI you regret it okay so the price is going up at this steady rate so there's this prefix of the option from time zero up to VI where any goods are just you're happy to have and then in the suffix of the trajectory after the price is VI you don't want anything because the price is going to be bigger than your value so note Goods clinched when the price is less than your value respectively bigger than your value contribute positive respectively negative utility top okay so basically you want to be present when the price is less than your value and you want to be absent when it's higher the other important observation is that what's the role of your bid in the clinching auction okay so let's remember how we define the demand of a bidder okay so if the current price is less than of bidders bid then we just define your demand as how many Goods you could afford at the current price since according to your bid you want as many as possible okay and as soon as the price exceeds your bid we effectively kick you out of the auction okay your demand is zero forevermore as soon as the price exceeds your bid okay so you're kicked out exactly when the price reaches your bid kicked out in the sense that your demand is zero forevermore so I'll just go through one of the cases since they're symmetric so let's just compare two situations situation one you bid truthfully bid your true value VI situation two you bid something less than VI okay well if you bid less than VI how do the initial iterations of the option change you'd be less than VI well as long as the price was remember thing about the case where your bid is less than your value so if the current price and the auction is less than your bid then these two worlds are identical effect so remember your demand it's just your budget over the price and then we know your budget that's public or we zero it out at this threshold okay so before we hit your bid your demand is independent of what you did okay it's just your budget which is known divided by the current price so if you've like formally by induction or whatever run the auction in parallel with the true--but VI and the smaller bit bi they're exactly the same and the price hits the smaller value the bid okay the auction is identical and execution up to that point and then what happens why is it different well suddenly you're kicked out with the smaller bid okay so there is no change in how the auction proceeds until the price reaches your low bid and so when I say the algorithm execution identical again I mean on the one hand with your true bid and the other hand with a smaller bid VI so the prefix up to the price bi is exactly the same the difference with the false bid is you're missing out on whatever happened in the clinching auction when the price was between bi and VI okay you don't know what happened but whatever happened could only have been good for you right the only thing that could have happened while you're participating the auction and a price less than the value the only thing that could happen you could have gotten Goods at a price less than your value and you just threw them away so summarizing the only thing that happens when you bit lower is you lose some Goods on which you would have otherwise earned positive utility obviously not a good idea the case where you bit higher is similar again run the auction in parallel with your true bid VI and this over bid bi nothing changes as long as the price is below VI the algorithm executes identically the difference is you stay in the auction longer with this high bid of BI what can happen in the when the price is bigger than VI unless thing idea the only thing that could happen is you get some Goods at a price higher than your value giving you negative utility you don't want that so that is why the clinching auction is D si si okay cool off well I think it's a cool option think about I haven't really proved to you in a very meaningful sense that it's a cool option what I proved it was D si si and they want to give me another D si D si si auction that respects budgets give the goods for free price zero budgets a respected D si si okay I have not actually given you any formal sense in which the clinching option is better than giving goods away randomly I'll tell you a secret people are still to this day kind of struggling with the right way to do that there's some valiant attempts there's some nice Theory here there are senses in which the clinton auction has been proved - in various worst-case senses have good surplus now what I mean good surplus good compared to what I certainly don't mean good compared to the maximum possible surplus compared to like the VCG surplus because we know even in a single item auction when all of the budgets are known and equal any DSi si mechanism could have far worse surplus than the VCG mechanism that didn't have to respect the budgets so I don't mean compared to the benchmark of the VCG mechanism that benchmarks just too strong to make any comparisons so that means you have to go back to the drawing board and think about benchmarks that are weaker but also just smarter that take into account that any solution has to respect budgets so there's a few ways of doing that I'm not going to cover any in the lecture they're all just sort of would take a little bit too long so the original paper that proposed this clinching auction for budget stubs in ski levy and Nissan they focused on a property Pareto optimality so they observed that the clinching auction outputs a Pareto optimal allocation what that means is is if you consider any other allocation in which some player is better off ie has higher utility there's a different player that's worse off okay so this is a relatively kind of weak notion of sort of efficiency to economic efficiency okay there are other allocations which are maybe incomparable where some players are better but other players are worse and what was nice about their contributions is they derive this sort of uniqueness result saying that if you care about Pareto optimality essentially the clinching option is what you have to do if you want to but respect budgets okay the drawback there is that Pareto optimality isn't you know it's need not be a necessary or sufficient condition for a mechanism to be optimal in various other senses so a second approach is the same one we took for revenue remember even when we put payments in the objective function we lost this ability to have a single mechanism which is always the best one and the first thing we did is we introduced Lucian's it did average case analysis and then what you might like to say is a simple versus optimal result there's a nice mechanism like say the clinching option which is almost as good as a possibly very complicated average case optimal mechanism so that's been there's been work on that very recently just appeared maybe four months ago even that only handles the case where everyone has identical budgets but that's good progress from just a few months ago and then a third approach people have looked at is they try to sort of redefine the welfare objective function in ways that it's a smaller number okay that takes into account budgets alright there's some progress here too but it's it's fairly ad-hoc at the moment but you'll get some more experience with that in the exercises so the takeaway is the clinching auction seems like a great idea it seems like an awesome auction in some sense and we're struggling with what that means and this is actually not uncommon research and research it's often that you find the solution before you know exactly what's the problem that it's solving and this is one of those cases I got one more really nice mechanism for you today that's all I'm gonna have to say about budgets for the rest of today and for Wednesday's lecture I want to make the constraints on payments still more stringent if you like I'm gonna sit the budget stall be zero okay so I want to talk a little bit about mechanism design without money this of course is I tie your hands even tighter as the designer so you can do even less but again there is some really quite beautiful and also practically useful mechanisms in this space all right so I've probably conditioned you to be thinking so much about auctions you're probably wondering whether it's an oxymoron to talk about mechanism design without money but really mechanism design is just about what do you do when preferences are not fully known Apriori it's not really about and then you know different flavors of mechanism design give the designer different abilities to interact to implement things some situations money is illegal or otherwise morally repugnant so organ donation okay tinnie exchange we'll talk about some on Wednesday there are markets for kidney exchange they do not use money at least not in the US last I checked Iran was the unique country that actually had a legal monetized market for kidney exchange not saying money never has anything to do with voting but it's supposed to be illegal the way kids get assigned to elementary schools and lots of different cities around the world it's done with Mecca doesn't design with no money the way recent graduates from med schools are assigned to their residency's same thing okay so there's lots of applications we'll talk more about them on Wednesday main thing I want to do today is just tell you a really nice algorithm really nice mechanism historically called the house allocation problem so there are n agents each begins with an initial endowment of one house you may covet other's houses you may want other people's houses more than your own in fact you have a total ordering over the houses that's your preferences suppose you wanted to take as input these n houses that the agents currently have and if you like to rearrange them but again with each agent having exactly one house you want to do that in the best possible way that make people as happy as possible what's a sensible approach something about the top trading cycle algorithm TTC a which is going to propose a particular reallocation a reassignment of the N houses back to the N agents which in some sense is the best allocation you might want so we're going to construct the allocation iteratively we're going to be deleting agents in bunches after we've fixed their reallocations the agents that remain will always be in possession of their original initial house conceptually for the agents that remain you imagine asking them you say hey of the houses that still remain that is the houses that belong to the remaining agents point to your favorite ok so remember you started with this total ordering over houses some of them have disappeared they've gone the other people bummer of those that are left tell me your favorite so you can think of this as defining a directed graph where the outdegree everywhere is equal to 100 agents each one chooses one outgoing orc maybe agent 2 is coveting agent ones house but agent 1 says well I like my house thank you very much and then maybe you have something interesting where 3 you really likes fours house who really likes 5s house who really likes threes house in any case when you have a directed graph whose outdegree everywhere is one you're gonna have at least one cycle ok start at a node just follow these outgoing arcs you're gonna repeat there may be more than one but it's gonna be one for sure this directed graph has two cycles ok the self loop that counts as a cycle and then there's the 3 4 5 cycle so there's at least one cycle the algorithm then picks one if there are many cycles it can pick any one that it wants I'm gonna pick the cycle it does the reallocation suggested by the cycle for example in the three four five cycle you just go ahead and give fours house two three you give fives house two four gives threes house two five if you pick the self-loop it's a cycle then one keeps its own house after you've done the reallocation you delete those nodes from the graph they're gone okay so and it's gotten their final houses whatever they got from the cycle that's what they get at the end of the day this terminates with a new allocation or with an allocation each agent gets exactly one house so it seems like a nice algorithm hopefully so is it any good does it does it have any reasonable properties let's just to build up your intuition let's start with a sanity check I claim at the very least you're not going to be worse off than where you started okay so every agent maybe it keeps it same house maybe get some new house but in any case the house it winds up with it likes at least as much as the one that it started with and it suggests a proof of why that's true yeah okay good so succinctly I'd put it you always have the option of pointing to your own house as long as you're in this graph okay so remember if you don't if you don't get if you don't participate in a cycle you keep your house for the next iteration okay so every iteration you're in the graph you have your house you can point to it if you want if you point to something else it's because you like it even better every agent is processed at some point in this algorithm when it's processed its given the house that it's pointing to which at that moment is going to be either its own house or something that likes them okay so that's good at least you can't do harm with this algorithm okay so let me again before I'm gonna have time to talk about welfare properties but let me just talk about incentive properties if you now imagine that these total orderings are unknown private to the agents there's an obvious direct revelation mechanism you could run tell me you're ordering I'll run this algorithm and then I'll output that allocation and of course there's no money okay and the claim is that direct revelation mechanism is dominant-strategy incentive compatible so if I'm going to reallocate goods using the top trading cycle however them tell me what she really wants it's always a good idea you just mean as far as how things get reported okay good good question so good question so the question is sort of comparing kind of what I asked for in the two different mechanisms we've seen so far and one thing that's really cool about this housing allocation setup is the space of preferences is very rich right so you know what I don't know about you could take on n factorial difference values so this is not a single parameter setting there's not a single number or two single numbers that summarize to me how you feel about everything okay by contrast when we were talking about the clinching auction we assumed that upfront that I need your budget and from that and your value I could conclude your demand at any given price okay okay so why is this true all right so now of course that we don't have money I mean we can't even speak about meyerson's lemma I mean for multiple reasons one this isn't single parameter there is structure from the problem but it's a different type of structure but to the whole point of meyerson's lemma was to give us the payment to make it D si si right we really need the payments to be zero okay so we're gonna have to check the D si si condition directly so fix I and as usual the other reports and suppose with a truthful report by I alright so we won the top trading cycle algorithm the Pyxis cycle does the reallocation deletes picks another cycle does a reallocation deletes cetera et cetera et cetera so that's some number of iterations let's say L iterations and it picks a single cycle in each so let's call the cycle C 1 up to CL semicolon and let's say that I lies in the Jade cycle ok the only fixed I we think about a truthful report we run the algorithm this is where we get so now let's think about what is eyes power we have various missed reports it might give and the way we can think about a miss report is that in each iteration of the top trading cycle algorithm it points to some other house it points to somehow a worst-case house for the designer a best-case house for itself so if we give I the power to point to different houses and what way can it influence the execution of the top trading cycle algorithm so let's say I with a truthful bid has chosen in the 10th iteration okay so let's say J equals 10 does this bitter have the ability to change what cycle gets picked in the first iteration how to do that to close another cycle by making a worse bit rights okay good good and so then what would be the case so I didn't point to itself it pointed to if it points to something else in the same cycle it's gonna be a worse house can be a house of like less okay so basically so eyes only ability to influence cycle chosen is two points to a house it likes less to close a cycle mmm-hmm said again sorry I didn't hear then its own you mean oh okay less than its own that's the complaint likes less than its favorite okay so this leads gonna be a little informal here this leads it's being allocated that's of a closest of the cycle and it's chosen right now the point is it's literally going to get that allocation right now okay we used to being allocated a worse house than before okay so details I'll leave for you to check I believe it will yes yes yes so in fact the way it's usually described it's just you delete all the cycles in the first iteration but but I'm almost positive it's uniquely defined okay so this brings us back to where we were with the clinching option okay I told you it was D si si and you'd be right to respond you know seems like a cool algorithm but so what another D IC mechanism would be to just output a constant allocation okay just always force bidders to have the same house that they started with so in what sense is this bitter better well here the theory is much more satisfying okay so here there's a sense in which the top trading cycle algorithm does the uniquely best thing I don't have time to discuss this in detail but I'll put some details either in the notes and or in the problem sets so this is the unique allocation and what's called the core okay and so basically what the core means is it's a there's a stronger version of incentive compatibility where if you imagine some subset of these bidders get to say there's a hundred agents overall with this allocation it's impossible for some subset of ten agents to sort of break away from the mechanism reallocate their ten houses merely amongst themselves and all be at least as well off as they are in the top trading cycle algorithm at least all as as well off plus one strictly better off okay so you cannot point wise do better than you're doing in the top trading cycle algorithm no matter which subset of agents you're talking about so claim one is that the top trading cycle algorithm has that property the allocation that it outputs no subsetting to better by breaking away the second claim is that every single other allocation fails to have that property every single other allocation is vulnerable to some subset breaking away doing exchanges only amongst themselves at least one will be strictly better off and no one will be worse off compared to this allocation so more on mechanism design without money on Wednesday see you then