Discrete Incremental Voting: New Bounds for General Graphs and Expanders

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Discrete Incremental Voting: New Bounds for General Graphs and Expanders

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

Discrete Incremental Voting New Bounds for General Graphs and Expanders

arXiv:2606.06381v1 [cs.DC] 4 Jun 2026

PETRA BERENBRINK, University of Hamburg, Germany COLIN COOPER, King’s College London, United Kingdom THORSTEN GÖTTE, University of Hamburg, Germany LUKAS HINTZE, University of Hamburg, Germany TOMASZ RADZIK, King’s College London, United Kingdom We analyze the discrete incremental voting process (DIV) introduced by Cooper, Radzik, and Shiraga [OPODIS ’23]. In this process, we consider a set 𝑉 of 𝑛 nodes connected in an undirected graph 𝐺 = (𝑉 , 𝐸 ) where each node has an integer opinion. In one step a randomly selected node interacts with its randomly selected neighbor and changes its opinion by 1 in the direction of the neighbour’s opinion. The process converges to a unique opinion that, in expectation, is the degree-weighted average of the initial opinions. We show that if the graph has conductance Φ(𝐺 ), the ratio of the average to smallest degree is 𝛾 (𝐺 ), and the maximal difference between initial opinions is 𝐾, then the expected convergence time is 𝑂 𝑛 (𝐾 log(𝐾𝑛) + 𝛾 (𝐺 )𝑛)/Φ(𝐺 ) 2 . This bound is essentially optimal for a large class of graphs of bounded expansion. We also show that for regular graphs, if the second largest eigenvalue is 𝑜 (1/log2 𝑛) and 𝐾 is 𝑜 𝑛/log2 𝑛 , then w.h.p. DIV converges to the initial average opinion (rounded up or down). CCS Concepts: • Mathematics of computing → Probability and statistics. Additional Key Words and Phrases: Voting, Asynchronous Processes, Load Balancing

Introduction

A voting process operates on an undirected connected graph 𝐺 = (𝑉 , 𝐸) with 𝑛 nodes representing agents, each holding its opinion, and 𝑚 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 [22] is perhaps the most well-known voting process in parallel and distributed computing. In each discrete time step, a randomly chosen node 𝑢 ∈ 𝑉 selects a random neighbor 𝑣 ∈ 𝑁 (𝑢) and adopts 𝑣’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. Authors’ Contact Information: Petra Berenbrink, University of Hamburg, Hamburg, Germany, [email protected]; Colin Cooper, King’s College London, London, United Kingdom, [email protected]; Thorsten Götte, University of Hamburg, Hamburg, Germany, [email protected] ; Lukas Hintze, University of Hamburg, Hamburg, Germany, [email protected]; Tomasz Radzik, King’s College London, London, United Kingdom, [email protected].

This work is licensed under a Creative Commons Attribution 4.0 International License.

Discrete Incremental Voting

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 [18], in which agents repeatedly average their neighbors’ opinions, and boundedconfidence models such as the Deffuant–Weisbuch [17] and Hegselmann–Krause [23] models, in which compromise occurs only between sufficiently similar opinions. In this paper we consider the discrete incremental voting (DIV) process introduced in [13], which bridges the gap between these two viewpoints. Nodes hold opinions from [𝐾] := {0, 1, . . . , 𝐾 } and aim to agree on a single opinion from this set. In each step, a node 𝑢 and one of its neighbors 𝑣 ∈ 𝑁 (𝑢) are chosen uniformly at random. However, instead of adopting 𝑣’s opinion outright, node 𝑢 moves just one step in that direction, updating its opinion by +1 or −1, depending whether 𝑣’s opinion is larger or smaller. This process is formalized below in Protocol 1 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. Protocol 1 The Asynchronous-DIV process For 𝑡 = 0, 1, 2, . . .

▷ step 𝑡 , changing configuration 𝑥® (𝑡 ) = (𝑥 𝑣 (𝑡 ) ) 𝑣 ∈𝑉 to 𝑥® (𝑡 + 1) ▷ 𝑥𝑢 (𝑡 ) is opinion of 𝑢 at the beginning of step 𝑡 Pick a node 𝑢 ∈ 𝑉 uniformly at random Node 𝑢 chooses a neighbor 𝑣 ∈ 𝑁𝑢 uniformly at random if 𝑥𝑢 (𝑡 ) > 𝑥 𝑣 (𝑡 ) :

𝑥𝑢 (𝑡 + 1) ← 𝑥𝑢 (𝑡 ) − 1

else if 𝑥𝑢 (𝑡 ) < 𝑥 𝑣 (𝑡 ) : 𝑥𝑢 (𝑡 + 1) ← 𝑥𝑢 (𝑡 ) + 1 else:

𝑥𝑢 (𝑡 + 1) ← 𝑥𝑢 (𝑡 )

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 𝐾. We present the first general analysis of the convergence time of discrete incremental voting on arbitrary graphs. For any graph 𝐺 with conductance Φ(𝐺) and the ratio of the average to smallest degree 𝛾 (𝐺), we prove that the expected convergence time is 𝑂

𝐾𝑛 log(𝐾𝑛) 𝛾 (𝐺 )𝑛 2 + Φ(𝐺 ) 2 Φ(𝐺 ) 2

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

Pull Voting. For the standard voting process (pull voter model) in a connected graph 𝐺, where nodes adopt opinions of randomly chosen neighbors, it is known that a given opinion 𝑠 wins with probability 𝑑 (𝑠)/2𝑚, where 𝑑 (𝑠) is the sum of the degrees of the nodes initially holding opinion 𝑠 [22]. In [5] the authors consider the synchronous version of this model and show that with constant probability the consensus is reached within 𝑂 (𝛾 (𝐺)𝑛/Φ(𝐺)) rounds. This result can be adopted to the asynchronous setting, giving a bound of 𝑂 (𝛾 (𝐺)𝑛 2 /Φ(𝐺)) steps. In [5], the authors also consider a biased variant of pull voting and dynamic graphs.

Discrete Incremental Voting

