Parallelized Monte Carlo methods for algorithmic mechanism design

$733.16 crowdfunded from 830 people

$236.54 received from matching pools

100%
average score over 1 application evaluations
Implementing parallelization and GPU acceleration for the Haskell 'monad-bayes' library, enhancing performance for Ethereum-based probabilistic programming and game theory applications.

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

Parallelized Monte Carlo methods for algorithmic mechanism design History

  • accepted into Ethereum Infrastructure 1 year ago. 830 people contributed $733 to the project, and $237 of match funding was provided.

People donating to Parallelized Monte Carlo methods for algorithmic mechanism design, also donated to

Developing web3 tech for nonprofits, with multilingual, zero-fee, crypto donation platforms, referral rewards, NFT collections, and plans for Quadratic Funding and DAO integration.
Praise is a digital platform enhancing community engagement through gratitude, providing insights, reputation scoring, and fostering a cooperative culture with tangible rewards.
Pairwise is an open-source, snapshot-style voting dApp designed to make Web3 community governance engaging and straightforward, reducing voter apathy and improving decision-making efficiency.
Revolutionizing impact-driven communities with sustainable token economics for governance and funding, empowering global initiatives to address economic, environmental, and social challenges through Commons Stack's collaborative tools and protocols.
Advocate for public goods conducted educational events and workshops, managed a successful Gitcoin grant round, and engaged African communities in funding impactful projects.