Conjecture on decreasing marginal value of defectors in majority dynamics

Let c1(k,n)c1(k,n) be the probability that Red wins when Red's camp initially has size n/2+kn/2+k, with p=.5p=.5, and define the value of the iith defector by

v(i,n)=ρ(i,n)ρ(i1,n),v(i,n)=\rho(i,n)-\rho(i-1,n),

with c1(n,0)=1/2c1(n,0)=1/2. Values of defectors conjecture. For any fixed ii and sufficiently large nn,

v(i,n)v(i+1,n).v(i,n)\geq v(i+1,n).

The claim formalizes the intuition that successive defectors provide diminishing advantages; the paper gives no proof or resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Linh Tran and Van Vu, “Reaching a Consensus on Random Networks: The Power of Few”, arXiv:1911.10279 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.