The authors of [8] derive a bound of 𝑂 ((1/(1−𝜆)) · (log4 𝑛 +𝜌)) on the expected convergence time of the synchronous pull voting. Here 𝜆 is the second largest (in absolute value) eigenvalue of the transition matrix of a random walk on 𝐺 and 𝜌 is the ratio of the square of the sum of node degrees over the sum of the squared degrees, which ranges from 𝑂 (1) (star graph) to 𝑛 (regular graphs). In [15] 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. Related Opinion Dynamics. In [19], the authors consider the synchronous MedianRule protocol on complete graphs with opinions drawn from an ordered set, say the set [𝐾 − 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. [19] derives bounds on the convergence time of this process, considering also adversarial scenarios. Note that in the case of two initial opinions (𝐾 = 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 𝑗-Majority dynamics. Every node samples randomly 𝑗 neighbours and adopts the majority opinion among the sample. The variants for 𝑗=2 and 𝑗=3 have been analyzed under the names of Two-Choices dynamics [9, 10, 12, 29] and the 3-Majority dynamics [2, 21, 3, 11, 29]. In averaging processes, the nodes adopt the average of the opinions of 𝑗 random neighbors. Such processes are considered, for example, in [4], 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 [1]. Graph Class

Reducing Discrepancy to 1

Reference

Clique (𝐾𝑛 ) G𝑛,𝑝 , 𝑝 ≥ (log1+𝜖 𝑛)/𝑛 General Graph Path 𝜆 -Expander, 𝛾 = 𝑂 (1)

𝑂 (𝐾𝑛 log 𝑛) 𝑂 (𝐾𝑛 log 𝑛), 𝐾 = 𝑂 (log 𝑛) 𝑂 (𝐾𝛾𝑛 2 /Φ) 𝑂 (𝐾𝑛 3 ) √ e (𝐾𝜆𝑛 2 + 𝜆𝑛 2 + 𝑛 5/3 ) 𝑂

[13] [13] [13] + [16] [13] + [16] [14]

General Graph General Graph Regular 𝜆 -Expander

e ( (𝐾 + 𝛾𝑛)𝑛 log(𝐾𝑛)/Φ2 ) 𝑂 Ω (𝐾𝑛/Φ) √ e (𝐾𝜆 2𝑛 2 + 𝜆𝑛 2 + 𝑛 5/3 ) 𝑂

Thm 2.1 Thm 2.2 Thm 2.3 + [14]

Table 1. An overview of the related work compared to ours. For better comparison, we compare the times to reduce to a discrepancy of 1.

1.2

Additional Notation and Preliminaries

We assume 𝑉 = {1, . . . , 𝑛}. Asynchronous-DIV is a Markov process evolving according to Protocol 1. We denote the random state at time 𝑡 ≥ 0 (the beginning of step 𝑡) by 𝑋® (𝑡) = (𝑋 1 (𝑡), . . . , 𝑋𝑛 (𝑡)) and its realization by 𝑥® (𝑡) = (𝑥 1 (𝑡), . . . , 𝑥𝑛 (𝑡)), where 𝑋𝑖 (𝑡) and 𝑥𝑖 (𝑡) refer to the opinion held by node 𝑖 at this time. Let X(𝐾) := {𝑥® = (𝑥 1, . . . , 𝑥𝑛 ) : 𝑥𝑖 ∈ [𝐾]} be the set of all possible configurations. For a configuration 𝑥® = (𝑥 1, . . . , 𝑥𝑛 ), let 𝑥 max := max𝑖 ∈𝑉 𝑥𝑖 and 𝑥 min := min𝑖 ∈𝑉 𝑥𝑖 . The discrepancy is defined as disc (𝑥) ® := 𝑥 max − 𝑥 min ≤ 𝐾 and the degree-weighted average as Í𝑛 1 𝑊 (𝑥) ® := 2𝑚 𝑖=1 𝑑𝑖 𝑥𝑖 , where 𝑑𝑖 is the degree of node 𝑖. The convergence time from configuration 𝑥® is a random variable

Discrete Incremental Voting

defined as o n 𝑇𝐺 (𝑥) ® := min 𝑡 ≥ 0 : 𝑋® (0) = 𝑥, ® disc 𝑋® (𝑡) = 0 . If 𝐾 = 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 T𝐺2𝑉 := max{E [𝑇𝐺 (𝑥)] ® : 𝑥® ∈ X(1)}. 2𝑚 We define the degree imbalance as 𝛾 = 𝛾 (𝐺) := 𝑛 2𝑚 , the ratio of the average degree 𝑑 min 𝑛 to the minimum degree 𝑑 min . Í ′ For a set 𝑆 ⊆ 𝑉 , its volume is vol(𝑆) := 𝑖 ∈𝑆 𝑑𝑖 , and for two disjoint sets 𝑆, 𝑆 ⊆ 𝑉 , we define 𝐸 (𝑆, 𝑆 ′ ) as the set of edges between 𝑆 and 𝑆 ′ . The conductance of 𝐺 is defined as |𝐸 (𝑆, 𝑉 \ 𝑆)| Φ = Φ(𝐺) := min : 𝑆 ⊂ 𝑉 , vol(𝑆) ≤ 𝑚 . vol(𝑆)

(1)

Let 𝐴 be the adjacency matrix of 𝐺 and 𝐷 the diagonal matrix of node degrees. The transition matrix and stationary distribution of a random walk on 𝐺 are 𝑃 = 𝐷 −1𝐴 and 𝜋𝑖 = 𝑑𝑖 /(2𝑚), 𝑖 ∈ 𝑉 . Let 1 = 𝜆1 ≥ 𝜆2 ≥ · · · ≥ 𝜆𝑛 ≥ −1 denote the eigenvalues of 𝑃, 𝜆 = 𝜆(𝐺) = max{𝜆2, |𝜆𝑛 |}, and define the spectral gap as 1 − 𝜆. 2

Our Results

We begin by establishing a general upper bound for the convergence time on any graph 𝐺, expressed in terms of the conductance Φ(𝐺) and the expected convergence time of 2-Value Pull Voting T𝐺2𝑉 . Theorem 2.1. Consider the Asynchronous-DIV process on a graph 𝐺 with conductance Φ(𝐺). Assume 𝑥® is an arbitrary configuration with discrepancy 𝐾. Then the following two bounds on the convergence time 𝑇𝐺 (𝑥) ® hold, with bound (2) holding both in expectation and with high probability (w.h.p),1 𝐾𝑛 log(𝐾𝑛) log(𝑛) 2𝑉 + · T , 𝑇𝐺 (𝑥) ® ∈ 𝑂 𝐺 Φ(𝐺) 2 Φ(𝐺) 𝐾𝑛 log(𝐾𝑛) 𝛾 (𝐺)𝑛 2 E [𝑇𝐺 (𝑥)] ® ∈ 𝑂 + . Φ(𝐺) 2 Φ(𝐺) 2

(2) (3)

To the best of our knowledge, these are the first upper bounds that hold for any initial discrepancy 𝐾 and are superior to the 2-Value Pull Voting majorization. Moreover, using these bounds and known bounds on T𝐺2𝑉 , we can 𝛾 (𝐺 ) 𝑛 2 derive near-tight bounds for many practical graph classes. The best-known bound on T𝐺2𝑉 is 𝑂 Φ(𝐺 ) , which was independently obtained in [5] and [16]. For near-regular graphs with constant conductance, i.e., Φ(𝐺), 𝛾 (𝐺) ∈ 𝑂 (1), bound (2) simplifies to 𝑂 (𝑛 2 log 𝑛) for 𝐾 ∈ 𝑂 (𝑛), and bound (3) simplifies to 𝑂 (𝑛 2 ) for 𝐾 ∈ 𝑂 (𝑛/log 𝑛). 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 𝐾 > 𝑛, 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 [5], the incremental nature of DIV restricts nodes to changing their opinion by at most one per interaction. Consequently, the convergence time must scale with 𝐾. More precisely, we show the following lower bound.

1 In this paper, ’with high probability’ (w.h.p.) means with probability at least 1 − 𝑂 (1/𝑛𝑐 ) for some constant 𝑐 > 1, where 𝑛 is the number of nodes in 𝐺 .

Discrete Incremental Voting

Theorem 2.2 (Lower Bound). Consider the Asynchronous-DIV process on a regular graph 𝐺 with conductance Φ(𝐺). Then there is a configuration 𝑥® with discrepancy 𝐾 such that E [𝑇𝐺 (𝑥)] ® ∈ Ω 𝐾𝑛/Φ(𝐺) + T𝐺2𝑉 . Thus, for graphs with constant conductance, our results are nearly-tight for 𝐾 ≥ 𝑛. To the best of our knowledge, the only other lower bound is Ω(𝑛 3 ) for line graphs shown in [13]. We next show a tighter bound on the convergence time for graphs with strong expansion properties, quantified by 𝜆(𝐺). Theorem 2.3. Consider the Asynchronous-DIV process on a regular graph 𝐺 with second-largest eigenvalue 𝜆(𝐺) ∈ 𝑜 (1). Assume 𝑥® (0) is an arbitrary configuration with discrepancy 𝐾, then E [𝑇𝐺 (𝑥® (0))] ∈ 𝑂 (𝐾 + log 𝑛)𝑛 log 𝐾𝑛 + 𝜆(𝐺) 2 𝑛 2 log 𝑛 + T𝐺2𝑉 . This may appear to be only a modest improvement over the conductance-based bound (2), as the additive T𝐺2𝑉 term precludes convergence faster than Θ(𝑛 2 ) in general, i.e, we shave off a log-factor from the previous bound when 𝐾 ∈ 𝑂 ( log𝑛 𝑛 ) and 𝜆(𝐺) ∈ 𝑂 ( √ 1 ). However, the spectral bound enables a much more refined analysis of the final log 𝑛

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 𝐾 is not too large, the process concentrates tightly around the weighted average of the initial opinions. Theorem 2.4. Consider the Asynchronous-DIV process on a regular graph 𝐺 with 𝜆(𝐺) ∈ 𝑜 (1/log2 𝑛). Assume 𝑥® (0) is an arbitrary configuration with discrepancy 𝐾 ∈ 𝑜 (𝑛/log2 𝑛), then with high probability all nodes agree on either ⌈𝑊 (𝑥® (0))⌉ or ⌊𝑊 (𝑥® (0))⌋. The above theorem improves the results of [14] for a range of parameters. The authors of [14] show for nearly-regular expander graph with second-largest eigenvalue 𝜆(𝐺) ∈ 𝑜 (1) that the final value of Asynchronous-DIV converges w.h.p. to ⌈𝑊 (𝑥® (0))⌉ or ⌊𝑊 (𝑥® (0))⌋, as long as 𝐾 ∈ 𝑜 (min(𝜆 −1 (𝐺), 𝑛/log 𝑛)). Given 𝜆(𝐺) ∈ 𝑜 (1/log2 𝑛), our theorem covers a much wider range of discrepancies. Note however, that for small values of 𝐾 we use their result to reduce the discrepancy to 𝑂 (1). 3

Proofs of our Results

Proof of Theorem 2.1 To show this result, we split the convergence time into two parts. In section 4 we show that the time to reduce the log 𝑛

discrepancy to 𝛼 = 32 Φ(𝐺 ) is 𝑂

𝐾𝑛 log (𝐾𝑛) Φ(𝐺 ) 2

w.h.p. and in expectation (Proposition 4.1 and Corollary 4.2). The second

part reduces the discrepancy from 𝛼 to 0. In [13], 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 T𝐺2𝑉 . From this result we get that the time to reduce the discrepancy from 𝛼 to zero is in expectation at most 𝛼 T𝐺2𝑉 and w.h.p. at most (6𝛼)T𝐺2𝑉 . For the latter bound, consider 3𝛼 phases of 2T𝐺2𝑉 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 Theorem 2.1.

□

Discrete Incremental Voting

Proof of Theorem 2.2 At a high level, we consider a large set 𝑆 which minimizes the conductance (cf. (1)) and its complement 𝑆 = 𝑉 \ 𝑆. All nodes in 𝑆 start with opinion 𝐾, 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 𝑆 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 (𝑆, 𝑆). Since these edges constitute only a fraction |𝐸 (𝑆, 𝑆)|/|𝐸| ≤ Φ(𝐺) 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/|𝑆 |. Hence, random fluctuations accumulate √ slowly, growing in the order of 𝑡/|𝑆 | after 𝑡 steps. As a result, if the initial gap between the mean opinions of 𝑆 and its complement is large, it cannot shrink significantly in a short time. We present the detailed formal proof in the appendix (cf. subsection 7.5). Proof of Theorem 2.3 In Theorem 2.3 we consider regular graphs with small absolute second eigenvalue 𝜆(𝐺) ∈ 𝑜 (1). Note that by Cheeger’s inequality (cf. Lemma 6.1 in the appendix), the conductance is at least (1 − 𝜆(𝐺))/2, so at least 1/2 −𝑜 (1) for 𝜆(𝐺) ∈ 𝑜 (1). Therefore, we already know that the discrepancy 𝐾 is reduced to 𝛼 ∈ 𝑂 (log 𝑛) in 𝑂 (𝐾𝑛 log 𝐾𝑛) steps, both in expectation and high probability (Corollary 4.2 in the proof of Theorem 2.1). Given this result, it only remains to consider how the discrepancy reduces from 𝑂 (log 𝑛) to 0. Again, the proof is divided into two parts. In section 5, we show that in expectation and with high probability, the discrepancy reduces from 𝐾 to 3 in 𝑂 ((𝐾 + log 𝑛) · (𝜆(𝐺) 2𝑛 2 + 𝑛 log 𝑛)) steps. For 𝐾 ∈ 𝑂 (log 𝑛), this further simplifies to 𝑂 (𝜆(𝐺) 2𝑛 2 log 𝑛 + 𝑛 log2 𝑛). The main tool for proving this is Proposition 5.1, 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 [13].

□

Proof of Theorem 2.4 To prove Theorem 2.4, we require insights from [13] and [14]. First, we use the result from [13] showing that it is sufficient to bound the time until discrepancy 1. More precisely, suppose the process starts with initial discrepancy 𝐾 and initial weighted average 𝑊 (𝑥® (0)). Suppose further that the discrepancy reduces to 1 within 𝑂 ((𝑛/𝛿 ) 2 ) steps for some 𝛿. Further let 𝑋® 𝑐 be the configuration when the process has converged so that 𝑊 (𝑋® 𝑐 ) is equal to the agreed value. Then, we have, 1 Pr |𝑊 (𝑥® (0)) − 𝑊 (𝑋® 𝑐 )| > ≤ 𝑒 −Ω (𝛿 ) . 2

(4)

From the proof of Theorem 2.3 (namely, Corollary 5.2) we know that for 𝐾 ∈ 𝑜 (𝑛/log2 𝑛) and 𝜆(𝐺) ∈ 𝑜 (1/log 𝑛), after 𝑂 (𝑛 2 /log 𝑛) steps w.h.p. the discrepancy is 3. Provided that 𝛾 (𝐺) ∈ 𝑂 (1), [14] bounds the time to get from 𝐾 to 1 as √︁ log 𝑛 𝐾 log 𝑛 𝑂 𝑛2 + 𝐾𝜆(𝐺) + 𝜆(𝐺) + 1/3 . 𝑛 𝑛 √︁ For 𝐾 = 3 this is dominated by 𝑂 ( 𝜆(𝐺) · 𝑛 2 + 𝑛 5/3 log 𝑛) = 𝑜 ((𝑛/log 𝑛) 2 ). Thus, Theorem 2.4 follows, using (4) with 𝛿 = log 𝑛.

□

Discrete Incremental Voting 4

Reducing Discrepancy to 𝑂

log 𝑛 Φ(𝐺 )

The main technical contribution of this paper is the following proposition, which bounds the time until the discrepancy 32 log 𝑛

is reduced from 𝐾 down to Φ(𝐺 ) . 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 (𝑢, 𝑣) 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. Proposition 4.1. Consider the Asynchronous-DIV process on a simple connected graph with conductance Φ(𝐺). 32·log 𝑛

Assume 𝑥® (0) is an arbitrary configuration with discrepancy 𝐾 ≥ Φ(𝐺 ) and 𝑐 > 0. Then, both in expectation and with 𝐾 ·𝑛·log(𝐾𝑛) 1 probability at least 1 − 𝑜 (𝐾𝑛) steps. 𝑐 , the discrepancy is reduced to (3/4) · 𝐾 in 20(𝑐 + 3) Φ(𝐺 ) 2 The following immediate corollary gives the first part of the proof of Theorem 2.1. Corollary 4.2. Let 𝛼 =

32·log 𝑛 Φ(𝐺 ) . Consider the Asynchronous-DIV process on a graph 𝐺 with conductance Φ(𝐺).

Assume 𝑥® (0) is a configuration with discrepancy 𝐾. Then, both in expectation and with high probability, the discrepancy is reduced to 𝛼 in 𝑂

𝐾 ·𝑛·log(𝐾𝑛) Φ(𝐺 ) 2

steps.

Proof. We divide the execution into 𝑂 (log 𝐾) phases. Each phase corresponds to reducing the discrepancy by a factor of 3/4. For 𝑖 ≥ 1 we define 𝐾𝑖 = 𝐾 · ( 34 )𝑖 . Hence, in phase 𝑖 the discrepancy is reduced from 𝐾𝑖 −1 to 𝐾𝑖 . In following, let the random variable 𝑇𝑖 denote the length of phase 𝑖. By Proposition 4.1, the time to reduce the discrepancy from 𝐾 ·𝑛 log (𝐾 𝑛)

𝐾𝑖 −1 to 𝐾𝑖 is 𝑂 ( 𝑖 Φ(𝐺 ) 2 𝑖 ), in expectation and with probability 1 − 𝑜 ( 𝐾𝑛1 𝑐 ) even when started from the worst possible configuration with discrepancy 𝐾𝑖 −1 . For convenience, define 𝛽 :=

𝐾 ·𝑛·log(𝐾𝑛) , Φ(𝐺 ) 2

and let 𝑖 ★ := log4/3

𝐾 𝛼

denote the number of phases required until the discrepancy drops below 𝛼. Then the time to reduce the discrepancy from 𝐾 to 𝛼 is ★ −1 𝑖∑︁

𝑖=0

𝑇𝑖 ≤ 𝑂 (𝛽) ·

★ −1 𝑖∑︁

( 34 )𝑖 ≤ 𝑂 (𝛽).

𝑖=0

This establishes the bound in expectation. For the high-probability bound, note that each phase duration satisfies the same bound with probability 1 − 𝑜 ( 𝐾𝑛1 𝑐 ). Since the total number of phases is 𝑖 ★ = 𝑂 (log(𝐾/𝛼)) = 𝑂 (log 𝐾) ∈ 𝑂 (𝐾), a union bound over all phases implies that the overall runtime satisfies the same bound with high probability.

□

We now outline the proof of Proposition 4.1. The proof is based on a potential-function argument. However, instead of using a single potential, we introduce a family of potential functions Ψ𝑘 (𝑋® (𝑡)), one for each index 𝑘 ∈ [𝐾/2, 𝐾]. To

Discrete Incremental Voting

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 [𝐾 − 𝑘, 𝑘] as: 𝜑𝑘(+) (𝑥) :=

𝜑𝐾(−) (𝑥) := −𝑘

  𝑥 − 𝑘, if 𝑥 ≥ 𝑘,    0, otherwise;     (𝐾 − 𝑘) − 𝑥, if 𝑥 ≤ 𝐾 − 𝑘,    0, 

(5)

otherwise.

Now we define the positive and negative potentials w.r.t. a fixed value 𝑘 ∈ [𝐾/2, 𝐾] as follows. Recall that 𝑑𝑖 is the degree of node 𝑖. Ψ𝑘(+) (𝑋® (𝑡)) =

∑︁

2 𝑑𝑖 · 𝜑𝑘(+) (𝑋𝑖 (𝑡)) ,

𝑖 ∈𝑉

Ψ𝐾(−) (𝑋® (𝑡)) = −𝑘

∑︁

2 𝑑𝑖 · 𝜑𝐾(−) (𝑋 (𝑡)) 𝑖 −𝑘

𝑖 ∈𝑉

The potential corresponding to index 𝑘 is defined as n o Ψ𝑘 (𝑋® (𝑡)) = min Ψ𝑘(+) (𝑋® (𝑡)), Ψ𝐾(−) (𝑋® (𝑡)) . −𝑘

(6)

Each potential Ψ𝑘 (𝑋® (𝑡)) measures the remaining discrepancy relative to the threshold 𝑘 at the end of 𝑡 steps. Note that as soon as Ψ𝑘 (𝑋® (𝑡)) = 0, the discrepancy is at most 𝑘 (i.e., has decreased by at least 𝐾 − 𝑘) because all node values are at most 𝑘 or all of them are at least 𝐾 − 𝑘. For the analysis, it will often be useful to consider the mirrored process (𝑋® ′ (𝑡))𝑡 ≥0 , defined by ’mirroring’ configurations of the actual process: 𝑋® ′ (𝑡) := (𝐾 − 𝑋 1 (𝑡), . . . , 𝐾 − 𝑋𝑛 (𝑡)). Note that the processes (𝑋® (𝑡))𝑡 ≥0 and (𝑋® ′ (𝑡))𝑡 ≥0 can be trivially coupled given that the original process starts in 𝑥® (0) and the mirrored process starts in 𝑥®′ (0). Under this coupling, any discrepancy reduction in 𝑋® (𝑡) corresponds to exactly the same discrepancy reduction in 𝑋® ′ (𝑡). We make the following observations. Observation 1. Let (𝑋® (𝑡))𝑡 ≥0 and (𝑋® ′ (𝑡))𝑡 ≥0 be the original and the mirrored processes. Then, for all 𝑡 ≥ 0, (1) disc 𝑋® (𝑡) = disc 𝑋®′ (𝑡) (2) Ψ𝐾(−) (𝑋® (𝑡)) = Ψ𝑘(+) (𝑋®′ (𝑡)) −𝑘 (3) min{Ψ𝑘(+) (𝑋® (𝑡)), Ψ𝐾(−) (𝑋® (𝑡))} = 0 ⇒ disc 𝑋® (𝑡) ≤ 𝑘 −𝑘 (4) min{Ψ𝑘(+) (𝑋® (𝑡)), Ψ𝑘(+) (𝑋®′ (𝑡))} = 0 ⇒ disc 𝑋® (𝑡) ≤ 𝑘 Proof. We show each observation separately. (1) For each configuration 𝑥, ® disc (𝑥) ® = 𝑥 max − 𝑥 min = (𝐾 − 𝑥 min ) − (𝐾 − 𝑥 max ) = disc 𝑥®′ . (2) Note that for every 𝑥 ≤ 𝐾 − 𝑘, it holds that 𝜑𝐾(−) (𝑥) = (𝐾 − 𝑘) − 𝑥 = (𝐾 − 𝑥) − 𝑘 = 𝜑𝑘(+) (𝐾 − 𝑥). −𝑘

Discrete Incremental Voting

Thus, for each configuration 𝑥, ® Ψ𝐾(−) (𝑥) ® = −𝑘

∑︁

𝑑𝑖 · 𝜑𝐾(−) (𝑥 ) 2 = −𝑘 𝑖

∑︁

𝑑𝑖 · 𝜑𝑘(+) (𝐾 − 𝑥𝑖 ) 2 = Ψ𝑘(+) (𝑥®′ ).

𝑖 ∈𝑉

(3) Note that Ψ𝑘(+) (𝑥) ® = 0 implies 𝑥 max ≤ 𝑘 and Ψ𝐾(−) (𝑥) ® = 0 implies 𝑥 min ≥ 𝐾 − 𝑘. Either event implies −𝑘 disc (𝑥) ® = 𝑥 max − 𝑥 min ≤ 𝑘, as 𝑥 max ≤ 𝐾 and 𝑥 min ≥ 0 always. (4) Follows directly from (1), (2), and (3).

□

Thus, by Observation 1(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 𝑘 ∈ [(1/2)𝐾, (3/4)𝐾] is zero, the phase must be over. Next, in subsection 4.1, we prove two key properties. First, we show that each potential function is monotonically non-increasing over time. Second, for each 𝑘 we define good configurations as configurations with many edges between nodes with opinions at least 𝑘 + 1 and nodes with opinions at most 𝑘 − 1. Definition 4.3 (𝑘-good Configurations). For any configuration 𝑥® and integer 𝑘, define 𝑆 := {𝑖 ∈ 𝑉 | 𝑥𝑖 ≥ 𝑘}, 𝑆 := 𝑉 \ 𝑆, 𝑆 +1 := {𝑖 ∈ 𝑉 | 𝑥𝑖 ≥ 𝑘 + 1}.

(7)

We call configuration 𝑥® 𝑘-good if and only if vol(𝑆) ≤ 𝑚 and |𝐸 (𝑆 +1, 𝑆)| ≥ 14 Φ(𝐺) · vol(𝑆 +1 ). Further, if the configuration 𝑥® (𝑡) at the beginning of step 𝑡 is 𝑘-good we say that the (threshold) index 𝑘 is good in step 𝑡. (Recall that step 𝑡 uses 𝑥® (𝑡) to decide 𝑋® (𝑡 + 1).) The definition of 𝑘-good configurations applies to both the original and the mirrored processes. We will show that in a good configuration the potential corresponding to index 𝑘 decreases at least by an amount that is proportional to the conductance. In subsection 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 𝑘 ★ ∈ [(1/2)𝐾, (3/4)𝐾] 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 subsection 4.3. Suppose 𝑘 ★ is good in the original process. ★ ® Since the potential Ψ (+) ★ (𝑋 (𝑡)) decreases whenever 𝑘 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 𝑘 ★ ≤ (3/4)𝐾, completing the proof of the proposition. 4.1

Potential Drop (For a Fixed 𝑘)

In this section, we analyze the expected drop for a potential. To this end, fix an arbitrary integer threshold 𝑘 ∈ [𝐾/2, 𝐾 −1] and show two things. First, the positive potential associated with 𝑘 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. Lemma 4.4. Let 𝐺 := (𝑉 , 𝐸) be a simple graph with conductance Φ(𝐺) and assume 𝑥® is an arbitrary configuration with discrepancy at most 𝐾. For any 𝑘 ∈ [𝐾/2, 𝐾 − 1], the following holds.

Discrete Incremental Voting

(1) The positive potential is non-increasing in expectation: i h E Ψ𝑘(+) (𝑋® (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ Ψ𝑘(+) (𝑥) ® (2) If 𝑥® is 𝑘-good in step 𝑡, then the positive potential exhibits multiplicative drift: h i Φ(𝐺) 2 E Ψ𝑘(+) (𝑋® (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ 1 − · Ψ𝑘(+) (𝑥) ® 5(𝐾 − 𝑘)𝑛 The same holds for the positive potential Ψ𝑘(+) (𝑋®′ (𝑡 + 1)) for the mirrored process. Proof. We begin the analysis by introducing some notations and assumptions that we use in this section. During ® the whole proof, we will condition all expectations and probabilities on the event h that {𝑋 (𝑡) i = 𝑥®} for h some valid i 𝑛 ® configuration 𝑥® ∈ [𝐾] . For readability, we just write E [·] and Pr [·] instead of E · | 𝑋 (𝑡) = 𝑥® and Pr · | 𝑋® (𝑡) = 𝑥® , respectively. Further, since we only consider the positive potential and a fixed 𝑘, we write 𝑓 (𝑥) instead of 𝜑𝑘(+) (𝑥). Recall that 𝑓 (𝑥) = (𝑥 − 𝑘) + , that is, the threshold function of the form 𝑓 (𝑥) =

  𝑥 − 𝑘,    0, 

if 𝑥 ≥ 𝑘, otherwise.

We define the random variable Δ(𝑋® (𝑡 + 1)) = Ψ𝑘(+) (𝑋® (𝑡 + 1)) − Ψ𝑘(+) (𝑋® (𝑡 + 1)) =

∑︁

𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) 2 −

𝑖 ∈𝑉

∑︁

𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡)) 2,

𝑖 ∈𝑉

which measures the change of the potential in step 𝑡. Since we condition on 𝑋® (𝑡) = 𝑥, ® we have " # h i ∑︁ ∑︁ E Δ(𝑋® (𝑡 + 1)) = E 𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) 2 − 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 . 𝑖 ∈𝑉

𝑖 ∈𝑉

Given this definition, it suffices to show that E Δ(𝑋® (𝑡 + 1)) ≤ 0 to prove part (1) of the lemma. To prove part (2), we need to show that if 𝑥® is 𝑘-good in step 𝑡, then h i ∑︁ Φ(𝐺) 2 E Δ(𝑋® (𝑡 + 1)) ≤ − · 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 . 5(𝐾 − 𝑘)𝑛 𝑖 ∈𝑉

(8)

While 𝐺 = (𝑉 , 𝐸) is a simple undirected graph, it will be convenient to view 𝐺 as a bi-directed graph that has two directed edges (𝑖, 𝑗) and ( 𝑗, 𝑖) for each undirected edge {𝑖, 𝑗 }; and we use the notation (7). Having established these preliminaries, we begin the analysis with a technical claim that will immediately imply (1) and aid us in the proof of (2). We show that while the potential can increase if a node increases its opinion, in expectation it does not. More precisely, we show that the expected potential change can be bounded by a sum over directed edges involving only linear differences of the form 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ). We present the full proof of the following claim in the appendix (cf. subsection 7.1). Claim 1. Let 𝐸𝑆+1 = {(𝑖, 𝑗) ∈ 𝐸 | 𝑖 ∈ 𝑆 +1 }. Then it holds: h i 1 ∑︁ E Δ(𝑋® (𝑡 + 1)) ≤ − 𝑛

𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1}

(9)

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

Proof Sketch. The claim follows from elementary calculations. The core idea is as follows: For two adjacent nodes 𝑖 and 𝑗 with 𝑥𝑖 > 𝑥 𝑗 , we can amortize the increase in potential when the edge ( 𝑗, 𝑖) is chosen with the decrease in

Discrete Incremental Voting

potential when (𝑖, 𝑗) is chosen. Both these changes cancel out in expectation for edges {𝑖, 𝑗 } with difference 1, while for edges with difference 2 or more, the convexity of the square function implies that the expected decrease of 𝑥𝑖 dominates the expected increase of 𝑥 𝑗 . The difference is precisely captured by the term 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ), and summing over all edges yields the claim.

□

Note that in this notation, we consider the potential difference along the edges (denoted by 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) and add an error term for those edges which have the opinion difference of exactly 1 (denoted by 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ). This claim will make the remainder of the proof significantly simpler, as it eliminates both the degree weights and the squared terms. Proof of (1). Having established Claim 1 we now use (9) to prove the first statement of the lemma. To this end, note that each summand in the sum in (9) is non-negative: as 𝑥𝑖 ≥ 𝑘 + 1, if |𝑥𝑖 − 𝑥 𝑗 | ≥h 1 then 𝑓 (𝑥𝑖i) − 𝑓 (𝑥 𝑗 ) ≥ 1 and the summand is non-negative, and if 𝑥𝑖 = 𝑥 𝑗 then the summand is equal to 0. Thus E Δ(𝑋® (𝑡 + 1)) ≤ 0, proving that the potential is non-increasing in expectation and therefore a supermartingale. Proof of (2). For proving (2), we require some more techniques. First, we show that the edge-wise differences 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) can be bounded in terms of the graph’s conductance. Using techniques from the analysis of random walk and continuous load balancing, we prove the following claim. Claim 2. Suppose that vol(𝑆) ≤ 𝑚, then h i 1 Φ(𝐺) ∑︁ · 𝑑𝑖 𝑓 (𝑥𝑖 ) + E Δ(𝑋® (𝑡 + 1)) ≤ − 𝑛 𝑛 𝑖 ∈𝑉

