Project summary

This project aims to implement parallelization and GPU acceleration features for the monad-bayes[1][2] Haskell library, a probabilistic programming library.

These extensions will result in faster performance and better optimization for all methods relying on Bayesian reasoning. In the context of the broader Ethereum ecosystem, this in particular means better performance for the growing corpus of protocols and research projects employing Compositional Game Theory, such as core research in MEV and PBS, financial incentive analysis of DeFi protocols and DAO governance.

Extended description

The last few years have seen a sharp rise in the employment of algorithmic mechanism design methods in the context of DeFi incentive alignment, MEV (Maximal Extractable Value), and PBS (Proposer-Builder Separation) research, with a steady inflow of new players in the crypto mechanism design space.

In particular, in the last years Compositional Game Theory has imposed itself as a reliable choice for fast prototypation and analysis of games and mechanisms.

Compositional Game Theory

Compared to other approaches in algorithmic mechanism design, Compositional Game Theory[3] relies on a novel mathematical paradigm called Compositionality, which defines games as processes that can be composed out of the box in ways that preserve their semantics.

What this means in practice is that Compositional Game Theory allows for much faster model prototyping as games and mechanisms can be built modularly as one would do in computer programming. This is in stark contrast with the majority of algorithmic game theory software stacks, that rely on monolithic design paradigms.

Compositional Game Theory is implemented in Haskell[4] and is open source under the MIT license. Among other things, its core development has been founded by two Ethereum Foundation grants[5][6], and the core stack is in the process of being fully and natively integrated with the Ethereum Virtual Machine.

Impact on the ecosystem so far

Up to now, Compositional Game Theory has proved itself a valuable tool in the study of problems in consensus[7], Proposer Builder Separation[8] and MEV[9]. Many well-known teams in the space - such as the Ethereum Foundation or Flashbots - have indeed used Compositional Game Theory either internally or in collaboration with specialized consulting firms.

Moreover, Compositional Game Theory is being actively used to research into innovative governance systems both in the context of DAOs and regenerative economics[10].

Finally, Compositional Game Theory is also being used also as a tool for financial incentive auditing by specialized auditing firms[11][12], demostrating value that goes beyond theoretical research.

The monad-bayes library and Monte Carlo methods

In the beginning, Compositional Game Theory was implemented as a purely research-oriented project. As such, optimization was not considered to be a priority.

Given the overwhelming interest this software stack is receiving from the ecosystem, these priorities have changed, and we have been working very hard to boost performance.

Among the many things that can be improved, the most important one revolves around Monte Carlo methods[13]: Compositional Game Theory works in a Bayesian setting, meaning that agents can reason probabilistically and mechanisms can be analyzed in terms of mixed strategies. Monte Carlo methods rely on random sampling to obtain numerical results, that is, they draw a value from the distribution and run the algorithm deterministically on it. Drawing enough values allows to build probabilistically faithful results.

Clearly, since the algorithm runs independently on each random input, Monte Carlo methods are naturally prone to scaling. The more GPU cores one has, the more these simulations can be parallelized.

The monad-bayes library

Unfortunately, the library that the Compositional Game Theory engine uses, called monad-bayes, is not optimized for parallelization. This leaves us with three options:

• Port the software to another language;
• Swap monad-bayes for another library;
• Implement parallelization features on monad-bayes.

Of these three alternatives, the less time-consuming and financially intensive one is by far the latter. With this grant, we hope to be able to pay for developer time to implement parallelization features on monad-bayes.

Benefits for the ecosystem

Having a parallelizable monad-bayes library will have multiple effects on the ecosystem:

1. All code using the monad-bayes library will benefit from parallelization. The Haskell programming language has been heavily employed to implement dev tools in the Ethereum ecosystem, most notably Dapptools and Echidna, which as a smart contract fuzzer would benefit from Monte Carlo parallelization directly.
2. Projects relying on Compositional Game Theory for modelling and research will benefit from a considerable speedup. This will make the application of mechanism design to web3 more scalable, widespread and, most importantly, more and more related to real world applications.

Roadmap and costs

1. Defining benchmarking scenario and metrics for evaluation (1 week)
2. Parallelization and multi-threading of particles (6 weeks)
3. GPU acceleration (6 weeks)
4. Test of implementation in actual use-case (2 weeks)

The project requires one programmer (familiar with Haskell and the relevant libraries). We estimate the costs at 30k USD.

References

[1]: monad-bayes on Hackage [2]: monad-bayes on github [3]: Introduction to Compositional Game Theory at EthCC[6] [4]: Compositional Game Theory repo [5]: EF Grant 1 - Software Engine for Game Theoretical Modeling [6]: EF Grant 2 - Game Theory Backend for Act [7]: PoS consensus attack analysis [8]: flashbots: FRP-27: Auction Simulations under PBS [9]: flashbots: FRP-26: Credible Commitments via Open Games [10]: arXiv: Composing games into complex institutions [11]: example of incentive auditing using Compositional Game Theory: manifold finance [12]: example of incentive auditing using Compositional Game Theory: blockswap [13]: wikipedia: Monte Carlo methods