ResearchUp to date by March 2021
Author: Danilo Lessa Bernardineli (BlockScience)
This is a terse math spec of the funding algorithm being utilized on Gitcoin Grants Rounds 8 as described on https://github.com/gitcoinco/web/blob/stable/app/grants/clr.py
\(\mathcal{G} = \bigcup{g}\): The set of all grants
\(\mathcal{U} = \bigcup{u}\): The set of all users
\(\mathcal{C} = \bigcup{c}\): The set of all collaborations
The collaborations are aggregated (sum) for each user and grant pair, so we have that: \(\mathcal{C} \subset \mathcal{G} \times \mathcal{U}\)
\(\mathcal{C}_g = \bigcup{c_g} \subset \mathcal{C}\): The set of all collaborations for a grant \(g\)
Note that due to the aggregation: \(C_g \subset 1 \times \mathcal{U}\)
\(u_i \in \mathcal{U}\): A user associated with a collaboration \(i\in \mathcal{C}\) (variable)
\(v_i \in \mathbb{R_+}\): A amount associated with a collaboration \(i \in \mathcal{C}\) (variable)
\(k \in \mathbb{R_+}\): Matching threshold (parameter)
\(\mathcal{T} \in \mathbb{R_+}\): Total pot for the current round (parameter)
\(P(a, b) = \mathcal{U} \times \mathcal{U} \to \mathbb{R_+}\): Pairwise totals between two users
\(T(u) = \mathcal{U} \to \mathbb{R_+}\): Trust bonus of a given user
\(M(g) = \mathcal{G} \to \mathbb{C}\): Theoretical CLR amount to be matched
\(\hat{M}(g) = \mathcal{G} \to \mathbb{R_+}: Re(M(g))\)
\(F(g) = \mathcal{G} \to \mathbb{R}\): Actual CLR amount to be matched
\([f]\): Iverson bracket
Reference: https://github.com/gitcoinco/web/blob/stable/app/grants/clr.py
\(P(a, b) = \sum_{i \in \mathcal{C}} \sum_{j \in \mathcal{C}} \sqrt{v_i * v_j} [a = u_i][b = u_j]\)
\(M(g) = k * \sum_{j \in \mathcal{C}_g} \sum_{i \in \mathcal{C}_g} \frac{\sqrt{v_i * v_j}} {1 + P(u_i, u_j)} * max(T(u_i), T(u_j)) * [i \neq j] * [i > j]\)
\(\sum M = \sum_{g \in \mathcal{G}} \hat{M}(g)\)
\(\begin{aligned} F(g) & = \mathcal{T}\frac{\hat{M}(g)}{\sum M} ,\; \sum M \gt \mathcal{T} \\ & = \hat{M}(g) * (1 + \frac{log(\mathcal{T} / \sum M)}{100}) ,\; \sum M \leq \mathcal{T} \end{aligned}\)
One natural extension is to expand the match summation over all grants:
\(\sum M = k * \sum_{j \in \mathcal{C}} \sum_{i \in \mathcal{C}} \frac{\sqrt{v_i * v_j}}{1 + \sqrt{v_i * v_j}} * max(T(u_i), T(u_j)) * [i \neq j] * [i > j]\) (derived)
We suppose then that the distribution associated with \(v_i * v_j\) is 'well-behaved' in the sense that it can be efficiently described by the first distribution moment: \(\langle v_i * v_j \rangle\). A example would be a Gaussian with \(\mu=15\) and \(\sigma=2\). Also, we define \(T = \bigcup_{g \in \mathcal{G}} T(g)\).
By taking limits over the collaboration amounts, we have that if \(\langle \sqrt{v_i * v_j} \rangle \gt \gt 1\), then \(\frac{\sqrt{v_i * v_j}}{1 + \sqrt{v_i * v_j}} \approx 1\), so:
\(\sum{M} \approx \frac{k (N - 1)^2}{2} * (\langle T \rangle + Std[T])\).
Where \(N\) is the total number of contributions to the CLR Round. Also, we can approximate \(max(T_i, T_j) \approx \langle T \rangle + \epsilon\), where we can adopt as a estimate: \(\epsilon = Std[T]\)
If \(\langle \sqrt{v_i * v_j} \rangle \approx 1\), then \(\frac{\sqrt{v_i * v_j}}{1 + \sqrt{v_i * v_j}} \approx \frac{1}{2}\), so:
\(\sum{M} \approx \frac{k (N - 1)^2}{4} * (\langle T \rangle + Std[T])\)
Supposing that \(\sum M \approx q(N-1)^2\), where \(q = k * \alpha * (\langle T \rangle + Std[T])\), where \(\alpha\) is a function of \(\langle v_i * v_j \rangle\):
\(\frac{d\sum{M}}{dN} \approx 2 q(N-1)\)
Or in a discrete formalism:
\(\Delta \sum M = 2q(N-1) \Delta N\)
This has the implication that in a limit case, the CLR match for a given contribution tends to increase linearly with the count of contributions. This can be a counter-intuitive result and has the implication that threshold for the total pot can be surpassed quickly even with a small total amount of contributions to all grants.
Note that this derivative is associated with the time arrow of the system. When the \(N\) increases by \(\Delta N > 0\) such that \(N^* = N + \Delta N\), then the associated time must necessarily be \(t^* = t + \Delta t\), such that \(\Delta t > 0\).
Another way of putting, is that if the time sequence of events are described by a Poisson process, such that \(\frac{\Delta N}{ \Delta t} = Poisson(\lambda) \leftrightarrow \langle N \rangle = \lambda t\), then:
Note that if we invert \(\sum M\) in regards to \(N\), we get a functional form that is identical to the quadratic voting canonical form.
\(N = 1 + \sqrt{\frac{\sum M}{q}} \leftrightarrow TotalVotes = 1 + \sqrt{TotalCost}\), where \(TotalVotes = N\) and \(TotalCost = \frac{\sum M}{q}\)
One direction that may be worth exploring in the future is a functional form for \(k\), such as \(k \propto \frac{1}{N \mathcal{F}}\)
This is a mathematical approach for defining \(\Delta \mathbf{P}\), which is the difference on the pair-wise product when a contribution is added/removed.
If we are not required to take a element-wise square root, it is possible to compute the pair-wise totals by keeping a minimal amount of state, while having a constant complexity factor \(O(k)\).
Else, it is needed to keep a extensive state in memory, and the complexity factor increases to \(O(n)\) in regards to the amount of 'neighboring' contributions-users pairs.
Vectors have arrows (eg: \(\vec{v}\))
Matrices are in bold (eg: \(\mathbf{M}\))
\(\mathbf{C}\): Contribution matrix, aggregated by user (shape: \(\mathcal{U} \times \mathcal{G} \to \mathbb{R}\))
\(\mathbf{P}\): Matrix of the pair-wise product (shape: \(\mathcal{U} \times \mathcal{U} \to \mathbb{R}\))
\(\mathbf{\Delta P}\): Difference on the matrix of the pair-wise product when there is a new collaboration (shape: \(\mathcal{U} \times \mathcal{U} \to \mathbb{R}\))
\(\vec{1}_\mathcal{G}\): Vector of ones. (shape: \(\mathcal{G} \to 1\))
\(\vec{\Sigma}_\mathcal{U}\): Total amount given by user (shape: \(\mathcal{U} \to \mathbb{R}\))
\(\vec{\sigma}\): New amount to be given (shape: \(\mathcal{U} \to \mathbb{R}\))
\(\vec{\Sigma}_\mathcal{U} = \mathbf{C} \cdot \vec{1}_\mathcal{G}\)
\(\mathbf{P}=\vec{\Sigma}_\mathcal{U} \cdot \vec{\Sigma}_\mathcal{U}^T\)
\(\Delta \vec{\Sigma}_\mathcal{U} = (\mathbf{C} + \mathbf{c}) \cdot \vec{1}_\mathcal{G}\)
\(\vec{\sigma} = \vec{c} \cdot \mathbf{1}^\mathcal{G}\)
\(\mathbf{\Delta P} = \vec{\sigma} \cdot \mathbf{\Sigma}_\mathcal{U}^T +\mathbf{\Sigma}_\mathcal{U} \cdot \vec{\sigma}^T + \vec{\sigma} \cdot \vec{\sigma}^T\)
\(\mathbf{C}\)
\(\mathbf{c}\)
\(\vec{\Sigma}_\mathcal{U}\)
\(\vec{\sigma}\)
\(\mathbf{P}\)
\(\mathbf{\Delta P}\)
Vectors have arrows (eg: \(\vec{v}\))
Matrices are in bold (eg: \(\mathbf{M}\))
\(\mathbf{C}\): Contribution matrix, aggregated by user (shape: \(\mathcal{U} \times \mathcal{G} \to \mathbb{R}\))
\(\vec{M}\): Quadratic match vector (shape: \(\mathcal{G} \to \mathbb{R}\))
\(\vec{M} = diag(\mathbf{C}^T \cdot \mathbf{P_\pi} \cdot \mathbf{C})\)
\(\mathbf{P_\pi}\): Permutation Matrix such that \(\pi(n) = n+k, \forall k \in \mathbb{N} \lt |\mathcal{U}|\)
\(\vec{c}\)
\(\vec{M}\)
\(\Delta \vec{M}\)
Be aware of bugs
This is one is difficult to proceed within a linear algebra formalism due to the different dimensions of the simple quadratic match vector and the pair-wise product matrix.
However, it is possible to use the independency among summating terms to perform approx:
\(\Delta M(v_i) = k \sum_{j \in \mathcal{C}_g} \frac{\sqrt{v_i * v_j}}{1 + P(u_i, u_j)} * max(T(u_i), T(u_j))\)
This reduces the algorithm complexity to \(O(n)\) in regards to the number of contribution to the receiving grant
\(M(g) + \Delta M(g) = k * \sum_{j \in \mathcal{(C+c)}_g} \sum_{i \in \mathcal{(C+c)}_g} \frac{\sqrt{v_i * v_j}} {1 + P(u_i, u_j)} * max(T(u_i), T(u_j)) * [i \neq j] * [i > j]\)
\(\Delta M(g) = \alpha + \beta\)
\(\alpha (j=Last) = k * 1 * \sum_{i \in \mathcal{(C+c)}_g} \frac{\sqrt{v_i * v_j}} {1 + P(u_i, u_j)} * max(T(u_i), T(u_j)) * [i \neq j] * [i > j] = 0\)
\(\beta (i=Last) = k * \sum_{j \in \mathcal{(C+c)}_g} * 1 * \frac{\sqrt{v_i * v_j}} {1 + P(u_i, u_j)} * max(T(u_i), T(u_j)) * [i \neq j] * [i > j]\)
**Given a new contribution
**
\[ Overlap = A_{up} B_{pv} = C_{uv} \]
\[ \mathbb{k} = \frac{m}{m + o} \]
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe