1 Introduction↩︎

A voting process operates on an undirected connected graph \(G = (V,E)\) with \(n\) nodes representing agents, each holding its opinion, and \(m\) edges. The agents interact to reach an agreement on a single opinion. Such processes arise in a wide range of settings, including distributed and parallel computing, as well as the social sciences. In parallel and distributed systems, voting serves as a fundamental primitive for various tasks, e.g., for the leader-election task where the system must agree on a unique coordinator. At the same time, voting processes provide abstract models of real-world opinion dynamics, in which agents repeatedly exchange information and seek to converge to a common decision. In contrast to problems such as Byzantine consensus, voting processes assume honest behavior and aim for the final outcome reflecting a non-trivial function of the initial opinions rather than being adversarially chosen.

The standard pull voter model [1] is perhaps the most well-known voting process in parallel and distributed computing. In each discrete time step, a randomly chosen node \(u\in V\) selects a random neighbor \(v \in N(u)\) and adopts \(v\)’s opinion. The process converges to a state in which all nodes hold the same opinion and the convergence time can be characterized via the coalescence time of independent random walks. Moreover, the probability that a given opinion is elected is proportional to its initial support.

On the other hand, in the social sciences, models of opinion dynamics typically incorporate some notion of compromise when agents interact, rather than simple adoption of opinions held by others. This is often expressed by updating opinions toward a (weighted) average of other opinions, possibly including own opinion in this calculation. Prominent examples are the DeGroot model [2], in which agents repeatedly average their neighbors’ opinions, and bounded-confidence models such as the Deffuant–Weisbuch [3] and Hegselmann–Krause [4] models, in which compromise occurs only between sufficiently similar opinions.

In this paper we consider the discrete incremental voting (DIV) process introduced in [5], which bridges the gap between these two viewpoints. Nodes hold opinions from \([K]\mathrel{\vcenter{:}}= \{0,1,\ldots,K\}\) and aim to agree on a single opinion from this set. In each step, a node \(u\) and one of its neighbors \(v \in N(u)\) are chosen uniformly at random. However, instead of adopting \(v\)’s opinion outright, node \(u\) moves just one step in that direction, updating its opinion by \(+1\) or \(-1\), depending whether \(v\)’s opinion is larger or smaller. This process is formalized below in Protocol [prot:edgeinteraction] as Asynchronous-DIV. As for other voting models, the central questions are to determine the convergence time (called also the consensus, or voting, time) and characterize the probability distribution of the winning opinion.

Despite the simplicity of this process, its convergence time is much less understood than that of the standard pull voter model. The existing bounds apply only to restricted graph classes or to a limited initial discrepancy of opinions \(K\). We present the first general analysis of the convergence time of discrete incremental voting on arbitrary graphs. For any graph \(G\) with conductance \(\Phi(G)\) and the ratio of the average to smallest degree \(\gamma(G)\), we prove that the expected convergence time is \({O}\left(\frac{Kn \log (Kn)}{\Phi(G)^2} + \frac{\gamma(G) n^2}{\Phi(G)^2}\right)\) and show a nearly matching lower bound. For regular expander graphs, we obtain sharper bounds and prove that the final consensus concentrates with high probability on the initial average opinion (rounded up or down). On a technical level, our analysis introduces a new multi-scale potential framework that may be of independent interest as it is also suitable for certain load-balancing processes.

1.1 Related Work↩︎

1.1.0.1 Pull Voting.

For the standard voting process (pull voter model) in a connected graph \(G\), where nodes adopt opinions of randomly chosen neighbors, it is known that a given opinion \(s\) wins with probability \(d(s)/2m\), where \(d(s)\) is the sum of the degrees of the nodes initially holding opinion \(s\) [1]. In [6] the authors consider the synchronous version of this model and show that with constant probability the consensus is reached within \(O(\gamma(G) n /\Phi(G))\) rounds. This result can be adopted to the asynchronous setting, giving a bound of \(O(\gamma(G) n^2 / \Phi(G))\) steps. In [6], the authors also consider a biased variant of pull voting and dynamic graphs.

The authors of [7] derive a bound of \(O((1/(1-\lambda))\cdot (\log^4 n+\rho))\) on the expected convergence time of the synchronous pull voting. Here \(\lambda\) is the second largest (in absolute value) eigenvalue of the transition matrix of a random walk on \(G\) and \(\rho\) is the ratio of the square of the sum of node degrees over the sum of the squared degrees, which ranges from \(O(1)\) (star graph) to \(n\) (regular graphs). In [8] the authors introduce Linear Voting Model, which generalizes several models of voting, including asynchronous and synchronous pull voting and push voting, and derive bounds on the probability that a given opinion wins and on the expected voting time.

1.1.0.2 Related Opinion Dynamics.

In [9], the authors consider the synchronous MedianRule protocol on complete graphs with opinions drawn from an ordered set, say the set \([K-1]\). In each round each node selects two random neighboring nodes and updates its opinion to the median of its own opinion and the two neighbors’ opinions. [9] derives bounds on the convergence time of this process, considering also adversarial scenarios. Note that in the case of two initial opinions (\(K=2\)) this protocol reduces to picking the majority of the three opinions. However, this process does not always converge to a single opinion on general graphs.

Other widely studied consensus protocols include \(j\)-Majority dynamics. Every node samples randomly \(j\) neighbours and adopts the majority opinion among the sample. The variants for \(j\)=2 and \(j\)=3 have been analyzed under the names of Two-Choices dynamics [10]–[13] and the 3-Majority dynamics [13]–[17]. In averaging processes, the nodes adopt the average of the opinions of \(j\) random neighbors. Such processes are considered, for example, in [18], where tight bounds on the variance on the final opinion for regular graphs are derived. If the initial opinions do not depend on the number of nodes the variance is negligible, and hence the nodes are able to estimate the average of the initial node opinions. Interestingly, this variance does not depend on the graph structure. For further references, see the survey of consensus dynamics [19].

8pt

1.2 Additional Notation and Preliminaries↩︎

We assume \(V=\{1, \ldots, n\}\). Asynchronous-DIV is a Markov process evolving according to Protocol [prot:edgeinteraction]. We denote the random state at time \(t\ge 0\) (the beginning of step \(t\)) by \(\vec{{X}}\left({t}\right)=(X_1(t),\ldots,X_n(t))\) and its realization by \(\Vec{x}(t)=(x_1(t),\ldots,x_n(t))\), where \(X_i(t)\) and \(x_i(t)\) refer to the opinion held by node \(i\) at this time. Let \(\mathcal{X}(K)\mathrel{\vcenter{:}}= \{\Vec{x}=(x_1,\ldots,x_n): x_i\in[K]\}\) be the set of all possible configurations. For a configuration \(\Vec{x} = (x_1, \ldots, x_n)\), let \({x}_{\mathsf{max}} \mathrel{\vcenter{:}}= \text{max}_{i \in V}\: x_i\) and \({x}_{\mathsf{min}} \mathrel{\vcenter{:}}= \min_{i \in V}\: x_i\). The discrepancy is defined as \(\mathbf{disc}\left(\Vec{x}\right)\mathrel{\vcenter{:}}= {x}_{\mathsf{max}} - {x}_{\mathsf{min}}\le K\) and the degree-weighted average as \(\overline{W}(\Vec{x}) \mathrel{\vcenter{:}}= \frac{1}{2m}\sum_{i=1}^n d_i x_i\), where \(d_i\) is the degree of node \(i\). The convergence time from configuration \(\Vec{x}\) is a random variable defined as \[\begin{align} {T_G(\Vec{x})} &\mathrel{\vcenter{:}}= \min\left\{t\ge0: \Vec{X}(0) = \vec{x}, \mathbf{disc}\left(\vec{{X}}\left({t}\right)\right)=0\right\}. \end{align}\]

