Credible Auctions: A Trilemma with Mohammad Akbarpour | a16z crypto research talks

Transcript

uh this is uh not a new observation uh victory in his 1961 paper in which he invented this auction format he basically said this is one of the problems at this option format that uh you can exaggerate the second highest speed uh and as a result uh uh bidders cannot bidders should trust the Chenier in order for this mechanism to make sense on the other hand in a first price option uh I'm gonna receive two bits B1 and B2 well the auctioneer could be an auction theorist who says Hey Muhammad I know that the fact that you had with 95 in a first place option means your value is

more than 95 so I'm gonna invert your bid identify your value and then come to you and say hey I know your value is 100 how about you pay me 99. now the auctioneer can do that but the key difference between this and the previous example is that now I can detect the action here without needing to talk to anyone else I can say hey this is against the rules of the game uh and this is again not a new observation William we carrying his again classic paper uh called first place auction automatically self-policing uh whereas uh the second price option is not like that so what I'm gonna do in this in the rest of this talk in the next 55 minutes is

to formalize the idea of automatic reset policing mechanisms which we actually call it credible mechanisms and see uh investigate the properties of this mechanism uh so we will get the to the formality but before that let me tell you that uh let me give you a lot of examples from The Real World that you guys might be interested in uh knowing that this is a serious challenge out there uh the first example is online advertising the like the second place auction has always been the lovely uh the poster child of success in auction Theory one of the reasons was that the online advertising platforms constantly use second place auction and around 2017

like the the the the the the like the people started getting worried that maybe ad exchanges are cheating in these second price auctions this is a quote from the industry newsletter that in a second price option raising the price flows after bits comes in uh coming allows the auctioneer to make extra cash of unsuspecting buyers so the way they they cheat in these auctions or at least that was the suspicion was that the bids come in and then you say hey my reserve price was actually higher than the second highest speed so you're going to charge them the reserve price which you invented after bits came in and the reason this practice persists is because neither the publisher nor the ad buyer has complete

access to all the data involved in the transaction so it's it's like one key part of our modeling uh and I think a lot is left to be done is how you model this data sharing type of like what what what's the information structure what do bidders observe we're gonna take one extreme which I will tell you uh but but there are so many like intermediate regimes one can think about um another example is like when we were working on this paper in 2019 2020 then 2021 and so on uh we were always asked okay but companies have reputation to lose like Google is not going to do that right there is no way they're going to

put their reputation at risk now what I'm gonna do since this being recorded is to show you a few codes from the recent lawsuits against Google these are allegations these are not like proofs uh I'm totally neutral in this case but this is one of the paragraphs in the like the Texas case against uh Google which says uh they invented this notion called reserve price optimization RPO that other roads or Publishers exchange floors and deceptively increase the amount advertisers pay for Impressions on Google Exchange so they had this idea that after they observed a bit they had this reserve

price optimization optimization that's the allegation uh the other example is uh this example from the same uh lawsuit that it's a piece from an email between uh people inside the company that one of them asks the other one doesn't that's what we are doing the RPO undermine the whole idea of second place auction uh either assurance that you can beat the maximum you're willing to pay with no negative one sequence but if the publisher manufactures the floor based on your bid to get you pay more than the second price this principle gets violated uh which is which is exactly what I just told you so these are a few examples of worries at least that people have

um and I mean I love this last part the auction uh if companies are allowed to do that they are allowed to change the reserve price this will defect to transform the system into a first place auction because if I know you can charge me my bit minus Epsilon from my view I'm playing your first choice option not the second place option uh so so we will see this would be actually this was one of the theorems of our paper that in the world of in the world in which you cannot trust action here the second place action would be played as if it's a First Choice auction um just just to make sure uh we know how an ascending auction Works in practice I mean you guys are in New York City these art options are happening all the time

and it turns out there's a question from the from the audience if that's okay so perfect would you mind going back to the last page but just a clarified question what is the publisher in this case for my own context like in the in the Google case is Google and publisher or who is no the the think of the publisher being the New York Times oh there is a display ad when you go to the New York Times on top of the page and advertisers compete for that uh the the ad exchange is the intermediary who receives the ads uh chooses the winner charges charges them the second highest speed and then uh puts the ad in the New York Times page and basically they pay

