Skip to main content

Computing a balanced solution

This is a technical note with algorithmic considerations related to the validator election protocol under NPoS. We consider a scenario where a committee of validators has already been elected, and we explore the best way to assign the nominators' stake to them. The reader should already be familiar with our research paper, and in particular the concept of balanced solutions defined in it. Although we prove in that paper that balanced solutions can be computed efficiently, not many details are given about it. Such details are presented in this note.

After establishing some notation, we introduce the balancing problem and explain why this is exactly the problem we need to solve. We then establish two algorithmic ways to solve the balancing problem, namely 1) using parametric flow algorithms, and 2) using a heuristic called star balancing, and we compare them.

1. Notation

We consider an instance of NPoS consisting of a bipartite graph (NA,E)(N\cup A, E), where NN is the set of nominators, AA is a committee of elected validators of size kk, with k:=ANk:=|A|\ll |N|, and there is an edge nvEnv\in E whenever nominator nn approves of validator vAv\in A. We are also given a vector sR0Ns\in\mathbb{R}^N_{\geq 0} of nominator stakes, where sns_n is the stake of nominator nn. An edge weight vector wR0Ew\in \mathbb{R}^E_{\geq 0} is feasible if it is component-wise non-negative and observes the constraints: vA: nvEwnvsn\sum_{v\in A: \ nv\in E} w_{nv} \leq s_n for each nominator nNn\in N. We say that ww is tight if the previous inequality is tight for each nominator nn that has at least one neighbor in AA.

Let B{0,1}A×EB\in \{0,1\}^{A\times E} be the node-edge incidence matrix for the validator set AA. For any wR0Ew\in \mathbb{R}_{\geq 0}^E, the total support that ww assigns to each validator in AA is given by the vector suppw:=BwRAsupp_w :=Bw\in \mathbb{R}^A, so that for any validator vAv\in A, its support suppw(v)=(Bw)v=nN: nvEwnvsupp_w(v)=(Bw)_v = \sum_{n\in N: \ nv\in E} w_{nv} is the total amount of stake that ww assigns to vv from the nominators.

Given an instance as above, the balancing problem consists of finding a tight vector ww that minimizes the squared 2\ell_2 norm of the support vector, i.e. minimize the value

val(w):=suppw2=Bw2.val(w):= \|supp_w\|^2 = \|Bw\|^2.

Clearly, an optimal solution to this problem corresponds precisely to a balanced solution, as defined in our paper.

2. Algorithms

There are three possible ways to solve the balancing problem:

  1. Via convex programming: it can be solved with numerical methods for convex quadratic programs, but this is too computationally expensive to consider any further.
  2. Via parametric flow algorithms: We show in the research paper that the balancing problem can potentially be solved in time O(Ek+k3)O(|E|k + k^3) using some advanced techniques for parametric flow problems.
  3. Via a simple combinatorial heuristic: the star balancing heuristic starts with any tight vector ww and converges to an optimal vector ww^* by following a local weight-balancing rule. It executes in time O~(Ek2)\tilde{O}(|E|k^2), ignoring logarithmic factors.

At first look, the worst-case complexity bound is much better for technique 2 than for technique 3. However, we point out that Babenko et al. (2007) studied a parametric max flow problem closely related to the balancing problem and performed experimental evaluations of both of these techniques, over real data for an application in revenue optimization as well as over synthetic data. They concluded that the performance of star balancing is actually comparable to that of parametric flow algorithms, except for instances with degenerate graph topologies. In fact, they conjecture that these two techniques have similar complexities whenever the underlying graph has moderately good expansion properties.

In view of this and of the fact that star balancing is vastly easier to implement than the algorithm based in parameter flow, we suggest that star balancing be used for NPoS.

3. The star balancing heuristic

Star balancing is a combinatorial randomized algorithm that outputs a solution arbitrarily close to optimal with high probability (this is what is known as a polynomial-time randomized approximation scheme, or PRAS). We remark that a different analysis to this algorithm can be found in Tarjan et al. (2006). We show the following.

