3-Majority and 2-Choices with Many Opinions

We present the first nearly-optimal bounds on the consensus time for the well-known synchronous consensus dynamics, specifically 3-Majority and 2-Choices, for an arbitrary number of opinions. In synchronous consensus dynamics, we consider an n-vertex complete graph with self-loops, where each vertex holds an opinion from {1,..., k}. At each discrete-time round, all vertices update their opinions simultaneously according to a given protocol. The goal is to reach a consensus, where all vertices support the same opinion. In 3-Majority, each vertex chooses three random neighbors with replacement and updates its opinion to match the majority, with ties broken randomly. In 2-Choices, each vertex chooses two random neighbors with replacement. If the selected vertices hold the same opinion, the vertex adopts that opinion. Otherwise, it retains its current opinion for that round.