all of the money of the ad to New York Times except the take rate of 20 percent so yeah so New York Times doing the RPO or is Google doing the RTO over here uh the RPO is being done by by Google the the auctioneer so the auctioneer is is intermediating between the seller New York Times and the buyer the advertisers yeah think of think of publisher as as Christians like the the art house that is selling an art piece or the real estate agent that is selling your house to a buyer okay thanks perfect so in art auctions there is this like uh super exciting uh not exciting super

interesting uh the practice that's called chandelier building so in ascending auctions they say who is willing to pay 10 million someone says yes who is willing to pay 11 million and the auctioneer can say oh there is that guy who is willing to pay 11 million even though there is no human being who was willing to pay 11 million they can do that and this is legal based on New York City uh laws uh so the regulation allows you to have a secret Reserve prize which means you can fabricate bids up to a certain number without really having having someone who is willing to pay that now uh just to be clear uh if everyone is in the same room and

everyone is observing everything that's happening uh that's one way to think about communication and data sharing uh when we look at the data even in art auctions that are these ascending options most leaders are not in the room uh many of them are over the phone many of them are on internet online bidding so the way the communication happens is that like Crisis and satovies have these staff Who call these people and say hey the current highest price is uh 20 million are you willing to pay 21. uh or they are on internet so this flow of information how this happens it's going to be super important for us I just I'm

just going through details because that would be the key modeling assumption uh there was a question good uh great so what I'm gonna do in this paper uh we're gonna think of a world in which um think of auctions by telephone so you have all these bidders who are on different phone lines so they have a private Communication channel with the auctioneer uh and then we are gonna ask in which formats that does the auctioneer want to follow the rules of the game okay let me get a little bit more clear about this so that the communication structure is gonna be this

so the auctioneer has private communication Channels with each bidder but bidders cannot talk to each other the classic mechanism design communication structured is a complete graph so everyone can talk to everyone and sees everything okay so think of that as like there is like you can you can you observe everything that happens between everyone so here I'm assuming that no one observed feeders observe only their own communication with the auctioneer which is like a fairly reasonable assumption for the world of online advertising we could we could start thinking about like different contexts but let's continue with that uh so the auctioneer is going to be the Nexus of communication makes these

communications with the readers potential in multiple rounds just not not just necessarily one round and so the auctioneer can misrepresent to me what team has told the actually so I'm going to say that an auction uh is credible if it's incentive compatible for the auctioneer to follow the rules of the game in this form of communication structure and what do I mean by incentive compatible is that the auctioneer can play the rules of the game according to the book or the auctioneer can deviates but the deviation should be such that no single bidder can detect the action

okay I'll be formalize it using like math uh in like in 20 minutes but the idea is pretty simple it's that actually you can tell you hey the second highest speed was something else but cannot tell you hey your bit was something else or you told me in the ascending auction that you are still in uh but I tell you hey you said you're out so you cannot misrepresent to me whatever happens between us but you can misrepresent whatever happens between other people uh and those misrepresentations also should be such that they cannot detect you sometimes I can detect you because you said something that even with my information I can catch you I have a question like for the problem you're mentioning like what about um using let's say digital signatures

let's say the auctioneer must if I claim the second price is a I must present a digital signature let's say signed by Kim and with the claimed price like would that to solve the problem yeah uh that's a great question um in fact I'm happy to be here because I'm sure you guys are gonna come up with a lot of ideas around this so uh a couple of like uh like reactions in favor of the the idea on them uh the idea of the paper is that uh the auctioneer can always even invent those signatures in principle so in a real estate auction if you're playing a

second price option the seller cannot the seller agent can always like write down a fake offer so then you get to the point that you have to go through auditing and stuff like that to make sure these offers are real uh so these this like in a way you have to think about like the auctioneers cousin in in some boards the other one is like the logistics and in a way we are part of this paper is explaining why some auction formats were super popular historically before we had blockchains before we had cryptography before we had these signatures uh these are all things that could potentially alleviate The credibility problem in in settings that you can actually Implement digital signatures or I mean Matt Weinberg who

was visiting you guys he has uh I think three papers or two or three papers exactly around implementing credibility using uh cryptography uh so so that's a great question and you're totally right if that's possible then oh but but notice that in an auction in which uh people are not sophisticated at least that's that would be really challenging because now I have to trust the whole signature and learn how it works and stuff like that all right so maybe just to follow up on the question like you mentioned that the Auctioneer can invent it open participation setting where like the set of ditters is not known like let's say I can just create some