Theorem: For any fixed parameters ε,δ>0\varepsilon, \delta>0, the star balancing algorithm returns a tight weight vector ww whose value val(w)val(w) has a probability at least (1δ)(1 - \delta) of being within a multiplicative factor at most (1+ε)(1+\varepsilon) from minimal, and runs in time O(Ek2log(k/εδ)).O(|E|k^2 \log (k/\varepsilon \delta)).

Algorithm: Star balancing.

Consider an instance (NA,E,s)(N\cup A, E, s). For each nominator nNn\in N let AnAA_n\subseteq A be its set of neighbors in AA.

Fix constants ε,δ>0\varepsilon, \delta>0. The algorithm starts with an arbitrary tight vector ww, and improves it iteratively by performing rr rounds, where we will give a precise value for rr and prove that r=O(Nk2log(k/εδ))r = O(|N|k^2\log(k/\varepsilon \delta)).

  1. Find any tight vector ww.

  2. Repeat rr times: a. Select a nominator nNn\in N uniformly at random. b. Modify the weights of the edges incident to nn, keeping ww tight and observing the non-negativity constraints, so that the supports of the neighboring validators are as close to each other as possible, i.e. so that

    v,vAn, suppw(v)>suppw(v)wnv=0.\forall v,v'\in A_n, \ supp_w(v)>supp_w(v') \rightarrow w_{nv}=0.

  3. Return ww.

Running time: Consider a round of the algorithm. If nominator nn is selected, the running time of the round is O(An)O(|A_n|), assuming that floating-point arithmetic operations take constant time. Hence, the average running time per round is proportional to 1NnNAn=EN\frac{1}{|N|}\sum_{n\in N} |A_n|=\frac{|E|}{|N|}. Together with the bound on rr, we obtain a global running time of O(rE/N)=O(Ek2log(k/εδ)).O(r|E|/|N|) = O(|E|k^2\log(k/\varepsilon \delta)).

Analysis: For each iri\leq r, let wiw^i be the state of weight vector ww at the end of the ii-th round, and let w0w^0 be the initial vector. Let ww^* be an optimal solution. Let's start with an easy observation.

Lemma 1: val(w0)kval(w)val(w^0)\leq k\cdot val(w^*).

Proof: Recall that the objective value to minimize is val(w)=Bw22=suppw22val(w)=\|Bw\|^2_2=\|supp_w\|_2^2. As both w0w^0 and ww^* are tight, the 1\ell_1 norm of their support vectors are equal. Hence

val(w0)=Bw022Bw012=Bw12kBw22=kval(w).val(w^0)=\|Bw^0\|_2^2 \leq \|Bw^0\|_1^2 = \|Bw^*\|_1^2 \leq k\cdot \|Bw^*\|_2^2 = k\cdot val(w^*).

Next we show that, in expectation, the progress in objective value perceived in each round is proportional to the difference between the current and optimal values.

Lemma 2: For each round i{1,,r}i\in\{1,\cdots,r\} that starts with vector wi1w^{i-1} and ends with vector wiw^i, the expected objective value of wiw^i is such that val(wi1)E[val(wi)]1k2N[val(wi1)val(w)].val(w^{i-1}) - \mathbb{E}[val(w^{i})] \geq \frac{1}{k^2|N|} [val(w^{i-1}) - val(w^*)].