∑︁

1 { |𝑥𝑖 −𝑥 𝑗 |=1} .

(10)

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

Proof. For the proof, we show that the RHS in (10) is at least the RHS in (9), that is, after canceling the error term and the 1/𝑛 factor, we need to show that ∑︁

∑︁ 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) ≥ Φ(𝐺) · 𝑑𝑖 𝑓 (𝑥𝑖 ).

(11)

𝑖 ∈𝑉

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

We show this inequality using a clever combinatorial trick from Mikhail [28], where it was used to bound the convergence of simple random walks on 𝑑-regular graphs. We only need to slightly adapt the analysis from [28] to fit our process. Assume w.l.o.g. the nodes are ordered by decreasing opinion, i.e., 𝑥 1 ≥ 𝑥 2 ≥ . . . ≥ 𝑥𝑛 . This way 𝑖 < 𝑗 implies 𝑥𝑖 ≥ 𝑥 𝑗 . Further, let 𝑗𝑘 be the last index with 𝑥 𝑗𝑘 > 𝑘, that is, 𝑆 +1 = {1, 2, . . . , 𝑗𝑘 }, and observe that 𝑓 (𝑥𝑖 ) = 0 for all 𝑖 > 𝑗𝑘 . Thus, ∑︁ ∑︁ 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) = (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )). (12) (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

(𝑖,𝑗 ) ∈𝐸 𝑖< 𝑗

For each ℓ ∈ [𝑛], let 𝐴ℓ := {𝑣 1, . . . , 𝑣 ℓ } be the set of the first ℓ nodes after ordering by decreasing opinion. Further, define O(𝐴ℓ ) to be set of edges leading out of 𝐴ℓ : O(𝐴ℓ ) := {{𝑣, 𝑤 } ∈ 𝐸 | 𝑣 ∈ 𝐴ℓ and 𝑤 ∉ 𝐴ℓ } . Mikhail [28] proves a useful identity, from which inequality (11) will follow, namely ∑︁ (𝑖,𝑗 ) ∈𝐸 𝑖< 𝑗

(𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) =

𝑛−1 ∑︁ ℓ=1

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 ))|O(𝐴ℓ )|.

(13)

Discrete Incremental Voting

The above identity holds because the LHS can be written as 𝑗 −1 ∑︁ ∑︁

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 )) =

𝑛−1 ∑︁

∑︁

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 )).

ℓ=1 (𝑖,𝑗 ) ∈𝐸 𝑖 ≤ℓ < 𝑗

(𝑖,𝑗 ) ∈𝐸 ℓ=𝑖 𝑖< 𝑗

The index set of the inner sum on the right is the set of edges (𝑖, 𝑗) ∈ 𝐸 where 𝑖 ≤ ℓ < 𝑗, so the set O(𝐴ℓ ), implying that this inner sum is equal to (𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 ))|O(𝐴ℓ )|.

With identity (13), we can return to the statement we want to prove. Recall that for each 𝑆 ⊆ 𝑉 , we defined vol(𝑆) = Íℓ 𝑣 ∈𝑆 𝑑 𝑣 , so for each 1 ≤ ℓ ≤ 𝑛, vol(𝐴ℓ ) = 𝑖=1 𝑑𝑖 and vol(𝐴ℓ ) − vol(𝐴ℓ −1 ) = 𝑑 ℓ , setting vol(𝐴0 ) = 0. By the definition of

the conductance Φ(𝐺) (given in Equation 1), we have |O(𝐴ℓ )| ≥ Φ(𝐺) · vol(𝐴ℓ ) for any ℓ ≥ 1 with vol(𝐴ℓ ) ≤ 𝑚. By the definition of 𝑗𝑘 and the conditions of the claim, for 1 ≤ ℓ ≤ 𝑗𝑘 , vol(𝐴ℓ ) ≤ vol 𝐴 𝑗𝑘 = vol(𝑆 +1 ) ≤ vol(𝑆) ≤ 𝑚; and recall that for ℓ > 𝑗𝑘 , 𝑓 (𝑥 ℓ ) = 0. Thus (11) follows from (12), (13) and the following: 𝑛−1 ∑︁

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 ))|O(𝐴ℓ )|

ℓ=1

𝑗𝑘 ∑︁

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 ))|O(𝐴ℓ )|

ℓ=1

≥ Φ(𝐺)

𝑗𝑘 ∑︁

(𝑓 (𝑥 ℓ ) − 𝑓 (𝑥 ℓ+1 ))vol(𝐴ℓ )

ℓ=1

= Φ(𝐺) = Φ(𝐺)

𝑗𝑘 ∑︁

𝑓 (𝑥 ℓ ) · vol(𝐴ℓ ) −

𝑗𝑘 ∑︁

ℓ=1

𝑗𝑘 ∑︁

𝑛 ∑︁

ℓ=1

𝑓 (𝑥 ℓ ) · 𝑑 ℓ = Φ(𝐺)

! 𝑓 (𝑥 ℓ ) · vol(𝐴ℓ −1 )

𝑓 (𝑥 ℓ ) · 𝑑 ℓ .

□

ℓ=1

We now use inequalities (9) and (10) to complete the proof of part (2) of Lemma 4.4. The next step is to prove the following claim. Claim 3. Suppose that 𝑥® is 𝑘-good in step 𝑡. Then, h i Φ(𝐺) 2 ∑︁ E Δ(𝑋® (𝑡 + 1)) ≤ − · 𝑑𝑖 𝑓 (𝑥𝑖 ). 5𝑛 𝑖 ∈𝑉

(14)

Proof sketch. (The full proof is in the appendix subsection 7.2.) We distinguish two cases defined by the magnitude Í 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ). Í +1 ) Case 1: Suppose 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ) ≥ 54 · vol(𝑆 Φ(𝐺 ) . In this case the error term sum in (10), maximized when every edge with Í an endpoint in 𝑆 +1 has difference exactly 1, is at most vol(𝑆 +1 ) ≤ 54 · Φ(𝐺) 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ). Using this in (10) gives of

h i 1 Φ(𝐺) ∑︁ Φ(𝐺) 2 ∑︁ E Δ(𝑋® (𝑡 + 1)) ≤ − · · 𝑑𝑖 𝑓 (𝑥𝑖 ) ≤ − · 𝑑𝑖 𝑓 (𝑥𝑖 ). 5 𝑛 5𝑛 𝑖 ∈𝑉 𝑖 ∈𝑉 Case 2: Suppose the opposite, that

5 vol(𝑆 +1 ) 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ) < 4 · Φ(𝐺 ) . In this case, we use (9) instead of (10). First, recall that

all summands in the sum in (9) are non-negative, as shown in the proof of part (1) of the lemma. In the following, we only count the contribution to this sum from the edges in 𝐸 (𝑆 +1, 𝑆), that is, from the edges (𝑖, 𝑗) with 𝑥𝑖 ≥ 𝑘 + 1 and

Discrete Incremental Voting

𝑥 𝑗 ≤ 𝑘 − 1. Each such edge contributes at least 1 to this sum, so h i 1 E Δ(𝑋® (𝑡 + 1)) ≤ − · |𝐸 (𝑆 +1, 𝑆)|. 𝑛 Second, since 𝑥® is 𝑘-good by assumption, we have by Definition 4.3 that |𝐸 (𝑆 +1, 𝑆)| ≥ 14 · Φ(𝐺) · vol(𝑆 +1 ) . Thus h i 1 E Δ(𝑋® (𝑡 + 1)) ≤ − · Φ(𝐺) · vol(𝑆 +1 ) . 4𝑛 Í Using now the assumption that vol(𝑆 +1 ) > 45 · Φ(𝐺) · 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ), we obtain the claimed bound (14) also in this case.

□

To finalize the proof of Lemma 4.4, we use Equation (14) and bound

𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ) in terms of

2 𝑖 ∈𝑉 𝑑𝑖 𝑓 (𝑥𝑖 ) . As each

𝑥𝑖 is at most 𝐾, then 𝑓 (𝑥𝑖 ) = (𝑥 − 𝑘) + is at most 𝐾 − 𝑘, so 𝑛 ∑︁

𝑑𝑖 𝑓 (𝑥𝑖 ) ≥

𝑖=1

𝑛 1 ∑︁ 𝑑𝑖 𝑓 (𝑥𝑖 ) 2 . 𝐾 − 𝑘 𝑖=1

Applying the above to (14) gives the required bound (8). 4.2

□

Existence of Good Indices

In this section, we show that there exists an index 𝑘 ★ whose corresponding potential decreases frequently in either the original or the mirrored process. Lemma 4.5. Let 𝐾 ≥

32 log 𝑛 Φ(𝐺 )

and consider a sequence of 𝑇 steps 0, 1, . . . ,𝑇 − 1. Then there exists an index 𝑘 ★ ∈

[( 1/2)𝐾, ( 3/4)𝐾] that is good in at least 𝑇 /4 steps in the original process or at least 𝑇 /4 steps in the mirrored process. Proof. For each step 𝑡, define 𝑆𝑘 (𝑡) := {𝑖 ∈ 𝑉 : 𝑋𝑖 (𝑡) ≥ 𝑘}, 𝑆 𝑘 (𝑡) := 𝑉 \ 𝑆𝑘 (𝑡). Since vol 𝑆𝐾/2 (𝑡) + vol 𝑆 𝐾/2 (𝑡) = 2𝑚, it follows that in every step 𝑡, at least one of the two sets 𝑆𝐾/2 (𝑡) and 𝑆 𝐾/2 (𝑡)

has volume at least 𝑚. Therefore, there exists a subset of steps 𝑇 ′ ⊆ [𝑇 − 1] with |𝑇 ′ | ≥ 𝑇 /2 such that either vol 𝑆𝐾/2 (𝑡) ≤ 𝑚, for all 𝑡 ∈ 𝑇 ′, or vol 𝑆 𝐾/2 (𝑡) ≤ 𝑚,

for all 𝑡 ∈ 𝑇 ′ .

In the following, we assume w.l.o.g. that the former holds and show that there is an index which is good in at least half of the steps in 𝑇 ′ in the original process. Otherwise we can do an analogous proof and show that there is an index which is good in at least half of the steps in 𝑇 ′ in the mirrored process. In the remainder of the proof, we restrict attention to steps 𝑡 ∈ 𝑇 ′ . Recall that an index 𝑘 ≥ 𝐾/2 is good in step 𝑡 if |𝐸 (𝑆𝑘+1 (𝑡), 𝑆 𝑘 (𝑡))| ≥ 14 Φ(𝐺) · vol(𝑆𝑘+1 (𝑡)) . Thus, if an index is bad (not good) in step 𝑡, it holds vol(𝑆𝑘 (𝑡)) > 1 + 43 Φ(𝐺) · vol(𝑆𝑘+1 (𝑡)) .

(15)

Discrete Incremental Voting

To see this, consider the difference vol(𝑆𝑘 (𝑡)) − vol(𝑆𝑘+1 (𝑡)), which is at least the number of edges between 𝑆𝑘+1 (𝑡) and 𝑆𝑘 (𝑡) \ 𝑆𝑘+1 (𝑡), which in turn, for a bad index 𝑘, is at least 34 Φ(𝐺) · vol(𝑆𝑘+1 (𝑡)): Í vol(𝑆𝑘 (𝑡)) − vol(𝑆𝑘+1 (𝑡)) = {𝑑𝑖 : 𝑖 ∈ 𝑆𝑘 (𝑡) \ 𝑆𝑘+1 (𝑡)} ≥ |𝐸 (𝑆𝑘+1 (𝑡), 𝑆𝑘 (𝑡) \ 𝑆𝑘+1 (𝑡))| = |𝐸 (𝑆𝑘+1 (𝑡), 𝑆 𝑘+1 (𝑡))| − |𝐸 (𝑆𝑘+1 (𝑡), 𝑆 𝑘 (𝑡))| > Φ(𝐺) · vol(𝑆𝑘+1 (𝑡)) − 41 Φ(𝐺) · vol(𝑆𝑘+1 (𝑡)) . Using (15), we first show that in any step 𝑡, the number of bad indices in [( 1/2)𝐾, ( 3/4)𝐾] is small. Fix a step 𝑡 and let 𝑘 0 > 𝑘 1 > · · · > 𝑘 ℓ be the bad indices in [( 1/2)𝐾, ( 3/4)𝐾] in this step. Since 𝑆𝑘ℓ −1 (𝑡) ⊆ 𝑆𝑘ℓ (𝑡), it follows from (15) that vol 𝑆𝑘ℓ (𝑡) > 1 + 34 Φ(𝐺) · vol 𝑆𝑘ℓ +1 (𝑡) ≥ 1 + 43 Φ(𝐺) · vol 𝑆𝑘ℓ −1 (𝑡) . Applying this inductively to indices 𝑘 ℓ , 𝑘 ℓ −1, . . . , 𝑘 1 yields ℓ ℓ 2𝑚 ≥ vol 𝑆𝑘ℓ (𝑡) > 1 + 34 Φ(𝐺) · vol 𝑆𝑘0 (𝑡) ≥ 1 + 43 Φ(𝐺) , where the last inequality holds since vol 𝑆𝑘0 (𝑡) ≥ 1. This implies ℓ<