pseudonyms and join like the basically the auctioneer can pretend yeah in the model I'm gonna assume that uh the setup videos there's like n participants this is like this is of all potential participants like including the auctioneers cousin uh but but yes the answer I gave you is basically uh was outside the model I assume that Auctioneer brought someone from the outside about the model you will see the modeling again slide it's going to tell you that uh the number of billers is known example uh and uh it's interesting what happens if that assumption is dropped but anyways that's a great question and

how can you overcome this issue of credibility is very much context dependent it's very hard to do this uh digital signatures in some contexts and easy to do in some other context so uh let me move uh by just giving you a glimpse of the results I'm not gonna probably have time to prove these results but we will come back to them later but if you take this definition of credibility just to give you a sense of the like why this is potentially a useful concept if you take this definition of credibility and put it in the monitors and optimal option setting in a simple version of that suppose you have regular distributions myosin

regularity assumption you have ild values for bidders there is an Auctioneer who wants to sell an item and suppose Only Winners are gonna make transfers losers are not going to pay and suppose action Year's objective function is revenue then we know from the green Lafont holmestron theorem the green lafonte almost from at the same time proved this result that if you want a mechanism that's a static meaning that you have only one round of communication so people tell you their type and you do something with their types and you want a mechanism that's truthful it's a strategy group or dominant strategy incentive compatible these three names are the same for me uh then the unique

mechanism that satisfies these properties is the second price option uh so there is no other mechanism that satisfies these properties that's a green level strong theorem so the question we ask is suppose now you want a mechanism that's static but also credible we know second price action is not great that's my inspection uh it turns out that there is one mechanism that satisfies this property which is first place auction it's like Myerson first place auction with Myerson Brazil and it's the only mechanism that satisfies this topic so there is no other mechanism that's both

credible and static and then if you say okay I'm willing to give up this aestheticness I mean I'm happy to have a like Christie and sativity is like a dynamic auction type in the space of all possible Dynamic mechanisms that you can have is there a mechanism that's both a strategy a strategy proof and credible and the second main theorem of the paper is that there is one and there is only one essentially and that's a sending option the English auction in which you started there is a price and you increase the price Epsilon by Epsilon you don't have price jump you go just up at minimum allowed large number that you can go up

and that's the unique credible strategy propulsion so in a way this credibility uh together with the staticness and the strategy pollutants helps us think about like a characterization of three most common auction formats out there in the world uh you cannot have all three properties at the same time and each two of them characterizes one of the like classic auction formats this is all within the space of Revenue Max like Revenue maximal auctions right absolutely yeah one key exactly okay so if you gave up a little bit on Revenue maybe this design space would get a lot richer exactly so if if for example the auctioneer wants I mean if

there is any positive data on Revenue and some positive data and efficiency still you get this but if you only care about efficiency then all of them are credible so in a way it's it's actually a super important question that you asked him because uh credibility is highly tied to the incentives of the auctioneer so you have to tell me what is the utility function like the national residency matching program that Al Roth and his colleagues designed uh if the utility of the nrmp is the match is uh to maximize hospitals like utility then uh and uh then you can be worried about the credibility if it's to maximize doctor's utility then you

shouldn't be worried because they are running Doctor proposing so that's a and that's that's complex again all right and what does the regular IIT values mean on the left top Corner oh it means that each Beetle has a value uh for the item that is being sold the distribution is the same for everyone it's IID it's identical and independent and regular is just uh it says that the that like basically the will be the the value minus inverse Hazard beta distribution is increasing so it's a it's an assumption that many natural distributions satisfy but not all of them uh these results will go through even without regularity there are ways to do

non-regular credibility analysis Muhammad dumb question and we've talked about this paper many times but for some reason I've never thought about this before like what would happen if you created friction to the auctioneer manipulating like to what is there a sense in which making it hard relative I guess there's I guess it should sort of be continuous so if there's a sense which making it hard relative to the gain from misrepresenting the reserve price or something like that like you've you've mostly committed to it but you can pay some big costs to swap it out you're only going to do if the returns are high is that the right intuition yeah that's a great um

yeah that's uh we we have definitely we have not thought about those uh you could even include some small probability of being audited for example yeah exactly as yeah and then your start uh yeah I I totally expect that as that cost gets higher and higher like the the deviations become uh only for very highly profitable stuff you're gonna actually deviate from the rules of the game yeah that makes perfect sense cool thanks another question like when you say it's the only mechanism because that's also taking into account randomized mechanisms so is it like in the space of possibly randomized mechanisms yeah it is I should have been more clear yeah we are not totally rule outs like the the