If \(K=1\), the opinion set is \(\{0,1\}\) and Asynchronous-DIV coincides with the standard (2-value) pull voting. We denote the expected (worst-case) convergence time of pull voting by \(\mathcal{T}^{2V}_G \mathrel{\vcenter{:}}= \text{max}\{{\boldsymbol{E}\left[T_G(\Vec{x})\right]}:\,{\Vec{x}\in\mathcal{X}(1)}\}\).

We define the degree imbalance as \(\gamma = \gamma(G)\mathrel{\vcenter{:}}= \frac{2m}{n\, {d}_{\mathsf{min}}}\), the ratio of the average degree \(\frac{2m}{n}\) to the minimum degree \({d}_{\mathsf{min}}\). For a set \(S\subseteq V\), its volume is \({\rm vol}\!\left(S\right)\mathrel{\vcenter{:}}= \sum_{i\in S} d_i\), and for two disjoint sets \(S,S'\subseteq V\), we define \(E(S,S')\) as the set of edges between \(S\) and \(S'\). The conductance of \(G\) is defined as \[\begin{align} \label{eq:conductance} \Phi \: = \: \Phi(G) \mathrel{\vcenter{:}}= \min\left\{\frac{|E(S,V\setminus S)|}{{\rm vol}\!\left(S\right)}:\; S\subset V,\: {\rm vol}\!\left(S\right)\le m\right\}. \end{align}\tag{1}\]

Let \(A\) be the adjacency matrix of \(G\) and \(D\) the diagonal matrix of node degrees. The transition matrix and stationary distribution of a random walk on \(G\) are \(P = D^{-1}A\) and \(\pi_i=d_i/(2m)\), \(i\in V\). Let \(1=\lambda_1\ge \lambda_2\ge \cdots \ge \lambda_n\ge -1\) denote the eigenvalues of \(P\), \(\lambda=\lambda(G) = \text{max}\{\lambda_2, \abs{\lambda_n}\}\), and define the spectral gap as \(1-\lambda\).

2 Our Results↩︎

We begin by establishing a general upper bound for the convergence time on any graph \(G\), expressed in terms of the conductance \(\Phi(G)\) and the expected convergence time of \(2\)-Value Pull Voting \(\mathcal{T}^{2V}_{G}\).

To the best of our knowledge, these are the first upper bounds that hold for any initial discrepancy \(K\) and are superior to the \(2\)-Value Pull Voting majorization. Moreover, using these bounds and known bounds on \(\mathcal{T}^{2V}_{G}\), we can derive near-tight bounds for many practical graph classes. The best-known bound on \(\mathcal{T}^{2V}_{G}\) is \(O\!\left(\tfrac{\gamma(G)\, n^2}{\Phi(G)}\right)\), which was independently obtained in [6] and [20].

For near-regular graphs with constant conductance, i.e., \(\Phi(G)\), \(\gamma(G) \in O(1)\), bound ?? simplifies to \(O(n^2 \log n)\) for \(K \in O(n)\), and bound ?? simplifies to \(O(n^2)\) for \(K \in O(n/\log n)\). Note that these graphs capture many distributed systems, parallel architectures, and social networks. In this regime, the convergence time of Asynchronous-DIV, both expected and w.h.p., matches asymptotically the convergence time of the standard 2-value pull voting. As DIV reduces to standard 2-value pull voting once the discrepancy is \(1\), this is the best we can hope for.

Complementary, for \(K > n\), we show that the dependence on the initial discrepancy in our upper bounds is unavoidable. In contrast to classical 2-value pull voting, whose convergence time does not depend on the number of initial opinions [6], the incremental nature of DIV restricts nodes to changing their opinion by at most one per interaction. Consequently, the convergence time must scale with \(K\). More precisely, we show the following lower bound.

Thus, for graphs with constant conductance, our results are nearly-tight for \(K\ge n\). To the best of our knowledge, the only other lower bound is \(\Omega(n^3)\) for line graphs shown in [5].

We next show a tighter bound on the convergence time for graphs with strong expansion properties, quantified by \(\lambda(G)\).

This may appear to be only a modest improvement over the conductance-based bound ?? , as the additive \(\mathcal{T}^{2V}_{G}\) term precludes convergence faster than \(\Theta(n^2)\) in general, i.e, we shave off a log-factor from the previous bound when \(K \in O(\tfrac{n}{\log n})\) and \(\lambda(G) \in O(\tfrac{1}{\sqrt{\log n}})\). However, the spectral bound enables a much more refined analysis of the final outcome. The first two terms above give the expected time to reduce the opinion set to three contiguous values. Thus we can show that when \(K\) is not too large, the process concentrates tightly around the weighted average of the initial opinions.

The above theorem improves the results of [21] for a range of parameters. The authors of [21] show for nearly-regular expander graph with second-largest eigenvalue \(\lambda(G) \in o(1)\) that the final value of Asynchronous-DIV converges w.h.p. to \(\lceil \overline{W}(\vec{x}(0)) \rceil\) or \(\lfloor \overline{W}(\vec{x}(0))\rfloor\), as long as \(K\in o(\min (\lambda^{-1}(G),n/\log n))\). Given \(\lambda(G) \in o(1/\log^2 n)\), our theorem covers a much wider range of discrepancies. Note however, that for small values of \(K\) we use their result to reduce the discrepancy to \(O(1)\).

3 Proofs of our Results↩︎

Proof of 1↩︎

To show this result, we split the convergence time into two parts. In 4 we show that the time to reduce the discrepancy to \(\alpha= 32 \frac{\log n}{\Phi(G)}\) is \(O\left( \frac{Kn\log{(Kn)} }{\Phi(G)^2 }\right)\) w.h.p.and in expectation ([lemma:phasescombined] and 1). The second part reduces the discrepancy from \(\alpha\) to \(0\). In [5], Cooper, Radzik and Shiraga reduce the incremental voting to iterative instances of 2-value pull voting, showing that the expected time of reducing the discrepancy by \(1\) in the incremental voting is at most the (worst-case) expected convergence time of 2-value pull voting \(\mathcal{T}^{2V}_{G}\). From this result we get that the time to reduce the discrepancy from \(\alpha\) to zero is in expectation at most \(\alpha\mathcal{T}^{2V}_{G}\) and w.h.p.at most \((6\alpha)\mathcal{T}^{2V}_{G}\). For the latter bound, consider \(3\alpha\) phases of \(2\mathcal{T}^{2V}_{G}\) steps and observe that for any given phase which starts with positive discrepancy, the probability that this phase does not reduce the discrepancy is at most \(1/2\). Using linearity of expectation together with the bounds from both parts proves 1. 0◻

Proof of 2↩︎

At a high level, we consider a large set \(S\) which minimizes the conductance (cf.  1 ) and its complement \(\overline{S} = V \setminus S\). All nodes in \(S\) start with opinion \(K\), all others with opinion \(0\). We know that eventually, all nodes must have the same opinion. The core insight of the proof is the following: the difference between the mean opinions inside set \(S\) and outside it evolves like a slow random walk with very small step size and very small drift. The only interactions that can systematically reduce this difference are those along edges crossing the cut \((S,\overline{S})\). Since these edges constitute only a fraction \(\abs{E(S,\overline{S})}/\abs{E} \le \Phi(G)\) of all edges, the expected change in the mean difference per step is small. Furthermore, each individual interaction changes the mean of either side by at most \(1/\abs{S}\). Hence, random fluctuations accumulate slowly, growing in the order of \(\sqrt{t}/\abs{S}\) after \(t\) steps. As a result, if the initial gap between the mean opinions of \(S\) and its complement is large, it cannot shrink significantly in a short time. We present the detailed formal proof in the appendix (cf. 7.5).

Proof of 3↩︎

In 3 we consider regular graphs with small absolute second eigenvalue \(\lambda(G) \in o(1)\). Note that by Cheeger’s inequality (cf. 5 in the appendix), the conductance is at least \((1-\lambda(G))/2\), so at least \(1/2 - o(1)\) for \(\lambda(G) \in o(1)\). Therefore, we already know that the discrepancy \(K\) is reduced to \(\alpha \in O(\log n)\) in \(O(Kn\log Kn)\) steps, both in expectation and high probability (1 in the proof of 1). Given this result, it only remains to consider how the discrepancy reduces from \(O(\log n)\) to \(0\). Again, the proof is divided into two parts. In 5, we show that in expectation and with high probability, the discrepancy reduces from \(K\) to \(3\) in \(O((K+\log n) \cdot (\lambda(G)^2 n^2 + n\log n))\) steps. For \(K \in O(\log n)\), this further simplifies to \(O(\lambda(G)^2 n^2 \log n + n\log^2 n)\). The main tool for proving this is [lem:one-step], which combines techniques from 2-value pull voting with our new machinery. The remaining time to reduce from \(3\) to \(0\) then follows from the aforementioned reduction to \(2\)-value pull voting described in [5]. 0◻

Proof of 4↩︎

To prove 4, we require insights from [5] and [21]. First, we use the result from [5] showing that it is sufficient to bound the time until discrepancy \(1\). More precisely, suppose the process starts with initial discrepancy \(K\) and initial weighted average \(\overline{W}(\vec{{x}}({0}))\). Suppose further that the discrepancy reduces to \(1\) within \(O((\frac{n}{\delta})^2)\) steps for some \(\delta\). Further let \(\Vec{X}^c\) be the configuration when the process has converged so that \(\overline{W}(\Vec{X}^c)\) is equal to the agreed value. Then, we have,

\[\begin{align} \label{final-disc-from-average} \boldsymbol{Pr}\left[|{\overline{W}(\vec{{x}}({0}))} - {\overline{W}(\Vec{X}^c)}| > \frac{1}{2}\right] \leq e^{-\Omega(\delta)}. \end{align}\tag{2}\] From the proof of 3 (namely, 2) we know that for \(K \in o(n/\log^2 n)\) and \(\lambda(G) \in o(1/{{\log n}})\), after \(O({n^2}/{\log n})\) steps w.h.p. the discrepancy is \(3\). Provided that \(\gamma(G) \in O(1)\), [21] bounds the time to get from \(K\) to \(1\) as \[\begin{align} O\left({n^2}\left(\frac{K\log n}{n}+K\lambda(G)+\sqrt{\lambda(G)}+ \frac{\log n}{n^{\frac{1}{3}}}\right)\right). \end{align}\] For \(K=3\) this is dominated by \(O(\sqrt{\lambda(G)}\cdot n^2 + n^{5/3}\log n) = o((n/\log n)^2)\). Thus, 4 follows, using 2 with \(\delta = \log n\). 0◻

4 Reducing Discrepancy to \(O\left(\tfrac{\log n}{\Phi(G)}\right)\)↩︎

The main technical contribution of this paper is the following proposition, which bounds the time until the discrepancy is reduced from \(K\) down to \(\tfrac{32\log n}{\Phi(G)}\).

To develop intuition, consider configurations with large discrepancies. In this regime, the process behaves similarly to the following discrete load-balancing, or token distribution, process. Suppose that in each interaction a pair of adjacent nodes \((u,v)\) is selected. Then the node with higher load sends one unit of load to the node with lower (or equal) load. The expected evolution of load differences between neighboring nodes closely resembles the evolution of opinion differences in our process. In fact, this process can be obtained by letting both endpoints perform the update of our protocol simultaneously. The key difference between the two processes is that, in our setting, the average of the opinions changes over time while the two-sided/load balancing process preserves the load. Nevertheless, we will see that techniques to analyze load balancing processes, most notably potential functions based on squared deviations, remain applicable, provided the potential is defined relative to suitable thresholds. Formally, in this section, we prove the following result.

The following immediate corollary gives the first part of the proof of 1.

We now outline the proof of [lemma:phasescombined]. The proof is based on a potential-function argument. However, instead of using a single potential, we introduce a family of potential functions \(\Psi_k(\Vec{X}(t))\), one for each index \(k \in [K/2, K]\). To define the potential functions it will be convenient to split the nodes into two groups based on their opinion. We thus define the positive distance and negative distance to the range \([K-k, k]\) as: \[\begin{align} \varphi^{(+)}_k(x) &:= \begin{cases} x - k, & \textit{if } x \geq k,\\ 0, & \textit{otherwise;} \end{cases} \nonumber \\ \varphi^{(-)}_{K-k}(x) &:= \begin{cases} (K-k) - x, & \textit{if } x \leq K-k,\\ 0, & \textit{otherwise}. \end{cases} \label{eqn:posneqdistance} \end{align}\tag{3}\]

Now we define the positive and negative potentials w.r.t.a fixed value \(k\in [K/2, K]\) as follows. Recall that \(d_i\) is the degree of node \(i\). \[\begin{align} \Psi^{(+)}_k(\vec{{X}}\left({t}\right)) &= \sum_{i \in V} d_i \cdot \left(\varphi^{(+)}_k(X_i(t))\right)^2, \\ \Psi^{(-)}_{K-k}(\vec{{X}}\left({t}\right)) &= \sum_{i \in V} d_i \cdot \left(\varphi^{(-)}_{K-k}(X_i(t))\right)^2 \end{align}\] The potential corresponding to index \(k\) is defined as \[\begin{align} \Psi_k(\vec{{X}}\left({t}\right)) = \min \left\{\Psi^{(+)}_k(\vec{{X}}\left({t}\right)), \Psi^{(-)}_{K-k}(\vec{{X}}\left({t}\right)) \right\}. \end{align}\] Each potential \(\Psi_k(\Vec{X}(t))\) measures the remaining discrepancy relative to the threshold \(k\) at the end of \(t\) steps. Note that as soon as \(\Psi_k(\vec{{X}}\left({t}\right)) = 0\), the discrepancy is at most \(k\) (i.e., has decreased by at least \(K-k\)) because all node values are at most \(k\) or all of them are at least \(K-k\).

For the analysis, it will often be useful to consider the mirrored process \((\Vec{X}'(t))_{t \geq 0}\), defined by ‘mirroring’ configurations of the actual process: \[\Vec{X}'(t) \mathrel{\vcenter{:}}= (K-X_1(t), \ldots, K-X_n(t)).\] Note that the processes \((\Vec{X}(t))_{t \ge 0}\) and \((\Vec{X}'(t))_{t \ge 0}\) can be trivially coupled given that the original process starts in \(\Vec{x}(0)\) and the mirrored process starts in \(\Vec{x'}(0)\). Under this coupling, any discrepancy reduction in \(\Vec{X}(t)\) corresponds to exactly the same discrepancy reduction in \(\Vec{X}'(t)\). We make the following observations.

Thus, by [obs:ActualMirrorred](4), it suffices to analyze the positive potentials in the original and the mirrored processes. We will therefore consider the positive potentials in the original and mirrored processes and show that at least one of them must decrease. Furthermore, once the potential for some \(k \in [(1/2) K,(3/4) K]\) is zero, the phase must be over.

Next, in 4.1, we prove two key properties. First, we show that each potential function is monotonically non-increasing over time. Second, for each \(k\) we define good configurations as configurations with many edges between nodes with opinions at least \(k+1\) and nodes with opinions at most \(k-1\).

The definition of \(k\)-good configurations applies to both the original and the mirrored processes. We will show that in a good configuration the potential corresponding to index \(k\) decreases at least by an amount that is proportional to the conductance.

In 4.2 we prove that either in the original or in the mirrored process many of the indices are frequently good. More precisely, using a pigeonhole argument together with structural properties of the configuration, we show that there exists an index \(k^\star \in [(1/2)K, (3/4)K]\) that is good in a constant fraction of all steps, either in the original or in the mirrored process. Finally we combine these results in 4.3. Suppose \(k^{\star}\) is good in the original process. Since the potential \(\Psi^{(+)}_{k^\star}(\Vec{X}(t))\) decreases whenever \(k^\star\) is good and it never increases, it follows that this potential eventually reaches zero, given a sufficiently number of good steps. This implies that the discrepancy drops below \(k^\star \le (3/4)K\), completing the proof of the proposition.

4.1 Potential Drop (For a Fixed \(k\))↩︎

In this section, we analyze the expected drop for a potential. To this end, fix an arbitrary integer threshold \(k \in [K/2, K-1]\) and show two things. First, the positive potential associated with \(k\) is a supermartingale and decreases in expectation; and second, in each good configuration, it decreases by multiplicative factor proportional to the conductance. Formally, we prove in this section the following lemma.

4.2 Existence of Good Indices↩︎

In this section, we show that there exists an index \(k^{\star}\) whose corresponding potential decreases frequently in either the original or the mirrored process.

4.3 Putting Everything Together↩︎

Finally, we put these results together to prove [lemma:phasescombined]. First, we show that for any index \(k\) the probability that there are many steps when \(k\) is good is large and that the probability that the corresponding potential is still large is negligible. In the appendix (cf. 7.3), we prove the following statement.

[lemma:phasescombined] follows from Lemmas 2 and 3.

5 Reducing Discrepancy to \(3\)↩︎

The main result of this section is the following proposition.

From [lem:one-step] we get the following corollary.

Without loss of generality, assume \({x}_{\mathsf{min}} = 0\), and let \[\begin{align} S_0(t) = \{ i \in V : x_i(t) = 0 \}, \;\;\; S_K(t) = \{ i \in V : x_i(t) = K \}. \end{align}\] Similar to the analysis \(2\)-Value pull voting in [6], [20], we will track the progress of the process via the minority opinion \[\eta(t) := \min\left\{{\rm vol}\!\left(S_0(t)\right), {\rm vol}\!\left( S_K(t)\right)\right\}.\] Clearly, the discrepancy has reduced by (at least) \(1\) once \(\eta(t) = 0\). In the appendix 7.4 we show a full proof of the following lemma, adapting the relevant proofs from Berenbrink et al. [6] and Cooper and Rivera [20].

With the help of this lemma, we can now complete the prove the proposition.

6 Tools↩︎

6.1 Combinatoric Tools↩︎

The spectral gap characterizes the presence of sparse cuts and the mixing behavior of random walks, a relationship made precise by Cheeger’s inequality.

Beyond expansion, the second eigenvalue controls how evenly edges are distributed between vertex sets, formalized by the following lemma.

If \(\gamma(G)\) is bounded by a constant, volume-based and cardinality-based notions of expansion are equivalent up to constant factors.

6.2 Tools from Probability Theory↩︎

All random processes are defined on a common probability space. Let \((\mathcal{F}_t)_{t\ge0}\) be a filtration, i.e., all available randomness until step \(t\). A stochastic process \((Y_t)_{t\ge0}\) adapted to \((\mathcal{F}_t)\) imartingale if \({\boldsymbol{E}\left[Y_{t+1}\mid \mathcal{F}_t\right]}=Y_t\) for all \(t\ge0\), and a supermartingale if \({\boldsymbol{E}\left[Y_{t+1}\mid \mathcal{F}_t\right]}\le Y_t\) for all \(t\ge0\). A random variable \(\tau\) is a stopping time with respect to \((\mathcal{F}_t)\) if the event \(\{\tau=t\}\) is measurable with respect to \(\mathcal{F}_t\) for all \(t\). We will make use of the following well-known tool; see, for example, [27].

We will also use concentration bounds for martingales with bounded increments, namely the following well-known bound; see, for example, [28].

We state the tail bounds of Janson Janson2018? for sums of independent geometric random variables.

7 Omitted Proofs↩︎

7.1 Proof of [Claim1]↩︎

For two values \(x_i\) and \(x_j\) define \[\begin{align} \iota(i,j) \mathrel{\vcenter{:}}= \begin{cases} 0 & \textit{if } x_i=x_j\\ -1 & \textit{if } x_i>x_j\\ 1 & \textit{if } x_i<x_j\\ \end{cases} \end{align}\] According to Protocol [prot:edgeinteraction], at a given step a random directed edge \(e=(u,v)\) is chosen as follows. Firstly a vertex \(u\) is chosen uniformly at random, and then a neighbour \(v \in N_u\) is chosen with probability \(1/d_u\). Thus for a given vertex \(i \in V\), \[\begin{align} {\boldsymbol{E}\left[d_i \cdot f(X_i(t+1))^2\right]} &= \boldsymbol{Pr}\left[u \ne i\right] \cdot d_i \cdot f(x_i)^2 +\boldsymbol{Pr}\left[u=i\right] \cdot d_i \cdot \sum_{j\in N_i}\boldsymbol{Pr}\left[v=j \mid u=i\right] \cdot {\boldsymbol{E}\left[ f(X_i(t+1)))^2 \mid (u,v)=(i,j)\right]}. \end{align}\] As the vertices \(u\) and \(v\) are random variables, for a given vertex \(i\), the probability that \(u=i\) is \(1/n\), and the probability that \(u \ne i\) is \((1-1/n)\). Further, \(\boldsymbol{Pr}\left[v=j \mid u=i\right] = \tfrac{1}{d_i}\). Thus, as \(f(X_i(t+1))=0\) if \(i \not \in S\), and \(f(X_i(t+1))=f(x_i+\iota(i,j))\) if \(i \in S\) and \((u,v)=(i,j)\), \[\begin{align} {\boldsymbol{E}\left[\sum_{i \in V} d_i \cdot f(X_i(t+1))^2 \right]} &= \left(1-\frac{1}{n}\right)\sum_{i \in V} d_i \cdot f(x_i)^2 + \frac{1}{n} {\sum_{\substack{(i,j) \in E \\ x_i \geq k}} d_i \cdot \tfrac{1}{d_i} \cdot f(x_i + \iota(i,j))^2} \nonumber \\ &= \left(1-\frac{1}{n}\right)\sum_{i \in V} d_i \cdot f(x_i)^2 + \frac{1}{n} \underbrace{\sum_{\substack{(i,j) \in E \\ x_i \geq k }} \;f(x_i + \iota(i,j))^2}_{(*)}. \label{eqn:total95exp} \end{align}\tag{14}\]

In the following, we focus on the sum \((*)\). Note that the potential \(\sum d_i f(X_i(t+1))^2\) can only differ from \(\sum d_i f(x_i)^2\) if at least one endpoint of the selected directed edge is in \(S_{+1} = \{ r \in V \mid x_r \geq k+1\}\). Otherwise, if neither value is above \(k\), the updated value cannot be above \(k\). Further, noting that \(\iota(i,j) = - \iota(j,i)\), we can rearrange this sum as follows, to introduce the constraint \(x_i \ge x_j\): \[\begin{align} (*) = \sum_{\substack{\substack{(i,j) \in E \\ x_i \geq k }}} f(x_i + \iota(i,j))^2 = \sum_{\substack{(i,j) \in E_{S_{+1}} \\ x_i > x_j}} \left(f(x_i + \iota(i,j))^2 + f(x_j - \iota(i,j))^2\right). \end{align}\] Consider a single summand in the right-hand sum above, i.e., the expected change along a single edge \(\{i,j\}\). Let \(i \in S_{+1}\) be a node with \(x_i > k\) and \(j \in V\) be a node with \(x_j \leq x_i\). We show that \[\begin{align} f(x_i + \iota(i,j))^2 + f(x_j - \iota(i,j))^2 \leq f(x_i)^2 + f(x_j)^2 - (f(x_i) - f(x_j)) + \mathbb{1}_{|x_i-x_j|=1}. \label{lem:edgediff} \end{align}\tag{15}\] To prove this inequality, we distinguish between the following three cases.

Case 1: \(x_i > x_j+1\). In this case, we have \(\iota(i,j)=-1\), i.e., \(x_i\) will decrease and \(x_j\) will increase. Our assumption that \(x_i > k\) implies that \(f(x_i)\) is at least one, so we have \[\begin{align} f(x_i-1)^2 &:= \big((x_i-1) - k \big)^2 = \big((x_i - k) - 1\big)^2\\ &= (f(x_i)-1)^2 = f(x_i)^2 - 2f(x_i) + 1 \end{align}\] Now, we distinguish between two subcases:

• If \(x_j < k\), it holds \(f(x_j ) = f(x_j + 1) = 0\). Therefore \[\begin{align} f(x_j + 1)^2 = 0 = f(x_j)^2 + f(x_j). \end{align}\] Together with the other bounds, this gives: \[\begin{align} f(x_i + \iota(i,j))^2 + f(x_j - \iota(i,j))^2 &= f(x_i-1)^2 + f(x_j+1)^2\\ &= f(x_i)^2 - 2f(x_i) + 1 + f(x_j)^2 + f(x_j)\\ &\leq f(x_i)^2 + f(x_j)^2 - (f(x_i) - f(x_j)). \end{align}\] Here, the last inequality follows from \(f(x_i) \geq 1\) (as \(x_i > k\)).

• Otherwise, if \(x_j \geq k\), it holds that: \[\begin{align} f(x_j+1)^2 &= \big((x_j+1) - k \big)^2 = \big((x_j - k) + 1\big)^2\\ &= (f(x_j)+1)^2 = f(x_j)^2 + 2f(x_j) + 1 \end{align}\] Thus, \[\begin{align} f(x_i-1)^2 + f(x_j+1)^2&= f(x_i)^2 + f(x_j)^2 - 2f(x_i) + 2f(x_j) + 2 \end{align}\] As \(f(x_i)-f(x_j)=x_i-x_j \ge 2\), this simplifies to \[\begin{align} f(x_i-1)^2 + f(x_j+1)^2&{\; \le} f(x_i)^2 + f(x_j)^2 - (f(x_i) - f(x_j)) \end{align}\] as claimed.

Case 2: \(x_i = x_j+1\) (the case with \(\mathbb{1}_{|x_i-x_j|=1} = 1\)). In this case, we also have \(\iota(i,j)=-1\). However, as the difference is exactly one, the process (locally) reduces to classical voting. We note that, since \(x_i-1 = x_j\) it holds: \[\begin{align} f(x_i-1) &= f(x_j)\\ f(x_j+1) &= f(x_{i}) \end{align}\] Therefore, the potential remains unchanged: \[\begin{align} f(x_i-1)^2 + f(x_j+1)^2&= f(x_i)^2 + f(x_j)^2 \end{align}\] By noting that \(f(x_i)-f(x_j)=1\), we get: \[\begin{align} f(x_i-1)^2 + f(x_j+1)^2 = f(x_i)^2 + f(x_j)^2 - (f(x_i) - f(x_j)) + 1. \end{align}\]

Case 3: \(x_i = x_j\). In this case, there is no change as neither node will change its opinion because they already agree, i.e., we have \(\iota(i,j)=0\). Thus, as \(f(x_i)=f(x_j)\), \[\begin{align} f(x_i-0)^2 + f(x_j+0)^2&= f(x_i)^2 + f(x_j)^2 {\; - (f(x_i) - f(x_j)).} \end{align}\]

Inequality 15 implies the following: \[\begin{align} (*) &\leq \sum_{\substack{(i,j) \in E_{S_{+1}} \\ x_i \geq x_j}} \left(f(x_i)^2 + f(x_j)^2 - (f(x_i) - f(x_j)) + \mathbb{1}_{|x_i-x_j|=1}\right)\\ &= \sum_{i \in V} d_i f(x_i)^2 - \sum_{\substack{(i,j) \in E_{S_{+1}} \\ x_i \geq x_j}} \left(f(x_i) - f(x_j) - \mathbb{1}_{|x_i-x_j|=1}\right). \end{align}\] Referring back to 14 , we see that \[\begin{align} {\boldsymbol{E}\left[\sum_{i \in V} d_i \cdot f(X_i(t+1))^2 \right]} \leq & \left(1-\frac{1}{n}\right)\sum_{i \in V} d_i \cdot f(x_i)^2\\ \phantom{=} & + \frac{1}{n} \left(\sum_{i \in V} d_i \cdot f(x_i)^2 -\sum_{\substack{(i,j) \in E_{S_{+1}} \\ x_i \geq x_j}} \left(f(x_i) - f(x_j) - \mathbb{1}_{|x_i-x_j|=1}\right) \right)\\ = & \sum_{i \in V} d_i\cdot f(x_i)^2 - \frac{1}{n}\left(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \; \left(f(x_i) - f(x_j) - \mathbb{1}_{|x_i-x_j = 1|}\right)\right) \end{align}\] The above inequality is equivalent to 5 .

7.2 Detailed Proof of [Claim2]↩︎

First, recall that \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\mathrel{\vcenter{:}}= {\boldsymbol{E}\left[\sum_{i \in V} d_i \cdot f(X_i(t+1))^2 \mid \vec{{X}}\left({t}\right) = \vec{x}\right]}- \sum_{i \in V} d_i \cdot f(x_i)^2 \nonumber\\ &\le -\, \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}}\left( f(x_i) - f(x_j) - \mathbb{1}_{\{|x_i-x_j = 1|\}}\right) \;\;\;\;\;\;\;\;\; \text{[ by \Cref{EsumClaim1} ]}\tag{16}\\ &\leq - \frac{1}{n}\left( \Phi(G)\sum_{i \in V } d_i \cdot f(x_i) - \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \mathbb{1}_{\{|x_i-x_j = 1|\}}\right) \;\;\; \text{[ by \Cref{Part2Ineq1}, as {\rm vol}\!\left(S\right) \leq m ]} \tag{17} \end{align}\] Recall that \(E_{S_{+1}} \mathrel{\vcenter{:}}= \{ (i,j) \in E \mid i \in {S_{+1}}\}\). To prove 10 we now use 16 and 17 . We distinguish between two cases based on the value of \(\sum_{i \in V} d_i \cdot f(x_i)\).