log(𝑛 2 ) 4 log 𝑛 ≤ Φ(𝐺 ) , log(1 + ( 3/4)Φ(𝐺))

where the last inequality holds because log(1 + 𝑥) ≥ ( 2/3)𝑥 for 0 < 𝑥 ≤ 1. Therefore, the number of bad indices in any 4 log 𝑛 step is at most 𝛼 := Φ(𝐺 ) ≤ 𝐾/8. For each step 𝑡 ∈ 𝑇 ′ , let 𝐵(𝑡) ⊆ [( 1/2)𝐾, ( 3/4)𝐾] denote the set of bad indices in that step. As shown above, |𝐵(𝑡)| ≤ 𝛼. Consider the set of pairs 𝑃 := {(𝑘, 𝑡) : 𝑡 ∈ 𝑇 ′, 𝑘 ∈ 𝐵(𝑡)}. Counting by steps yields |𝑃 | =

Í3𝐾/4 ′ ′ 𝑡 ∈𝑇 ′ |𝐵(𝑡)| ≤ 𝛼 |𝑇 |, counting by indices yields |𝑃 | = 𝑘=𝐾/2 |{𝑡 ∈ 𝑇 : 𝑘 ∈ 𝐵(𝑡)}|, so

3𝐾/4 ∑︁

|{𝑡 ∈ 𝑇 ′ : 𝑘 ∈ 𝐵(𝑡)}| ≤ 𝛼 |𝑇 ′ |.

𝑘=𝐾/2

Therefore, there exists an index 𝑘 ★ ∈ [( 1/2)𝐾, ( 3/4)𝐾] such that |{𝑡 ∈ 𝑇 ′ : 𝑘 ★ ∈ 𝐵(𝑡)}| ≤

𝛼 |𝑇 ′ | |𝑇 ′ | ≤ . 𝐾/4 2

Such an index 𝑘 ★ is good in at least |𝑇 ′ |/2 ≥ 𝑇 /4 steps. 4.3

□

Putting Everything Together

Finally, we put these results together to prove Proposition 4.1. First, we show that for any index 𝑘 the probability that there are many steps when 𝑘 is good is large and that the probability that the corresponding potential is still large is negligible. In the appendix (cf. subsection 7.3), we prove the following statement. Lemma 4.6. Fix 𝑘 ∈ [𝐾/2, 𝐾] and let𝑇 = 20𝑐·(𝐾−𝑘)

𝑛 log(𝐾𝑛) for some 𝑐 > 2. Let 𝜏𝑘 (𝑡) := |{𝜏 ∈ [𝑡] : 𝑘 is good in step 𝜏 }|. Φ2 (𝐺 )

Then h i Pr Ψ𝑘(+) (𝑋® (𝑇 )) > 0 ∧ 𝜏𝑘 (𝑇 − 1) ≥ 𝑇 /4 ≤

1 , (𝐾𝑛)𝑐 −2

Discrete Incremental Voting

The event above means that the potential w.r.t. index 𝑘 is still positive after the steps 0, 1, . . . ,𝑇 − 1 despite this index being good in at least quarter of these steps. The same holds for the mirrored process. Proof Sketch. We begin with some definitions and assumptions. Let F (𝑡) be the natural filtration of the process that contains all configurations (and thus all random choices) up to (the beginning of) step 𝑡. Note that 𝜏𝑘 (𝑡) is completely determined by F (𝑡). Further denote the event which probability we want to upper bound by 𝐵𝑘 (𝑇 ) := {Ψ𝑘(+) (𝑋® (𝑇 )) > 0} ∩ {𝜏𝑘 (𝑇 − 1) ≥ 𝑇 /4}.

(16)

We define the following auxiliary random process:  (+) ®   if 𝑡 = 0,   Ψ𝑘 (𝑋 (0))  −𝜏𝑘 (𝑡 −1) 𝜓 (𝑡) := 2 Φ(𝐺)  (+) ®  if 𝑡 > 0.   Ψ𝑘 (𝑋 (𝑡)) · 1 − 5(𝐾 − 𝑘)𝑛  Note that 𝜓 (𝑡) is measurable with respect to the filtration F (𝑡). First, we show that (𝜓 (𝑡))𝑡 ≥0 is a supermartingale, i.e., for all 𝑡 ≥ 0, E [𝜓 (𝑡 + 1) | F (𝑡)] ≤ 𝜓 (𝑡). This follows by a simple case distinction we present in the appendix subsection 7.3. The core idea is to use Lemma 4.4 that the increase in the term 1−

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝜏𝑘 (𝑡 −1)

is always compensated by the expected decrease in Ψ𝑘(+) (𝑋® (𝑡)). Now define the stopping time 𝑇 ′ := min {𝑇 , inf {𝑡 ≥ 0 : 𝜏𝑘 (𝑡 − 1) ≥ 𝑇 /4}} . As (𝜓 (𝑡))𝑡 ≥0 is a nonnegative supermartingale and the stopping time 𝑇 ′ is bounded by 𝑇 , the conditions of Doob’s optional stopping theorem (cf. Theorem 6.3) are satisfied and we obtain E [𝜓 (𝑇 ′ )] ≥ 𝜓 (0). On the event 𝐵𝑘 (𝑇 ), we have Ψ𝑘(+) (𝑋® (𝑇 ′ )) > 0, and since the potential is integer-valued, it follows that Ψ𝑘(+) (𝑋® (𝑇 ′ )) ≥ 1. Further, since 𝐵𝑘 (𝑇 ) implies 𝜏𝑘 (𝑇 ′ − 1) ≥ 𝑇 /4, we have 𝜓 (𝑇 ′ ) = Ψ𝑘(+) (𝑋® (𝑇 ′ )) · 1 − ≥ 1−

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝜏𝑘 (𝑇 ′ −1)

−𝑇 /4 .

Therefore, E [𝜓 (𝑇 ′ )] ≥ Pr [𝐵𝑘 (𝑇 )] · E [𝜓 (𝑇 ′ ) | 𝐵𝑘 (𝑇 )] −𝑇 /4 Φ(𝐺) 2 ≥ Pr [𝐵𝑘 (𝑇 )] · 1 − . 5(𝐾 − 𝑘)𝑛 Since 𝜓 (0) = Ψ𝑘(+) (𝑥® (0)) ≤ 𝐾 2𝑛 2 , we obtain 𝐾 2𝑛 2 ≥ Pr [𝐵𝑘 (𝑇 )] · 1 −

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝑇 /4 .

Discrete Incremental Voting

Solving for Pr [𝐵𝑘 (𝑇 )] and using 𝑇 = 20𝑐

(𝐾 −𝑘 )𝑛 log(𝐾𝑛) gives Φ(𝐺 ) 2

Pr [𝐵𝑘 (𝑇 )] ≤ (𝐾𝑛)

Φ(𝐺) 2 1− 5(𝐾 − 𝑘)𝑛

𝑇 /4

5(𝐾 −𝑘 2)𝑛 ·𝑐 log(𝑛𝐾 ) Φ(𝐺 ) Φ(𝐺) 2 = (𝐾𝑛) 1 − 5(𝐾 − 𝑘)𝑛 1 ≤ (𝐾𝑛) 2𝑒 −𝑐 log 𝐾𝑛 = . (𝐾𝑛)𝑐 −2

□

Proposition 4.1 follows from Lemmas 4.5 and 4.6. Proof of Proposition 4.1. Let 𝐹 be the event that for each 𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾] both potentials (original and mirrored) are still positive after 𝑇 = 20(𝑐 + 3)

𝐾𝑛 log 𝐾𝑛 steps, that is, Φ(𝐺 ) 2

Ψ𝑘(+) (𝑋® (𝑇 )) > 0 and Ψ𝑘(+) (𝑋®′ (𝑇 )) > 0. If 𝐹 does not occur, then the discrepancy must have dropped by 14 𝐾 by time 𝑇 , as desired. Thus it suffices to upper bound the probability of 𝐹 . That being said, for each 𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾], consider the events 𝐵𝑘 (𝑇 ) for the original process and 𝐵𝑘′ (𝑇 ) for the mirrored process defined in Lemma 4.6 in (16). By Lemma 4.5, there must exist an index 𝑘 ★ ∈ [( 1/2)𝐾, ( 3/4)𝐾] such that 𝜏𝑘 (𝑇 − 1) ≥ 𝑇 /4 in the original or mirrored process. Hence, if 𝐹 occurs, then 𝐵𝑘 ★ (𝑇 ) or Ð ( 3/4 )𝐾 𝐵𝑘′ ★ (𝑇 ) occurs, so 𝐹 ⊆ 𝑘=( {𝐵𝑘 (𝑇 ) ∪ 𝐵𝑘′ (𝑇 )} and by the union bound, 1/2 )𝐾  ( 3Ø   /4 )𝐾  Pr [𝐹 ] ≤ Pr  {𝐵𝑘 (𝑇 ) ∪ 𝐵𝑘′ (𝑇 )} 𝑘=( 1/2 )𝐾    ( 3∑︁ /4 )𝐾 ≤ Pr [𝐵𝑘 (𝑇 )] + Pr 𝐵𝑘′ (𝑇 ) 𝑘=( 1/2 )𝐾

≤ 5

𝐾 1 2 = 𝑜 · . 4 (𝐾𝑛) (𝑐+3) −2 (𝐾𝑛)𝑐

□

Reducing Discrepancy to 3

The main result of this section is the following proposition. Proposition 5.1. Let 𝐺 be a regular graph with second largest (in absolute value) eigenvalue 𝜆(𝐺) ∈ 𝑜 (1). Then, from any configuration with discrepancy 𝐾 ≥ 4, the probability that the discrepancy reduces by one within 𝑂 (𝜆(𝐺) 2 ·𝑛 2 +𝑛 log 𝑛) steps is at least 21 , From Proposition 5.1 we get the following corollary. Corollary 5.2. Consider the Asynchronous-DIV process on a regular graph 𝐺 with second largest eigenvalue 𝜆(𝐺) ∈ 𝑜 (1) in absolute value. Assume 𝑥® (0) is a configuration with discrepancy 𝐾. Then, both in expectation and with high probability, the discrepancy is reduced to 3 in 𝑂 (𝐾 + log 𝑛) · 𝜆(𝐺) 2 · 𝑛 2 + 𝑛 log 𝑛 steps. Proof. For each 𝑘 ≥ 0, let 𝑇𝑘 be the time in which the discrepancy drops by one for the first time when started form Í𝐾 the worst-case configuration with discrepancy 𝑘. Clearly, 𝑘=4 𝑇𝑘 is an upper bound for the time we are looking for as it pessimistically assumes we are in the worst case configuration after each drop in discrepancy. By Proposition 5.1 we know there is a 𝛽 ∈ 𝑂 (𝜆(𝐺) 2 𝑛 2 + 𝑛 log 𝑛) such that from any time 𝑡, regardless of the past, within the next 𝛽 steps the

Discrete Incremental Voting

discrepancy drops by 1 with probability at least 1/2. Thus, if we partition time into phases of length 𝛽, in each phase the discrepancy drops with probability at least 12 . Hence, for 𝑘 = 𝐾, 𝐾 − 1, . . . , 4, there are i.i.d. Geom(1/2) random variables 𝑌𝑘 such that 𝑇𝑘 ≤ 𝛽𝑌𝑘 . Therefore 𝐾 ∑︁

𝑇𝑘 ≤ 𝛽

𝑘=4

𝐾 ∑︁

𝑌𝑘 .

𝑘=4

Using the Chernoff bound for sums of geometric random variables (see Theorem 6.5 in the appendix), there exists an absolute constant 𝑐 > 0 such that for all 𝐾 ≥ 4, "𝐾 # "𝐾 # ∑︁ ∑︁ Pr 𝑇𝑘 ≥ 2𝑐𝛽 (𝐾 + log 𝑛) ≤ Pr 𝑌𝑘 ≥ 2𝑐 (𝐾 + log 𝑛) 𝑘=4

𝑘=4

≤ exp − Ω(𝐾 + log 𝑛) ≤ 𝑛 −Ω (1) . The corollary follows from the above bound.

□

Without loss of generality, assume 𝑥 min = 0, and let 𝑆 0 (𝑡) = {𝑖 ∈ 𝑉 : 𝑥𝑖 (𝑡) = 0}, 𝑆𝐾 (𝑡) = {𝑖 ∈ 𝑉 : 𝑥𝑖 (𝑡) = 𝐾 }. Similar to the analysis 2-Value pull voting in [5, 16], we will track the progress of the process via the minority opinion 𝜂 (𝑡) := min {vol(𝑆 0 (𝑡)) , vol(𝑆𝐾 (𝑡))} . Clearly, the discrepancy has reduced by (at least) 1 once 𝜂 (𝑡) = 0. In the appendix subsection 7.4 we show a full proof of the following lemma, adapting the relevant proofs from Berenbrink et al. [5] and Cooper and Rivera [16]. 𝑠 ·𝑛 Lemma 5.3. Suppose that 𝜂 (𝑡) = 𝑠. Then, with probability at least 12 , the discrepancy drops by 1 within 𝑂 Φ(𝐺 ) ·𝑑 min (𝐺 ) steps. √︁ Proof Sketch. Consider 𝜂 (𝑡). For 𝑠 > 0, define n o 𝜏𝑠 := min 𝑡 ≥ 0 : Pr [𝜂 (𝑡) = 0 | 𝜂 (0) = 𝑠] ≥ 12 . √ Using Taylor bounds for the concave · and calculations from [16], we show2 there exists a constant 𝑐 > 0 such that for all 𝑡 < 𝜏𝑠 ,

h√︁ i h√︁ i 𝑐𝑑 min (𝐺) · Φ(𝐺) . 𝜂 (𝑡 + 1) | 𝜂 (0) = 𝑠 ≤ E 𝜂 (𝑡) | 𝜂 (0) = 𝑠 − √ 𝑠 ·𝑛 By induction, for all 𝑡 < 𝜏𝑠 it follows that h√︁ i √ 𝑑 min (𝐺) · Φ(𝐺) E 𝜂 (𝑡) | 𝜂 (0) = 𝑠 ≤ 𝑠 − 𝑡 · 𝑐 · . √ 𝑠 ·𝑛 √︁ Moreover, since 𝜂 (𝑡) is integral, 1 {𝜂 (𝑡 ) >0} ≤ 𝜂 (𝑡), and hence h√︁ i Pr [𝜂 (𝑡) > 0 | 𝜂 (0) = 𝑠] ≤ E 𝜂 (𝑡) | 𝜂 (0) = 𝑠 . E

Therefore, if 𝑡 ≥ then E

√ √ 𝑠 − 21 𝑠 ·𝑛 𝑠𝑛 · ∈𝑂 , 𝑐 𝑑 min (𝐺) · Φ(𝐺) Φ(𝐺) · 𝑑 min (𝐺)

h√︁ i 𝜂 (𝑡) | 𝜂 (0) = 𝑠 ≤ 12 , implying Pr [𝜂 (𝑡) = 0 | 𝜂 (0) = 𝑠] ≥ 21 and thus 𝑡 ≥ 𝜏𝑠 .

2 For the precise calculation see Claim 4 in subsection 7.4.

□

Discrete Incremental Voting

With the help of this lemma, we can now complete the prove the proposition. Proof of Proposition 5.1. We distinguish two cases based on the size of 𝜂 (𝑡). Case 1: 𝜂 (𝑡) ≤ 16 · 2𝑚 · 𝜆(𝐺) 2 . In this case, we apply Lemma 5.3. This lemma shows that and extreme opinion disappears after

𝑛𝜂 (𝑡) 𝑑 min (𝐺) · Φ(𝐺) steps with probability at least 1/2. Note that by Cheeger’s inequality (cf. Lemma 6.1 in the appendix), we can lower 𝑇 =𝑂

bound the conductance by (1−𝜆(𝐺))/2. Thus, for 𝜆(𝐺) ∈ 𝑜 (1), the conductance is constant. Together with 𝐺’s regularity and the fact that 𝜂 (𝑡) ≤ 𝑚 (which must be true as 𝑆𝐾 (𝑡) ∩ 𝑆 0 (𝑡) = ∅), we get 𝑛𝜂 (𝑡) 𝑛 · 𝜆(𝐺) 2 · 𝑚 𝑂 =𝑂 = 𝑂 𝜆(𝐺) 2 · 𝑛 2 𝑑 min (𝐺) · Φ(𝐺) 𝑑 min (𝐺) Thus, in this case, the lemma holds. Case 2: 𝜂 (𝑡) > 16 · 2𝑚 · 𝜆(𝐺) 2 . In this case, either 1 or 𝐾 − 1 must be good in the sense of Lemma 4.4 Recall that the discrepancy is at least 4 and suppose, w.l.o.g., the median opinion is at most 𝐾 − 2. Otherwise, consider the mirrored configuration. Now consider the opinions with opinion at most 𝐾 − 2, namely 𝑆 (𝑡) = {𝑖 ∈ 𝑉 : 𝑥𝑖 (𝑡) ≤ 𝐾 − 2}. In order to show that 𝐾 − 1 is good, we must show |𝐸 (𝑆𝐾 (𝑡), 𝑆 (𝑡))| ≥ 41 Φ(𝐺) · vol(𝑆𝐾 (𝑡)) . We want to apply the expander mixing lemma, which gives vol(𝑆𝐾 (𝑡)) · vol 𝑆 (𝑡) |𝐸 (𝑆𝐾 (𝑡), 𝑆 (𝑡))| ≥ 2𝑚 √︂ − 𝜆(𝐺) ·

