A strange kind of pairwise-bounded quadratic funding

Economics
1

Prerequisites: https://vitalik.ca/general/2019/12/07/quadratic.html and Pairwise coordination subsidies: a new quadratic funding design

  • Let C_p be the vector of sqrt-contributions to p, so C_p[i] equals the square root of the amount that i contributed to project p.
  • Let M_p = C_p^{\top}C_p (this is the square matrix where M_p[i, j] equals C_p[i] * C_p[j]) and let M^* = \sum_p M_p
  • In normal QF, we would calculate the subsidy as \sum_{i \ne j} M_p[i, j]. In pairwise-bounded QF, we would calculate the subsidy as \sum_{i \ne j} \frac{M_p[i, j] * D}{D + M^*[i, j]} where D is a bounding coefficient.
  • Here, we instead let N_p = M_p^2 and N^* = (\sum_p M_p)^2 and calculate the subsidy as \sqrt{\sum_{i \ne j} \frac{N_p[i, j] * D}{D + N^*[i,j]}}.

Here it is in code:

import numpy

BOUND_COEFF = 100

def get_subsidies(donation_lists):
    coeff_squares = []
    for donations in donation_lists:
        sqrt_vec = numpy.matrix([[d**0.5 for d in donations]])
        coeffs = numpy.transpose(sqrt_vec) * sqrt_vec
        coeffs_sq = coeffs ** 2
        coeff_squares.append(coeffs_sq)
    o = []
    for donations, squares in zip(donation_lists, coeff_squares):
        total_sub = 0
        for i in range(len(donations)):
            for j in range(len(donations)):
                if j != i:
                    total_sub += BOUND_COEFF * squares[i, j] / (BOUND_COEFF + sum([c[i,j]**0.5 for c in coeff_squares])**2)
        o.append(total_sub ** 0.5)
    return o

The idea is roughly as follows. The matrix M_p = C_p^{\top}C_p counts pairs in C_o that both support the same project. The matrix N_p = M_p^2 counts triplets of users (x_1, x_2, x_3) that all support the same project. The matrix N* = (\sum_p M_p)^2 counts length-2 paths between different users (ie. A and B both support P1 and B and C both support P2), and is used to compute a “richer” measure of “closeness” between two participants that takes into account second-degree similarities.

The mechanism has some interesting properties (here we define get_subsidy(x) as the single-project equivalent, equal to get_subsidies([x])[0]):

  • Low-end multiplicativeness: get_subsidy(A * k) = k * get_subsidy(A) for A with small-sized elements (same as traditional QF and pairwise-bounded QF)
  • Low-end square-root incentive curve: get_subsidy(concat(A, [r])) - get_subsidy(A) \approx k * \sqrt{r} for small r (same as traditional QF and pairwise-bounded QF)
  • Split invariance: sum(get_subsidies([A, A])) = get_subsidy(A * 2) (same as traditional QF and pairwise-bounded QF)
  • Monotonic partial derivatives: get_subsidy(A + [r + d]) - get_subsidy(A + [r]) is increasing for small A, r, d
  • Low-end N^1.5 returns: get_subsidy([k] * N) \approx N^{1.5} for small k and N
  • N^1.5 max extraction from collusion: get_subsidy([k] * N) < c * N^{1.5} (note that the strategy for doing this is itself involved and requires many projects; with a single project you can only extract O(N) funds)

Thus, this version of QF seems to have all the nice properties of both traditional and pairwise, while having stronger properties against colluding attackers.

Note that there may be some flaw here, and indeed adding complexity generally increases risk of flaws, but it seems to work fine.

1 Like
2

It would be great to see a worked example of this, either theoretical or an example used in the field - any suggestions?

3

Vitalik, we are discussing the math behind this in the FDD workstream for Gitcoin. One of our squads is working on building simulations we can use to better protect Gitcoin grants.

A question popped up:
"Does he realize that sqrt(x) > x for 0 < x < 1?
“He must…but taking the square root here for a grant with small support actually pulls up the amount in an undesirable way.”
“Also worth mentioning here is hypergraphs…a generalization of graphs where we look at more than two vertices in an edge.”

If you’d like to join in, let me know.

2 Likes