• Case 1: Assume \({\sum_{i \in V} d_i \cdot f(x) \geq (4/3){{\rm vol}\!\left(S_{+1}\right)}/{\Phi(G)}}\). Here, we use 17 to obtain: \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\, (-1)} \;\;\frac{1}{n}\left( \Phi(G)\sum_{i \in V} d_i f(x_i) - \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ & \text{ (using that \sum_{i \in V} d_i \cdot f(x) \geq {(4/3){\rm vol}\!\left(S_{+1}\right)}/{\Phi(G)})}\\ &\leq {\, (-1)}\frac{1}{n}\left( \frac{\Phi(G)}{4} \sum_{i \in V} d_i f(x_i) + \frac{3\Phi(G)}{4}\cdot\frac{(4/3){\rm vol}\!\left(S_{+1}\right)}{\Phi(G)} - \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ &\leq {\, (-1)}\frac{1}{n}\left( \frac{\Phi(G)}{4} \sum_{i \in V} d_i f(x_i) + {\rm vol}\!\left(S_{+1}\right) - \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \mathbb{1}_{\{|x_i-x_j| = 1\}}\right) \end{align}\] Now, we focus on the last summand, namely \(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} \mathbb{1}_{\{|x_i-x_j| = 1\}}\). First, we pessimistically assume that the difference along all edges with an endpoint in \(S_{+1}\) is exactly \(1\). Then, the formula simplifies to \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\, (-1)}\frac{1}{n}\left( \frac{\Phi(G)}{4} \sum_{i \in V} d_i f(x_i) + {\rm vol}\!\left(S_{+1}\right) - \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} 1\right) \end{align}\] We continue by bounding \(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} 1\) by \({\rm vol}\!\left(S_{+1}\right)\). Note that the sum \(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} 1\) counts each edge adjacent to a node in \(S_{+1}\) exactly once. On the other hand, in \({\rm vol}\!\left(S_{+1}\right) \mathrel{\vcenter{:}}= \sum_{i \in S_{+1}} d_i\), each edge is counted once for each endpoint in \(S_{+1}\). This means, each edge \(\{i,j\}\) that is within \(S_{+1}\), i.e., between \(i \in S_{+1}\) and \(j \in S_{+1}\), is counted twice and each edge that with precisely one endpoint in \(S\), i.e, between \(i \in S\) and \(j \not\in S\), is counted once. Thus, \({\rm vol}\!\left(S_{+1}\right)\) is always bigger than \(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}} 1\). Therefore, \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\, (-1)}\frac{1}{n}\left( \frac{\Phi(G)}{2} \sum_{i \in V} d_i f(x_i) + {\rm vol}\!\left(S_{+1}\right) - \sum_{ i \in S_{+1}} d_i\right)\\ &\leq{\, (-1)} \frac{1}{n}\left( \frac{\Phi(G)}{4} \sum_{i \in V} d_i f(x_i) + {\rm vol}\!\left(S_{+1}\right) - {\rm vol}\!\left(S_{+1}\right) \right)\\ &\leq{\, (-1)} \frac{1}{n}\left( \frac{\Phi(G)}{4} \sum_{i \in V} d_i f(x_i)\right) \leq {\; (-1)} \frac{1}{n}\left( \frac{\Phi^2}{4} \sum_{i \in V} d_i f(x_i)\right) . \end{align}\] This proves the fist case.