vol(𝑆𝐾 (𝑡)) · vol 𝑆 (𝑡) .

Since the median opinion is at most 𝐾 − 2, we have vol 𝑆 (𝑡) ≥ 𝑚. Furthermore, by assumption vol(𝑆𝐾 (𝑡)) ≥ 𝜂 (𝑡) ≥ 16 · 2𝜆(𝐺) 2𝑚 ≥ 16 · 𝜆(𝐺) 2 vol 𝑆 (𝑡) . −2 𝐾 (𝑡 ) ) Therefore, vol 𝑆 (𝑡) ≤ 𝜆 (𝐺 ) vol(𝑆 . Using these upper and lower bound in the expander mixing lemma, we get 16 √︄ vol(𝑆𝐾 (𝑡)) 𝜆(𝐺) −2 vol(𝑆𝐾 (𝑡)) 2 − 𝜆(𝐺) |𝐸 (𝑆𝐾 (𝑡), 𝑆 (𝑡))| ≥ 2 16 vol(𝑆𝐾 (𝑡)) vol(𝑆𝐾 (𝑡)) vol(𝑆𝐾 (𝑡)) = − = 2 4 4 As Φ(𝐺) is at most 1, index 𝐾 − 1 is good. 𝑛 log 𝑛 Now consider the process over an interval of length 𝑇 ∈ 𝑂 𝜆(𝐺) 2 · 𝑛 2 + Φ2 (𝐺 ) . If at some time during this interval

we enter Case 1, by the argument above, an extreme opinion disappears within an additional 𝑂 (𝜆(𝐺) 2 · 𝑛 2 ) ≤ 𝑇 steps with probability at least 1/2. Otherwise, Case 2 holds throughout the entire interval, and hence in each step either index 𝐾 − 1 or 1 (or both) are good. In particular, one of them must be good for at least 𝑇 /2 steps or vanish. In this case, by 𝑛 log 𝑛

Lemma 4.6, either 𝐾 or 0 disappears within 𝑂 ( Φ2 (𝐺 ) ) ≤ 𝑇 steps , again with probability at least 1/2. Therefore, starting from any configuration with discrepancy 𝐾, within at most 2𝑇 steps, discrepancy decreases by one with probability 12 . Finally, as 𝜆 ∈ 𝑜 (1) implies Φ(𝐺) ∈ 𝑜 (1) by Lemma 6.1, the proposition follows.

□

Discrete Incremental Voting 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. Lemma 6.1 (Cheeger ineqality [26, 27]). Let 𝐺 = (𝑉 , 𝐸) be a connected, undirected graph with random-walk matrix 𝑃. Then Φ(𝐺 ) 2 2

≤ 1 − 𝜆2 (𝑃) ≤ 2Φ(𝐺).

Beyond expansion, the second eigenvalue controls how evenly edges are distributed between vertex sets, formalized by the following lemma. Lemma 6.2 (Expander Mixing Lemma [7, 24]). Let 𝐺 = (𝑉 , 𝐸) be a connected, undirected graph with random-walk matrix 𝑃. Then for all 𝑆,𝑇 ⊆ 𝑉 , √︁ )vol(𝑇 ) 𝐸 (𝑆,𝑇 ) − vol(𝑆2𝑚 ≤ 𝜆2 (𝑃) vol(𝑆) vol(𝑇 ), where 𝐸 (𝑆,𝑇 ) denotes the number of edges between 𝑆 and 𝑇 (counting edges in 𝑆 ∩ 𝑇 twice). If 𝛾 (𝐺) 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 (F𝑡 )𝑡 ≥0 be a filtration, i.e., all available randomness until step 𝑡. A stochastic process (𝑌𝑡 )𝑡 ≥0 adapted to (F𝑡 ) imartingale if E [𝑌𝑡 +1 | F𝑡 ] = 𝑌𝑡 for all 𝑡 ≥ 0, and a supermartingale if E [𝑌𝑡 +1 | F𝑡 ] ≤ 𝑌𝑡 for all 𝑡 ≥ 0. A random variable 𝜏 is a stopping time with respect to (F𝑡 ) if the event {𝜏 = 𝑡 } is measurable with respect to F𝑡 for all 𝑡. We will make use of the following well-known tool; see, for example, [20]. Theorem 6.3 (Doob’s Optional Stopping Theorem). Let (𝑌𝑡 )𝑡 ≥0 be a supermartingale and let 𝜏 be a stopping time such that 𝜏 ≤ 𝑐 almost surely for some constant 𝑐. Then E [𝑌𝜏 ] ≤ E [𝑌0 ]. We will also use concentration bounds for martingales with bounded increments, namely the following well-known bound; see, for example, [6]. Lemma 6.4 (Azuma–Hoeffding ineqality). Let (𝑋𝑡 )𝑇𝑡=0 be a martingale with respect to a filtration (F𝑡 )𝑇𝑡=0 . Assume that |𝑋𝑡 − 𝑋𝑡 −1 | ≤ 𝑐 almost surely for all 𝑡 ≥ 1. Then for all 𝜆 > 0, 2 Pr [|𝑋𝑇 − 𝑋 0 | ≥ 𝜆] ≤ 2 exp − 2𝑇𝜆 𝑐 2 . We state the tail bounds of Janson [25] for sums of independent geometric random variables. Theorem 6.5. Let 𝑋 1, . . . , 𝑋𝑛 be independent random variables with 𝑋𝑖 ∼ 𝐺𝑒𝑜 (𝑝). and define 𝑋 := Í 𝜇 := E[𝑋 ] = 𝑛𝑖=1 𝑝1 and every 𝜆 ≥ 1, Pr [𝑋 ≥ 𝜆𝜇] ≤ exp − 𝑝𝜇 (𝜆 − 1 − ln 𝜆) .

Í𝑛

𝑖=1 𝑋𝑖 For

Discrete Incremental Voting 7

Omitted Proofs

7.1

Proof of Claim 1

For two values 𝑥𝑖 and 𝑥 𝑗 define    0     𝜄 (𝑖, 𝑗) := −1     1 

if 𝑥𝑖 = 𝑥 𝑗 if 𝑥𝑖 > 𝑥 𝑗 if 𝑥𝑖 < 𝑥 𝑗

According to Protocol 1, at a given step a random directed edge 𝑒 = (𝑢, 𝑣) is chosen as follows. Firstly a vertex 𝑢 is chosen uniformly at random, and then a neighbour 𝑣 ∈ 𝑁𝑢 is chosen with probability 1/𝑑𝑢 . Thus for a given vertex 𝑖 ∈ 𝑉, ∑︁ E 𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) 2 = Pr [𝑢 ≠ 𝑖] · 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 + Pr [𝑢 = 𝑖] · 𝑑𝑖 · Pr [𝑣 = 𝑗 | 𝑢 = 𝑖] · E 𝑓 (𝑋𝑖 (𝑡 + 1))) 2 | (𝑢, 𝑣) = (𝑖, 𝑗) . 𝑗 ∈𝑁𝑖

As the vertices 𝑢 and 𝑣 are random variables, for a given vertex 𝑖, the probability that 𝑢 = 𝑖 is 1/𝑛, and the probability that 𝑢 ≠ 𝑖 is (1 − 1/𝑛). Further, Pr [𝑣 = 𝑗 | 𝑢 = 𝑖] = 𝑑1𝑖 . Thus, as 𝑓 (𝑋𝑖 (𝑡 + 1)) = 0 if 𝑖 ∉ 𝑆, and 𝑓 (𝑋𝑖 (𝑡 + 1)) = 𝑓 (𝑥𝑖 +𝜄 (𝑖, 𝑗)) if 𝑖 ∈ 𝑆 and (𝑢, 𝑣) = (𝑖, 𝑗), " # ∑︁ 1 ∑︁ 1 ∑︁ 2 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 + 𝑑𝑖 · 𝑑1𝑖 · 𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 E 𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) = 1 − 𝑛 𝑖 ∈𝑉 𝑛 𝑖 ∈𝑉 (𝑖,𝑗 ) ∈𝐸 𝑥𝑖 ≥𝑘

1 ∑︁ 1 ∑︁ 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 . = 1− 𝑛 𝑖 ∈𝑉 𝑛

(17)

(𝑖,𝑗 ) ∈𝐸 𝑥𝑖 ≥𝑘

| In the following, we focus on the sum (∗). Note that the potential

{z (∗)

}

𝑑𝑖 𝑓 (𝑋𝑖 (𝑡 + 1)) 2 can only differ from

𝑑𝑖 𝑓 (𝑥𝑖 ) 2

if at least one endpoint of the selected directed edge is in 𝑆 +1 = {𝑟 ∈ 𝑉 | 𝑥𝑟 ≥ 𝑘 + 1}. Otherwise, if neither value is above 𝑘, the updated value cannot be above 𝑘. Further, noting that 𝜄 (𝑖, 𝑗) = −𝜄 ( 𝑗, 𝑖), we can rearrange this sum as follows, to introduce the constraint 𝑥𝑖 ≥ 𝑥 𝑗 : ∑︁ (∗) = 𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 = (𝑖,𝑗 ) ∈𝐸 𝑥𝑖 ≥𝑘

∑︁

𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 + 𝑓 (𝑥 𝑗 − 𝜄 (𝑖, 𝑗)) 2 .

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑥 𝑗

Consider a single summand in the right-hand sum above, i.e., the expected change along a single edge {𝑖, 𝑗 }. Let 𝑖 ∈ 𝑆 +1 be a node with 𝑥𝑖 > 𝑘 and 𝑗 ∈ 𝑉 be a node with 𝑥 𝑗 ≤ 𝑥𝑖 . We show that 𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 + 𝑓 (𝑥 𝑗 − 𝜄 (𝑖, 𝑗)) 2 ≤ 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) + 1 |𝑥𝑖 −𝑥 𝑗 |=1 .

(18)

To prove this inequality, we distinguish between the following three cases. Case 1: 𝑥𝑖 > 𝑥 𝑗 + 1. In this case, we have 𝜄 (𝑖, 𝑗) = −1, i.e., 𝑥𝑖 will decrease and 𝑥 𝑗 will increase. Our assumption that 𝑥𝑖 > 𝑘 implies that 𝑓 (𝑥𝑖 ) is at least one, so we have 𝑓 (𝑥𝑖 − 1) 2 := (𝑥𝑖 − 1) − 𝑘

= (𝑥𝑖 − 𝑘) − 1

= (𝑓 (𝑥𝑖 ) − 1) 2 = 𝑓 (𝑥𝑖 ) 2 − 2𝑓 (𝑥𝑖 ) + 1

Discrete Incremental Voting

Now, we distinguish between two subcases: • If 𝑥 𝑗 < 𝑘, it holds 𝑓 (𝑥 𝑗 ) = 𝑓 (𝑥 𝑗 + 1) = 0. Therefore 𝑓 (𝑥 𝑗 + 1) 2 = 0 = 𝑓 (𝑥 𝑗 ) 2 + 𝑓 (𝑥 𝑗 ). Together with the other bounds, this gives: 𝑓 (𝑥𝑖 + 𝜄 (𝑖, 𝑗)) 2 + 𝑓 (𝑥 𝑗 − 𝜄 (𝑖, 𝑗)) 2 = 𝑓 (𝑥𝑖 − 1) 2 + 𝑓 (𝑥 𝑗 + 1) 2 = 𝑓 (𝑥𝑖 ) 2 − 2𝑓 (𝑥𝑖 ) + 1 + 𝑓 (𝑥 𝑗 ) 2 + 𝑓 (𝑥 𝑗 ) ≤ 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )). Here, the last inequality follows from 𝑓 (𝑥𝑖 ) ≥ 1 (as 𝑥𝑖 > 𝑘). • Otherwise, if 𝑥 𝑗 ≥ 𝑘, it holds that: 𝑓 (𝑥 𝑗 + 1) 2 = (𝑥 𝑗 + 1) − 𝑘

= (𝑥 𝑗 − 𝑘) + 1

= (𝑓 (𝑥 𝑗 ) + 1) 2 = 𝑓 (𝑥 𝑗 ) 2 + 2𝑓 (𝑥 𝑗 ) + 1 Thus, 𝑓 (𝑥𝑖 − 1) 2 + 𝑓 (𝑥 𝑗 + 1) 2 = 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − 2𝑓 (𝑥𝑖 ) + 2𝑓 (𝑥 𝑗 ) + 2 As 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) = 𝑥𝑖 − 𝑥 𝑗 ≥ 2, this simplifies to 𝑓 (𝑥𝑖 − 1) 2 + 𝑓 (𝑥 𝑗 + 1) 2 ≤𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) as claimed. Case 2: 𝑥𝑖 = 𝑥 𝑗 + 1 (the case with 1 |𝑥𝑖 −𝑥 𝑗 |=1 = 1). In this case, we also have 𝜄 (𝑖, 𝑗) = −1. However, as the difference is exactly one, the process (locally) reduces to classical voting. We note that, since 𝑥𝑖 − 1 = 𝑥 𝑗 it holds: 𝑓 (𝑥𝑖 − 1) = 𝑓 (𝑥 𝑗 ) 𝑓 (𝑥 𝑗 + 1) = 𝑓 (𝑥𝑖 ) Therefore, the potential remains unchanged: 𝑓 (𝑥𝑖 − 1) 2 + 𝑓 (𝑥 𝑗 + 1) 2 = 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 By noting that 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) = 1, we get: 𝑓 (𝑥𝑖 − 1) 2 + 𝑓 (𝑥 𝑗 + 1) 2 = 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) + 1. Case 3: 𝑥𝑖 = 𝑥 𝑗 . In this case, there is no change as neither node will change its opinion because they already agree, i.e., we have 𝜄 (𝑖, 𝑗) = 0. Thus, as 𝑓 (𝑥𝑖 ) = 𝑓 (𝑥 𝑗 ), 𝑓 (𝑥𝑖 − 0) 2 + 𝑓 (𝑥 𝑗 + 0) 2 = 𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 −(𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )). Inequality (18) implies the following: ∑︁ (∗) ≤ (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

𝑓 (𝑥𝑖 ) 2 + 𝑓 (𝑥 𝑗 ) 2 − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) + 1 |𝑥𝑖 −𝑥 𝑗 |=1

Discrete Incremental Voting

22 =

∑︁

𝑑𝑖 𝑓 (𝑥𝑖 ) 2 −

𝑖 ∈𝑉

𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 |𝑥𝑖 −𝑥 𝑗 |=1 .

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

Referring back to (17), we see that " # ∑︁ 1 ∑︁ 2 E 𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) ≤ 1 − 𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 𝑛 𝑖 ∈𝑉 𝑖 ∈𝑉