chance moves uh uh the randomization if you assume you have a public randomization device that's a different thing because if something that everyone can verify the outcome of if for randomization you have to trust the auctioneer than that of course no mechanism becomes credible because the action year can play with the randomization however they like uh it's an amazing direction to see uh if there is a public randomization device uh what can you do with it with credibility well I I don't understand that point why why do you say if it's randomized it cannot be credible because it could be that it's the uh Auctioneer clicks randomness it doesn't improve it so so one feature of on jumping forward one

feature of credibility is that once you put a bit or report something to the mechanism you have to know exactly what would be your payment if you win if that number has more than if there is more than one number you could potentially pay then the auctioneer is always going to charge you the the higher number so either the randomization is irrelevant by the way I'm coming up with this answer on the spot maybe I have to think more and get back to you after the talk but if there are two numbers and the randomization is gonna determine one of them with some probability of course I'm always going to tell you hey the higher number ended up being the right number so one feature of them there is a result

in the paper that says the mechanism is credible if I know I mean it has to be the case that conditional on uh as a function of your report you exactly know your payment now what happens if randomization is publicly observable as I said that's that's actually interesting R2 yeah thanks uh Muhammad yeah I just wanted to ask in this ascending auction what will be the information that will be revealed to other bidders is it yes I will uh I will get there it's yeah let me get there by the end of the talk um basically you only observe your own comments so the ascending auction says Hey Abdul are you willing to pay 20 you

say yes 21 yes 22 no but you don't know really what's happening out there the auctioneer could have a bit of 21 or 22 or could not cool let me do a little bit of uh modeling uh those of you who know mechanism design it's gonna be uh obvious for those of you who don't know it's gonna be uh easy so there is a set of agents and uh and then there is a type of space which is like think of type as value potential values that readers can have so each Peter has a value for the item that is being sold there is a probability measure for the for the

types there is a set of potential outcomes in an auction it's uh who wins and how much they pay for example or who wins uh and how much everyone pays that's an outcome the utility of bidders is a function of what happened in the auction their tie to a real number so in an auction it's basically your value minus price the utility of an Auctioneer is the new piece in this model which is again a function of the outcome the set of types of all bidders to a real number so this could be Revenue but this could also be efficiency in which case the utility of the auctioneer is just about the type of the highest speeder and then for each agent we are going to

have an information partition which is the minimal physical restrictions that you have okay the auctioneer can potentially like create more uh limitations but one example of this partition that the bidder observed this is something that the auctioneer cannot choose uh that this takes this like this this notion of partition I have So You observe your own payments uh but uh You observe uh I direct my own payment directly observe it but I do not observe team statements now the auction could be designed such that the auctioneer even reveals team statement for me that's an option the auctioneer has but the auctioneer cannot hide my own

payment from okay that's that's the that's the key assumption here that there is a minimal level of stuff that you cannot lie to me for example you cannot sell me a fake Mona Lisa I mean that's that's nothing I can always observe whether I actually want the one that is so sure what's this probability measure oh it's just a distribution of types so for each person I know my own type value for the item but what I know about other people is just a distribution uh and Auctioneer only knows the distribution so like for example just the valuation distribution right exactly so think of it as the value distribution and auction

uh so we are going to work with extensive game forms I'm going to implement again uh and this is the part that mechanism design typically uh escapes because working with extensive gang forms is a mess we love Revelation principle because we don't have to work with extensive game forms but in this world we have to do it because we don't have the full commitment and the flow of information matters so I'm going to say that again uh is an extensive game phone with consequences in the outcome set X we are going to implement each game using this extensive game form uh I'm gonna assume games that are finites there are no chance moves

and players remember what they have done before so an example of this is an ascending option so in the first the highest part of the tree I go and ask up to are you willing to pay 10. if he says yes I go to the left if he says no I go to the right and then I asked him are you willing to pay 11. if he says yes I go to the left if he says no I go to the right so I have this like uh multiple rounds of communication now a strategy for the player in this extensive game form is a marking from the information set what do they know what do they observe their type to an action again it's in a way super simple in an

ascending auction your information set is this is the current highest price out there your type is something are you going to pay one dollar more or not um and then we're gonna do a few uh actions these are actually from shengu's obviously a strategy proof mechanisms paper which allows us to work with extensive game forms in a tractable way so we are going to prune again in the following sense if there is part of the game tree that for no types of players we're gonna play I'm gonna kill last part of the three okay I'm gonna make sure that anything that remains in this tree is is actually a positive probability event there's