• Case 2: Assume \(\sum_{i \in V} d_i \cdot f(x) < (4/3){\rm vol}\!\left(S_{+1}\right)/\Phi(G)\). In this case, use 16 and bound the term in two steps. First, we let the internal edges between nodes in \(S_{+1}\) cancel each other out. To this end, we divide the summand into two groups: The edges within \(S_{+1}\) where both endpoints have a value larger than \(k\) and the the edges that leave \(S_{+1}\) and end in \(S \setminus S_{+1}\) or \(\overline{S}\). Note that we can ignore edges between \(S \setminus S_{+1}\) and \(\overline{S}\) as both endpoints are at most \(k\) as they do not contribute to the sum. Further, note that both endpoints of an edge \((i,j) \in E_{S_{+1}}\) are in \(S_{+1}\) if and only if \(x_i, x_j > k\). In light of these observations, it holds: \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &= - \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i\geq x_j}}\left( f(x_i) - f(x_j) - \mathbb{1}_{\{|x_i-x_j = 1|\}}\right)\nonumber\\ &\leq {\,(-1)}\frac{1}{n}\left( \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i \geq x_j > k}} f(x_i)-f(x_j) + \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}} f(x_i)-f(x_j)\right) \nonumber\\ & \phantom{\leq}{\;( +1)} \frac{1}{n}\left(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i \geq x_j > k}} \mathbb{1}_{\{|x_i-x_j| = 1\}} + \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}} \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\nonumber \\ &\leq {\,(-1)}\frac{1}{n}\left( \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i \geq x_j > k}} (f(x_i)-f(x_j)) - \mathbb{1}_{\{|x_i-x_j| = 1\}} \right) \tag{18}\\ &\phantom{\leq} {\, -} \frac{1}{n}\left(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}} (f(x_i)-f(x_j)) - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\tag{19} \end{align}\] Now we bound 18 and 19 separately. We begin with 18 : Note that whenever it holds \(|x_i-x_j| = 1\) the difference \(f(x_i) - f(x_j)\) is also exactly one as both \(i\) and \(j\) are larger than \(k\). Formally, \[\begin{align} f(x_i) - f(x_j) = (x_i - k) - (x_j - k) = x_i - x_j \geq \mathbb{1}_{|x_i - x_j| = 1} \end{align}\] Therefore, the terms cancel each other and we get: \[\begin{align} \eqref{eq:internal} &= - \frac{1}{n}\left(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i \geq x_j > k}} (f(x_i)-f(x_j)) - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right) \\ &\leq - \frac{1}{n}\left(\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i \geq x_j > k}} \mathbb{1}_{\{|x_i-x_j| = 1\}} - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right) = 0. \end{align}\] Thus, we only need to consider 19 and analyze: \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]}&\leq {\,(-1)} \frac{1}{n} \sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}} \left( f(x_i)-f(x_j) - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right) \end{align}\] Next, we exploit that the endpoints of all remaining edges are between \(S_{+1}\) and \(V \setminus S\) have a difference of at least one. Since one endpoint is larger than \(k\), for all \((i,j) \in E_{S_{+1}}\) with \(x_i > k\) and \(x_j \leq k\), we have: \[\begin{align} f(x_i) - f(x_j) = (x_i - k) - 0 = x_i - k \geq 1. \end{align}\] Recall that we defined \(\mathbb{O}(S_{+1}) \mathrel{\vcenter{:}}= \{ (i,j) \in E \mid i \in S_{+1}, j \in V\setminus S_{+1} \}\). Together with this definition, we get: \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\,(-1)} \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}}\left( (f(x_i) - f(x_j)) - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ &\text{As (f(x_i) - f(x_j)) \geq 1, we get}\\ &\leq {\,(-1)} \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}}\left( 1 - \mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ &= {\,(-1)} \frac{1}{n} \mathbb{O}(S) + \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}}\left(\mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ &\text{As \mathbb{O}(S_{+1}) \geq \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right)by definition,}\\ &= {\,(-1)} \frac{1}{n} \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right) + \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j \leq k}}\left(\mathbb{1}_{\{|x_i-x_j| = 1\}}\right) \end{align}\] Now, we further divide the edges and distinguish between edges that start in \(S_{+1}\) and end in \(S\setminus S_{+1}\) and edges that start in \(S_{+1}\) and end in \(\overline{S}\). By definition, all edges that start in \(S_{+1}\) and end in \(\overline{S}\) have a difference of at least \(2\). In addition, we pessimistically assume that all that start in \(S_{+1}\) and end in \(S\) have a difference of precisely \(1\) (although it theoretically can be larger, too). \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\,(-1)} \frac{1}{n} \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right) + \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j = k}}\left(\mathbb{1}_{\{|x_i-x_j| = 1\}}\right)\\ &\leq {\,(-1)} \frac{1}{n} \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right) + \frac{1}{n}\sum_{\substack{(i,j) \in E_{S_{+1}}\\ x_i > k, x_j = k}}1\\ &= {\,(-1)} \frac{1}{n} \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right) + \frac{1}{n}|E(S_{+1},S)|\\ &\leq {\,(-1)} \frac{1}{n} \Phi(G)\cdot {\rm vol}\!\left(S_{+1}\right) + \frac{1}{n}\frac{3}{4} \Phi(G) {\rm vol}\!\left(S_{+1}\right) \end{align}\] Finally, we get \[\begin{align} {\boldsymbol{E}\left[\Delta(X_i(t+1)) \mid \vec{{X}}\left({t}\right) = \vec{x}\right]} &\leq {\,(-1)} \frac{1}{n}\left( \frac{1}{2} \Phi(G){\rm vol}\!\left(S_{+1}\right) \right) \leq {\,(-1)} \frac{1}{n}\left( \frac{1}{4} \Phi^2(G) \sum_{i \in V} d_i f(x_i) \right). \end{align}\] This proves the second case.

