d4-conf-ecai-2012-0180 (d4-conf-ecai-2012-0180)

Given rational sincere-type masses \(\mu\) and an initial rational state \(x\) of reported ballots, consider plurality with randomized tie-breaking and all locally uniform subsequential limits of interpolated RBR runs on exact finite replications, where each update transfers mass \(1/N\) and time is scaled as \(u=k/N\). Does every such fluid trajectory become stationary by time \(u=m-1\)?

Let \(C\) contain \(m\geq 2\) candidates. A society is given by its support: \(\tau\) sincere types, each a strict ranking of \(C\), with positive binary rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. The initial state is a binary rational matrix \(x_{t,c}\geq0\) with \(\sum_c x_{t,c}=\mu_t\), recording the mass of type \(t\) currently voting for \(c\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), and additionally \(N\) for finite replications.
Plurality ballots are identified with their top candidate. At every finite state, the outcome is the uniform lottery on the plurality winner set. An RBR move changes one voter's ballot from \(a\) to \(b\neq a\), strictly improves this lottery under first-order stochastic dominance for that voter's sincere ranking, and has \(b\) in the new winner set. Both cases are allowed: \(a\) belongs to the old winner set, or \(a\) does not belong to it.
For every integer \(N\) with all \(Nx_{t,c}\) integral, an exact replication consists of \(Nx_{t,c}\) voters of sincere type \(t\) initially voting for \(c\). Any voter with an RBR move may move next; take maximal runs without idle steps and extend each terminal state constantly forever.
Normalize the state by \(N\), linearly interpolate between consecutive states at times \(u=k/N\), and call any subsequential limit as admissible \(N\to\infty\), uniform on every compact time interval in the matrix maximum norm, a fluid trajectory \(X\). Stationarity by \(m-1\) means \(X(u)=X(m-1)\) for every \(u\geq m-1\).