some types of players that are gonna go there uh if I go to Team and say hey this is your information and you only have one action tell me what you do well I'm gonna take that action on his behalf it's I'm not going to ask him if there is only one option uh so each information set has at least two actions and the last one is that if I go to a team and say hey are you gonna play A or B in this information set and he says a or he says b but that changes nothing in the game I'm gonna ignore that choice choose one of them and and continue it again so these are without loss of generality in a sense that if I had a big game that is non-prooned that's uh credible the

pruned game Wizard will also be credible okay so for the world of credibility uh these are without laws for game theorists of the crowd the reason we do this is that we don't want to deal with beliefs of the equilibrium path and sequential equilibrium and all those massive stuff we're gonna work with the lovely base uh incentive compact with mechanisms because everything is a positive probability uh perfect so let me tell you an example of the of the what I'm doing here so this is an example of the second price option I go to player one and say hey are you willing to pay uh I basically I ask are you a five type or a 10 type uh actually before that let me tell you

about these observations so this is the second place auction player one can have a type of 5 or 10 player two can have a five type of 5 or 15. if player one's type is 5 and player 2's type is 15 two wins uh in fact if players 2 it type is 15 he always wins but the payment of player 2 is a function of player one style if player one's type is 5 and 2 is also five uh one wins at the price of five so I'm assuming tie breaking is in the favor of one if player one type is 10 and 2 is 5 1 will spins against at the price of five so this thing I have down here the information partitions is the key object

in my analysis player one what do player one observes at the end of the game player one observes that if he wins he observes a feeling he won at the price of five because that's the only price player one can win if player two wins then player one does not observe which price you pay okay notice that if ip10 and Player 1 and player 2 wins I know that player two should must have paid 10 but I do not observe it okay I mean that's if the action you'll follow the rules at the end this should have happened but I do not observe I cannot distinguish between these two

outcomes that's why I have them in this bracket which means from one's perspective these two are the same now from player two's perspective however if he loses he knows that player one one at a price of five so he exactly knows this and if he wins he knows that he won at a price of five or he wanted to play some ten so player two completely observe what happens at the end player one cannot distinguish between these two outcomes now what happens in the game I ask one hey what's your B he says my B is five I go to two what is your beat she says my bid is 15.

and notice that by having this in this like Circle issues around player two I mean player 2 does not observe player one speed this is a seal speed auction uh so player two says hey my video is 15. uh this is the outcome I have to choose two should win at a price of five in the first place in the second price auction the auctioneer is gonna change the outcome and deviate from the rules of the game and say hey player two uh you want and the player one speed was 10. okay this is the way I'm implementing a second price auction using this extensive caring for technology and this is one example of a deviation now here is uh what I'm going to formally Define but this path that is

green is what we call an innocent explanation an innocent explanation is a story that each player can say to themselves at the end of the game that justifies their observation so what player one observed in this game player one observed I paid five and I lost the game so he could say hey I paid five so we were here and then probably player two's type was 15 uh in which case I lost the game and player one cannot observe whether player two paid 5 or 10 so player find is completely fine okay this happened the story makes sense this is an innocent explanation for

player two player two observes that his own beat was 15. that one I cannot change so in my innocent explanation I'm always on the right side of this this this tree for player two um but then he's like okay I paid 10. can I justify that with positive probability yes if player wants type was 10 which I do not observe uh then I win and I pay 10. so this is a story that player two can tell herself and justify the observation in this game each player has a story that they can say as a result this deviation is non-detectable so I'm gonna say deviation is non-detectable if each

player has an innocent explanation for their observation okay that's gonna be like the the most important definition of the paper is this notion of innocent explanation that every player based on their own observation and what happened in the game can justify what happened with positive Pro there was a type of profile that could make this happen the type of players that would make this happen um so let me tell you a formal definition of uh this this notion uh so the way the game works I'm going to define a new game between the auctioneer and players that incorporates the the option or the mechanism uh in it

so it's kind of uh uh it looks complicated but the idea is pretty simple the way it works is that uh at each step Auctioneer can either end the game and choose an outcome uh or go to the next step uh in the this is step two the auctioneer chooses one player sends a message uh and tells this player hey if you are here in the game uh and then this player observes this message and chooses a reply privately and tells like Shania hey this is my reply uh and then action here observed this reply and goes back

