Explore Group Wise Matching for Quadratic Funding

[samajammin]

Creating this issue to track previous research & development efforts.

As of 2023-10-01, work has paused on this, but we hope to return to this work soon™

Introduction

Quadratic Funding, in many existing implementations, relies on pairwise matching - a mechanism that calculates a similarity score between each pair of voters, using these scores to weight individual donations. This approach, however, has certain limitations. For one, the computation involved can be highly resource-intensive, and these difficulties compound when working within a SNARK.

Advancing Towards Group Wise Matching

To address these limitations, we have begun exploring the concept of group wise matching using K-means clustering, a notable shift from the pairwise paradigm. In this new approach, we treat voting weights across different projects on Quadratic Funding ballots as vectors. We then apply K-means clustering on these vectors to group voters into distinct clusters. Each vote’s weight is then determined inversely proportional to the size of the group it belongs to.

Advantages of Group Wise Matching

Group wise matching offers several distinct advantages:

1. Promotes Diversity of Opinions: It discourages ‘groupthink’ often perpetuated by influential figures or entities, thus ensuring a fairer distribution of resources.
2. Efficient Computation: Checking whether a vote belongs to the right cluster is more computationally efficient compared to pairwise Quadratic Funding.
3. Improved Performance within Snarks: The group wise matching approach is computationally less demanding within a snark, thereby improving overall performance. (Pairwise was unable to even finalize for produciton size voting rounds)
4. Visual Interpretability: Using K-means clustering provides a unique opportunity to visualize abstract interest space, thus enhancing interpretability and transparency.

Potential Next Steps

Our approach to group wise matching uses K-means on votes themselves, treating each person’s ballot as an interest vector weighted by donation amounts. This allows us to derive group-wise coefficients to weight donation amounts. This strategy presents some benefits and drawbacks. For instance, it confirms that voters represent the sum of the marginal utility they wish to see. It’s also O(1) to verify if the vector is in the cluster at the closest centroid, which eliminates the need to rerun the algorithm inside a snark.

In terms of progress, we are currently developing the algorithm and the initial circuits to evaluate its feasibility and ensure it aligns with our goals. We are also using data from previous Quadratic Funding rounds to simulate what payouts would have looked like under this new formula. This simulation will provide us with valuable insights and guide us in refining the algorithm as we move forward.

References

• MACI v1.0: pairwise coordination subsidy