# Gitcoin Grant CLR match math spec

###### tags: `Research`

:::info
Up 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

## Terminology

### Sets

$\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}$

### Objects

$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)

### Functions

$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](https://en.wikipedia.org/wiki/Iverson_bracket)

## Definitions

**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}$

## Implications

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}}$

---

## Optimizing the Quadratic Match Algorithm

### Pair-wise totals

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.

#### Meanings

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}$)

#### Expressions

$\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$

#### Examples

---

$\mathbf{C}$
- | A | B
- | - | -
a | $w_{a, A}$ | $w_{a, B}$
b | $w_{b, A}$ | $w_{b, B}$
c | $w_{c, A}$ | $w_{c, B}$

$\mathbf{c}$
- | A | B
- | - | -
a | v | 0
b | 0 | 0
c | 0 | 0

---

$\vec{\Sigma}_\mathcal{U}$
- | -
- | -
a | $w_{a, A} + w_{a, B}$
b | $w_{b, A} + w_{b, B}$
c | $w_{c, A} + w_{c, B}$

$\vec{\sigma}$
- | -
- | -
a | v
b | 0
c | 0

---

$\mathbf{P}$
- | a | b | c
- | - | - | -
a | $(w_{a, A} + w_{a, B})^2$ | $(w_{a, A} + w_{a, B})*(w_{b, A} + w_{b, B})$ | $(w_{a, A} + w_{a, B})*(w_{c, A} + w_{c, B})$
b | $(w_{b, A} + w_{b, B})*(w_{a, A} + w_{a, B})$ | $(w_{b, A} + w_{b, B})^2$ | $(w_{b, A} + w_{b, B})*(w_{c, A} + w_{c, B})$
c | $(w_{c, A} + w_{c, B})*(w_{a, A} + w_{a, B})$ | $(w_{c, A} + w_{c, B})*(w_{b, A} + w_{b, B})$ | $(w_{c, A} + w_{c, B})^2$

$\mathbf{\Delta P}$

- | a | b | c
- | - | - | -
a | $v^2$ | $v(w_{b, A} + w_{b, B})$ | $v(w_{c, A} + w_{c, B})$
b | $v(w_{b, A} + w_{b, B})$ | 0 | 0
c | $v(w_{c, A} + w_{c, B})$ | 0 | 0

### Simple Quadratic Match

#### Meanings

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](https://en.wikipedia.org/wiki/Permutation_matrix) such that $\pi(n) = n+k, \forall k \in \mathbb{N} \lt |\mathcal{U}|$

#### Examples

---
$\vec{c}$
- | - |
- | - |
A | v |
B | 0 |

$\vec{M}$
- | - |
- | - |
A | $w_{a, A} w_{b, A} + w_{a, A} w_{c, A} + w_{b, A} w_{c, A}$ |
B | $w_{a, B} w_{b, B} + w_{a, B} w_{c, B} + w_{b, B} w_{c, B}$ |

$\Delta \vec{M}$
- | - |
- | - |
A | $v * (w_{a, A} + w_{b, A} + w_{c, A})$ |
B | $0$ |

### Quadratic Match with Pair Wise

:::danger
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
**

1. We update P by using $\Delta P$
2.

### Einstein Summations

$$
Overlap = A_{up} B_{pv} = C_{uv}
$$

$$
\mathbb{k} = \frac{m}{m + o}
$$