2nd research iteration results & roadmapping

tags: gitcoin Reports

Authors: Danilo Lessa Bernardineli

Results under the original scope

• The definitions & methodology of the research plan were sucessfully implemented
  • This includes creating rewiring optimizers based on Hill Climbing and Simulated Annealing that were pushed to the NetworkX module

^{_{Source: https://github.com/gitcoinco/gitcoin_cadcad_model/tree/main/optimality_gap}}

• We have the capacity of knowing the Optimality Gap under limited circumstances
  • The current capacity is limited due to the complexity factor of the current QF algorithm implementation, which is quadratic: \(O(n^2)\)

^{_{Source: https://github.com/gitcoinco/gitcoin_cadcad_model/blob/main/optimality_gap.ipynb}}

• The further testing of the proposed hypothesis is blocked by further R&D
  • Large-scale analysis and simulations requires potentially tens of thousands of evaluations, or the adoption of better heuristics. A more comprehensive mathematical description of the algorithm could also create shortcuts.

^{_{Source: https://github.com/gitcoinco/gitcoin_cadcad_model/blob/main/optimality_gap.ipynb}}

Results Outside the scope

• We've written drafts of mathematical specs that could result in drastic improvements to QF evaluation performance on operations and research.

^{_{Source: https://hackmd.io/7HYPPp7zQcShQLrKQ2KOxQ?view#Simple-Quadratic-Match}}

• We've tested the effect of attack vectors under limited subsets of the Gitcoin Grants data.

^{_{Source: https://github.com/jiajia20/GitCoin_attack/blob/main/attack_vector.ipynb}}

^{_{Source: https://github.com/gitcoinco/gitcoin_cadcad_model/blob/main/attack_vector_ab_test.ipynb}}

• We've promoted public research interest on Gitcoin and Quadratic Funding.

^{_{Source: https://www.notion.so/Gitcoin-Modelling-Co-Lab-TL-DR-dba6e25863a1413a81e75f989f4a1f67}}

Next Steps

• Improving the scalability of the Optimality Gap calculations
  • Starting point heuristics based on attack vectors
  • Iterative rewiring algorithm for QF
  • Linear Algebra formalism for QF
  • Researching analytical solutions for optimizing QF

• Investigating the effect of attack vectors under a range of scenarios on synthetic / subset scenarios
  • What if the distribution of the amounts change?

• Searching for attack vector patterns on synthetic / subset scenarios