Episode 269: Auctions with Kshitij Kulkarni, Matheus V. X. Ferreira and Tarun

Transcript

foreign [Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online [Music] this week we dive into the topic of auctions with guests Kulkarni a PhD student at Berkeley in the eecs department and Matthias fajeta a postdoc at Harvard tarun is my co-host for this one but he's also the co-author of most

of the work that we cover we share a history of auctions in the real world in finance and advertising and in blockchain and then explore how different types of auctions are used in these different scenarios we then cover their newer work built for more recent blockchain use cases such as Mev and nft auctions and then look at the incentives of both auction holders and the participants and how these designs might influence the effectiveness of the auctions themselves in the last stretch of the episode we look at how zkps are being incorporated into some of these designs and how this might be an interesting new problem space to try out Advanced cryptography in now before we start one of our sponsors for the upcoming ZK Summit 9 had a quick message jump crypto is inviting all researchers

academics and protocols to join them for ZK week happening in Chicago from May 15th to May 20th expect six full days of inspiring talks from Top researchers shoulder to shoulder collaborations and plenty of opportunities to build meaningful relationships head over to jumpcrypto.com ZK week to apply we'll add the link in the show notes and as mentioned ZK Summit 9 is happening next week as well as zika hack Lisbon and so we won't be releasing an episode next week we decided as a team to give ourselves a little pause so that we could focus on making those events amazing if we don't see you there then you will hear us back here on April 5th with our next episode and now Tanya will

share a little bit about this week's sponsor [Music] Elio is a new layer 1 blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a roll-up if you're interested in building private applications then check out Elio's programming language called Leo Leo enables non-cryptographers to harness the power of zkps to deploy to centralized exchanges hidden information games regulated stable coins and more visit developer.alio.org to learn more you can also participate in Elio's incentivized testnet 3 by downloading and running a snark OS node no sign up is necessary to participate for questions join their Discord at elio.org forward slash Discord

so thanks again Elio and now here's our episode [Music] So today we're going to be exploring the concept of auctions in all of their forms with our guests Kulkarni a PhD student at Berkeley in the eecs department and Matthias fejera postdoc at Harvard in the School of Engineering welcome to the show thanks a lot for having us yeah thank you very much I'm very excited to talk about our work the work we're going to be talking about today is entitled credibility and incentives in gradual Dutch auctions this is work that the two of you wrote together with tarun who's also here hey Troon hey everyone all I have to say is as both the host and a

guest this time in some ways co-hosts and a guest I'm excited to talk about this paper because somehow you know we we haven't talked too much about like ZK applications and I really feel like this is one of the first things that is in that vein that you know I've spent a lot of time thinking about because I've been on this podcast a lot interesting okay so before we jump into this let's learn a little bit about UK and Matthias do you want to introduce yourselves Matthias why don't you go first yes I'm currently a postdoc at Harvard so before I did my PhD at Princeton in computer science so I'm generally my research has been look into aspects of security

algorithmic economics and cryptography and I think cryptocurrency and blockchain general is a very exciting area to actually be combine these different aspects of computer science so tell me a little bit about the kinds of work and research like what is the exact field of like what have you been working on yes so auction design has been one of the errors I've been doing a lot of work so I've been very interested on this aspect of Designing credible options which are essentially options where you cannot trust the auctioneer so it's a very different take from traditional economics because often you assume the auctioneer is honest um

to follow the auction their promised to do but in practice uh auctioneers might actually try to manipulate their auction to increase Revenue um yeah yeah and and that has been a problem in especially in the internet because you don't you really can't see if you're not actually is manipulating their own auction over the Internet because it's just a black box right the only thing you see is you're sending your beds and you're getting a quote of how much you need to pay um and and you really don't know what the auction it can be doing there so this is interesting it's almost like you were just studying auctions period

not necessarily like auctions in a blockchain context but like yeah I first learned about these kinds of I mean I'd heard about auctions generally but I guess the first time I started looking into them was very much when they were being used back in 2017 for some of the like Ico token sales that was the first time I started to see and specifically these Dutch auctions Mateus actually also spent a lot of time doing research on proof of stake attacks and um attacks against transaction fee mechanisms like EIP 1559 so he's actually done a lot of other crypto related research in his PhD so I feel like we shouldn't Short change some of that because it's actually kind of

relevant because we've talked about a lot of that in the show ah yes I can say more about it so um yeah the way I might take on that is I try to understand the different aspects of blockchain so auctions I see as an application but also incentives they take a very important role on the layer one blockchain so something I've been very interested is to understand when proof of stake blockchains are what we call incentive compatible which means that when miners have incentive to actually follow the protocol because when a designer basically creates a new product called they're basically telling what miners should do but you really have to

incentivize them to actually do that so I have done some work on uh how on actually analyzing protocols one particular was the algorithm to protocol uh where we unders we try to understand the the incentives of the protocol and and I have some other work where we try to design alternative uh proof of State protocols they are incentive compatible and as Tyrone was saying also in in the application lab when you start going more in the higher levels of the stack I have done some work on transaction fees in particular I got interested on that after the EAP 1559

came around where I was basically trying to understand what would be the equilibrium properties of that protocol and and we had the a paper on and analyzing the eip1559 and actually proposing alternative designs for that cool it's okay let's hear a little bit about your background what have you been working on what led you to this problem yeah so so roughly I would sort of frame my PhD work as sort of following the area of of dynamic incentive design or dynamic mechanism design so that those are split those three words into it you know what they mean so Dynamic something that's happening over time so people are interacting with a mechanism or an

incentive system over time um and then of course incentive design is the problem of sort of a social planner or a central planner trying to get some self-interested people or agents to do something that is good or something that you know as he wants yeah and I've been also working with Turin recently after getting nerd sniped on this Mev problem um and so we really got interested in these gradual Dutch auctions because they have sort of all of these properties that their options that happen over time and uh there is this sort of very interesting problem like how do you incentivize players in these auctions to to do well as as Mateus was saying uh to be incentive compatible for

the auction to be credible uh but now over time instead of sort of in this one shot context uh so yeah so that's what got me interested in this problem the problem is sort of dynamic and happening over time and thought it was very interesting cool tarun now I'm curious how did you get to this problem where for you did auctions first pop up is it through Mev as well or is this something you've been tracking I think you know when I was working in trading um I used to trade a lot of the opening auctions and one of the things when I was doing that was you know maybe it's like 2014 or 2015 I spent a lot of time reading kind of books like Tim rough Gardens 20 lectures and algorithmic Game

Theory and um no Nissans like random books on like auction complexity and automated market makers actually by santome and a couple others and at that time I was just trying to understand like how well the theory of what people had written in algorithmic games Theory actually matched what people really do when they're training against auctions so you know unlike crypto most markets in the world have a beginning and end time and the way we you go you know the markets closes or begins is there sort of an auction for the opening price of the day or for the closing price okay and so people are bidding in the auction

for what the opening price should be at like 9 30. before they open the market trades continuously before it opens and that's the price that starts at and then people can fill the order book based on that interesting and one interesting thing was like I had noticed like different exchanges I was trading on had like very different designs uh and I was just trying to understand like how I mean this is one of the reasons I I like didn't like working in trading a lot of times the people around me would just be like oh yeah that's just the way that's just what the spec was that we got for like why it works and I would always just be like why did they choose that auction like what's the history that we went into like your ex using some weird Dutch auction but like

the CME having just like an ascending auction whose clearing price was like some random reserve price of like some initial price earlier in the morning they have some sort of like notion of overnight training but it's like a it's a different instrument technically um and so I just like never really understood how those were chosen and whether they're manipulable or not and how to reason about their property so my journey had started then and then I think once I had been in crypto I just observed that you know yeah transaction fees are basically a certain type of auction and Mev those sort of auction and and it did feel like it was much more reasonably designed than the ones

that people were sort of using in finance or even maybe the Spectrum he's like Legacy systems yeah I think the ones in finance like because they work well enough people are just like yeah whatever they're fine and also there's a centralized entity running it so you don't even have a choice it's just like this is the auction that you use whereas I do feel like in crypto there's this idea that like hey you could always make it better I know that nerd sniped me that's maybe the longer short story long going back to that kind of time though or like just that system in traditional markets the fact that it's built this way do you think like have the actors working in those systems developed all of their strategies around it so it's not only the centralized entity that would need to change but

like everything built around it would need to change is that also what's potentially holding it back um I think yeah certainly the participants who've become good at it obviously are entrenched with into not changing the auction format but I also think there's um there's some legal requirements for different types of assets for like how things should clear so for instance um indices like if I trade the S P 500 or I trade the fdax and or the in in Europe or you know something like that indices trade overnight but the overnight products are actually sort of like Futures on the opening auction price so your trade you're kind of

guessing what the opening auction price is and if you hold it to the opening auction you can convert that future into real asset at the opening auction price um they're sort of the sellers of the opening auction the Futures holders but like single name stocks don't have that right so it's like if I you know go and buy Tesla or something there's not an auction for Tesla stock individually uh oftentimes but there might be for you know options depending on how the day how much liquid there is so there's some regulation on the index auctions versus like single name things and and that part is very complicated and encumbered by history not not due to like mechanism design that was just like

this is just the way these markets evolved and that's it and so I think like crypto gives you a new way of actually kind of getting to outcomes for solving the same problems but maybe using more well-designed techniques do you think there was even an intermediate step between the kind of traditional ones and crypto and the reason I say this I know before just earlier in this episode I just said that I first kind of understood auctions with the Ico stuff but actually I just remembered once upon a time worked around like marketing and AD Tech I didn't do ad Tech but I was like aware of what it did and over there there's a

ton of auctions right that's like it's digital so it's not dealing with like stocks and opening you know it's not that much Legacy I think this is I mean I'm guessing this is like 15 20 years old a lot of that stuff so would you call that sort of the intermediate step like it does that does that make sense that it would be like that that was sort of a place where some sort of the experimentation that might get used in crypto today might have started sort of um you know like or is it such a different product no no no so so like at a very high level and I think hopefully we talk a little bit about the Google antitrust case because it's related to this at a very high level the auctions for online ads are extremely high

dimensional but very sparse and what I mean by that is when you bid on Facebook you're bidding on a category a category meaning like female London buys lots of clothes drinks green smoothies who is this person I don't know I'm just making up I'm making up attributes right but okay there's categories right and there's sort of like a set of these kind of tags that's and there's a huge number of them right for for different cohorts of users and each cohort is its own auction right so like you can bid on that cohort and send and send it and so you have this huge number of options possibly like exponential in the number of users there

might be even more tags than users oh wow um but there are very few auctions that are active at any particular time because there's only like certain cohorts that are using the product right so that's what I mean by sparse that's very different than the finance auctions which are extremely continuous and dense like there's many people concentrated on just bidding on like what the S P 500 should be when it opens yeah right and Nev is sort of a mix of the two of those interesting but the interesting thing is like people really invented a lot of the automated Market making literature in the late 2000s I mean I guess they it sort of existed early 2000 but you know I'd say there was like a big fervor for it

around the 2010-ish and a lot of that was done at tech companies because people had thought maybe over optimistically that people would be doing these like high dimensional ad auctions in automated market makers but then people proved all these really like sad impossibility results and then people kind of gave up on automated market makers and like crypto people accidentally figured out yeah a different way of doing it right so uh I I'd say there's definitely a very interesting connection where the online ad world is the middle ground but then the online ad world as sort of some of the Google case shows it is a bit gerrymandered because people aren't even making their own bids right you can't

even control your strategy like Google executes your strategy for you so yeah yeah uh so it wasn't really like a fair market on like say at the Mev Market interesting so now let's start on the history I mean we've kind of touched a little bit about it but like let's cover the history of auctions in the blockchain context do you know kind of where this starts like I said the where I first saw it was in 2017 for these kind of Ico token sale type things but yeah I don't know if either of you or if any of you are actually aware of earlier cases what those look like yeah so it's actually auctions start very early in the coin paper right so Nakamoto when he's is already thinking that he's gonna have

way more interest for actually sending transactions in the Bitcoin Network then actually would have spacing blocks so he proposed the use of a first price auction to actually sell that space in the market so auctions have been around since the beginning of blockchain are the fee like the Bitcoin mining fees built like auctions actually then yeah so the transaction fees are exactly bids on a the transaction fees were were in fact a bit on a first price auction is basically the same concept where in the boxing space we just call transaction

fees but in mechanism design we call them bids okay actually continue that story then where do we next see kind of examples of auctions yeah so then I would say with the rise of I uh the initial coin offering so auctions have been used to as far as I know that was the Second Use case for auctions versus actually how you uh start a new market around a new coin um even more recently we have seen anyfts which are another example of a resource that's scarce and an auctions an ideal case on how you can actually allocate something that's scars and you don't know how much how much you

should price it so so that's I would say that's the second use the for good case after so the first one would be Bitcoin transaction fees and then the initial coin offerings and now we have nfts where options are very important actually to how you allocate and sell nifties and I guess Mev yes in the early days of Bitcoin there were definitely also a lot of like off-chain auctions that were settled on chain so like there were auctions denominated in Bitcoin blockchain effectively centralized but then they were settled in Bitcoin and I think that was one of those times people were like I wish we

could actually write the auction as a in Bitcoin script but like people then like could never quite do it I I do sort of remember there being an auction an nft auction on bitcoin for one of those like rare Pepe type of like very early Proto nfts but it was like a weird auction and I don't think it was like first price or Dutch it was like sort of some weird thing where like you would post your bids to the blockchain and then like there were a couple instructions I would like pick which bid to to take but it had a maximum size of the number of bids and people were ddosing it or dosing it I I I just remember reading about this but I can't remember where whether it was like rare Pepes which is like this

like early Bitcoin nft type of thing or something else but this is like 2014 people where people tried to implement auctions and it like didn't really work on bitcoin very well I'll just say one more thing about the history of these auctions um which is that uh in all three of these examples of sort of the block space on the Bitcoin Network or icos or nfts the kind of item that you're selling in all three of these contexts are very different so in the context of the Bitcoin Network you're selling something like what should one unit of space on the Bitcoin Network be worth and that's the scarce resource that you're trying to price in the icos you're trying to price something like what should these you know have this

batch of sort of fungible tokens and I'm trying to understand what should what should those be valued I don't know what their value is I'm trying to discover their value over time in the context of an nft you have one single item whose value you're trying to figure out or like a batch of you know replicas of single individual items that you're trying to figure out and these are sort of very different kinds of of say products that you're trying to price uh and it's sort of it's a you know I I find it remarkable that sort of the same auction Theory helps you price all three of these different very different kinds of products so like it's scarce block space these fungible tokens and the these you know non-fungible sort of very unique products that uh that you can

sell for you know different prices yeah that's just a little bit more on the history of these auctions cool so I want to go back to something that tarun just said this first price and Dutch I want to understand each of these and how they relate so let's start with this first price what is a first price auction yeah so so roughly uh auctions can be sort of split up you know one way of splitting up the space of auctions is are they something called open outcry or are they are sort of public auctions or are they private auctions so okay in public auctions you know there's going to be some kind of a uh open outcry process either the auctioneer is going

to be saying what the price is at any given moment and or the bidders are going to be saying what their bids are at any given moment and this is sort of the classic one where people have signs and they put up like I bid this and then they're like stamping okay exactly or it's private in which case uh the bidders are going to submit some kind of bid to the auctioneer in a sealed kind of format and uh and those bids may or may not get revealed afterwards the price may or may not get revealed afterwards uh and so English auctions are sort of they fall in this kind of in this open out choir kind of format they've been going on for hundreds of years uh and roughly their format in which uh the the seller is going to ask every buyer at every time hey do you

want to remain in this auction if you want to remain in this auction you have to raise your bid by at least some amount um and so he goes around asking everyone this and you know this is a fine process that people have been doing for a long time it's like poker I just realized right yeah is poker a form of auction do you want to raise or phone right yeah yeah okay and and so this is in contrast to these first price sort of usually first price sealed bed auctions in which the bidders are now going to so there's going to be sort of one pro like sort of a one-round process for getting the bids to the auctioneer so everyone submits sort of these sealed bids via some kind of you know they have some phone call with the auctioneer this is how they

still do these auctions at I don't know uh when they do these art auctions at Christie's or whatever um and they're going to submit their bids and the auctioneer is going to decide who the winner should be and in a first price auction the auctioneer decides who the winner is and he says the highest bidder the highest bid that I got that person wins and they have to pay that same price and they have to pay the highest price this is in sort of uh contrast to other kinds of auctions uh in which that's not the rule in which the rule is something like the highest bidder still wins but he has to pay the price that the second highest bidder to the auction and these are called second price auctions

okay yeah auction theorists are not that their naming was very like yeah it was very simple but did they ever do the average somehow the to the top person gets to pay the average I guess that would just cause the weirdest incentives people would just go higher higher higher they'd never have to actually pay it so so there are these things called all all pay options in which whoever wins the item pays but then the losers also pay like everyone pays oh they just don't get anything right and they don't get the item so yeah so there's all sorts of variations on you know what what kind of pricing rules you can have what kind of allocation rules you can have but

roughly the the space of auctions can be served at least in my head gets divided up into these either private or open outcry either first price or second price if they're private uh and then either English or and coming to the sort of title of this work Dutch Dutch okay but one other thing and I think maybe matteus might be a good person to to discuss this is the notion of of Revelation um of like how participants in an auction reveal their preferences because like all you have all these different mechanisms but they all kind of are meant to capture different forms of Revolution like direct versus

indirect Revolution and I think like explaining what that is is probably also worthwhile because that's sort of you know what's the point of an option that's supposed to elicit people's preferences and then you know allocate to the people with the highest preferences but you know there's not a unique way to determine the highest preference yeah is a consonant auction field called the Revelation principle which basically says that any option that you could like if you have a complicated option where it involves a very complicated communication between beaters of the auctioneer the Revelation principles says that if you want to maximize Revenue then you can actually just consider the options that request bids from bidders

so it's basically saying you don't really need to have a lot of complexity on the option because if you want if you're going to maximize Revenue you could just have a mechanism that requests for bids uh what's very interesting for me though is that if you look on the proof of the Revelation principle it actually assumes that you need to trust the auction here right so the revolution principle doesn't hold it actually it could manipulate the auction because you could have an option that's credible and the Revelation principle transforms it in an auction that's that simply request bids but that result option might not be credible although the initial auction was credible the resulting auction after you apply the

Revelation principle might not be credible because it in the proof it really requires this assumption that you trust the auction here and that I would say that's one reason why even though you have the revolution principle you might still be interested in on trying to understand other types of options in practice interesting is first price English is that is it because it was from England I guess there's sort of the Strategic equivalence between these Dynamic ascending like the English auction and uh actually the second price auction okay and the Dutch so so I'll say a little bit about this this Dutch auction uh because the format's kind of interesting it's

basically the the flipped version of the English auction so in English auction the auctioneer is going to query everyone and ask like do you want to raise your bid if so raise it by this amount if not you're out of the auction yeah the Dutch auction is actually the auctioneer saying hey I have this price that I'm willing to sell this item at at this moment and in the next time step I'm going to decrease the price by some amount right and he asks he basically gives the buyers sort of an option which is do you want to buy at this price or not right like do you want to buy this price if if you want to take the item if not I'm going to decrease the price and you'll see sort of there's there there's

sort of a difference in just uh I think Mateos was talking about the communication complexity or the kinds of communication that the auctioneer needs to have with the with with the buyers and in the English auction this the seller needs to actually query go around and query everyone right he needs to like ask everyone do you want to raise your bid do you want to raise your bid at this as you can see this could be very expensive if there's a large number of buyers if there's like too many buyers in the system then you have to ask everyone what their what their new bid should be they want to stay the option as opposed to these Dutch auctions where you can simply it's like you're I'm just like posting a price that I'm saying like hey does anyone want to buy it at this price uh and for

that reason these Dutch auctions are sort of even though there is this equivalence between English auctions and second price auctions strategically at Dutch and First Press auctions from an implementation perspective these Dutch auctions can be much more you know they can be much more efficient and I've always understood them also that like they might be better suited if you have if you want a lot of winners right like it doesn't seem like it's as much this for you know highest bid wins but rather that there's like a lot of people bidding at the same time and they're all going to get something and maybe this is just the implementation that I'm that I'm thinking about but yeah so I think these polka dot options like these Ico auctions in the early uh in like 2017 uh they kind of had this feature that like

many early bidders could could get these tokens and they could get them at different prices that were sort of going down over time uh but certainly you can have uh Dutch auctions in which you're only selling one item in which case one person is going to end up getting the item at some price uh but that price is going to be decided by the sort of descending Auctioneer posting this price at every time and asking everyone if you didn't want to buy it I want to talk about a few of those early ones that I did see so one I think you just mentioned was the polka dot one I think they did something called a reverse Dutch auction where it was like high and then it went the price actually dropped over time as more people bid on it and then I remember seeing I think Flo did

something like that and also gnosis I remember them making tools for this or they were like building the tool kit to be able to run your own do you feel like was that I mean was that just perfect for selling fungible tokens and it doesn't really kind of you'd have to rethink it for things like nfts or do you ever have an nft case where you're trying to sell I don't know 10k of them and you're also trying to find this like medium price yeah so there's this famous use case of these uh like these Paradigm art gobbler nft collections that they were trying to sell and they were like you know I I don't know what the right price for these things is I have 10 000 of them each of them is like roughly like the other but I don't know I don't

know what the price I don't know what the price each one um and so yeah one solution is you dump them all on the market at the same time and you ask who wants to buy these 10 000 nfts uh you could try doing that that will probably end up with your nfts getting sold for you know pennies for like a fraction of the price that they should get or you should you could do this kind of as you said this kind of process where you either batch them or you sort of sell tell them slowly if you sort of release some levels slowly into the market uh at sort of these decaying prices over time right like so roughly you need to say hey I want to find an equilibrium price I want to find some kind of you know average price for this

for this collection I don't know what that is Let Me Slowly like release these nfts into the into the world at different you know at different sets of prices and by seeing who buys I'll be able to get a sense of what the equilibrium price of this thing should be hmm would you call this this concept of gradual Dutch auctions this is what you mean by that right so the formally it's it's a sequence of auctions so I start an auction so gradual Dutch auction is like a sequence of auctions that I start one at every time and eat the price of each auction is going to Decay like that of a Dutch auction okay so like at every discrete time at every like I every time a clock ticks I start a new auction I see and the price of each one of those auctions

is decaying over time so roughly you can think of at any given time in the future I have this portfolio I have the sequence I have this like collection of prices of things of auctions that were started in the past right so like I'm at time 50. I have 49 auctions that were started before me in the past all at different prices uh and now depending on who buys who bought those 49 auctions or who buys in the 50th auction I can get a sense of what the what the price or what the value of this item is I also wanted to say one benefit of it that auction over say selling the item over I posted like a fixed price is that if you sell the item at the very low price you might create a secondary market and and we have some cases of nft projects using

fixed price thing to sell items that clear at the price that's very low and then the blockchain gets very congested because the buyers they start selling these items in a secondary Market in the blockchain it just creates this this very congested environment because now the market doesn't know what the price of that item is so the benefit of that option is that you might sell the item at the higher closer to the Cleveland price we can avoid a secondary Market one other thing I guess that I would uh kind of add to what Mateo said is Dutch auctions even though there's a sense theoretically they don't often achieve

sort of like the minimum possible amount of communication between the bidder and the auctioneer they oftentimes have much lower communication and in a blockchain environment communication is extremely expensive if I needed to you know if you think about user interactions if a user has to repeatedly participate and submit many transactions over many blocks it's not going to work right but the problem is if you think about the sending auction if you try to do that on a blockchain you would let's say I post a bid of three ethereum for something then I see someone else in the mempool posted for ethereum now I have to go post something at 4.2 ethereum and that's very communication inefficient whereas in the Dutch auction you have this idea

get that okay at block one the price is 10 East block two the price goes to 90. block three it goes to eight eighth okay there's like three people who want to buy eighty block four if you go to 70 there's ten people want to buy at 70. and you you minimize the amount of communication now again it's not a totally formal statement there exists worst case auctions where Dutch auctions still have a ton of communication but they are on average a lot better uh and and yeah that's sort of one of the reasons I think people like using them outside of sort of the Strategic uh reason that matteus mentioned cool so I guess we've now uh introduced the concept of Dutch auctions and gradual

Dutch auctions I wanted to talk about this work that I mentioned at the top of the show this credibility and incentives in gradual Dutch auctions tell me a little bit about what kind of area you were focused on for this and what were you doing with this work the core question at hand here is like what so we've defined these class of auctions where you know these gradual attractions where sellers going to sell say some nft collection over time at these different prices and and the question is like what are the incentives of the seller in this process and what are the incentives of the buyer or it could also be fungible tokens by the way it doesn't have to be nfts yeah so the question was to sort of just try to understand what the incentives of both parties here look like and in

particular do these parties have an incentive to deviate from either the auctioneer running the gradual Dash auction as he had promised for example uh could he participate at the auction could he does he have an incentive to like lie in the auction does he have to do something in the option that is you know he didn't he didn't uh explicitly say earlier and then do the buyers do the buyers have an incentive to report their truthful evaluation and what we mean by report their truthful evaluation here is do they have an incentive to buy at their true values for the items or do they uh because these auctions are Dynamic and happening over time do they have an incentive to do stuff like holding out buying now for a chance of buying at

lower prices in the future or do they do stuff like buying now at the hopes of of selling in in a secondary resale Market if there's going to be some high value buyer that comes later in the auction so there's a sort of space of incentives for the buyers and space of you know these deviations for the seller and that's roughly what we what we try to understand is there also a chance in this case where like like the buyers would potentially collaborate with one another is this ever a fear that they're like yeah making decisions in another Forum in order to sort of corrupt this there is this sort of notion uh that's been sort of generically defined in these anytime you're running a mechanism on chain there's a sort of General very

general notion of something called off-chain agreements right like this idea that you could like there's some mechanism that you're running on a chain and these off-chain agreements could be happening between generically people what people are interested in are they happening between the person that's running the mechanism and one of the buyers so like is the seller colluding with the buyer but it could also be buyers colluding with each other right they could be colluding to you know raise the price of this you know it it's sort of difficult so so the kind of strategies that you have available in these gradual Dutch options you can't actually raise the price of Any Given nft well what you can do is you can artificially make the supply scarce by buying as a group or like by buying as a group and then waiting to sell in a

resale in a secondary Market uh and yeah that's something that you definitely have to be worried about maybe let's dig in what are the you know let's maybe talk first about this Auctioneer what what kind of incentives how how are you supposed to balance this what are you looking for so the main thing that Auctioneer can do even here in this auction is set these prices right set this price curve over time for every for every for selling every item so that's this that's a strategy he could like decide what the Decay rate of say each uh each item is and how many what initial price am I going to sell uh you tried about over pi that's what he could do in the context of setting like the actual mechanism but

then there's a couple of other things that he can do the first thing is he can participate in this auction right he can like he he can be one of the bidders in this auction uh and in this case uh you sort of have this problem where the auctioneer could say something like let me make the initial Supply scarce by say buying up some of the initial initial nfts an expectation that I'm going to get some high value buyers later who are now going to have a have to pay a higher equilibrium price than they would have otherwise had he not you know made these initial items in some sense disappear from the from the auction at some cost and so this is sort of the main like deviation that the

auctioneer has available or you can think of it as the auctioneer has some costs for making each item disappear uh and by doing so he can extract additional amount of value from the from the buyers that are remaining in the eye in the auction in the future and because these buyers are sort of considering what is happening over time because they have these values that depend on what other people are buying at because they can see the history of the auction uh this turns out to be a profitable attack on these on these class of auctions if you don't set these price scrubs properly did you also look at the buyer side of this so from the buyer's perspective uh it really sort of matters what your model of the buyer is here so as an example if your buyer is a person who can simply

come into the auction at any given time and he has a take it or leave it offer to buy the items that are currently up for sale and then he leaves and never comes back it's actually very clear what the buyer should do here the buyer should just buy the items that match his value or you know or less than of value so that's what you should do but if your model of the buyer and this is sort of where the Dynamics of this process are very interesting if your model of the buyer is something more complicated like a buyer can uh come into the auction see the history of the auction of course you can see the history of the auction but then also reason about sort of future buyers that might come into the auction he has this valuation that's dependent on sort of the entire history

of the option then something sort of much more complicated can arise where you need to reason about sort of the expected utility of the buyer at any given time over this entire sequence of you know of all of potential buyers that could arrive uh both that have arrived in the past and that could arrive in the future uh and that turns out to be sort of the more complicated case to handle uh and of course there's there's even more complicated models of buyers that we don't consider which are like buyers that can arrive now buy or not see what happens in the auction for a little bit and then come back later and then you know like you know all of this sort of dynamic arrival you know these process models but as a stroke to get a

rough handle of things you just consider these buyers they can reason about you know future arrivals of higher low value buyers okay I have two more questions on this one I don't know that you covered this but are there other actors other than the buyers and the auctioneers that you ever take into account for this like influence from outside third party actors that are like causing some sort of misperception like does that ever factor into these analyzes so I think this is actually one of the one of the benefits of these what what are effectively acting as posted price mechanisms like at every time I'm just posting like a sequence of prices is that the prices themselves are harder to manipulate here right or if you're not

if you're not the auctioneer if you're not the person that's setting up the mechanism there's no real way in which I can like give you a different price uh but the I think the interesting place where this all you know comes up and this is something that we don't consider in this in this paper is what happens in these secondary markets which is really where if you have some understanding of what could happen outside of so the place that's outside of this mechanism is the second dairy market where these nfts are going to be sold and resold and you know people are going to pump and dump and they're going to do all their stuff and it's almost like is it if they know that that's a possibility does that alter their behavior in a way right right and it should right it should it

should if you and so effectively which what would happen there is that you would have to sort of construct this like expanded game like this expanded strategy space of things that people can do in the auction itself and also in this sort of external attached game and then you would study sort of the joint equilibrium as we say of the of this game but I think that's much harder because they're the strategy space or like what what the external actors can do can be much larger than what they can do in these auctions and this is something that I learned from Matthias about auction because I'm not I'm not an auction theorist by any means but auctions have this very they're typically ways of expressing very simple

desiderata about what you want to happen in you know in in a mechanism like these rules of like okay I'm gonna post the sequence of prices you can take it or leave it uh are just very simple whereas what can happen outside of these mechanisms and like a general resale Market the strategies there can be very different for example strategies there could be collusion so you could like collude with other buyers uh it could be signaling so like there's some privileged actor who can signal to everyone hey I'm buying this so imagine you have like a really popular Twitter account yes or you can like pump and dump your nfps and now you can signal to your followers that like hey this thing

is valuable uh so signaling is an option uh like direct payments like bribing people is an option uh and so there's just a lot of stuff that can happen outside of this auction that cannot really happen in the auction as defined itself uh that I think makes these auctions like relatively simple to follow and analyze interesting this particular uh work and actually kind of what you even described with like a secondary Market just in terms of the kinds of things that would follow this it sounds like you're talking really about nfts is there ever a case where this is also something more fungible right so they're versions of these of these gradual Dutch

auctions that work for fungible tokens in which you what you basically do is instead of setting an item up for sale at every time you set some fraction of your token Supply up for sale at every time and then you try to get a price for that batch basically you try to you know do these batches and try to get a price for that the issue I think with these with these fungible tokens I think is I think they're secondary markets I mean it's sure you can have an initial coin offering or like some kind of you know token offering but then they might trade like really in a liquid fashion back and forth in the The Daily markets I think typically people are like more interested in finding like these daily prices for things as opposed to just the

initial price uh I don't know if icos are like as popular as they used to be uh but yeah certainly if you're trying to find sort of you you have uh fungible tokens that you don't know what they're what what the starting price for these things should be you can do this sort of batching and selling over you know sequence of times cool you know let's say I'm a person who wants to sell a bunch of nfts there's two ways to do it one is I just say like here's 500 things you can mint them and go wild and that's basically a first price auction in the men pool for for who can be the first one to call the function or at least the first 500 and then there's a gas War over that and that gas war is a first price auction and this

gets to the fact that like selling many items especially multi-dimensional like items of different qualities all at once is really really hard the complexity of it is potentially exponential in the number of items possibly worse if you care about the sequencing of how the items are sold another way to do it is to be like hey I'm going to sell items one by one one at a time and you lose some information when you do that because people can't buy arbitrary sequences they can't go backwards and buy the fourth auction in time but there is a sense in which it's easier to reason about for the seller the seller knows like okay I sell sold something someone bought it for a price higher than I thought okay I can sell

the next one at a higher price and this type of sequentiality is like something I think people in auction Theory have studied but have not studied when it was used in sort of these like low communication complexity auctions like you have to have it in blockchains and I think as we talk about other types of auctions in crypto like me V auctions in Mev auctions communication complexity is super super important like you can't in a way that is almost much more important than in the nfts and that changes the design and I think that that's probably the nice stepping off point for talking about mvv options cool let's do this let's explore a little bit more where auctions and Mev intersecting how does that work yeah so

maybe I'll give it a tiny bit of a background on how it actually looks in practice and then then kind of set the stage for Mateus to talk about what it could look like in the future because if we're being completely honest the current Mev auctions are kind of shitty and there's not really any way of getting around that and understanding why they're not good and how that can change is quite important and obviously there's a very big economic fight going on for who who will be in charge to some extent of that and I think this is where auction design is very important and taking advantage of CK to make the auctions fair is even more important um So currently you know when at the way

Mev works is first flashbots sort of came around uh to kind of reduce spam on ethereum by basically having people bid in an auction off chain instead of spamming the validators to insert transactions on chain and the idea was that like by moving some of the you know the people sniping each other's bids like someone saying I'm willing to pay three something and say I'm only pay four so I'm saying I'm willing to pay five and so all three of those transactions going in the blockchain and two of two out of three failing you instead only post the one that's completed the one that's at five e and you you sort of run an auction off chain and then the validators agree to the outcome of that auction

and use that for the ordering of the block and what validators are really what people are really bidding on is two things one is inclusion of a particular transaction and ordering of a particular transaction so I want my transaction to be included in the block and I always want it to be before or after a particular transaction or I want this group of transactions to be executed in order so for instance if I'm front running some a sequence of transactions I might say hey put my trade first then put this sequence of Trades after and you bid on that sequence of transactions now the interesting thing about the space of Mev options is that they're combinatorial auctions in the sense that you're

bidding on sequences of transactions you're not just bidding on like hey I want my transaction in right like when I'm bidding in in eit1559 I'm just saying hey I'm willing to pay a gas price I don't really care where I'm going instead you're bidding on sequences and the set of all sequences is way way larger yeah it changes the Candor of the auction are you bidding on the sequence or your position in a sequence do you still have any sort of selfishness here like yeah I'm kind of confused on what that looks like so so you you construct these things called bundles which are ordered sequences of transactions so let's say I'm going to front run someone and it's a particular transaction I submit a bundle that has

my transaction first and then their transaction and I and you you can think of it as almost like an order type that says I'm willing to submit this transaction and pay you this fee this excess fee that I'm bidding on only if you execute these two transactions into the sequence together I see so that even no matter where it is in the block I will always be before the other person okay are there like in reality though can these be quite complicated where it's not just two transactions that you're trying to like match but actually like they can be arbitrary size okay and in fact they can be the whole block okay so um in the current version of ethereum the block Builders who are people who propose blocks or people who build

blocks that the proposer who is the person the proof of stake protocol chooses to make the next block the the builders say hey here's a whole block it's valid and here's how much I'm bidding for this particular block and you know ethereum moved post merge to this model but prior to the merge um flashbots basically was running something whereas like you bid on the sequences so now it's sort of people send their orders as bundles to the builders and the builders guarantee them that some execution guarantees but the long story shortages these are actually auctions that look a little more like the ad auctions remember how I said they're oh yeah the ad auctions you have these like many many possible options but actually only a small number of them

are active at any time interesting yeah yeah um and so there's there's a huge relation but the difference is the ad auctions are run by centralized Auctioneers and you you they're trusted parties and sometimes you're making this assumption and we are still sort of making this assumption with flashbots although in the current ethereum case block Builders are competitive so anyone can be a block Builder so the goal of decentralizing this auction is actually quite important but one thing that's you know I think in the traditional Auction World whether it's in normal Finance or whether it's in aductions that people never cared about was this idea of credibility which is uh you know you could think of a seller

incentive compatibility which means that the seller is not trying to add fake bids or maliciously reorder transactions or you know things like that because we've in those worlds you just assume that the auctioneer is the auctioneer and they can do whatever they want there's no real recourse of course this Google antitrust cases the US government trying to give Google some recourse for manipulating their auction but I think yeah the stage is sort of set with this idea of how do we make these auctions resistant to sellers you know the the seller of block space in in the case of Mev manipulating it to either sensor transactions or change the profit you

know payoff function of a user and so I think maybe Matthias might be good to talk about credibility at this point yes that brings me to my work on credible auctions where I think work on that for quite a while now I think four years so I had the this worked with Tyrone and Christian are we we're basically studying how could blockchains help us design these options they are robust from manipulations by the auctioneer so I had some prior work where we actually showed that cryptography can avoid some possibility results from economic theory so there was this very influential paper for an economist

around 2018 where they showed that if you wanna design an option that strategy proof where where beers have incentive to reveal their bits or they reveal their value their evaluations and if you want the option to be Revenue optimal and credible so if you want all these properties at the same time they show that the ascending price option is the only option that that could do that okay so we talked a little bit about the outstanding price option so the problem there is the communication is very expensive so in the blockchain context that would just not be practical to implement an ascending price auction so then I had the paper around 2020 where I

show where you could actually avoid their impossibility result you can actually design options there are communication efficient if you can if you have access to like basic cryptography so the way you should take is that their impossibility result is is what we cover information theoretical impossibility result where cryptography introduces assumptions that can allow you to avoid that and and we show that you can actually avoid the impossibility result and design options there satisfy how those food properties what kind of cryptography are you talking about is what we call our limbo commitment schemes so it's actually a very

interesting connection with zero knowledge because zero knowledge proves are very important tool to actually design those those type of technique all of those designers that that type of tools from in cryptography these constructions are they influenced by anything else in like the or anything like in that in in sort of consensus anything else or is it is it really just kind of being created for this particular use case yes so there is this particular use case in the blockchain so when I started thinking about it was more generals would be for any any context in general so you just work with the room and K recently

actually showed that you can even relax our some of the assumptions in the paper I wrote before by using a blockchain so in that context the blockchain here is actually at two to expand the design space because it you basically show that this the blockchain allows us to reduce the space of manipulations that the seller could try to do so that was quite interesting because I guess there's like a three-step here right so if my work in 2020 was showing that just by having cryptography we could we could reduce the the manipulations of the seller whereby now also introducing a

blockchain we can even reduce the the manipulation space even more uh so I think that's really interesting here is that there is actually is actually seeing the separation of of the design space right by introducing these additional tools that that really expand what can we actually do and how we can actually build these options yeah another way of thinking about it is by adding in particular cryptographic Primitives and then making assumptions about the users like the users are computationally bounded in that they can't break particular cryptographic Primitives you can get around a lot of impossibility results in auction Theory and one of the more surprising things

about this paper um to me was that you know you already got this thing where you got around this impossibility result this trilemma by using non-maluable commitments but the idea that posting the non-malleable commitments publicly on a blockchain reduces the set of possible bad actions the auctioneer can take is quite surprising it says that like the auction you you reduce it so much that the bidders can have Wilder bidding strategies so it's like sort of a trade-off between the strategy space By Post forcing people to post commitments publicly not just privately one between each other you change the strategy spaces that the auctioneer can't deviate as much and the bidders can do more complex stuff and

there's this trade-off between the two and the cryptography media and public posting mediates you know how much power is on each side in some way cool uh the work you're describing there it's entitled I'm just gonna say it for the listener credible optimal auctions via blockchains but in that it also references this other kind of auction the Deferred Revelation auction is that significantly different from what we've talked about like should we Define that yes that is essentially that's actually the auction I might take in 2020 so that was when I created that and in fact the auction is very similar to a second price okay we're the highest beta wins

the item and they pay the second highest bid but there is a Twist here that we use the commitments to actually try to hide your bid from the auctioneer so the you're trying to tie the hands of the auctioneer so he should not be able to create fake beds without knowing what your building is so that the goal is should limit how much he could manipulate um the auction and your payment so one example of how the seller could manipulate the second price auction is that say you come to the auction you bid ten dollars Alice comes to bits five what should happen is that you should

win and pay only five dollars but if you can't see if you can't see what Alice is beating the auction they actually could come in line and say oh actually Elizabeth nine dollars so now you should pay nine instead of being five um and there is really no way for you to know if that's happening unless you force the auctioneer to post a commitment whether it's a ZK proof or you know a non-mallieable commitment of sort of their bids yeah so by introducing uh cryptographic commitment of your bid say now your cryptograph will commit into ten dollars now the auctioneer actually doesn't see your bid in 10. so now if he he has to if he's

trying to create fake bits he's gonna do that in the actual knowing what you're bidding and that might be very risky for the auction year uh because later on he has actually to prove that you are really the winner of the auction so he he might risk sending a fake bid of 11 when your bid is actually 10 uh and he can't convince you that you are the highest bidder if you're beating 10 and he had the fake beat of 11. and I guess like in the past the way that this Auctioneer would often also be kind of like kept in line was this idea of like the reputation of the auction house or the reputation of the company is there a reason that you would say

like in the blockchain space you need kind of more strict cryptographic ways to keep them in line I guess is reputation sort of not as clear even if you have a reputation as you're saying like if you go to a second price option like in eBay let's say eBay has a reputation but so they're not willing to harm their reputation right but if they're if they're manipulating the second highest bid in the auction you can't you can't even tell oh you couldn't tell anyway yeah so even if they care about the reputation you're not gonna be able to prove their their manipulating it with the blockchain at least you or you can re you can weaken this Assumption of the seller having a reputation because

you have a contract tell me so the non-maleable commitments are they zkps like are they something else I'm kind of curious you sort of mentioned there's a connection point between these two things but yeah yeah so a traditional commitment scheme it's very simple the idea is that it's it's similar to a hash function where you are hashing your bit and you're sending it to this seller and the idea is that if the hatch function is Collision resistant later on if you say you you hash say ten dollars and later on you have to prove you have to convince the seller that whatever you had committed to was really ten dollars so what you do you reveal 10 and now the

seller can compute the hash function at 10 and he sees if those if they actually send in the first round is equals to the hash is Computing after you reveal your bin the problem with that though is that even document can hide a bit and can be binding there is this concept of malleability where I might the auctioneer might be able to create a commitment to nine dollars by knowing your commitment to ten dollars without actually knowing that you have committed to ten dollars and and in fact there is very simple constructs of commitment schemes they are malleable like if you bid ten

dollars is very easy to generate a commitment to mine even even without knowing that you have committed to 10. and then there is this goal of design commitments there are non-valuable in the sense that you should not be able to no one should be able to generate a commitment to a value that's related to what you committed to and one direction to actually do that is to use a zero knowledge proof so what you do is the following I want to commit to ten dollars but if I commit to ten dollars I have to prove that I know what I have committed to why would that be non-valuable right because if if someone tries to see my

commitment to 10 and generate a commitment to nine either actually knowing someone else that's committed to 10 they have to prove in zero knowledge that they know that they have committed to nine but if they don't know that I had committed to 10 that they cannot generate the approved to that so that's one direction to build a normal level commitments by requiring the person who is committing to proving zero knowledge that they know what they are really committing to I I think like the nft auction world has a lot of stuff where users preferences could be expressed in a way that users can kind of buy collections that they want automatically

without revealing all of their preferences and getting front-run by the sellers or any V Bots and in some sense like if crypto gaming is ever to become a thing I think you need some form of this such that it doesn't just become like any vbot versus Mev bot yeah which is like almost all crypto games like you know like if you think about like dark forests versus all these other crypto games the ZK aspect of dark force actually is what kind of makes it harder to make these kind of thoughts in general strategy wise uh and I think that's going to also be true for these preferences expressing preferences in a game like being like Oh I like this type of item in the game and like this

is the strategy I want to execute but I don't want everyone else to know it versus some something like axi where it's like you're publicly showing your strategy in hand at all times always I basically think that like the blockchain gaming world only works if you can somehow allow people to participate in auctions without revealing everything about themselves and it's a very weird maybe like too far in the future view but I I just don't think humans are gonna like playing games that are always just going to be like bought for a spot right no one wants to just be like you know unless it's just like at that point it's just trading right it's not really like playing a game and I sort of think like having these

kind of mechanisms for revealing preferences without revealing your whole strategy is it going to be key to kind of like preserving Humanity on the blockchain whoa that was bigger than I expected I was just thinking oh wow it's really cool it might be in gaming but like damn so the fate of humanity is is at stake yeah yeah I guess like in in a world where everyone is is talking about agis sometimes we also have to think about the other side yeah I was curious about Tyrone like what does you mean by like Bots like in in blockchain games what do you mean like by people using Bots to play so there have been like a ton of games right that have these

nfts that you know have some either some value in a game that's off chain or have a resale market and what ends up happening is people just write Bots that play the games to harvest particular items and then sell them immediately it's not so different to people having bots of like Starcraft or something right but there you have this team of people who are dedicated to trying to remove the Bots because otherwise the human players will leave and then like the game you know they can't sell real items to real people anymore but in blockchain games there's kind of this perverse incentive where the game developers get to pad their metrics by having more Bots play the game right they get to say like oh like our total usage was X or we transferred this many

dollars of items and it sort of also ruins the ability for like humans to play it just becomes this kind of like only the people writing automated strategies are playing and it's sort you know I don't think video games in general you know I don't really play video games but I will say one thing which I think is true is I don't think there's ever been a video game that you know once computers are a lot better at it than humans that people were like oh yeah I still like playing it a lot and I think that in some ways blockchain games went the opposite way they're very bot friendly right now and maybe this could bring some Humanity back to them I guess yes

and the Bots are always just front running the human players and like copying their transactions and then just basically getting the item before them yeah yeah I mean feed is very interesting aspect of like humans don't like to be manipulated and feel like some someone or something take advantage of them I think that's I think that's like very important as as your design these applications like to make sure that users feel like they they have a chance and they are not like just being played by the person who is designing the protocol or being outmatched by the Bots that are just like far too sophisticated

yeah I I mean in a lot of ways this is this is definitely the reason I think like this economics idea of revealing preferences without revealing strategy is somehow key to fairness in in these systems and and I I don't know how else to do it without cryptography it doesn't seem possible I like that well I want to say thank you to both of you for coming on the show actually all three of you thank you tarun for also being kind of the co-host and guest for this one um yeah and thanks for sharing with us all of your insights about auctions and the work you've been doing around it thanks a lot for having us thank you very much for having us I'm happy we finally dived into the world of auctions because they're a lot more complicated and everywhere in crypto no matter how

much you want to avoid interacting with them cool all right thanks again and I want to say thank you to the podcast team Henrik Rachel and Tanya and to our listeners thanks for listening [Music]