CredibleCommitments.WTF (http://crediblecommitments.wtf/) is a series of open discussions on the WIP work of exploring practical implementations of cooperative AI on top of cryptoeconomic/cryptographic credible commitment devices. We specifically focus our discussion on concrete, approachable ways to study and realize commitments for coordination between algorithmic agents. This event is to bring together facilitate discussions between pragmatic commitment device researchers and cooperative AI researchers to better map out the directions of this collaboration. 

We focus on answering two questions:

1. How we can better formalize and study the properties of crypto commitment devices and the coordination games mediated by it via the lens of commitment games? Specifically, what kind of concrete simple games we can study to illustrate the power of crypto commitment devices.

2. How can we better design blockchains (a technology for implementing commmitments) for coordination games with algorithmic agent participants (cooperative AI)? What are some benchmark games that we can devise for boostrapping? e.g., are there any simple games where we can observe what kind of behavior emerges when AIs play games with the presence of a crypto commitment device.

You You I'm going to use a microphone, bro.

This was supposed to be animated, but it's not.

So first of all, I want to talk about credible mechanisms.

This was an idea that was introduced by Lee and Akhbapor,

They wanted to ask at a high level, what happens if the entity that is operationalizing a mechanism is able to deviate from the intended rules of the mechanism?

So, maybe a canonical example to have in mind, which you're all familiar with in this audience, I think is, um, a second price auction.

Would not be credible because there are deviations available that are not visible, uh, to the participants and they, they formalize this.

So they said that a rule describes an intended behavior.

For example, the intended behavior might be take all bids and run a first price auction.

They describe the concepts of a safe deviation.

This is a deviation from the rule that generates an output for which there exists an input consistent with the rule, given each participant's knowledge of the input.

So, you know, you may know your bid, you may not know the other bids, and then you observe the outcome.

Is the outcome consistent with some possible completion of the input?

The entity operationalizing the mechanism may have deviated from the intended behavior, but in a way that is not observable to any party based on what they know.

And then they say that a rule is credible if there is no profitable safe deviation.

So they don't require there to be no safe deviations, but they require there to be no useful safe deviations.

So I think it's useful to imagine that deviations that are not safe are sanctioned in some way.

You're staking your reputation as a mechanism entity on following the rule, at least up until the point where your deviations can be caught.

There are other things you can do that nobody will know about.

You're not making any guarantees in that regard.

And we still want to be able to say useful things about the mechanism.

And what they proved in this paper, they proved the trial lemma, which I'm not going to step through in detail, but they proved, for example, that revenue optimal first price auctions are credible, but second price auctions are not credible.

Um, and I think when we think about commitment, then I'm going to try to tie things into commitment.

Uh, I think we could say that credibility gives a self-interested mechanism commitment power.

If my mechanism rules are credible, then I can commit in a credible way to follow those rules.

It is incentive compatible for me to follow them and not use a safe deviation.

So this notion of credibility, which now you can kind of situate this in the DeFi space.

So in the DeFi space, and let's think about transaction ordering into an AMM.

In the DeFi space, a rule is an intended behavior.

It might be take all transactions that you have seen and follow a particular sequencing methods to order those transactions onto an AMM.

And then a safe deviation is 1 that again, generates an output for which there is an input that is consistent with the rule given knowledge of the input.

I think Oftentimes when we think about blockchain, we will think about the input as being observable.

That is the input that is used as being observable.

So when I think about DeFi, for example, concretely, we can all observe the transactions that were pushed through Uniswap in that block.

So in that sense, we all have information about the input.

And so a safe deviation is any deviation where if there's some space, either if there's some space in the rules, you still are following the requirements of the rule, or a deviation where you perturb the input in some way.

You're, you're, you're allowed to perturb the input.

It's just that you have to follow the rule given what people see about the input.

And here the input is all of the transactions that are written into the block.

I'm going to mention in a second the result we have, and it's just a slight tweak on the credibility definition.

So the definition I gave you earlier is there is no profitable safe deviation.

The definition I'm now going to use is that any profitable safe deviation from the rule still achieves design goals that we care about.

So there may be deviations, and I'm okay with that as long as any deviations that the mechanism chooses to follow still lead to properties that are good for me.

For example, a property I might care about in the DeFi context is I'm okay with MEV, but only if the execution price on the transaction that is MEVed is good in a way that we could formalize.

And again, think about other deviations being sanctioned.

So this is credibility where I say, I'm going to follow this particular sequencing rule.

If you ever see, based on what you see about the input that I'm using, that I didn't follow the rule, you can sanction me.

And now going forward, people will choose not to submit transactions to my mechanism.

So here, credibility gives a self-interested party commitment power to achieve desiderata, where again desiderata might be what we could think about informally as tolerable MEV.

It is essentially commendable for me to achieve these as a router, even if I might choose to use some safety deviations.

So we have a forthcoming paper that I'm not going to get into in any detail other than to advertise it here.

You can ask me about it later if we want to go there, which is coming up in stock, where we give a verifiable sequencing rule that ensures this kind of tolerable, um, uh, MEV property.

So it ensures that for any executed transaction, A, either the price of A is as good as if A was the only order to execute or no MEV is gained by executing A.

And you could think about, for example, um, builders and relays choosing to adopt that rule.

And then now they are committing to be observed and have staked their reputation on not deviating.

And the question is whether those rules have nice properties.

That's the first thing that I wanted to talk about is role of credibility.

Second thing I want to now jump back in time and talk about this idea of faithful implementations.

The backdrop to this was that algorithmic mechanism design started in around

There was a flurry of activity around polynomial time mechanisms.

And then some people, particularly Joan Feigenbaum and Scott Schenker, started thinking about what would happen if we had distributed algorithms that were implementing the mechanisms.

And so now the question wasn't so much, Is there a polynomial time centralized algorithm that can operationalize the rule supermechanism?

But is there a decentralized algorithm with nice communication complexity and computational complexity that can run the algorithm?

The question they didn't ask is they didn't ask

was incentive aligned to follow the distributed algorithm.

So they said, here's a distributed algorithm where if it is wrong, it will effectively compute the output of the mechanism.

And they, they wanted mechanisms because mechanisms were providing incentive alignments around inputs, but they were not insisting that parties wouldn't want to deviate from the algorithm itself.

And yet, at the same time, the motivating story were often things like BGP, Border Gateway Protocol for autonomous systems on the internet, which are self-interested parties executing decentralized algorithms.

And there's no reason to really think they would choose to follow the algorithm if they could benefit by deviating from it.

And so what we did in this work was we wanted to add this additional criterion of incentive alignment with choosing to follow the algorithm.

And that's what I mean by a faithful implementation.

So it's nice that we're adjacent to RMAS today.

I called this specification faithfulness.

So this work with Jeff Schneiderman and I want to contrast it to credibility.

So in credibility, there is a privileged party, say a mechanism that receives inputs, can tamper with them in various ways, and then selects an output.

When we were thinking about faithfulness, we didn't have any kind of center, any privileged party.

So I would often draw these types of pictures.

Uh, here's a sensor and here it's like, no, you take the rules of the mechanism and you give them to all of the participants in the, in the system.

And they're all doing some part of the distributed computation.

And we wanted all of that communication and computation to be in equilibrium.

So it's a weaker form of commitment reflecting that multi-party aspect.

It says it's incentive aligned for me to follow my part of the mechanism rules, given that others do the same.

And what we did is we asked the question, can following a protocol be made an exposed Nash equilibrium?

Roughly this says, as long as others follow the protocol, then whatever the inputs, you also want to follow the protocol, whatever the private inputs.

And if it's true, then we say that specification is faithful.

We formalized it by breaking up the, um, uh, the strategy now of an, of a agent represents the computation that they're doing.

And we, we thought about that in terms of a revelation component, a computation component and a message passing component.

Um, so revelation is computation you're doing that is touching your private input.

Computation is work you're doing that is depending on inputs that you've received and message passing is you sending messages to others.

And we developed a proof recipe that I will flash and not spend a lot of time on, where we first of all defines this notion of algorithm compatible, which says that an agent will choose to follow the suggested computation in equilibrium.

Communication compatible, an agent will choose to follow the suggested message passing in equilibrium.

And then we strengthened AC, and we said, well, strong AC is that you will choose to follow your suggested computation, whatever you do in regard to your revelation action and your communication action.

So assuming others do what they're supposed to be doing, but even if you were to deviate in arbitrary ways for revelation and message passing, it's still incentive alliance for you to do the computation correctly.

And you can similarly strengthen communication compatibility.

And then we can prove, it's quite easy to then prove that if a mechanism is strategy proof and you have a correct distributed specification that is strong AC and strong CC, then the specification will be faithful.

So then the game is all about how to establish these properties and we provided techniques for that in these papers.

RMS04, almost 20 years ago, it's hard to believe.

We had our BGP protocol, which was in PODC and then a more general distributed optimization algorithm in RMS 06.

Go back 1 year now, strategy-proof computing.

This is something I was playing around with pretty early as a professor at Harvard.

And I remember giving this talk actually within a little room at IJCAI in

And I don't think I've talked about it since.

So I was developing this notion of what it would mean to have something called strategy-proof computing.

And I'd been motivated by what's known as the end-to-end principle in network systems, where somehow you don't try to do too much in the network.

And I wanted to kind of think through what would that mean for mechanism design?

And my main idea was, well, you don't want there to be 1 designer.

You want them to be innovation amongst mechanism designers.

You want anybody to be able to deploy a mechanism and have kind of a competitive landscape for which mechanisms get used.

And then I was thinking through, okay, what would that mean?

1 thing I decided was that I wanted each mechanism to be strategy proof, um, at least kind of locally for the things that it's doing.

And so what I mean by that is that strategy proof, this doesn't compose very well, If you're trying to buy a bundle of stuff, and I give you a strategy proof mechanism for 1 part of the stuff you want to buy, and a strategy proof mechanism for the second part, it doesn't mean that your dominant strategy is to bid truthfully for this part and be truthfully for this part, because you might not put everything together correctly.

So there's this composability problem, which I raised in the paper.

But what I did want to insist is that if somebody deploys a mechanism to allocate this particular bundle of resources, that that mechanism should be strategy-proof in a particular way and should be certified as such.

I wanted to support continued innovation and competition, focusing on resource allocation, arbitration of resources.

And by individual users can treat other resources as their own.

This is the notion of simplicity that comes from strategy proofness, that you shouldn't have to game in the requests that you're making for resources.

You should just be able to describe what you're interested in, just as you would, if you weren't competing with others for those resources.

I'm just going to tell you what they were.

And then I will point you to the paper, which I think we've now, we've, we've posted on the webpage.

So I laid out 5 guiding principles and then I laid out 5 principles where we should care about incentives.

We should be focused on utility and not utilization.

We want openness and we want things to be decentralized.

And then the challenges were, were design, were how to describe what it is your mechanism does and who it is designed for and what properties does it have.

Um, how we can verify in a data-driven way the incentive properties of the mechanism.

Because I had in mind that the infrastructure, which was vaguely discussed in the paper, is monitoring inputs and outputs to these mechanisms and is able to, by looking at the trace of inputs and outputs, notice violations in strategy proofness.

I have proof by looking at the things you've been doing over time.

That's the way I was thinking about this.

I have a paper on that verification step.

Compositionality, And I'd forgotten about this until I looked at the paper yesterday.

I talked about the idea of learning, using machine learning to try to design mechanisms as well in that paper.

So then fast forward to this year, where we are using machine learning to design mechanisms.

And I've been working on this idea of differentiable economics now for a few years with a number of collaborators.

And the particular project that I wanted to briefly mention is about contract design, so it fits with commitment devices.

So, oh, and I didn't mention commitments here, but I, what I wanted to say is that assume the ability to commit to the rules of a mechanism, that you are not going to change the rules of the mechanism.

This was an implicit assumption in my paper, that you can deploy something and you will not change it.

Which today, I think we can roughly do that.

A whole bunch of co-authors, including Jia Fang and Sai Ravindranath, more recently Jeff Zhang and Tonghan Wong in my research group.

It says, OK, that represents the rules of a mechanism via a differentiable function, neural network.

And let's use differentiable techniques to try to optimize the rules of the mechanism.

The technical challenge is, I mean, there are a few, but 1 technical challenge is that you need incentive compatibility.

So if, if I, if I gave the network, the objective of minimizing negated revenue or maximizing expected revenue.

So if you say your loss function is negated revenue, Well, it's going to do that in a non-incentive compatible way.

It's going to kind of charge you your bid, which of course is not sensible economically.

So we have to have a way to regularize, penalize in some way the mechanisms that are learned, which we do in this research in various ways.

Just as a quick example before I talk about contracts, in the first work we talked about optimal auction design.

Very simple example, just with 1 bidder, just to illustrate what happens.

And you can't have auctions for a single bidder.

I know it sounds a little silly, but actually digital goods do tend to decompose across bidders because they're what's called a non-rival good.

So suppose we had a single bidder with an additive valuation function, uniform 0, 1 for item 1, uniform 0, 1 for item 2.

The theoretical economic literature tells us what the optimal design of an auction is.

It says that if the value is in this space, less than this number for item 1, less than this for item 2, then don't allocate.

If your value is high for both, allocate.

If it's high for 1 but not 2, allocate item 1.

And then the payments follow from a typical auction theory.

So if you just want to decompose it down, this is the allocation rule from theory for item 1, and this is the allocation rule from theory for item 2.

So it has this threshold kind of structure to it.

And when you train the network, you learn things that look like this.

So this is the density plot of a tanh-based neural network.

So you can see it kind of smooths out the boundaries, but it's approximately doing what it should do.

So Just basically my last slide, but hopefully we will have enough time for this session.

Working paper led by Tonghan Wang in my research group on using this technique for optimal contract design.

Let me tell you what I mean by a contract here.

And I mean it in the very classical sense from economics.

So we think here about the being an agent with unobservable costly actions, each action causing a distribution on observable outcomes and the being a principal, another actor in the system with value for the outcomes.

So think about the agent as your contractor.

If you're improving your house, you don't watch what the contractor does all the time, but based on the behavior of the contractor, your house is high quality or not, is on time or late, you can contract on payments with the, you can offer your contractor payments that are conditioned on whether or not the outcome is high quality or low quality on time or late.

And the goal is to, in our work is to learn a contract.

It's these outcome contingent payments to maximize the expected utility of the principal.

Which is the, so think about for a given contract, this induces a distribution over outcomes.

You have an expected value for that, you have an expected cost because you're paying and you want to find out of all possible contracts, the 1 that is best.

So what we do here is we recognize that if you think about the design space, this is a bit washed out, but this is a two-dimensional contract space showing the utility function of the principal.

The utility function of the principal as you move in contract space is discontinuous because as you move from 1 contract to another, the principal's best response, the agent's best response action can change, and that can lead to a discontinuity in the utility to the principle.

And so we know it is the, for example, ReLU networks are piecewise continuous approximations.

So we introduced a new network architecture, which gives a discontinuity, which is appropriate to modeling this problem.

So we learn the utility function to the principle and then we do inference on that space to find the optimal contract.

Going back to commitment here, this is assuming in the background the ability to commit to a contract.

If you can commit to a contract, which are these outcome contingent payments, then there's a contract design problem that can be solved using machine learning.

So just to wrap up, I wanted to give you these 4 illustrations on alignments and commitments.

Emphasize that each of them has a different notion of commitments in credible mechanisms.

Your commitment power comes from it being in your own self-interest, not to use a safe deviation, or in your own interest, to only use deviations that are tolerable.

In the faithful implementation space, your commitment power comes from it being in your self-interest to follow the rules of the protocol as long as others are doing the same.

In strategy proof computing, we assumed in that work that different parties are able to commit to the rules of mechanisms.

And then we argued that it would be in the self-interest of a party to publish a strategy proof mechanism because the infrastructure is going to run a reputation system to catch a deviation.

And then in this optimal contract design work, we're assuming the ability to commit to a contract, which has an outcome contingent payment role and using machine learning to design that commitment device.

I wanted to kind of share this with you because I think these are all examples where I hope that ideas from distributed AI, multi-agent systems research, Econ CS research can continue to get picked up in the crypto space.

And I'm guessing a bunch of you are building out and designing things in that space.

I'm curious that the kind of the fire challenge.

not exactly sure what they are but yeah, which ones do you kind of currently see as the kind of biggest outstanding ones that are

What do you think we've actually made a bit of progress on?

Yeah, What is that standing in place of the API writing?

I would say good progress on mechanism design, good progress on the automation of mechanism design.

People haven't really worried so much about developing languages to describe appropriations of mechanisms.

on languages to describe inputs to mechanisms, but not that all that's a question of how you describe the mechanism itself.

want to say there's been a lot of work on this idea, but I'm just writing up that paper on why can't you trace the input output of the decisions from mechanisms and developing algorithms that can give with high probability guarantees that in fact the algorithm is strategy proof.

We did some work on this like create space for more work and maybe there's a whole different approach to this which will be modern cryptographic techniques which we weren't thinking about here.

Maybe we can chat a little bit about that.

Compositionality is something that people are very aware of.

There was some work on this after I wrote this paper.

There was a paper by Moalan and Minsan that gave 1 way in which you can compose factors together.

We also did some work where we talked about mechanisms for auctions.

See all Flashbots transcripts on Youtube

CredibleCommitments.WTF | David C. Parkes - Illustrations on Commitment in Decentralized Systems