Together, the two cases imply the claim.

7.3 Proof of 3↩︎

We begin with some definitions and assumptions. Let \(\mathcal{F}(t)\) be the natural filtration of the process that contains all configurations (and thus all random choices) up to step \(t\). Note that \(\tau_k(t)\) is completely determined by \(\mathcal{F}(t)\). Further define the event \[\begin{align} B_k(T) \mathrel{\vcenter{:}}= \{\Psi^{(+)}_k(\vec{{X}}\left({T}\right)) > 0\} \;\cap\; \{\tau_k(T) \ge T/4\}. \end{align}\]

We define the following auxiliary random process \[\begin{align} \psi(t) \mathrel{\vcenter{:}}= \begin{cases} \Psi^{(+)}_k(\vec{{X}}\left({0}\right)) & \text{if t=0},\\[2pt] \Psi^{(+)}_k(\vec{{X}}\left({t}\right))\cdot\left(1- \dfrac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t-1)} & \text{if t>0}. \end{cases} \end{align}\] Note that \(\psi(t)\) is measurable with respect to the filtration \(\mathcal{F}(t)\). First, we show that \((\psi(t))_{t \geq 0}\) is a supermartingale, i.e., for all \(t\ge 0\), \[{\boldsymbol{E}\left[\psi(t+1) \mid \mathcal{F}(t)\right]} \le \psi(t).\] This follows by a simple case distinction. Fix \(t\ge 0\) and condition on \(\mathcal{F}(t)\). For easier notation, define \[\mathbf{E}_t\!\left[\cdot\right] \mathrel{\vcenter{:}}= {\boldsymbol{E}\left[\cdot \mid \mathcal{F}(t) = (\vec{x}(t), \ldots, \vec{x}(0))\right]}.\]