Proof: We fix a round ii, and for notational convenience we drop the superscripts ii and i1i-1 within the scope of this proof. In particular, we let ww be the initial vector, and let wnw'^n be the final vector in the case that nominator nn is picked in the round. Clearly, the expected progress in objective value equals the average progress 1NnN[val(w)val(wn)]\frac{1}{|N|}\sum_{n\in N} [val(w) - val(w'^n)]. To lower bound the latter, it is sufficient to exhibit a different family of weight vectors {wn}nN\{w^n\}_{n\in N} such that val(wn)val(wn)val(w'^n)\leq val(w^n) for each nn, and then bound the average progress when moving from ww to a member of that family.

Define the vector f:=wwREf:=w-w^*\in\mathbb{R}^E. The following is a necessary technical observation whose proof we delay temporarily.

Lemma 3: f2k2Bf2.\|f\|^2 \leq k^2 \|Bf\|^2.

Consider the decomposition of vector ff as f=nNfnf=\sum_{n\in N} f^n, where fnf^n is the restriction of ff over the edges incident to nominator nn, and define the family of weight vectors {wn:=w1k2fn}nN\{w^n:= w-\frac{1}{k^2} f^n\}_{n\in N}. We have val(wn)val(wn)val(w'^n) \leq val(w^n) for all nNn\in N as desired, because by construction (step 2.b. of the algorithm), wnw'^n is precisely the vector of minimum objective value among all maximally affordable vectors that differ from ww only at the edges incident to nn. Hence, it only remains to bound the average progress in objective value with respect to the new family.

For a fixed nNn\in N, we have

val(w)val(wn)=Bw2B(w1k2fn)2=2k2(Bw)Bfn1k4fn2.\begin{align} val(w) - val(w^n) &= \|Bw\|^2 - \|B(w-\frac{1}{k^2} f^n)\|^2 \\ & = \frac{2}{k^2} (Bw)^\intercal Bf^n - \frac{1}{k^4} \|f^n\|^2. \end{align}

Thus, the average progress over all nNn\in N is

1NnN[val(w)val(wn)]=2k2N(Bw)B(nNfn)1k4NnNfn2=1k2N[2(Bw)Bf1k2f2]1k2N[2(Bw)BfBf2]=1k2N(Bf)B(2wf)=1k2N[B(ww)]B(w+w)=1k2N[Bw2Bw2]=1k2N[val(w)val(w)],\begin{align} \frac{1}{|N|}\sum_{n\in N} [val(w)-val(w^n)] &= \frac{2}{k^2|N|}(Bw)^\intercal B(\sum_{n\in N}f^n) - \frac{1}{k^4|N|}\sum_{n\in N}\|f^n\|^2 \\ &= \frac{1}{k^2|N|}[2(Bw)^\intercal Bf - \frac{1}{k^2} \|f\|^2] \\ &\geq \frac{1}{k^2|N|}[2(Bw)^\intercal Bf - \|Bf\|^2] \\ & = \frac{1}{k^2|N|} (Bf)^\intercal B(2w-f) \\ &= \frac{1}{k^2|N|} [B(w-w^*)]^\intercal B(w+w^*) \\ &= \frac{1}{k^2|N|} [ \|Bw\|^2 - \|Bw^*\|^2] \\ &= \frac{1}{k^2|N|} [val(w) - val(w^*)], \end{align}

where the inequality comes from Lemma 3. This completes the proof of Lemma 2.


Proof of Lemma 3: We interpret ff as a flow over the network (NA,E)(N\cup A, E). As both ww and ww^* are tight, there is flow preservation over all nominators. Let As,AtAA_s, A_t\subseteq A be respectively the sets of sources and sinks, i.e. the sets of validators with net excess and net demand. By the flow decomposition theorem, there exists a decomposition f=vAsfvf=\sum_{v\in A_s} f^v into single-source subflows, where fvf^v has vv as its single source. We can assume that this decomposition generates no cycles by adjusting the choice of the optimal solution w=wfw^*=w-f.

Consider one of these subflows fvf^v. Its edge support looks like a directed acyclic graph (DAG) with single root vv. We arrange the edges on this DAG by levels, where the level of an edge is the length of the longest path from vv containing this edge. These levels start at 1 for the edges incident to vv, up to at most 2k2k because any simple path alternates between a nominator and a validator and there are only kk validators. We now split fvf^v by levels, fv=i2kfv,if^v=\sum_{i\leq 2k} f^{v,i}, where fv,if^{v,i} is the restriction of fvf^v over the edges at level ii. Since the excess in node vv is suppw(v)suppw(v)=(Bf)vsupp_w(v)-supp_{w^*}(v)=(Bf)_v and no other node in the DAG has any excess, the sum of edge weights along each level ii is fv,i1(Bf)v\|f^{v,i}\|_1 \leq (Bf)_v. Therefore,

fv22=i2kfv,i22i2kfv,i122k(Bf)v2.\|f^v\|_2^2 = \sum_{i\leq 2k}\|f^{v,i}\|_2^2 \leq \sum_{i\leq 2k} \|f^{v,i}\|_1^2 \leq 2k\cdot (Bf)^2_v.

Putting things together, we get

\begin{align} |f|^22 &= |\sum{v\in As} f^v|_2^2 \ &\leq |A_s|\sum{v\in As} |f^v|_2^2 \ & \leq 2k|A_s|\sum{v\in A_s} (Bf)_v^2 \ &= 2k|A_s|\cdot |Bf|_2^2, \ \end{align}

where the first inequality is an application of a Cauchy-Schwarz inequality.

In a similar manner, working with sinks instead of sources, we can obtain the bound f22kAtBf2\|f\|^2 \leq 2k|A_t| \cdot \|Bf\|^2. Summing up these two bounds and dividing by two, we get f2k(As+At)Bf2k2Bf2,\|f\|^2 \leq k(|A_s|+|A_t|) \cdot \|Bf\|^2 \leq k^2 \|Bf\|^2, which proves the claim.


For each round iri\leq r, consider the random variable Δi:=val(wi)val(w)\Delta^i:= val(w^i) - val(w^*), which represents how far from optimal the current solution is in terms of objective value. We now use Lemma 2 to show that Δi\Delta^i decays exponentially fast in expectation.

Lemma 4: For any 0<ir0<i\leq r, the expected value of Δi\Delta^i observes E[Δi]k(11k2N)ival(w).\mathbb{E}[\Delta^i] \leq k\cdot (1-\frac{1}{k^2|N|})^i val(w^*).

Proof: A reformulation of Lemma 2 gives E[Δi](11k2N)Δi1\mathbb{E}[\Delta^i]\leq (1-\frac{1}{k^2|N|}) \Delta^{i-1}. By induction and linearity of expectation, this implies that E[Δi](11k2N)iΔ0\mathbb{E}[\Delta^i]\leq (1-\frac{1}{k^2|N|})^i \Delta^0. Finally, Δ0=val(w0)val(w)<kval(w)\Delta^0 = val(w^0) - val(w^*) < k\cdot val(w^*) by Lemma 1.


Recall now that we want the value of the output solution val(wr)val(w^r) to be within a factor of (1+ε)(1+\varepsilon) from val(w)val(w^*) with probability at least (1δ)(1-\delta). The next lemma completes the analysis of the algorithm and the proof of the main theorem.

Lemma 5: If r=Nk2ln(k/ϵδ)r=\lceil |N|k^2\ln(k/\epsilon \delta) \rceil, then P[val(wr)>(1+ε)val(w)]δ\mathbb{P}[val(w^r) > (1+\varepsilon)val(w^*)]\leq \delta.

Proof: By Lemma 4 and the choice of value rr, it follows that E[Δr]ϵδval(w).\mathbb{E}[\Delta^r]\leq \epsilon\cdot \delta\cdot val(w^*).

As the variable Δr\Delta^r is non-negative, we can use Markov's inequality:

δP[Δr>E[Δr]δ]P[Δr>ϵval(w)]=P[val(wr)>(1+ϵ)val(w)],\delta \geq \mathbb{P}[\Delta^r > \frac{\mathbb{E}[\Delta^r]}{\delta}] \geq \mathbb{P}[\Delta^r > \epsilon\cdot val(w^*)] = \mathbb{P}[val(w^r) > (1+\epsilon)\cdot val(w^*)],

which is the claim.