Is deciding, from \((\mu,x)\), whether every such fluid trajectory is stationary by time \(u=m-1\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

Discrete plurality RBR dynamics with uniform randomized tie-breaking and stochastic-dominance improvements converge from any state to a Nash equilibrium within \(m+(m-1)n\) moves for \(n\) voters ([Reyhani–Wilson](https://www.cs.auckland.ac.nz/~mcw/Research/Outputs/ReWi2011.pdf)). No result addressing exactly the fluid-trajectory decision problem above was verified in the literature search.

Result

The decision problem is in \(\mathrm{P}\). Every valid input satisfies the required stationarity property. This follows from the supplied finite convergence bound, because its additive term vanishes under normalization.

1. Applying the finite convergence theorem

Fix a valid input and an admissible replication size \(N\). The replication has exactly \(N\) voters, since
\[ \sum_{t,c}Nx_{t,c}=N\sum_t\mu_t=N. \]

The finite theorem supplied in the question applies to plurality, uniform randomized tie-breaking, strict stochastic-dominance improvements, and arbitrary initial states. Its plurality RBR definition includes precisely the two permitted cases: the departing ballot belongs to the old winner set, or it does not, while the destination belongs to the new winner set. See Definition 5.1 and Theorem 5.7 of [Reyhani–Wilson](https://www.cs.auckland.ac.nz/~mcw/Research/Outputs/ReWi2011.pdf).

Consequently, for every maximal run in this replication, its number of moves \(K_N\) satisfies
\[ K_N\leq m+(m-1)N. \]
The theorem allows arbitrary selection of the next voter having an RBR move, so this bound covers every schedule in the question.

2. A uniform bound on movement after the threshold

Write \(Y_N(u)\) for the normalized, linearly interpolated trajectory, extended constantly after termination. Set \(T=m-1\).

Time \(T\) is exactly a grid time, corresponding to move index \(NT=(m-1)N\). Therefore, the number of moves remaining after time \(T\) is at most
\[ \max\{0,K_N-NT\}\leq m. \]

Each move changes two entries of the normalized matrix by magnitude \(1/N\). Its change in matrix maximum norm is thus \(1/N\). Linear interpolation traverses only a fraction of the corresponding change. The triangle inequality consequently gives, for every \(u\geq T\),
\[ \|Y_N(u)-Y_N(T)\|_{\max}\leq \frac{m}{N}. \]
This also holds when the run terminates before \(T\), since its trajectory is then already constant.

3. Passing to every fluid limit

Let \(X\) be any fluid trajectory. By definition, there are admissible \(N_j\to\infty\) and corresponding trajectories \(Y_{N_j}\) converging to \(X\) uniformly on every compact time interval.

Fix any \(u\geq T\), and define
\[ \varepsilon_j=\sup_{0\leq v\leq u}\|Y_{N_j}(v)-X(v)\|_{\max}. \]
Compact uniform convergence gives \(\varepsilon_j\to0\). Using the preceding bound,
\[ \|X(u)-X(T)\|_{\max} \leq 2\varepsilon_j+\frac{m}{N_j}\longrightarrow0. \]
Hence \(X(u)=X(T)\). Since \(u\geq T\) was arbitrary, \(X\) is stationary by time \(m-1\). Since \(X\) was arbitrary, this holds for every fluid trajectory.

The quantification is also nonvacuous. A common denominator \(D\) of the rational entries \(x_{t,c}\) makes every \(N=jD\) admissible. Their trajectories take values in the compact set of nonnegative matrices with row sums \(\mu_t\), and are \(1\)-Lipschitz in matrix maximum norm. Arzelà–Ascoli on successive compact time intervals, followed by diagonal subsequence extraction, therefore supplies a fluid trajectory.

4. Decision algorithm and running time

On the specified valid-input domain, return YES.

The decision takes constant time under the validity promise, or \(O(L)\) time including reading the input, for arbitrary \(m\) and support size \(\tau\). It requires no dependence on a replication size \(N\). For each finite replication, the mathematical move bound used above is \(m+(m-1)N\).

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves the assigned decision problem. Its application of the supplied finite convergence bound is valid, and its normalization and limit arguments establish stationarity by \(u=m-1\) for every fluid trajectory. No mathematical gaps or false steps were found.

1. Applicability of the finite theorem

The replication contains exactly \(N\) voters: summing its integer counts gives
\[ \sum_{t,c}Nx_{t,c}=N. \]
The stipulated integrality and nonnegativity therefore produce a valid finite electorate. Each voter retains the strict sincere ranking of their type. Identifying a plurality ballot with its top candidate preserves all scores and outcomes.

The cited result matches the permitted dynamics. Definition 5.1 allows improving moves with the destination in the new winner set, whether or not the departing candidate belongs to the old winner set. Section 2.2 uses stochastic dominance between uniform winner lotteries; Section 3 permits arbitrary selection of the next eligible voter. Theorem 5.7 states convergence from any state within \(m+(m-1)n\) moves under randomized tie-breaking. These hypotheses match the task. [Reyhani–Wilson, Sections 2.2, 3, and 5](https://www.cs.auckland.ac.nz/~mcw/Research/Outputs/ReWi2011.pdf).

Consequently, the bound
\[ K_N\leq m+(m-1)N \]
applies to every maximal run under consideration. No sincerity assumption on the initial ballots, scheduling restriction, or omitted restriction on the two allowed move cases invalidates this application.

2. Movement after the threshold

With \(T=m-1\), the time \(T\) is a grid point because \(NT=(m-1)N\) is an integer.

If the run has not terminated by that index, its remaining number of moves is at most
\[ K_N-NT\leq m. \]
If it has terminated, the constant extension contributes no further movement. Thus the displayed bound using the maximum with zero is correct in both cases.

A move transfers exactly \(1/N\) between two distinct entries in a single type row. Its matrix maximum norm displacement is exactly \(1/N\). Linear interpolation contributes at most that amount over any portion of a move. The triangle inequality therefore correctly yields
\[ \|Y_N(u)-Y_N(T)\|_{\max}\leq \frac{m}{N} \qquad\text{for every }u\geq T. \]
This bound also covers fractional grid times and arbitrarily late times after termination.

3. Passage to every fluid limit

For any fluid trajectory \(X\), the defining subsequence has \(N_j\to\infty\) and compact uniform convergence. Fixing any finite \(u\geq T\), the interval \([0,u]\) contains both comparison times. Hence the prover correctly obtains
\[ \|X(u)-X(T)\|_{\max} \leq 2\varepsilon_j+\frac{m}{N_j}. \]
Both terms tend to zero. Since a norm is nonnegative, this proves \(X(u)=X(T)\).

The quantifiers are handled correctly: the fluid trajectory and the time \(u\geq T\) were arbitrary. No simultaneous convergence on an unbounded interval is required. The argument includes the boundary time \(u=T\).

4. Nonvacuity of the fluid-trajectory definition

The supplementary existence argument is valid.

A common denominator of the finitely many rational entries provides an unbounded sequence of admissible replication sizes. The normalized trajectories remain in the closed, bounded set of nonnegative matrices with the prescribed row sums, which is compact in this finite-dimensional space.

Each interpolation segment has speed at most \(1\) in matrix maximum norm, and the constant extensions have speed zero. Thus the family is uniformly \(1\)-Lipschitz. The compact-range and equicontinuity hypotheses of Arzelà–Ascoli hold on every compact time interval. Successive subsequence extraction and a diagonal subsequence provide the required compact uniform convergence. This verifies the stated nonvacuity.

5. Decision algorithm and complexity

Since every valid input satisfies the property, returning YES correctly decides the problem on its specified domain.

The claimed constant-time decision under a validity promise, or \(O(L)\) time when reading the input, is consistent. The decision requires neither constructing a replication nor simulating its dynamics. Its running time therefore has no additional dependence on \(N\), \(m\), or \(\tau\) beyond the input-reading bound. The separately stated finite move bound correctly records its dependence on \(m\) and \(N\).

Required repair or clarification: none. The argument establishes the claimed polynomial-time classification.

⟨structured verdict parsed — rendered above⟩