Now distinguish between the following cases:

1. If \(k\) is good in step \(t\), then \[\begin{align} \mathbf{E}_t\!\left[\psi(t+1)\right] &= \mathbf{E}_t\!\left[\Psi_k^{(+)}(\vec{{X}}\left({t+1}\right))\cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)}\right]. \end{align}\] The factor \(\left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)}\) is completely determined by \(\mathcal{F}(t)\) and can be pulled out of the expectation, so \[\begin{align} \mathbf{E}_t\!\left[\psi(t+1)\right] &= \mathbf{E}_t\!\left[\Psi_k^{(+)}(\vec{{X}}\left({t+1}\right))\right]\cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)}. \end{align}\] As \(k\) is good in step \(t\), by 1, \[\mathbf{E}_t\!\left[\Psi_k^{(+)}(\vec{{X}}\left({t+1}\right))\right] \le \Psi_k^{(+)}(\vec{{x}}({t}))\cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right).\] Hence, \[\begin{align} \mathbf{E}_t\!\left[\psi(t+1)\right] &\le \Psi_k^{(+)}(\vec{{x}}({t}))\cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right) \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)}\\ &= \Psi_k^{(+)}(\vec{{x}}({t})) \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)+1}. \end{align}\] Since \(k\) is good in step \(t\), we have \(\tau_k(t)=\tau_k(t-1)+1\), and thus \(-\tau_k(t) + 1=-\tau_k(t-1)\). Therefore, \[\begin{align} \mathbf{E}_t\!\left[\psi(t+1)\right] &\le \Psi_k^{(+)}(\vec{{x}}({t})) \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t-1)} = \psi(t). \end{align}\]