to step one let me give you an example that completely clarifies this in an ascending option Auctioneer choose the first player goes and says hey the price is 10 million dollars are you willing to pay so that's the information set says hey you are the first player I'm coming to the price is one with 10 10 million dollars in or out player observes and says I'm in as a function of that I go back to step one either I end the game or I go to another play or the same play it doesn't matter so for any game tree that you give me this messaging game can Implement that game tree or you start at the top of the tree I'll go to the player and that point at that point and I say hey this is the

current information situation these are your actions choose one of them and then the reply comes in I go to the next player as a function of the reply uh so this is uh again from shingles OSP paper it turns out that actually it's even older than that for Newman and Morganson in in their book and Roger Myerson in his informed principle paper uh they they they Factor they found an ocean like this that says there is a there is a there is a person out there who can Implement any extensive game form using this messaging game now why this is a cool object in the world of full commitment the auctioneer commits to a strategy in this game that

actually implements the promise so this is the strategy of the auctioneer in this game I'm gonna denote it by S zero zero is the option here G is the game that the auctioneer has promised to play so full commitment says Hey in this game at the auctioneer is playing with players I'm gonna actually do what I promise in a partial commitment board the auctioneer can play this commitment or can deviate to any other strategy in this messaging game that no single player can detect and distinguish from that okay so the way we are going to Define these deviations is through this this messaging then so the auctioneer is playing a game with you and he is

allowed to change the strategy and not play the strategy that's committed conditional on the fact that you cannot detect let me formalize this notion of that's my last uh formalization which has the notion of innocent explanation defined so think of a protocol an ascending auction for example G and the strategy of the players so strategy of players in an ascending auction is like play uh yes up to the point that I hit your value and then drop and then Auctioneer has a strategy in this game in this messaging game that runs my ascending option the strategy is go to the first player ask in or out go to the second player as in or out back to the first player

again asking or out at the at the new price and so on as a function of the game uh and the strategy of the player each player is going to have an observation at the end of the game your observation is a communication sequence that you had with the auctioneer That's What You observe plus what happened at the end hitting an ascending option these observations would be the auctioneer came to me asking or out I said yes ask in or out at 11 million I said yes asking or out that's 12 million I said yes and then ask you know after 13 million I said no and then the outcome is that I lost again that's an example of an observation it's

a vector now here is the uh now of course this observation is a function of What is strategy Auctioneer plays what a strategy players play and the types of players so if I have the highest type my observation would be yes yes yes yes I want if I don't have the highest type it would be yes yes yes no I lost so this observation is a function of what the auctioneer does what other players do and what is everyone's time and notice that here I don't have this commitment strategy Auctioneer could play a different game and that also creates a different observation for me I'm going to say that the observation that you had as an

innocent explanation could be that the auctioneer did not play the writer strategy in a second price auction that Junior charge you your Bitcoin is Epsilon if so if this observation has an innocent explanation if there is some type of other players that if the auctioneer followed the rules of the game uh and other players have don't have those types the observation that this generates for me is exactly what it was it happened to me right now okay so notice what happened the auctioneer deviated played a different game charged me my bit minus

but I was able to find a set of types for other players such that if the auctioneer followed the rules of the game what I observed today as a function of this deviation is exactly that so one example is if there was actually a bidder whose type was 99 well what then paying 99 as the second highest speed is actually makes sense okay so innocent explanation is a type of other players that together with Auctioneer playing the writer strategy justifies whatever you experienced in the game and then I'm gonna say a strategy for Auctioneer is safe

if all players and all types of players have an innocent explanation okay so Auctioneer is allowed to deviate to any safe strategy which means whatever election year does everyone can tell a story that makes sense there are no inconsistencies in players observations in this sense SN just means there is no Dynamic strategy on the player's part or on the so SN is the strategy of the player in the in the uh in the committed in the committed game yeah so it's a remember a strategy is a full hunt engine plan so it says at each

point of this game three you're gonna do that maybe I'm not gonna hit a lot of the game three points but this actually includes the dynamic consideration because it's a full continued plan I mean I don't have a lot of time but this is actually kind of an unusual definition of the mechanism which is the gain the mechanism and the strategy of player together we typically say second price option we don't say second place auction and everyone bids truthfully but this pair that I have up here uh the gnsn says uh this is a second place auction and everyone is going to be truthfully oh I actually think this is a better way to define second place auction because when we say second price action is efficient we are implicitly assuming a specific