∑︁ (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

« =

∑︁ 𝑖 ∈𝑉

𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2 −

The above inequality is equivalent to (9).

∑︁ (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

ª® 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 |𝑥𝑖 −𝑥 𝑗 |=1 ®® ® ¬

ª® 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 |𝑥𝑖 −𝑥 𝑗 =1| ®® ® ¬

Discrete Incremental Voting 7.2

Detailed Proof of Claim 3

First, recall that h

E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® := E

∑︁

𝑑𝑖 · 𝑓 (𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® − 2

𝑖 ∈𝑉

1 ≤− 𝑛

∑︁

𝑑𝑖 · 𝑓 (𝑥𝑖 ) 2

𝑖 ∈𝑉

∑︁

𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 { |𝑥𝑖 −𝑥 𝑗 =1| }

[ by Equation (9) ]

(19)

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

© ª ∑︁ ∑︁ ® 1 𝑑𝑖 · 𝑓 (𝑥𝑖 ) − 1 { |𝑥𝑖 −𝑥 𝑗 =1| } ®® [ by Equation (10), as vol(𝑆) ≤ 𝑚 ] ≤ − Φ(𝐺) 𝑛 ® 𝑖 ∈𝑉 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗 « ¬ (20) Recall that 𝐸𝑆+1 := {(𝑖, 𝑗) ∈ 𝐸 | 𝑖 ∈ 𝑆 +1 }. To prove Equation 14 we now use Equation 19 and Equation 20. We distinguish Í between two cases based on the value of 𝑖 ∈𝑉 𝑑𝑖 · 𝑓 (𝑥𝑖 ). Í • Case 1: Assume 𝑖 ∈𝑉 𝑑𝑖 · 𝑓 (𝑥) ≥ (4/3)vol(𝑆 +1 )/Φ(𝐺). Here, we use Equation 20 to obtain: © ª h i ∑︁ ∑︁ ® 1 ® Φ(𝐺) 𝑑 𝑓 (𝑥 ) − E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) 1 𝑖 𝑖 { |𝑥 −𝑥 |=1} 𝑖 𝑗 ® 𝑛 ® 𝑖 ∈𝑉 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗 « ∑︁ ¬

𝑑𝑖 · 𝑓 (𝑥) ≥ (4/3)vol(𝑆 +1 )/Φ(𝐺))

(using that

𝑖 ∈𝑉

© ª ∑︁ ® 3Φ(𝐺) (4/3)vol(𝑆 +1 ) 1 Φ(𝐺) ∑︁ 𝑑𝑖 𝑓 (𝑥𝑖 ) + · − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® ≤ (−1) 𝑛 4 𝑖 ∈𝑉 4 Φ(𝐺) ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥 ≥𝑥 𝑖 𝑗 « ¬ © ª ∑︁ ® 1 Φ(𝐺) ∑︁ ≤ (−1) 𝑑𝑖 𝑓 (𝑥𝑖 ) + vol(𝑆 +1 ) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® 𝑛 4 𝑖 ∈𝑉 ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥 ≥𝑥 𝑖 𝑗 « ¬ Í Now, we focus on the last summand, namely (𝑖,𝑗 ) ∈𝐸𝑆+1 1 { |𝑥𝑖 −𝑥 𝑗 |=1} . First, we pessimistically assume that the 𝑥𝑖 ≥𝑥 𝑗

difference along all edges with an endpoint in 𝑆 +1 is exactly 1. Then, the formula simplifies to © ª h i ∑︁ ® 1 Φ(𝐺) ∑︁ E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) 1®® 𝑑𝑖 𝑓 (𝑥𝑖 ) + vol(𝑆 +1 ) − 𝑛 4 𝑖 ∈𝑉 (𝑖,𝑗 ) ∈𝐸𝑆 +1 ® 𝑥𝑖 ≥𝑥 𝑗 « ¬ Í Í We continue by bounding (𝑖,𝑗 ) ∈𝐸𝑆+1 1 by vol(𝑆 +1 ). Note that the sum (𝑖,𝑗 ) ∈𝐸𝑆+1 1 counts each edge adjacent to a 𝑥𝑖 ≥𝑥 𝑗 𝑥𝑖 ≥𝑥 𝑗 Í node in 𝑆 +1 exactly once. On the other hand, in vol(𝑆 +1 ) := 𝑖 ∈𝑆+1 𝑑𝑖 , each edge is counted once for each endpoint in 𝑆 +1 . This means, each edge {𝑖, 𝑗 } that is within 𝑆 +1 , i.e., between 𝑖 ∈ 𝑆 +1 and 𝑗 ∈ 𝑆 +1 , is counted twice and each edge that with precisely one endpoint in 𝑆, i.e, between 𝑖 ∈ 𝑆 and 𝑗 ∉ 𝑆, is counted once. Thus, vol(𝑆 +1 ) is always

Discrete Incremental Voting

bigger than

(𝑖,𝑗 ) ∈𝐸𝑆 +1 1. Therefore, 𝑥𝑖 ≥𝑥 𝑗

∑︁ 1 Φ(𝐺) ∑︁ E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) 𝑑𝑖 𝑓 (𝑥𝑖 ) + vol(𝑆 +1 ) − 𝑑𝑖 𝑛 2 𝑖 ∈𝑉 𝑖 ∈𝑆 h

! 1 Φ(𝐺) ∑︁ 𝑑𝑖 𝑓 (𝑥𝑖 ) + vol(𝑆 +1 ) − vol(𝑆 +1 ) ≤ (−1) 𝑛 4 𝑖 ∈𝑉 ! ! 1 Φ(𝐺) ∑︁ 1 Φ2 ∑︁ ≤ (−1) 𝑑𝑖 𝑓 (𝑥𝑖 ) ≤ (−1) 𝑑𝑖 𝑓 (𝑥𝑖 ) . 𝑛 4 𝑖 ∈𝑉 𝑛 4 𝑖 ∈𝑉 This proves the fist case. Í • Case 2: Assume 𝑖 ∈𝑉 𝑑𝑖 · 𝑓 (𝑥) < (4/3)vol(𝑆 +1 ) /Φ(𝐺). In this case, use Equation 19 and bound the term in two steps. First, we let the internal edges between nodes in 𝑆 +1 cancel each other out. To this end, we divide the summand into two groups: The edges within 𝑆 +1 where both endpoints have a value larger than 𝑘 and the the edges that leave 𝑆 +1 and end in 𝑆 \ 𝑆 +1 or 𝑆. Note that we can ignore edges between 𝑆 \ 𝑆 +1 and 𝑆 as both endpoints are at most 𝑘 as they do not contribute to the sum. Further, note that both endpoints of an edge (𝑖, 𝑗) ∈ 𝐸𝑆+1 are in 𝑆 +1 if and only if 𝑥𝑖 , 𝑥 𝑗 > 𝑘. In light of these observations, it holds: h i 1 ∑︁ E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® = − 𝑛

𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 { |𝑥𝑖 −𝑥 𝑗 =1| }

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 ≥𝑥 𝑗

ª ® 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) + 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) ®® ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘 « 𝑥𝑖 ≥𝑥 𝑗 >𝑘 ¬ ∑︁

∑︁

© ª ∑︁ ® 1 ∑︁ 1 { |𝑥𝑖 −𝑥 𝑗 |=1} + 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® (+1) 𝑛 ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘 « 𝑥𝑖 ≥𝑥 𝑗 >𝑘 ¬ © ª ® 1 ∑︁ ≤ (−1) (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® 𝑛 ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 « 𝑥𝑖 ≥𝑥 𝑗 >𝑘 ¬ © ª ® 1 ∑︁ − (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® 𝑛 ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥 >𝑘,𝑥 ≤𝑘 𝑖 𝑗 « ¬

(21)

(22)

Now we bound Equation 21 and Equation 22 separately. We begin with Equation 21: Note that whenever it holds |𝑥𝑖 − 𝑥 𝑗 | = 1 the difference 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) is also exactly one as both 𝑖 and 𝑗 are larger than 𝑘. Formally, 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) = (𝑥𝑖 − 𝑘) − (𝑥 𝑗 − 𝑘) = 𝑥𝑖 − 𝑥 𝑗 ≥ 1 |𝑥𝑖 −𝑥 𝑗 |=1

Discrete Incremental Voting

Therefore, the terms cancel each other and we get: © 1 (21) = − 𝑛

∑︁

ª ® (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 « 𝑥𝑖 ≥𝑥 𝑗 >𝑘 ¬ ª ® 1 { |𝑥𝑖 −𝑥 𝑗 |=1} − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ®® = 0. ® (𝑖,𝑗 ) ∈𝐸𝑆 +1 « 𝑥𝑖 ≥𝑥 𝑗 >𝑘 ¬

Thus, we only need to consider Equation 22 and analyze: h i 1 ∑︁ E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) 𝑛

𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1}

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘

Next, we exploit that the endpoints of all remaining edges are between 𝑆 +1 and 𝑉 \ 𝑆 have a difference of at least one. Since one endpoint is larger than 𝑘, for all (𝑖, 𝑗) ∈ 𝐸𝑆+1 with 𝑥𝑖 > 𝑘 and 𝑥 𝑗 ≤ 𝑘, we have: 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 ) = (𝑥𝑖 − 𝑘) − 0 = 𝑥𝑖 − 𝑘 ≥ 1.

(23)

Recall that we defined O(𝑆 +1 ) := {(𝑖, 𝑗) ∈ 𝐸 | 𝑖 ∈ 𝑆 +1, 𝑗 ∈ 𝑉 \ 𝑆 +1 }. Together with this definition, we get: h i 1 ∑︁ E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} 𝑛 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘

As (𝑓 (𝑥𝑖 ) − 𝑓 (𝑥 𝑗 )) ≥ 1, we get 1 ∑︁ 1 − 1 { |𝑥𝑖 −𝑥 𝑗 |=1} ≤ (−1) 𝑛 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘

1 1 = (−1) O(𝑆) + 𝑛 𝑛

∑︁

1 { |𝑥𝑖 −𝑥 𝑗 |=1}

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘

As O(𝑆 +1 ) ≥ Φ(𝐺) · vol(𝑆 +1 ) by definition, 1 1 ∑︁ = (−1) Φ(𝐺) · vol(𝑆 +1 ) + 1 { |𝑥𝑖 −𝑥 𝑗 |=1} 𝑛 𝑛 (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 ≤𝑘

Now, we further divide the edges and distinguish between edges that start in 𝑆 +1 and end in 𝑆 \ 𝑆 +1 and edges that start in 𝑆 +1 and end in 𝑆. By definition, all edges that start in 𝑆 +1 and end in 𝑆 have a difference of at least 2. In addition, we pessimistically assume that all that start in 𝑆 +1 and end in 𝑆 have a difference of precisely 1 (although it theoretically can be larger, too). h i 1 1 E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) Φ(𝐺) · vol(𝑆 +1 ) + 𝑛 𝑛