2. If \(k\) is not good in step \(t\), then \(\tau_k(t)=\tau_k(t-1)\) and \[\begin{align} \mathbf{E}_t\!\left[\psi(t+1)\right] &= \mathbf{E}_t\!\left[\Psi_k^{(+)}(\vec{{X}}\left({t+1}\right))\right] \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t)}\\ &= \mathbf{E}_t\!\left[\Psi_k^{(+)}(\vec{{X}}\left({t+1}\right))\right] \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t-1)}\\ &\le \Psi_k^{(+)}(\vec{{x}}({t})) \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(t-1)} = \psi(t), \end{align}\] where the last inequality follows from the first statement of 1.

This shows that \((\psi(t))_{t\ge 0}\) is a supermartingale.

Now define the stopping time \[T' \mathrel{\vcenter{:}}= \min\left\{ T,\; \inf\{t\ge 0:\tau_k(t)\ge T/4+1\} \right\}.\]

Since \(T' \le T\), Doob’s optional stopping theorem (cf.5) yields \[\psi(0) \ge {\boldsymbol{E}\left[\psi(T')\right]}.\] On the event \(B_k(T)\), we have \(\tau_k(T')\ge T/4+1\), and thus \[\begin{align} \psi(T') &= \Psi_k^{(+)}(\vec{{X}}\left({T'}\right)) \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-\tau_k(T'-1)} \ge \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-T/4}. \end{align}\]