equilibrium strategy of players because there is a terrible equilibrium second place auction that I be the trillion everyone beats zero and this is not efficient so we are working with this pair so that it's clear that we are considering a specific equilibrium from a strategy of players and it's a full contingent plan but I have just a clarification question so everyone has this valid story but their stories may not be consistent right the state of I prime Theta minus I prime is not necessarily the same for our lives exactly exactly absolutely it's a very good important question for each player oh let me go back for each player uh I have a different story as I showed you in that graph the the Green

Path of player one was different from the Green Path of player two but each one of them has a consistent story for themselves okay so again this was the innocent explanation for player one uh the types of players that justified what they observed this was an innocent explanation for player two there is another example in the paper that I'm not gonna go through but uh it's not that the auctioneer can only change the outcome in this framework to actually can get a game like this and play an entirely different game so you can even deviate Midway and play a totally different game be proven the

paper that this game on the right is a safe deviation of the game on the left I'm not gonna get into that because it's a very long example but the thing I want you to get from this is that there are Midway deviations that the auctioneer can do it's not just changing the outcome do you mean the message schedule is not static it's not fixed a priority Midway deviations means yeah exactly I promise that if player one here said that I play right I'm gonna go to player two but in principle I can go to player three uh and uh and you can show that this is this is a this is a safe experiation it's not even like a tree right the game is like because the message ordering is

not um sticks a party he's like what might you talk about this extensive form okay usually the player is fixed at every level but now you're seeing the level the player at every level is now fixed uh yeah I'm saying that you exactly it's it's not fixing this there is no calendar time it's not that I say player two hey I'm gonna call you at 2PM uh but I have committed that I'm gonna call players in this order on the left that's I will call one as a function I will of that response I go to three or two uh and I can change that order that's possible to do in a safe way but let me not spend a lot of time on this because I want to get to the last bit of

definition I'm gonna say a protocol is credible if in the space of all possible safe deviations that the auctioneer has playing the commitment strategy what the strategy that actually implements what you have committed in the book maximizes The auctioneers expected utility so remember you commit you're gonna play a second place auction this creates for you a lot of safe deviations and a lot of deviations that are not safe I mean of course you can charge me number more than my bid that's not a safe deviation but we are gonna just focus on safe deviations and if in the

space of safe deviations uh the commitment strategy maximizes your expected utility then that's a credible mechanism and and notice that going back to the previous question uh this uh definition implies best responding to updated beliefs as well so these strategies that I'm considering are full contingent plans so it's it's like at any point as a function of whatever other players do I can I can change and play a different game uh and even though you can do that as a function of new information you're just gonna follow the rules of the game that's the idea here foreign

observation that in the world of mechanism design a mechanism and this like equilibrium strategy of players is based in scientific compatible and credible so you're satisfy both of these if and only if in this like messaging game the strategy that implements that protocol and the strategy of player is a base Nash equilibrium okay so that's how these walls get connected I Define this world of messaging game which is a game between Auctioneer and players a base Nash equilibrium of this messaging game uh if the commitment and strategy of the planner is actually a base Nash equilibrium together with the strategy of the players uh then you can only deviate to the like

safe deviations then your original mechanism is based incentive compatible and relevant uh so let me uh get to the auction application uh so this is actually uh funny because in the paper when we wrote we said uh here is an example of a Midway credible deviation so you're a seller you choose a price for the object and tell it to the buyer uh and the object is sold if the price of the buyer so there's an Auctioneer with a seller and a buyer the seller chooses a surprise the auctioneer goes and tells the price to the buyer and if the price of the uh

price of the seller is higher than the like the price that the buyer codes that he is willing to buy the the trade happens and the auctioneer gets a 10 Commission and we were like this is this is a this is uh has a safe deviation I can quote a higher price to the buyer and pocket the difference if the buyer accepts okay so you tell me you're willing to sell at 3.2 million uh I'm gonna say it was 3.5 million to the buyer and if the buyer accepts I will pocket the difference that's it this is a non-credible mechanism if I'm intermediating between buyers and sellers uh which was completely made up it turns out and this in this allegation case uh against Google again I repeat uh

this is an allegation but Wallace Street Journal wrote it so uh that Google had this project perilanka and this is exactly the Ben where London won the Nobel Prize by the way and the idea was that guy was doing this auctioneering between New York Times and bidders or the the Publishers and the bidders bidders coming without Denver like your projects bidders come in and beat 2016 10-5 Google is like okay the highest speeder is this guy he wins pays 16. I'm gonna get 20 of it as my take rate as the auction here and pay New York Times 12.8 the rest Google said okay let me drop this 16 bit