∑︁ (𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 =𝑘

1 { |𝑥𝑖 −𝑥 𝑗 |=1}

Discrete Incremental Voting

26 1 1 ≤ (−1) Φ(𝐺) · vol(𝑆 +1 ) + 𝑛 𝑛

∑︁

(𝑖,𝑗 ) ∈𝐸𝑆 +1 𝑥𝑖 >𝑘,𝑥 𝑗 =𝑘

1 1 = (−1) Φ(𝐺) · vol(𝑆 +1 ) + |𝐸 (𝑆 +1, 𝑆)| 𝑛 𝑛 1 13 Φ(𝐺)vol(𝑆 +1 ) ≤ (−1) Φ(𝐺) · vol(𝑆 +1 ) + 𝑛 𝑛4 Finally, we get ! h i ∑︁ 1 1 1 1 2 E Δ(𝑋𝑖 (𝑡 + 1)) | 𝑋® (𝑡) = 𝑥® ≤ (−1) Φ(𝐺)vol(𝑆 +1 ) ≤ (−1) Φ (𝐺) 𝑑𝑖 𝑓 (𝑥𝑖 ) . 𝑛 2 𝑛 4 𝑖 ∈𝑉 This proves the second case. Together, the two cases imply the claim. 7.3

Proof of Lemma 4.6

We begin with some definitions and assumptions. Let F (𝑡) be the natural filtration of the process that contains all configurations (and thus all random choices) up to step 𝑡. Note that 𝜏𝑘 (𝑡) is completely determined by F (𝑡). Further define the event 𝐵𝑘 (𝑇 ) := {Ψ𝑘(+) (𝑋® (𝑇 )) > 0} ∩ {𝜏𝑘 (𝑇 ) ≥ 𝑇 /4}. We define the following auxiliary random process  (+) ®   if 𝑡 = 0,   Ψ𝑘 (𝑋 (0))  −𝜏𝑘 (𝑡 −1) 𝜓 (𝑡) := 2   Ψ (+) (𝑋® (𝑡)) · 1 − Φ(𝐺) if 𝑡 > 0.   𝑘 5(𝐾 − 𝑘)𝑛  Note that 𝜓 (𝑡) is measurable with respect to the filtration F (𝑡). First, we show that (𝜓 (𝑡))𝑡 ≥0 is a supermartingale, i.e., for all 𝑡 ≥ 0, E [𝜓 (𝑡 + 1) | F (𝑡)] ≤ 𝜓 (𝑡). This follows by a simple case distinction. Fix 𝑡 ≥ 0 and condition on F (𝑡). For easier notation, define E𝑡 [·] := E [· | F (𝑡) = (𝑥® (𝑡), . . . , 𝑥® (0))]. Now distinguish between the following cases: (1) If 𝑘 is good in step 𝑡, then " E𝑡 [𝜓 (𝑡 + 1)] = E𝑡 Ψ𝑘(+) (𝑋® (𝑡 + 1)) ·

Φ(𝐺) 2 1− 5(𝐾 − 𝑘)𝑛

−𝜏𝑘 (𝑡 ) # .

−𝜏𝑘 (𝑡 ) Φ(𝐺 ) 2 The factor 1 − 5(𝐾 is completely determined by F (𝑡) and can be pulled out of the expectation, so −𝑘 )𝑛 h

E𝑡 [𝜓 (𝑡 + 1)] = E𝑡 Ψ𝑘(+) (𝑋® (𝑡 + 1))

i · 1−

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝜏𝑘 (𝑡 ) .

Discrete Incremental Voting

As 𝑘 is good in step 𝑡, by Lemma 4.4, h i E𝑡 Ψ𝑘(+) (𝑋® (𝑡 + 1)) ≤ Ψ𝑘(+) (𝑥® (𝑡)) · 1 −

Φ(𝐺) 2 . 5(𝐾 − 𝑘)𝑛

Hence, −𝜏𝑘 (𝑡 ) Φ(𝐺) 2 Φ(𝐺) 2 · 1− 1− 5(𝐾 − 𝑘)𝑛 5(𝐾 − 𝑘)𝑛 −𝜏𝑘 (𝑡 )+1 2 Φ(𝐺) . = Ψ𝑘(+) (𝑥® (𝑡)) · 1 − 5(𝐾 − 𝑘)𝑛

E𝑡 [𝜓 (𝑡 + 1)] ≤ Ψ𝑘(+) (𝑥® (𝑡)) ·

Since 𝑘 is good in step 𝑡, we have 𝜏𝑘 (𝑡) = 𝜏𝑘 (𝑡 − 1) + 1, and thus −𝜏𝑘 (𝑡) + 1 = −𝜏𝑘 (𝑡 − 1). Therefore, −𝜏𝑘 (𝑡 −1) Φ(𝐺) 2 E𝑡 [𝜓 (𝑡 + 1)] ≤ Ψ𝑘(+) (𝑥® (𝑡)) · 1 − = 𝜓 (𝑡). 5(𝐾 − 𝑘)𝑛 (2) If 𝑘 is not good in step 𝑡, then 𝜏𝑘 (𝑡) = 𝜏𝑘 (𝑡 − 1) and Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝜏𝑘 (𝑡 )

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛 −𝜏𝑘 (𝑡 −1) 2

−𝜏𝑘 (𝑡 −1)

h i E𝑡 [𝜓 (𝑡 + 1)] = E𝑡 Ψ𝑘(+) (𝑋® (𝑡 + 1)) · 1 − h i = E𝑡 Ψ𝑘(+) (𝑋® (𝑡 + 1)) · 1 − ≤ Ψ𝑘(+) (𝑥® (𝑡)) · 1 −

Φ(𝐺) 5(𝐾 − 𝑘)𝑛

= 𝜓 (𝑡),

where the last inequality follows from the first statement of Lemma 4.4. This shows that (𝜓 (𝑡))𝑡 ≥0 is a supermartingale. Now define the stopping time 𝑇 ′ := min {𝑇 , inf {𝑡 ≥ 0 : 𝜏𝑘 (𝑡) ≥ 𝑇 /4 + 1}} . Since 𝑇 ′ ≤ 𝑇 , Doob’s optional stopping theorem (cf. Theorem 6.3) yields 𝜓 (0) ≥ E [𝜓 (𝑇 ′ )]. On the event 𝐵𝑘 (𝑇 ), we have 𝜏𝑘 (𝑇 ′ ) ≥ 𝑇 /4 + 1, and thus −𝜏𝑘 (𝑇 ′ −1) −𝑇 /4 Φ(𝐺) 2 Φ(𝐺) 2 (+) ® ′ ′ ≥ 1− . 𝜓 (𝑇 ) = Ψ𝑘 (𝑋 (𝑇 )) · 1 − 5(𝐾 − 𝑘)𝑛 5(𝐾 − 𝑘)𝑛 Therefore, E [𝜓 (𝑇 ′ )] ≥ Pr [𝐵𝑘 (𝑇 )] · 1 −

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝑇 /4 .

Since 𝜓 (0) = Ψ𝑘(+) (𝑥® (0)) ≤ 𝐾 2𝑛, we obtain 𝐾 2𝑛 ≥ Pr [𝐵𝑘 (𝑇 )] · 1 −

Φ(𝐺) 2 5(𝐾 − 𝑘)𝑛

−𝑇 /4 .

Discrete Incremental Voting

Solving for Pr [𝐵𝑘 (𝑇 )] and using 𝑇 = 20𝑐

(𝐾 −𝑘 )𝑛 log(𝐾𝑛) gives Φ(𝐺 ) 2

Φ(𝐺) 2 Pr [𝐵𝑘 (𝑇 )] ≤ 𝐾 𝑛 1 − 5(𝐾 − 𝑘)𝑛

𝑇 /4

Φ(𝐺) 2 ≤𝐾 𝑛 1− 5(𝐾 − 𝑘)𝑛

5𝑐 𝐾𝑛 log(𝐾𝑛) 2

7.4

Φ(𝐺 )

≤

1 . (𝐾𝑛)𝑐

Proof of Lemma 5.3

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 𝜂 (𝑡) = min{vol(𝑆 0 (𝑡)) , vol(𝑆𝐾 (𝑡))}. Further, for simplity denote 𝑆 (𝑡) to the set archieving vol(𝑆 (𝑡)) = 𝜂 (𝑡) and 𝑆 (𝑡) = 𝑉 \ 𝑆 (𝑡). Note that once 𝜂 (𝑡) = 0, one opinion √︁ must have vanished from the system. We study the process 𝜂 (𝑡), in particular h√︁ i E 𝜂 (𝑡) | 𝑆 (0) = 𝑆 . √ Note that both (𝑆 0 (𝑡))𝑡 ≥0 and (𝑆𝐾 (𝑡))𝑡 ≥0 are martingales and · is concave. Therefore, by Jensen’s inequality, (𝜂 (𝑡))𝑡 ≥0 is a supermartingale. Further, let 𝑍 (𝑡) be the change in the measure of 𝑆 (𝑡) in step 𝑡, i.e. 𝑍 (𝑡) := vol(𝑆 (𝑡 + 1)) − vol(𝑆 (𝑡)) . Note that 𝜂 (𝑡 + 1) = min{vol(𝑆 (𝑡)) + 𝑍 (𝑡), vol(𝑆 ′ (𝑡)) − 𝑍 (𝑡)}. Further, define 𝜌𝑡 = 𝜌 (𝑆 (𝑡)) = 21vol(𝑆 (𝑡 ) ) ≤vol(𝑆 ′ (𝑡 ) ) − 1, so 𝜌𝑡 ∈ {−1, 1}. Then 𝜂 (𝑡 + 1) ≤ 𝜂 (𝑡) + 𝜌𝑡 𝑍 (𝑡). Finally, define Υ(𝑆) := E 𝑍 (𝑡) 2 1𝜌𝑡 𝑍 (𝑡 ) <0 | 𝑆 (𝑡) = 𝑆 . To bound Υ(𝑆) let 𝑋𝑖 𝑗 be the indicator that 𝑖 adopts 𝑗’s opinion. Note that 𝜌𝑡 𝑍 (𝑡) < 0 exactly when a vertex from the current minority switches to the majority (i.e. the minority decreases). If 𝑖 ∈ 𝑆 (𝑡) switches, the measure drops by 𝑑𝑖 , hence ∑︁

Υ(𝑆) =

Pr 𝑋𝑖 𝑗 (𝑑𝑖 ) 2 =

(𝑖,𝑗 ) ∈𝐸 (𝑆,𝑆 )

1 (𝑑𝑖 ) 2 𝑛𝑑𝑖

(𝑖,𝑗 ) ∈𝐸 (𝑆,𝑆 )

𝑑𝑖 𝑑 min ≥ |𝐸 (𝑆, 𝑆)|. 𝑛 𝑛

∑︁

(𝑖,𝑗 ) ∈𝐸 (𝑆,𝑆 )

Using |𝐸 (𝑆, 𝑆)| ≥ Φ(𝐺) vol(𝑆) we obtain Υ(𝑆) ≥

𝑑 min Φ(𝐺) vol(𝑆) 𝑛

1 Claim 4. Let Υ := 8𝑛 · 𝑑 min · Φ(𝐺). Then, for all sets 𝑆 ⊆ 𝑉 , i √︁ h√︁ 1 E 𝜂 (𝑡 + 1) | 𝑆 0 = 𝑆 ≤ vol(𝑆) − Υ · √︁ . 4 vol(𝑆)

Discrete Incremental Voting

Proof. Since 𝑍 (𝑡) depends only on 𝑆 (𝑡), we first show that for fixed 𝑆 (𝑡) = 𝑆, h√︁ i √︁ 1 E 𝜂 (𝑡 + 1) | 𝑆 (𝑡) = 𝑆 ≤ vol(𝑆) − Υ · √︁ . vol(𝑆) Let 1+ := 1𝜌𝑡 𝑍 (𝑡 ) ≥0 and 1− := 1𝜌𝑡 𝑍 (𝑡 ) <0 . Taking expectations, h√︁ i h√︁ i E 𝜂 (𝑡 + 1) | 𝑆 (𝑡) = 𝑆 = E 𝜂 (𝑆) + 𝜌𝑡 𝑍 (𝑡) | 𝑆 (𝑡) = 𝑆 √︃ √︃ √︁ √︁ 𝜌 𝑍 (𝑡 ) 𝜌 𝑍 (𝑡 ) = 𝜂 (𝑆) E 1 + 𝜂𝑡 (𝑆 ) 1+ | 𝑆 (𝑡) = 𝑆 + 𝜂 (𝑆) E 1 + 𝜂𝑡 (𝑆 ) 1− | 𝑆 (𝑡) = 𝑆 .

(24)

Let 𝑥 = 𝜌𝑡 𝑍 (𝑡)/𝜂 (𝑆). Then 𝑥 ≥ −1. For 𝑥 ≥ −1 we use the bounds √ 1 + 𝑥 ≤ 1 + 𝑥,

(25)

√ 𝑥2 1+𝑥 ≤ 1+𝑥 − 8

for 𝑥 ∈ [−1, 0].

(26)

Applying (25) to the 1+ term and (26) to the 1− term in (24), and using that vol(𝑆 (𝑡)) is a supermartingale so E [𝑍 (𝑡) | 𝑆 (𝑡) = 𝑆] ≤ 0, we obtain h√︁ i √︁ √︁ (𝜌𝑡 𝑍 (𝑡)) 2 − E 𝜂 (𝑡 + 1) | 𝑆 (𝑡) = 𝑆 ≤ 𝜂 (𝑆) − 𝜂 (𝑆) E 1 | 𝑆 (𝑡) = 𝑆 8𝜂 (𝑆) 2 2 √︁ 𝑍 (𝑡) 1 | 𝑆 (𝑡) = 𝑆 ≤ 𝜂 (𝑆) − E {𝜌𝑡 𝑍 (𝑡 ) <0} 8𝜂 (𝑆) 3/2 √︁ √︁ Υ(𝑆) 𝑑 min Φ(𝐺) vol(𝑆) = 𝜂 (𝑆) − ≤ 𝜂 (𝑆) − 3/2 8 𝜂 (𝑆) 8𝑛 𝜂 (𝑆) 3/2 √︁ 1 . ≤ 𝜂 (𝑆) − Υ · √︁ 𝜂 (𝑆) In the following, we take total expectation over 𝑆 (𝑡) and apply Jensen to obtain the stated claim: ! h√︁ i ∑︁ √︁ 1 E 𝜂 (𝑡 + 1) | 𝑆 (0) = 𝑆 = Pr [𝑆 (𝑡) = 𝑆 ′ | 𝑆 (0) = 𝑆] ( 𝜂 (𝑆) − Υ · √︁ ) 𝜂 (𝑆) 𝑆 ′ ⊂𝑉 vol(𝑆 ) >0

1 h√︁ i E 𝜂 (𝑆 (𝑡)) | 𝑆 (𝑡) > 0, 𝑆 (0) = 𝑆

By the law of total probability: h√︁ i ≤ E 𝜂 (𝑆 (𝑡)) | 𝑆 (0) = 𝑆 − Pr [𝜂 (𝑡) > 0 | 𝑆 (0) = 𝑆] 2 · Υ ·

1 h√︁ i E 𝜂 (𝑆 (𝑡)) | 𝑆 (0) = 𝑆

By using that 𝜂 (𝑡) is a supermartingale: h√︁ i 1 ≤ E 𝜂 (𝑆 (𝑡)) | 𝑆 (0) = 𝑆 − Pr [𝜂 (𝑡) > 0 | 𝑆 (0) = 𝑆] 2 · Υ · √︁ . vol(𝑆) Finally, note that Pr(𝜂 (𝑡) > 0) ≥ 21 and the claim follows.

□

Discrete Incremental Voting

By induction, for all 𝑡 < 𝜏𝑠 it follows that h√︁ i √ 𝑑 min (𝐺) · Φ(𝐺) E 𝜂 (𝑡) | 𝜂 (0) = 𝑠 ≤ 𝑠 − 𝑡 · 𝑐 · . √ 𝑠 ·𝑛 √︁ Moreover, since 𝜂 (𝑡) is integer-valued, 1{𝜂 (𝑡) > 0} ≤ 𝜂 (𝑡) and hence i h√︁ Pr [𝜂 (𝑡) > 0 | 𝜂 (0) = 𝑠] ≤ E 𝜂 (𝑡) | 𝜂 (0) = 𝑠 . Therefore, if 𝑡 ≥ then E 7.5

√ √ 𝑠 − 21 𝑠 ·𝑛 𝑠𝑛 · ∈𝑂 , 𝑐 𝑑 min (𝐺) · Φ(𝐺) Φ(𝐺) · 𝑑 min (𝐺)

i h√︁ 𝜂 (𝑡) | 𝜂 (0) = 𝑠 ≤ 12 , which implies Pr [𝜂 (𝑡) = 0 | 𝜂 (0) = 𝑠] ≥ 12 and thus 𝑡 ≥ 𝜏𝑠 .

Proof of Theorem 2.2

Í Given a nonempty set of vertices 𝑆 ⊆ 𝑉 and a vector of opinions 𝑥® = (𝑥𝑖 )𝑖 ∈ [𝑛] , we write 𝜇𝑆 (𝑥) ® := |𝑆1 | 𝑖 ∈𝑆 𝑥𝑖 for the mean opinion of 𝑆’s agents in 𝑥. ® Furthermore, we write Δ𝑆 (𝑥) ® := 𝜇𝑆 (𝑥) ® − 𝜇𝑆 (𝑥) ® for the difference between the mean opinions within 𝑆 and its complement in 𝑥. ® Lemma 7.1. Let 𝑆 ⊆ 𝑉 be a nonempty subset of 𝑉 having size |𝑆 | ≤ 𝑛/2. Then for all 𝑡 ≥ 1 and 𝑥® ∈ N𝑉 , we have h i |O(𝑆)| E Δ𝑆 (𝑋® (𝑡)) − Δ𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® ≤ . |𝐸||𝑆 | Proof. First, let us consider the expected change in 𝜇𝑆 : When two agents in 𝑆 interact, whether the sum of opinions in 𝑆 increases by one or decreases by one is decided by a fair coin flip, so that in this case, there is, in expectation, no change. The same trivially holds whenever two agents not in 𝑆 interact. In the remaining case, when an agent in 𝑆 interacts with an agent not in 𝑆, the sum of opinions in 𝑆 changes only if the opinions are different and the coin flip decides that the agent in 𝑆 should change its opinion. Hence, h i E 𝜇𝑆 (𝑋® (𝑡)) − 𝜇𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® =

∑︁ (𝑖,𝑗 ) ∈O(𝑆 )

sign(𝑥 𝑗 − 𝑥𝑖 ) 1 · , 2|𝐸| |𝑆 |

where sign(𝑧) is 1 if 𝑧 is positive, −1 if 𝑧 is negative, and 0 otherwise. The same holds when substituting 𝑆 for 𝑆. Using this, by definition of Δ𝑆 (𝑥), ® linearity of expectation, and the fact that sign(−𝑧) = − sign(𝑧), we get h i h i E Δ𝑆 (𝑋® (𝑡)) − Δ𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® = E 𝜇𝑆 (𝑋® (𝑡)) − 𝜇𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® h i − E 𝜇𝑆 (𝑋® (𝑡)) − 𝜇𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® ∑︁ sign(𝑥 𝑗 − 𝑥𝑖 ) sign(𝑥𝑖 − 𝑥 𝑗 ) 1 = · · − 2|𝐸| |𝑆 | |𝑆 | (𝑖,𝑗 ) ∈O(𝑆 ) ∑︁ sign(𝑥 𝑗 − 𝑥𝑖 ) sign(𝑥 𝑗 − 𝑥𝑖 ) 1 = · · + 2|𝐸| |𝑆 | |𝑆 | (𝑖,𝑗 ) ∈O(𝑆 ) ∑︁ 1 1 1 = · · + · sign(𝑥 𝑗 − 𝑥𝑖 ). 2|𝐸| |𝑆 | 𝑛 − |𝑆 | (𝑖,𝑗 ) ∈O(𝑆 )

Discrete Incremental Voting

Since 1/(𝑛 − |𝑆 |) ≤ 1/|𝑆 | (since |𝑆 | ≤ 𝑛/2 and thus |𝑆 | ≤ 𝑛 − |𝑆 |), and |sign(𝑥 𝑗 − 𝑥𝑖 )| ≤ 1, we have, by the triangle inequality, h i 1 E Δ𝑆 (𝑋® (𝑡)) − Δ𝑆 (𝑋® (𝑡 − 1)) | 𝑋® (𝑡 − 1) = 𝑥® ≤ 2|𝐸|

∑︁ (𝑖,𝑗 ) ∈O(𝑆 )

2 |O(𝑆)| ·1≤ , |𝑆 | |𝐸||𝑆 |

as claimed.

□

Lemma 7.2. Let 𝑆 ⊆ 𝑉 be annonempty subsetoof 𝑉 having size |𝑆 | ≤ 𝑛/2, and let 𝑋® (0) such that Δ𝑆 (𝑋® (0)) = 𝑘. Then

for all 𝑝 ∈ (0, 1), and 𝑡 = min

𝑘 |𝐸 | |𝑆 | 𝑘 2 |𝑆 | 2 4|O(𝑆 ) | , 8 log(2/𝑝 )

, we have 𝑘 ≥ 1 − 𝑝. Pr Δ𝑆 (𝑋® (𝑡)) > 2

)| 1 ® ® Proof. By Lemma 7.1, 𝑍𝑡 := Δ𝑆 (𝑋® (𝑡)) − 𝑡 · |O(𝑆 |𝐸 | · |𝑆 | is a submartingale. Now |Δ𝑆 (𝑋 (𝑡)) − Δ𝑆 (𝑋 (𝑡 − 1))| ≤ |𝑆 |

since at most one agent can change its opinion in one step (so only one of 𝜇𝑆 and 𝜇𝑆 can change at a time), and as )| 1 |𝑆 | ≤ 𝑛/2. Combining this with Lemma 7.1 and |O(𝑆 |𝐸 | · |𝑆 | ≤ |𝑆 | , we can use a two-sided Azuma’s inequality to see that for √︁ 𝜀 = 2𝑡 log(2/𝑝)/|𝑆 |, we have 2 |O(𝑆)| 𝜀 · |𝑆 | 2 2𝜀 2 Pr Δ𝑆 (𝑋® (𝑡)) − Δ𝑆 (𝑋® (0)) ≥ 𝑡 · + 𝜀 ≤ 2 exp − = 2 exp − = 𝑝. (27) |𝐸||𝑆 | 𝑡 (2/|𝑆 |) 2 2𝑡

We assume that Δ𝑆 (𝑋® (0)) = 𝑘, so that we have Δ𝑆 (𝑋® (𝑡)) > 𝑘/2 with probability at least 1 − 𝑝 if √︁ 2 log(2/𝑝) |O(𝑆)| √ 𝑡· + 𝑡· < 𝑘/2. |𝐸||𝑆 | |𝑆 | This is definitely the case when both terms are at most 𝑘/4 individually, i.e., when !2     𝑘 |𝐸||𝑆 |    𝑘 |𝑆 | 𝑘 2 |𝑆 | 2 𝑘 |𝐸||𝑆 | 𝑡 ≤ min , , √︁ , = min  4|O(𝑆)| 8 log(2/𝑝)  4|O(𝑆)| 2 2 log(2/𝑝)     yielding the claim. 7.6

□

Proof of Theorem 2.1, bound (3)

Our proof of the convergence bound (2) in Theorem 2.1 was split into two parts. The first part dealt with the discrepancy decreasing from the initial 𝐾 to 𝛼 = (32log 𝑛)/Φ, and the second part considered the time needed to decrease the discrepancy from 𝛼 to 0. (We are simplifying notation here, using Φ and 𝛾 for Φ(𝐺) and 𝛾 (𝐺).) 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 T𝐺2𝑉 , so all but one of the remaining 𝛼 opinions are eliminated in 𝑂 𝛼 T𝐺2𝑉 time, in expectation as well as with high probability. Now we refine the analysis of the second part to obtain bound (3) in Theorem 2.1. For convenience, we repeat below this bound as a separate theorem. Theorem 7.3. Consider the Asynchronous-DIV process on a graph 𝐺 with conductance Φ and the ratio of average to minimum degree 𝛾. Assume 𝑥® is an arbitrary configuration with discrepancy 𝐾. Then 𝐾𝑛 log(𝐾𝑛) 𝛾𝑛 2 E [𝑇𝐺 (𝑥)] ® = 𝑂 + 2 . Φ2 Φ

(28)

This theorem implies the bound of 𝑂 (𝛾𝑛 2 ) on the expected consensus time of Asynchronous-DIV for graphs with constant conductance and the initial discrepancy 𝐾 = 𝑂 (𝑛/log 𝑛) . This bound of 𝑂 (𝛾𝑛 2 ) is of the same asymptotic

Discrete Incremental Voting

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 Theorem 7.4 in the form as it was derived in [16]. For regular graphs with constant conductance, bound (28) becomes 𝑂 (𝑛 2 ), matching the lower bound of Ω(𝑛 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 𝑆 ⊆ 𝑉 (𝐺), let 𝜇 (𝑆) = vol(𝑆 2𝑚 denote the volume of this set as a fraction of the total graph volume.

For the 2-Value Pull Voting in graph 𝐺 with the initial minority support 𝑆 ⊆ 𝑉 (𝐺) (understood as 𝜇 (𝑆) ≤ 𝜇 (𝑉 (𝐺) \ 𝑆)), let the random variable 𝑇𝐺2𝑉 (𝑆) denote the time when the consensus is reached. Further, extending the definition of T𝐺2𝑉 , define for 0 < 𝜖 ≤ 1/2 the worst-case expected consensus time when the initial minority vote fraction is at most 𝜖: T𝐺2𝑉 (𝜖) = max E 𝑇𝐺2𝑉 (𝑆) : 𝑆 ⊆ 𝑉 , 𝜇 (𝑆) ≤ 𝜖 . The following bound on T𝐺2𝑉 (𝜖) can be extracted from the analysis of voting processes presented in [16]. Theorem 7.4 ([16]). The worst-case expected time of completing the 2-Value Pull Voting process starting with a minority support set 𝑆 such that 𝜇 (𝑆) ≤ 𝜖 has the following bound. T𝐺2𝑉 (𝜖) = 𝑂

√ 𝛾𝑛 2 𝜖 . Φ

Our proof of Theorem 7.3 is based on the following lemma, which can be viewed as an extension of Proposition 4.1 to cover also the case of smaller discrepancies, and on the bound on the worst-case expected time T𝐺2𝑉 (𝜖) stated in Theorem 7.4. Lemma 7.5. For 𝑘 ≥ 1, let 𝜖𝑘 = 𝑒 −Φ𝑘/16 and 𝑇𝑘 = 80

𝑘 ·𝑛·log(𝑘𝑛) (this value 𝑇𝑘 is set to align with 𝑇 in Proposition 4.1 for Φ2

any configuration 𝑥® with discrepancy at most 𝐾. The worst-case expected time to reduce the discrepancy to 𝑐 = 1). Consider Í𝐾 2𝑉 3 ( /4)𝐾 is 𝑂 𝑇𝐾 + 𝑘=( 3/4 )𝐾 T𝐺 (𝜖𝑘 ) . We use throughout this section the parameters 𝜖𝑘 and 𝑇𝑘 defined in this lemma. For initial discrepancies greater than 32·log 𝑛 Φ , this lemma is essentially a version of Proposition 4.1, 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 𝐾, they provide new insight (beyond what we showed in Proposition 4.1) only for initial discrepancies smaller than this threshold. Let 𝜇 (𝑡) = min{𝜇 (𝑉𝑘 ′ (𝑡)), 𝜇 (𝑉𝑘 ′′ (𝑡))}, where 𝑉𝑘 ′ (𝑡) and 𝑉𝑘 ′′ (𝑡) are the support sets for the highest and lowest opinions 𝑘 ′ and 𝑘 ′′ still present in the configuration in step 𝑡. To prove Lemma 7.5, we will need two additional lemmas. Lemma 7.6 extends Lemma 4.5 to smaller discrepancies, ascertaining the existence of good indices also for small values of 𝐾, providing that the support for the extreme opinions is not two small. We prove Lemma 7.6 by showing how the proof of Lemma 4.5 should be adapted. Lemma 7.7 is a slight generalization of Lemma 4.6, and we omit its proof as it is essentially the proof of Lemma 4.6 with obvious notational adjustments. Lemma 7.6. Let 𝑇 ≤ 𝑇e and consider a sequence of 𝑇e steps 0, 1, . . . , 𝑇e − 1 in the Asynchronous-DIV process starting from an arbitrary configuration with discrepancy at most 𝐾. If 𝜇 (𝑡) > 𝜖𝐾 in at least 𝑇 of these steps, then there exists an index 𝑘 ★ ∈ [( 1/2)𝐾, ( 3/4)𝐾] that is good in at least 𝑇 /4 steps in the original process or at least 𝑇 /4 steps in the mirrored process.

Discrete Incremental Voting

Proof. Let Υ ⊆ 𝑇e be a set of 𝑇 steps such that for each 𝑡 ∈ Υ, 𝜇 (𝑡) > 𝜖𝐾 . We take any step 𝑡 ∈ Υ and follow exactly the proof of Lemma 4.5 up to the point where we establish that ℓ 2𝑚 ≥ vol 𝑆𝑘ℓ (𝑡) > 1 + 34 Φ · vol 𝑆𝑘0 (𝑡) ,

(29)

where 𝑘 0 > 𝑘 1 > · · · > 𝑘 ℓ are the bad indices in [( 1/2)𝐾, ( 3/4)𝐾] in this step. At this point in the proof of Lemma 4.5 we use the fact that vol 𝑆𝑘0 (𝑡) ≥ 1. Here we deviate and use instead the assumption that 𝜇 (𝑡) > 𝜖𝐾 . This implies that vol 𝑆𝑘0 (𝑡) /(2𝑚) ≥ 𝜇 (𝑡) > 𝜖𝐾 , so (29) implies ℓ 1 + 34 Φ 𝜖𝐾 < 1, giving Φ𝐾/16 ≤ 𝐾8 . log(1 + ( 3/4)Φ Thus, as in the proof of Lemma 4.5, there are at most 𝐾/8 bad indices in step 𝑡, so, as per the concluding part of the ℓ<

proof of Lemma 4.5, there is an index in 𝑘 ★ ∈ [( 1/2)𝐾, ( 3/4)𝐾] in the original or mirrored process which is good in at least 𝑇 /4 steps in [𝑇 − 1]. Lemma 7.7. Let 𝑇 = 20𝑐 · 𝐾

□ 𝑛 log(𝐾𝑛) for some 𝑐 > 2, let 𝑇e ≥ 𝑇 , and consider a sequence of 𝑇e steps 0, 1, . . . , 𝑇e − 1 in the Φ2 (𝐺 )

Asynchronous-DIV process starting from an arbitrary configuration with discrepancy at most 𝐾. Fix 𝑘 ∈ [𝐾/2, 𝐾], and define 𝜏𝑘 (𝑡) := |{𝜏 ∈ [𝑡] : 𝑘 is good in step 𝜏 }|. Then h i 1 Pr Ψ𝑘(+) 𝑋® 𝑇e > 0 ∧ 𝜏𝑘 (𝑇e − 1) ≥ 𝑇 /4 ≤ . (𝐾𝑛)𝑐 −2 The same holds for the mirrored process. Proof of Lemma 7.5. Consider the Asynchronous-DIV process of eliminating extreme opinions one by one, from 𝐾 opinions to ( 3/4)𝐾 opinions. To keep the notation simple, we assume that the initial discrepancy is 𝐾 rather than at most 𝐾. For 0 ≤ 𝑖 ≤ 𝐾/4, define 𝑡𝑖 as the first step when the discrepancy is 𝐾 − 𝑖. Hence 𝑡 0 = 0 and 𝑡𝑖+1 > 𝑡𝑖 (as in one step the discrepancy can reduce only by 1). Furthermore, define 𝑡𝑖′ as the first step 𝑡 in {𝑡𝑖 , 𝑡𝑖 + 1, . . . , 𝑡𝑖+1 − 1} when 𝜇 (𝑡) ≤ 𝜖𝐾 −𝑖 , or 𝑡𝑖′ = 𝑡𝑖+1 , if 𝜇 (𝑡) remains above 𝜖𝐾 −𝑖 in all these steps. (If 𝜖𝐾 −𝑖 is particularly small, then 𝜇 (𝑡) may remain above 𝜖𝐾 −𝑖 until, and including, step 𝑡𝑖+1 − 1, when one of the two extreme opinions disappears and the discrepancy in the next step 𝑡𝑖+1 is 𝐾 − 𝑖 − 1 for the first time.) With this notation, the steps [𝑡𝑖 , 𝑡𝑖+1 ) is the phase of the computation when the discrepancy reduces from 𝐾 − 𝑖 to 𝐾 − 𝑖 − 1. This phase is subdivided into two parts. First, in steps [𝑡𝑖 , 𝑡𝑖′ ), the parameter 𝜇 (𝑡) – the fractional volume of the smaller of the two extreme opinions – is reduced to 𝜖𝐾 −𝑖 , and then, in steps [𝑡𝑖′, 𝑡𝑖+1 ), one extreme opinion is eliminated. We bound the expectation of the length of the second part of the phase using the reduction from the process of eliminating one extreme opinion in the context of the incremental voting to the process of reaching consensus in the 2-value pull voting, as described in [13]. Thus we have, E 𝑡𝑖+1 − 𝑡𝑖′ ≤ T𝐺2𝑉 (𝜖𝐾 −𝑖 ).

(30)

We bound the combined length of the first parts of the phases using Lemma 7.6 and Lemma 7.7, taking 𝑇 as defined Í (𝐾/4) −1 2𝑉 T𝐺 (𝜖𝐾 −𝑖 ). 𝑖=0

in Lemma 7.7 with 𝑐 = 4, so 𝑇 = 𝑇𝐾 for 𝑇𝐾 defined in the statement of Lemma 7.5, and 𝑇e = 𝑇 + 2 · For 𝑡𝐾/4 , the first step when the discrepancy drops to ( 3/4)𝐾, we have, Pr 𝑡𝐾/4 > 𝑇e = Pr [𝑡𝐾/4 − 1] ⊇ [𝑇e − 1]

Discrete Incremental Voting

≤ Pr

" ( 𝐾/4−1 Ø

34 )

[𝑡𝑖 , 𝑡𝑖′ ) ∩ [𝑇e − 1]

# ∩ 𝑡𝐾/4 > 𝑇e

≥𝑇

+ Pr

𝑖=0

≤ Pr

|{𝑡 ∈ [𝑇e − 1] : 𝜇 (𝑡) > 𝜖𝐾 }| ≥ 𝑇

(𝐾/4) ∑︁−1 (𝑡𝑖+1 − 𝑡𝑖′ ) ≥ 2 · T𝐺2𝑉 (𝜖𝐾 −𝑖 ) 𝑖=0 𝑖=0

"𝐾/4−1 ∑︁

1 ∩ 𝑡𝐾/4 > 𝑇e + 2

(31)

(32)

The bound of 1/2 on the second term on line (31) follows from (30): the probability that the value of a random variable is greater than twice its expectation is less than 1/2. The bound on the first term in (31) comes from the definition of the steps 𝑡𝑖 and 𝑡𝑖′ : for each 𝑡 ∈ [𝑡𝑖 , 𝑡𝑖′ ), we have 𝜇 (𝑡) > 𝜖𝐾 −𝑖 ≥ 𝜖𝐾 . We continue from this bound, introducing notation 𝑋® P (𝑡), where P ∈ {original, mirrored}, to refer to the configuration at step 𝑡 in process P. Pr

|{𝑡 ∈ [𝑇e − 1] : 𝜇 (𝑡) > 𝜖𝐾 }| ≥ 𝑇 ∩ 𝑡𝐾/4 > 𝑇e ≤ Pr |{𝑡 ∈ [𝑇e − 1] : 𝜇 (𝑡) > 𝜖𝐾 }| ≥ 𝑇 n oi ∩ ∀𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾] ∀P ∈ {original, mirrored} : Ψ𝑘(+) 𝑋® P (𝑇e) > 0 ≤ Pr ∃𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾] ∃P ∈ {original, mirrored} : 𝑘 is good in 𝑇 /4 steps in [𝑇e − 1] in process P n oi ∩ ∀𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾], ∀P ∈ {original, mirrored} : Ψ𝑘(+) 𝑋® P (𝑇e) > 0 ≤ Pr ∃𝑘 ∈ [( 1/2)𝐾, ( 3/4)𝐾] ∃P ∈ {original, mirrored} : 𝑘 is good in 𝑇 /4 steps in [𝑇e − 1] in P i and Ψ𝑘(+) 𝑋® P (𝑇e) > 0 1 1 𝐾 ≤ · = 𝑂 . 4 (𝐾𝑛) 2 𝑛2