Therefore, \[\begin{align} {\boldsymbol{E}\left[\psi(T')\right]} \ge \boldsymbol{Pr}\left[B_k(T)\right] \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-T/4}. \end{align}\]

Since \(\psi(0)=\Psi_k^{(+)}(\vec{{x}}({0}))\le K^2 n\), we obtain \[\begin{align} K^2 n \ge \boldsymbol{Pr}\left[B_k(T)\right] \cdot \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{-T/4}. \end{align}\]

Solving for \(\boldsymbol{Pr}\left[B_k(T)\right]\) and using \(T = 20 c \tfrac{(K-k)n\log(Kn)}{\Phi(G)^2}\) gives \[\begin{align} \boldsymbol{Pr}\left[B_k(T)\right] &\le K^2 n \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{T/4}\\ &\le K^2 n \left(1-\frac{\Phi(G)^2}{5(K-k)n}\right)^{5 c \tfrac{Kn\log(Kn)}{\Phi(G)^2}} \le \frac{1}{(Kn)^c}. \qedhere \end{align}\]

7.4 Proof of 4↩︎

Our proof follows the arguments of Cooper and Rivera for linear pull voting almost verbatim and uses essentially the same techniques. We begin the proof with some useful definitions. Define \(\eta(t)= \min\{{\rm vol}\!\left(S_0(t)\right), {\rm vol}\!\left(S_K(t)\right)\}\). Further, for simplity denote \(S(t)\) to the set archieving \({\rm vol}\!\left(S(t)\right) = \eta(t)\) and \(\overline{S}(t) = V \setminus S(t)\). Note that once \(\eta(t) = 0\), one opinion must have vanished from the system. We study the process \(\sqrt{\eta(t)}\), in particular \[\begin{align} {\boldsymbol{E}\left[\sqrt{\eta(t)} \mid S(0) = S\right]}. \end{align}\] Note that both \((S_0(t))_{t \geq 0}\) and \((S_K(t))_{t \geq 0}\) are martingales and \(\sqrt{\cdot}\) is concave. Therefore, by Jensen’s inequality, \((\eta(t))_{t \geq 0}\) is a supermartingale. Further, let \(Z(t)\) be the change in the measure of \(S(t)\) in step \(t\), i.e. \[\begin{align} Z(t) \mathrel{\vcenter{:}}= {\rm vol}\!\left(S(t+1)\right) - {\rm vol}\!\left(S(t)\right). \end{align}\] Note that \[\begin{align} \eta(t+1) = \min\{{\rm vol}\!\left(S(t)\right) + Z(t), {\rm vol}\!\left(S'(t)\right) - Z(t)\}. \end{align}\] Further, define \(\rho_t = \rho(S(t)) = 2 \mathbb{1}_{{\rm vol}\!\left(S(t)\right) \leq {\rm vol}\!\left(S'(t)\right)} - 1\), so \(\rho_t \in \{-1,1\}\). Then \[\begin{align} \eta(t+1) \le \eta(t) + \rho_t Z(t). \end{align}\] Finally, define \[\Upsilon(S) \mathrel{\vcenter{:}}= {\boldsymbol{E}\left[Z(t)^2 \,\mathbb{1}_{\rho_t Z(t) < 0} \mid S(t) = S \right]}.\] To bound \(\Upsilon(S)\) let \(X_{ij}\) be the indicator that \(i\) adopts \(j\)’s opinion. Note that \(\rho_t Z(t) < 0\) exactly when a vertex from the current minority switches to the majority (i.e.the minority decreases). If \(i\in S(t)\) switches, the measure drops by \(d_i\), hence \[\begin{align} \Upsilon(S) &= \sum_{(i,j)\in E(S,\overline{S})} \boldsymbol{Pr}\left[X_{ij}\right]\left(d_i\right)^2 = \sum_{(i,j)\in E(S,\overline{S})} \frac{1}{n d_i}\left(d_i\right)^2 \\ &= \sum_{(i,j)\in E(S,\overline{S})} \frac{d_i}{ n } \;\ge\; \frac{d_{\min}}{ n }\,|E(S,\overline{S})|. \end{align}\] Using \(|E(S,\overline{S})| \ge \Phi(G)\,{\rm vol}\!\left(S\right)\) we obtain \[\begin{align} \Upsilon(S) &\ge \frac{d_{\min}}{ n }\,\Phi(G)\,{\rm vol}\!\left(S\right) \end{align}\]

By induction, for all \(t<\tau_s\) it follows that \[{\boldsymbol{E}\left[\sqrt{\eta(t)} \mid \eta(0)=s\right]} \;\le\; \sqrt{s} \;-\; t \cdot c \cdot \frac{{d}_{\mathsf{min}}(G)\cdot \Phi(G)}{\sqrt{s}\cdot n}.\] Moreover, since \(\eta(t)\) is integer-valued, \({\mathbb{1}}\{\eta(t)>0\} \le \sqrt{\eta(t)}\) and hence \[\boldsymbol{Pr}\left[\eta(t)>0 \mid \eta(0)=s\right] \;\le\; {\boldsymbol{E}\left[\sqrt{\eta(t)} \mid \eta(0)=s\right]}.\] Therefore, if \[t \;\ge\; \frac{\sqrt{s}-\tfrac12}{c}\cdot \frac{\sqrt{s}\cdot n}{{d}_{\mathsf{min}}(G)\cdot \Phi(G)} \in O\left(\frac{s n}{\Phi(G) \cdot {d}_{\mathsf{min}}(G)}\right),\] then \({\boldsymbol{E}\left[\sqrt{\eta(t)} \mid \eta(0)=s\right]} \le \tfrac12,\) which implies \(\boldsymbol{Pr}\left[\eta(t)=0 \mid \eta(0)=s\right] \ge \tfrac12\) and thus \(t \ge \tau_s\).

7.5 Proof of 2↩︎

Given a nonempty set of vertices \(S \subseteq V\) and a vector of opinions \(\Vec{x}= (x_i)_{i \in [n]}\), we write \(\mu_S(\Vec{x}) \mathrel{\vcenter{:}}= \frac{1}{\abs{S}} \sum_{i \in S} x_i\) for the mean opinion of \(S\)’s agents in \(\Vec{x}\). Furthermore, we write \(\Delta_S(\Vec{x}) \mathrel{\vcenter{:}}= \mu_S(\Vec{x}) - \mu_{\overline{S}}(\Vec{x})\) for the difference between the mean opinions within \(S\) and its complement in \(\Vec{x}\).

7.6 Proof of 1, bound ??↩︎

Our proof of the convergence bound ?? in 1 was split into two parts. The first part dealt with the discrepancy decreasing from the initial \(K\) to \(\alpha= (32 {\log n})/{\Phi}\), and the second part considered the time needed to decrease the discrepancy from \(\alpha\) to \(0\). (We are simplifying notation here, using \(\Phi\) and \(\gamma\) for \(\Phi(G)\) and \(\gamma(G)\).) The analysis of the second part was based on the reduction to iterative application of the 2-Value Pull Voting. This reduction says that the expected time needed to eliminate one extreme opinion is at most \(\mathcal{T}^{2V}_{G}\), so all but one of the remaining \(\alpha\) opinions are eliminated in \(O\left(\alpha\mathcal{T}^{2V}_{G}\right)\) time, in expectation as well as with high probability. Now we refine the analysis of the second part to obtain bound ?? in 1. For convenience, we repeat below this bound as a separate theorem.

This theorem implies the bound of \(O(\gamma n^2)\) on the expected consensus time of Asynchronous-DIV for graphs with constant conductance and the initial discrepancy \(K = O(n/\log n)\) . This bound of \(O(\gamma n^2)\) is of the same asymptotic order as the best bound for the expected consensus time in the 2-value pull voting for graphs with constant conductance, which is stated in 8 in the form as it was derived in [20]. For regular graphs with constant conductance, bound ?? becomes \(O(n^2)\), matching the lower bound of \(\Omega(n^2)\) on the expected consensus time of the 2-value pull voting for this class of graphs.

Our analysis is based on the bound for 2-value pull-voting consensus time which takes into account the initial size of the minority vote: smaller the initial minority means faster consensus time; translating in the incremental-voting context to: smaller size of the extreme opinion means that it disappears faster.

For a subset of vertices \(S\subseteq V(G)\), let \(\mu(S) = \frac{{\rm vol}\!\left(S\right)}{2m}\) denote the volume of this set as a fraction of the total graph volume. For the 2-Value Pull Voting in graph \(G\) with the initial minority support \(S\subseteq V(G)\) (understood as \(\mu(S) \le \mu(V(G)\setminus S)\)), let the random variable \(T_{G}^{{2V}}(S)\) denote the time when the consensus is reached. Further, extending the definition of \(\mathcal{T}^{2V}_{G}\), define for \(0<\epsilon\le 1/2\) the worst-case expected consensus time when the initial minority vote fraction is at most \(\epsilon\): \[\mathcal{T}^{2V}_{G}(\epsilon) = \underset{}{\text{max}}\left\{{\boldsymbol{E}\left[T_{G}^{{2V}}(S)\right]}:\: \text{S\subseteq V, \mu(S)\le \epsilon}\right\}.\] The following bound on \(\mathcal{T}^{2V}_{G}(\epsilon)\) can be extracted from the analysis of voting processes presented in [20].

Our proof of [thm:main:version2] is based on the following lemma, which can be viewed as an extension of [lemma:phasescombined] to cover also the case of smaller discrepancies, and on the bound on the worst-case expected time \(\mathcal{T}^{2V}_{G}(\epsilon)\) stated in 8.

We use throughout this section the parameters \(\epsilon_k\) and \(T_k\) defined in this lemma. For initial discrepancies greater than \(\tfrac{32\cdot \log n}{\Phi}\), this lemma is essentially a version of [lemma:phasescombined], with the difference that it refers to the expectation rather than the high probability. Thus, while the lemma and its proof below apply to any \(K\), they provide new insight (beyond what we showed in [lemma:phasescombined]) only for initial discrepancies smaller than this threshold.

Let \(\mu(t) = \min\{ \mu(V_{k'}(t)), \mu(V_{k''}(t))\}\), where \(V_{k'}(t)\) and \(V_{k''}(t)\) are the support sets for the highest and lowest opinions \(k'\) and \(k''\) still present in the configuration in step \(t\). To prove 10, we will need two additional lemmas. 11 extends 2 to smaller discrepancies, ascertaining the existence of good indices also for small values of \(K\), providing that the support for the extreme opinions is not two small. We prove 11 by showing how the proof of 2 should be adapted. 12 is a slight generalization of 3, and we omit its proof as it is essentially the proof of 3 with obvious notational adjustments.

References↩︎

---

1. In this paper, ‘with high probability’ (w.h.p.) means with probability at least \(1-O(1/n^c)\) for some constant \(c>1\), where \(n\) is the number of nodes in \(G\).↩︎

2. For the precise calculation see [claim:taylorclaim] in 7.4.↩︎