metadata: {"signature": "0xfa3da5fbcc1189668b3a254a3e3450925b9c2e09338373842345499ad84160700bb87f9c7bbec2ab142a02e0719368a42ba43c2ce7d931525841a9d18aabc1571b", "application": {"round": "0x222ea76664ed77d18d4416d2b2e77937b76f0a35", "answers": [{"type": "email", "hidden": true, "question": "Email Address", "questionId": 0, "encryptedAnswer": {"ciphertext": "UPXST5cbwZimD8pfP83yl5rUAruzXISY3H5weYY0N01XyebsqB95GK+da+4HxrDc", "encryptedSymmetricKey": "19f875d090126a6537428a6e05c8fd0e956543f30faceaba4cd362906c7d54bddbb1a8e5e4bdada666cd09d7754c98172cc95cdff2b6267da68d0a53f8daadb22723d8525ed8d33c0522224ee309cb4eae5955885410583a2986cf7c7ceefe91d6669c335fd6ad13c0edfab54e5adc724ae23c4d362bf8a834c389df4dce34c900000000000000207a34de570a284fb1d28ec1993305dc21243a4ddcf24b384b3323e602d175e0027707eb03377e67da67b981b285d4e489"}}, {"type": "link", "answer": "https://github.com/CyberCat-Institute/open-game-engine", "hidden": false, "question": "Project GitHub Repo", "questionId": 1}, {"type": "short-answer", "hidden": true, "question": "Telegram Handle", "questionId": 2, "encryptedAnswer": {"ciphertext": "RzHTvSbXTBYdaN4I9Tu8Ru50T5sMde0RDA95uKfz6H8=", "encryptedSymmetricKey": "124cdb52af71a1f7a3c4a1f3c58c5bc869e7b82a1e3aeb922811bd5bf84c8e8b60ff73f40485697e180d2be79ede710451454d2248a39bcda444128b7a2b4797395e6d4c543f172ba7dac66423790f270b7b1404ef409db26e2954157255b8865e372d0843283cbba95c1c097ae3642a4d0abcfdac7bc4d30d1a05428299f5220000000000000020123de78281445863c3c5274771bb9ab7bb276cb1b7c4365ac0e35453cb241b887a4bdbcc8331c455e3eb39705c99dbb1"}}, {"type": "link", "hidden": false, "question": "Link to your Public Group Chat (Discord or Telegram)", "questionId": 3}, {"type": "number", "answer": "152000", "hidden": false, "question": "Total prior funding for the project in USD", "questionId": 4}, {"type": "paragraph", "answer": "We received two grants from the Ethereum Foundation up to now. \nThe first was 32k USD, under the name 'Software Engine for Game Theoretical Modeling':\nhttps://blog.ethereum.org/2021/07/01/esp-allocation-update-q1-2021\nThe second was 120k USD, and is still active. It is filed under the name 'Game Theory Backend for ACT':\nhttps://blog.ethereum.org/2022/12/07/esp-allocation-q3-22\n\nWe applied for both grants when CyberCat Institute wasn't yet an independent entity, so the grants are filed under different affiliations.", "hidden": false, "question": "Please expand on how much funding you\u2019ve received from each funding source and when? (VC, grants by foundation, token sales, etc)", "questionId": 5}, {"type": "number", "answer": "5", "hidden": false, "question": "Total team size", "questionId": 6}, {"type": "number", "answer": "36", "hidden": false, "question": "How old (in Months) is the project?", "questionId": 7}, {"type": "address", "answer": "", "hidden": true, "question": "If you participated in past grant rounds using a different project payout wallet address, please share it here:", "questionId": 8}, {"type": "paragraph", "answer": "https://twitter.com/_julesh_", "hidden": false, "question": "Profiles or socials of other main team members publicly associated with the project:", "questionId": 9}, {"type": "multiple-choice", "answer": "No", "hidden": true, "question": "Have you read and confirmed your grant abides by the Program General Eligibility Policy? https://gitcoin.notion.site/GG18-Eligibility-cb4a5754c56043d4b3ed34eddbac261c?pvs=4", "questionId": 10}, {"type": "paragraph", "answer": "This project is about rewriting a library component for a software that is part of the dev tooling employed by many Ethereum researchers and teams. It doesn't get more 'Ethereum Infrastructure' than this, to be honest.", "hidden": false, "question": "Please explain how your project meets the round-specific eligibility criteria", "questionId": 11}, {"type": "paragraph", "answer": "We never participated in any Gitcoin grant round.\n\nAs for the Ethereum Foundation grants mentioned above, we've been meeting all the relevant milestones within the established deadlines up to now (the second grant is still open so things may still go badly, but at the moment we're aligned with what we planned!)", "hidden": false, "question": "If you've participated in past grant rounds, please share any new updates or milestones from the prior months", "questionId": 12}, {"type": "paragraph", "answer": "The simplest metrics are:\n- Computation performance benchmarks, since this grant is about optimization;\n- The increase in the number of people using Compositional Game Theory in their workflow, to measure impact on the community.", "hidden": true, "question": "How do you measure the impact of your project? Please provide examples and/or standard metrics. This might be used in future impact reports", "questionId": 13}, {"type": "paragraph", "answer": "We know this isn't the most exciting project ever, but it is nevertheless much needed. This library lies very deep in the stack, but making it faster means that a tool being heavily used in economic simulations gets faster. Which in turn means that more builders and teams will be able to build more economically reliable code. Which hopefully means less TERRA/LUNA situations, basically.", "hidden": false, "question": "Anything else you'd like to share about your project, previous work, or other project affiliations? Anything you'd like to add that may help in determining project eligibility?", "questionId": 14}, {"type": "multiple-choice", "answer": "No", "hidden": true, "question": "Would you like to opt-in to future messages from Gitcoin for updates, information, and/or interviews?", "questionId": 15}, {"type": "multiple-choice", "answer": "No", "hidden": true, "question": "Would you like to opt-in to us sharing your information with select third-parties for investment opportunities?", "questionId": 16}, {"type": "multiple-choice", "answer": "Europe", "hidden": false, "question": "Location/Region where the project is based", "questionId": 17}], "project": {"id": "1:0x03506eD3f57892C85DB20C36846e9c808aFe9ef4:1080", "title": "Parallelized Monte Carlo methods for algorithmic mechanism design", "metaPtr": {"pointer": "bafkreiavjw5ncqoeigdzsdrxv3ifwo6ivsxalkq4mtd6yfa2nnkgpetfmq", "protocol": "1"}, "website": "https://github.com/CyberCat-Institute/open-game-engine", "createdAt": 1691757222628, "userGithub": "fabrizioromanogenovese", "credentials": {"github": {"type": ["VerifiableCredential"], "proof": {"jws": "eyJhbGciOiJFZERTQSIsImNyaXQiOlsiYjY0Il0sImI2NCI6ZmFsc2V9..eoCOQKM0BKbmecWuC4hsNhXdkZAIcsoYuhYGDF1l5HwRdf_Rhl13m4X0Lm0qBJyQRftgUuaDHVfnTKuGW854BQ", "type": "Ed25519Signature2018", "created": "2023-08-11T13:02:06.043Z", "proofPurpose": "assertionMethod", "verificationMethod": "did:key:z6MkghvGHLobLEdj1bgRLhS4LPGJAvbMA1tn2zcRyqmYU5LC#z6MkghvGHLobLEdj1bgRLhS4LPGJAvbMA1tn2zcRyqmYU5LC"}, "issuer": "did:key:z6MkghvGHLobLEdj1bgRLhS4LPGJAvbMA1tn2zcRyqmYU5LC", "@context": ["https://www.w3.org/2018/credentials/v1"], "issuanceDate": "2023-08-11T13:02:06.043Z", "expirationDate": "2023-11-09T13:02:06.043Z", "credentialSubject": {"id": "did:pkh:eip155:1:0x9f2589aEDe1BB71E7513B3F1be6BC8e6F2ab6136", "hash": "v0.0.0:BCcJAO3AMyBvYuL/SmbEEDTvid+PP6h/zmV71tRrqko=", "@context": [{"hash": "https://schema.org/Text", "provider": "https://schema.org/Text"}], "provider": "ClearTextGithubOrg#CyberCat-Institute#16508879"}}}, "description": "## Project summary\nThis project aims to implement parallelization and GPU acceleration features for the `monad-bayes`[1][2] Haskell library, a probabilistic programming library. \n\nThese 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.\n\n## Extended description\n\nThe 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. \n\nIn particular, in the last years *Compositional Game Theory* has imposed itself as a reliable choice for fast prototypation and analysis of games and mechanisms.\n\n### Compositional Game Theory\n\nCompared 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.\n\nWhat 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.\n\nCompositional 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.\n\n\n\n#### Impact on the ecosystem so far\n\nUp 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.\n\nMoreover, Compositional Game Theory is being actively used to research into innovative governance systems both in the context of DAOs and regenerative economics[10].\n\nFinally, 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.\n\n### The `monad-bayes` library and Monte Carlo methods\n\nIn the beginning, Compositional Game Theory was implemented as a purely research-oriented project. As such, optimization was not considered to be a priority.\n\nGiven 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.\n\nAmong 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.\n*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.\n\nClearly, 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.\n\n### The `monad-bayes` library\n\nUnfortunately, the library that the Compositional Game Theory engine uses, called `monad-bayes`, is not optimized for parallelization. This leaves us with three options:\n\n- Port the software to another language;\n- Swap `monad-bayes` for another library;\n- Implement parallelization features on `monad-bayes`.\n\nOf 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`.\n\n## Benefits for the ecosystem\n\nHaving a parallelizable `monad-bayes` library will have multiple effects on the ecosystem:\n\n1. 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](https://dapp.tools/) and [Echidna](https://github.com/crytic/echidna), which as a smart contract fuzzer would benefit from Monte Carlo parallelization directly.\n2. 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.\n\n\n\n## Roadmap and costs\n\n1. Defining benchmarking scenario and metrics for evaluation (1 week)\n2. Parallelization and multi-threading of particles (6 weeks) \n3. GPU acceleration (6 weeks)\n4. Test of implementation in actual use-case (2 weeks)\n\nThe project requires one programmer (familiar with Haskell and the relevant libraries). We estimate the costs at 30k USD. \n\n#### References\n\n\n[1]: [`monad-bayes` on Hackage](https://hackage.haskell.org/package/monad-bayes)\n[2]: [`monad-bayes` on github](https://github.com/tweag/monad-bayes)\n[3]: [Introduction to Compositional Game Theory at EthCC[6]](https://www.youtube.com/watch?v=QQMDj0HN2zs)\n[4]: [Compositional Game Theory repo](https://github.com/CyberCat-Institute/open-game-engine/)\n[5]: [EF Grant 1 - Software Engine for Game Theoretical Modeling](https://blog.ethereum.org/2021/07/01/esp-allocation-update-q1-2021)\n[6]: [EF Grant 2 - Game Theory Backend for Act](https://blog.ethereum.org/2022/12/07/esp-allocation-q3-22)\n[7]: [PoS consensus attack analysis](https://github.com/20squares/block-validation)\n[8]: [flashbots: FRP-27: Auction Simulations under PBS](https://collective.flashbots.net/t/frp-27-auction-simulations-under-pbs/1629)\n[9]: [flashbots: FRP-26: Credible Commitments via Open Games](https://collective.flashbots.net/t/frp-26-credible-commitments-via-open-games/1616)\n[10]: [arXiv: Composing games into complex institutions](https:/arxiv.org/abs/2108.05318)\n[11]: [example of incentive auditing using Compositional Game Theory: manifold finance](https://github.com/20squares/manifold-finance/tree/main/manifold-hedger)\n[12]: [example of incentive auditing using Compositional Game Theory: blockswap](https://github.com/20squares/C002-BlockSwap/tree/main/blockswap-PoN)\n[13]: [wikipedia: Monte Carlo methods](https://en.wikipedia.org/wiki/Monte_Carlo_method)", "lastUpdated": 0, "projectGithub": "CyberCat-Institute", "projectTwitter": "cybercatinst"}, "recipient": "0x93793660aa3Bad1252548c86feD0e2e4e28dD0bc"}}