uh tell the New York Times that the second high speed was 10. but tell the advertiser who won this guy on the top that the second high speed was 16. I'm gonna pocket the difference the six dollar difference I'm also gonna get 20 of this ten dollars pay New York Times eight and we are gonna call this Bernanke pool I'm just quoting from New York Times I don't know whether this is right or wrong so this is exactly this uh non-credibility of this middleman being between sellers and buyers that's that if you're intermediating and getting a take rate you cannot really transaction if this is lower lowering

the quality of the bit why would it uh uh like why would it boost its own system overcome editors if the bids are systematically worse after the program well uh I I'm not sure if I fully understood the question but there is a there is a there is a huge level of Market power here for foreign they are they are they are not absolutely monopolists but they have a lot of Market power um I'm just reading the the New York Times quote on the right lower corner it says uh Google boosts its own system over competitors but the project

seem to suggest that Google is actually lowering the bids on behalf of the bidder so from the perspective of New York Times they're they're seeing worse fits coming from Google right so we're gonna make Google worse compared to its competitors why would I say boost itself over competitors well it yeah it's I mean uh trying to see uh so I mean I didn't get to the details so what Korean claimed they did maybe it's about this question you're asking that they use this pool later to supplement the bids of their own customers and make

make it more likely for them to win that was their claim uh so maybe that's what this is referring to the point I was trying to make is that it's if this is right it's pretty clear they didn't follow the rules of the game that's that's the only thing I'm going to point two so I'm not gonna uh have enough time to go through theorems and I totally expected that but let me just tell you that uh the fact that first place auction is credible is is by inspection uh if you want revenue and you have a bunch of bits the best thing you can do is to sell to the highest speeder a little bit the fact that this is the unique credible mechanism comes from the observation that any credible

mechanism should have the property that's at the point that you put a report in the mechanism you know in the auction you know that if you win you're gonna pay X because whenever there are two numbers you can pay X and Y and uh you don't know which one is going to happen the auctioneer can always charge you why there's a higher number so surprisingly or actually it's interestingly this is also a feature of the ascending option so this is a shared feature of First Choice option and ascending option in ascending auction when I say hey I'm willing to pay 21 million dollars I may not win but if I win I know I'm gonna pay 21 million dollars so there is no other number if there is

not a 22 million as an option on the table otherwise Auctioneer is always going to charge that so that's that's a shared feature uh the type of the ascending option that uh is credible going back to Abdul's question is just an ascending option in which I have agreed of values anyone can have the value of one million two million three million up to 100 million uh and I observe my own communication with the bidder but I don't know what's happening between other videos on the auctioneer uh and then uh you're gonna start at the reserve price ask readers back and forth are you willing to pay X yes are you willing to pay X yes X Plus Epsilon X Plus Epsilon he says yes and then bidder

2 says no and uh this is the payment uh this auction is credible I will not have time for to prove it for you uh well you guys can uh easily relatively easy to show that uh increasing the speed from this point and charging with the one more than what the rules of the game say despite the fact that you can do that that's a key point I can't tell this guy hey this guy accepted to pay 22 million are you willing to pay 23. I'm not gonna do that and the reason I'm not gonna do that is that there is a chance that this device says no and the expected costs because this guy may say no and I have no potential buyer

is outweighs the expected benefit of getting Epsilon more dollars from this guy does that argument rely on regularity at all or it does rely on like irregularity action you're totally right uh if you look at the proof uh it's completely gets to the point that I show that the expected the net cost is the virtual value so if the virtual value is negative neutral value so if the visual value is positive then you don't want to do that uh but we can do iron uh ascending auction too uh so there is a way to do ironing for the ascending option so I'm gonna close uh given the fact

that we don't have the the reverse proof by the way the the hardest proof in this in this paper is the reverse group of this theorem that there is no other Dynamic protocol that gives you credibility and a strategy goodness at the same time so let me conclude uh by uh basically this this picture that uh this notion of credibility managed to help characterize these three options uh all three properties together are not possible and it's even completely context dependent which one of these properties you may like the most like in an online advertising board you cannot have a dynamic mechanism you have to have a

static mechanism because of the limitations of the speed of light uh in some settings credibility is not important you can totally transaction here so you can run the second place option uh but which ones are crucial uh or not the point of this paper the point is that credibility is a feature that first place auction and ascending option share thank you for inviting thanks