(33)

(34)

Inequality (33) follows from Lemma 7.6. Inequality (34) follows from the union bound and Lemma 7.7. The bounds (32) and (34) imply that with probability at least 1/3, in 𝑇e steps the discrepancy is reduced to at most ( 3/4)𝐾, so, using the argument of restarting in case of failure, the expected time of reducing the discrepancy to ( 3/4)𝐾 is 𝑂 (𝑇e).

□

Proof of Theorem 7.3. Using Lemma 7.5, the expectation of the completion time in the Asynchronous-DIV process is at most of the following order. 𝑖

log4/3 𝐾 ( 3∑︁ /4 ) 𝐾 𝐾 ∑︁ © ∑︁ ( 3/4)𝑖 𝐾𝑛 log(𝐾𝑛) ∑︁ 2𝑉 ª + T𝐺 (𝜖𝑘 ) T𝐺2𝑉 (𝜖𝑘 ) ® ≤ 80 𝑇 ( 3/4 ) 𝑖 𝐾 + Φ2 𝑖=0 « 𝑖=0 𝑘=0 𝑘=( 3/4 ) 𝑖+1 𝐾 ¬ ∑︁ 𝐾 𝐾𝑛 log(𝐾𝑛) =𝑂 + T𝐺2𝑉 (𝜖𝑘 ). 2 Φ

log4/3 𝐾

(35)

𝑘=0

For the final sum above, the bound stated in Theorem 7.4 gives 𝐾 ∑︁

T𝐺2𝑉 (𝜖𝑘 )

! 𝐾 𝛾𝑛 2 ∑︁ √ = 𝑂 𝜖𝑘 ) , Φ

(36)

𝑘=1

and we have 𝐾 𝐾 ∑︁ ∑︁ √ 𝜖𝑘 = 𝑒 −Φ𝑘/32 ≤ 𝑘=1

𝑘=1

1 1 =𝑂 . Φ 1 − 𝑒 −Φ/32

(37)

Putting together (35), (36) and (37), we get the bound on the expectation of the completion time in the AsynchronousDIV process stated in the theorem.

□

Discrete Incremental Voting

References [1] Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. SIGACT News, 51(1):58–104, 2020. [2] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Comput., 30(4):293–306, 2017. [3] Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 335–344, 2017. [4] Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik, and Nicolas Rivera. Distributed averaging in opinion dynamics. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 211–221, 2023. [5] Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the voter model in dynamic networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 146:1–146:15, 2016. [6] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, Oxford, UK, 2013. [7] Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997. [8] Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM J. Discret. Math., 27(4):1748–1758, 2013. [9] Colin Cooper, Robert Elsässer, and Tomasz Radzik. The power of two choices in distributed voting. In Automata, Languages, and Programming (ICALP), pages 435–446, 2014. [10] Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast consensus for voting on general expander graphs. In Distributed Computing - 29th International Symposium (DISC), pages 248–262, 2015. [11] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4095–4131, 2025. [12] Colin Cooper, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast plurality consensus in regular expanders. In 31st International Symposium on Distributed Computing (DISC), 2017. [13] Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete Incremental Voting. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), pages 10:1–10:22, 2024. [14] Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete incremental voting on expanders. Discret. Math., 349(1):114708, 2026. [15] Colin Cooper and Nicolas Rivera. The linear voting model. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 144:1–144:12, 2016. [16] Colin Cooper and Nicolas Rivera. The linear voting model. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 144:1–144:12, 2016. [17] Guillaume Deffuant, David Neau, Frédéric Amblard, and Gérard Weisbuch. Mixing beliefs among interacting agents. Advances in Complex Systems, 3(1–4):87–98, 2000. [18] Morris H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118–121, 1974. [19] Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, page 149–158, 2011. [20] Richard Durrett. Probability: Theory and Examples, volume 49 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 5th edition, 2019. [21] Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 305–313, 2018. [22] Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput., 171(2):248–268, 2001. [23] Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of Artificial Societies and Social Simulation, 5(3), 2002. [24] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439– 561, 2006. [25] Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1–6, 2018. URL: https://www. sciencedirect.com/science/article/pii/S0167715217303711, doi:10.1016/j.spl.2017.11.017. [26] Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149–1178, 1989. [27] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009. [28] Milena Mihail. Conductance and convergence of markov chains-a combinatorial treatment of expanders. In 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 526–531, 1989. [29] Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 207–217, 2025.

Record · ID 259417 · SHA-256 ee82ca53d301320a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.