d4-conf-aaai-2012-0108 (d4-conf-aaai-2012-0108)

Given alternatives \(A\), an explicit distance table \(d\) on rankings, a discount factor \(\gamma>1-1/D\), and an initial rational distribution \(\mu^0\) over \(\tau\) supported rankings, find an optimal stationary winner policy for infinite discounted reward. At each distribution \(\mu\), choosing \(x\) gives reward \(\sum_{P:P[1]=x}\mu_P\); each mass at a ranking \(P\) not already placing \(x\) first sends fraction \(q(P,x)=\frac{1}{\gamma}\left(\frac{1}{\hat d(P,x)}-(1-\gamma)\right)\) to a \(d\)-closest ranking \(S(P,x)\) with \(x\) first, where \(\hat d(P,x)=d(P,S(P,x))\), and the remaining mass stays at \(P\).

Let \(A\) contain \(m\geq2\) alternatives, and let \(\mathcal R\) be all strict rankings of \(A\), with \(P[1]\) denoting the top alternative. The input includes the full table of an integer-valued metric \(d:\mathcal R\times\mathcal R\to\mathbb Z_{\geq0}\). Set \(D=\max_{P,Q}d(P,Q)\), and take a binary rational discount factor \(1-1/D<\gamma<1\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are rankings, \(\tau\) is the support size, not the number of possible rankings, and masses sum to \(1\). An initial society \(\mu^0\) is supplied.
Fix an order of alternatives and its induced lexicographic order on rankings. Define \(S(P,x)\) as the lexicographically first minimizer of \(d(P,Q)\) among rankings \(Q\) with \(Q[1]=x\), and set \(\hat d(P,x)=d(P,S(P,x))\).
At state \(\mu\), action \(x\in A\) earns \(r(\mu,x)=\sum_{P:P[1]=x}\mu_P\). Every ranking \(P\) with \(P[1]\ne x\) simultaneously transfers fraction \(q(P,x)=\gamma^{-1}(\hat d(P,x)^{-1}-(1-\gamma))\) of its mass to \(S(P,x)\); its remaining mass stays at \(P\). Rankings already topping \(x\) retain their mass, and incoming masses add. Write \(F_x(\mu)\) for this deterministic update.
A deterministic stationary policy \(\pi\) maps distributions on \(\mathcal R\) to alternatives. It is optimal if it maximizes \(\sum_{t=0}^{\infty}\gamma^t r(\mu^t,\pi(\mu^t))\), with \(\mu^{t+1}=F_{\pi(\mu^t)}(\mu^t)\), from every initial distribution. A computational policy is represented by a finite procedure for evaluating its winner at rational societies. Let \(L\) be the total binary encoding length, including the full distance table and, for evaluation, the queried society.

Can an optimal deterministic stationary winner policy be constructed and evaluated in polynomial time in \(m,\tau,L\), or is this computational problem NP-hard?

For finite electorates with independent stochastic voter transitions having these probabilities, deterministic optimal policies are exactly those selecting a minimizer of \(\sum_i\hat d(P_i,x)\) at every profile. [Boutilier–Procaccia](https://www.cs.toronto.edu/~cebly/Papers/BoutilierProcaccia_aaai12.pdf).
No result settling the complexity of exactly the deterministic mass evolution defined above was located in the literature search.

The problem is polynomial-time solvable with the supplied full distance table. An optimal winner minimizes the mass-weighted distance to consensus. This holds for the deterministic mass evolution itself.

1. Statement and valid transitions

For each alternative \(x\), define
\[ C_x(\mu)=\sum_{P\in\mathcal R}\mu_P\hat d(P,x), \qquad \Phi(\mu)=\min_{x\in A}C_x(\mu). \]
Then the optimal value is
\[ V^*(\mu)=\frac{1}{1-\gamma}-\Phi(\mu), \]
and a deterministic stationary policy is optimal from every initial distribution if and only if
\[ \pi(\mu)\in\operatorname*{arg\,min}_{x\in A}C_x(\mu) \]
at every distribution \(\mu\).

We prove this directly. Although the characterization agrees with [Boutilier–Procaccia’s finite-electorate theorem](https://www.cs.toronto.edu/~cebly/Papers/BoutilierProcaccia_aaai12.pdf), no identification of deterministic evolution with stochastic evolution is needed.

Because \(d\) is an integer-valued metric, \(D\geq1\), and
\[ \hat d(P,x)=0\quad\Longleftrightarrow\quad P[1]=x. \]
Otherwise, \(1\leq\hat d(P,x)\leq D\). The discount assumption therefore gives
\[ 0<\frac{1}{\hat d(P,x)}-(1-\gamma)\leq\gamma. \]
Thus every transfer fraction satisfies \(0<q(P,x)\leq1\), so the updates preserve nonnegative masses and total mass.

2. The triangle inequality controls every update

For every ranking \(P\) and alternatives \(b,x\),
\[ \hat d(P,x)\leq\hat d(P,b)+\hat d(S(P,b),x). \tag{1} \]
Indeed, \(S(S(P,b),x)\) tops \(x\), so the definition of \(\hat d\) and the metric triangle inequality imply
\[ \begin{aligned} \hat d(P,x) &\leq d(P,S(S(P,b),x))\\ &\leq d(P,S(P,b)) +d(S(P,b),S(S(P,b),x))\\ &=\hat d(P,b)+\hat d(S(P,b),x). \end{aligned} \]

For action \(b\), define its distance reduction
\[ \Delta_b(\mu) =\sum_{P:P[1]\ne b}\mu_Pq(P,b)\hat d(P,b). \]
Write \(c(\mu,b)=1-r(\mu,b)\) for the one-period lost reward. The prescribed transition probabilities give the exact identity
\[ \gamma\Delta_b(\mu) =c(\mu,b)-(1-\gamma)C_b(\mu). \tag{2} \]

The deterministic update also gives
\[ C_x(F_b(\mu)) =C_x(\mu)+ \sum_{P:P[1]\ne b}\mu_Pq(P,b) \bigl(\hat d(S(P,b),x)-\hat d(P,x)\bigr). \]
Applying (1) term by term yields
\[ C_x(F_b(\mu))\geq C_x(\mu)-\Delta_b(\mu). \tag{3} \]
For \(x=b\), equality holds, because every transferred mass arrives at a ranking topping \(b\):
\[ C_b(F_b(\mu))=C_b(\mu)-\Delta_b(\mu). \tag{4} \]

Consequently,
\[ \Phi(F_b(\mu))\geq\Phi(\mu)-\Delta_b(\mu). \tag{5} \]
Moreover, if \(C_b(\mu)=\Phi(\mu)\), equations (4) and (5) force
\[ \Phi(F_b(\mu)) =C_b(F_b(\mu)) =\Phi(\mu)-\Delta_b(\mu). \tag{6} \]
In particular, a distance-minimizing alternative remains a minimizer after its own update.

3. Optimality and the exact value

Combining (2) and (5), for every action \(b\),
\[ \begin{aligned} c(\mu,b)+\gamma\Phi(F_b(\mu)) &\geq c(\mu,b)+\gamma\Phi(\mu)-\gamma\Delta_b(\mu)\\ &=\gamma\Phi(\mu)+(1-\gamma)C_b(\mu)\\ &=\Phi(\mu)+(1-\gamma)\bigl(C_b(\mu)-\Phi(\mu)\bigr)\\ &\geq\Phi(\mu). \end{aligned} \tag{7} \]
If \(b\) minimizes \(C_b(\mu)\), equation (6) shows that equality holds throughout (7).

Now consider any action sequence, with its resulting states \(\mu^t\). Applying (7) at each time, multiplying by \(\gamma^t\), and summing gives
\[ \sum_{t=0}^{T-1}\gamma^t c(\mu^t,x_t) \geq \Phi(\mu^0)-\gamma^T\Phi(\mu^T). \tag{8} \]
Since \(0\leq\Phi(\mu)\leq D\), the last term tends to zero. Hence every policy incurs discounted lost reward at least \(\Phi(\mu^0)\).

Choose the first alternative, in the fixed alternative order, minimizing \(C_x(\mu)\). This defines a deterministic stationary policy. For this policy, equality holds at every step of (8), so its infinite discounted lost reward is exactly \(\Phi(\mu^0)\). Since
\[ \sum_{t=0}^{\infty}\gamma^t r(\mu^t,x_t) =\frac{1}{1-\gamma} -\sum_{t=0}^{\infty}\gamma^t c(\mu^t,x_t), \]
the asserted optimal value follows.

The characterization is also necessary. If the first action \(b\) satisfies \(C_b(\mu)>\Phi(\mu)\), even an optimal continuation incurs total lost reward at least
\[ c(\mu,b)+\gamma\Phi(F_b(\mu)) \geq\Phi(\mu)+(1-\gamma)\bigl(C_b(\mu)-\Phi(\mu)\bigr) >\Phi(\mu). \]
Thus that action is strictly suboptimal. Because optimality is required from every initial distribution, every optimal stationary policy must select a distance minimizer at every state.

4. Polynomial-time construction and exact evaluation

Let \(N=|\mathcal R|=m!\). The full distance table contains \(N^2\) integer entries, so scanning it takes polynomial time in its explicit encoding length \(L\).

Precompute every \(\hat d(P,x)\) by scanning row \(P\) and taking the minimum distance among rankings topping \(x\). This requires \(O(N^2)\) integer comparisons, together with polynomial overhead for ranking labels. The resulting table has \(Nm\) entries and polynomial encoding size. The transition selector \(S\) is unnecessary for winner evaluation.

At a queried society with support size \(\tau\), compute
\[ C_x(\mu)=\sum_{P\in\operatorname{supp}(\mu)} \mu_P\hat d(P,x) \]
for each alternative, and return the first minimizer. This uses \(O(m\tau)\) exact arithmetic operations.

These operations also have polynomial bit complexity. Write each supported mass as \(a_P/b_P\), and use the common denominator
\[ B=\prod_{P\in\operatorname{supp}(\mu)}b_P. \]
Its bit length is at most the sum of the input denominators’ bit lengths. Every score has the integer numerator
\[ BC_x(\mu) =\sum_{P\in\operatorname{supp}(\mu)} a_P(B/b_P)\hat d(P,x). \]
Because \(0\leq C_x(\mu)\leq D\), this numerator is at most \(BD\), and therefore has polynomial bit length. Comparing these numerators determines the winner exactly.

Thus both constructing the finite evaluation procedure and evaluating its winner are polynomial-time operations in \(m,\tau,L\). The procedure is optimal from every initial distribution, including the supplied \(\mu^0\).

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the stated deterministic mass-evolution problem. The proposed policy is optimal from every initial distribution and can be constructed and evaluated in polynomial time under the supplied full-table encoding. No substantive or minor gaps were found.

• Domain and transition probabilities.

Since \(m\geq2\), there are distinct rankings. An integer-valued metric therefore has \(D\geq1\). For rankings topping \(x\), the unique zero-distance minimizer is the ranking itself, so \(\hat d(P,x)=0\). For other rankings, \(1\leq\hat d(P,x)\leq D\).

The discount assumption implies \(0<\gamma<1\) and
\[ 1-\gamma<\frac1D\leq\frac1{\hat d(P,x)}\leq1. \]
Thus the stated bound \(0<q(P,x)\leq1\) is correct wherever the transfer formula is used. No division by zero occurs, since that formula applies only to rankings not topping the action. Simultaneous transfers preserve nonnegative mass and total mass, including when several transfers share a destination.

• The metric inequality (1).

Every application of the triangle inequality is valid: \(P\), \(S(P,b)\), and \(S(S(P,b),x)\) are rankings in the metric’s domain. The final ranking tops \(x\), so it is an admissible candidate in the minimization defining \(\hat d(P,x)\). Consequently, (1) follows exactly as written.

This also covers \(P[1]=b\), because then \(S(P,b)=P\). The proof requires only that the selectors attain their respective minima; lexicographic tie-breaking makes them well-defined.

• The reduction identity (2).

For every ranking included in \(\Delta_b\), direct substitution gives
\[ \gamma q(P,b)\hat d(P,b) =1-(1-\gamma)\hat d(P,b). \]
Summing with weights \(\mu_P\) gives (2): the first term sums to \(c(\mu,b)\), and rankings topping \(b\) contribute zero to \(C_b(\mu)\). The signs and discount factors are correct.

• The update bounds (3)–(6).

The displayed formula for \(C_x(F_b(\mu))\) correctly accounts for both outgoing and incoming mass, including merged destinations. Rearranging (1) gives
\[ \hat d(S(P,b),x)-\hat d(P,x)\geq-\hat d(P,b), \]
which establishes (3) because all transfer weights are nonnegative.

When \(x=b\), each destination has distance zero to the set of rankings topping \(b\), so (4) is exact. Taking the minimum over \(x\) in (3) establishes (5), since \(\Delta_b(\mu)\) is independent of \(x\).

If \(C_b(\mu)=\Phi(\mu)\), (4) supplies a candidate attaining the lower bound in (5). This proves (6) and the assertion that the chosen minimizer remains a minimizer after its own update.

• The optimality inequality (7).

Substitution of (2) into (5) yields precisely
\[ c(\mu,b)+\gamma\Phi(F_b(\mu)) \geq\Phi(\mu)+(1-\gamma)\bigl(C_b(\mu)-\Phi(\mu)\bigr). \]
The final term is nonnegative, and it is strictly positive for a nonminimizing action because \(1-\gamma>0\). For a minimizing action, (6) supplies the equality needed throughout (7).

• Infinite-horizon passage and attainment.

Multiplication by \(\gamma^t\) and summation correctly telescope to (8). Every state remains a probability distribution, so \(0\leq\Phi(\mu^T)\leq D\). Hence \(\gamma^T\Phi(\mu^T)\) tends to zero. The discounted loss series also converges because each one-period loss lies in \([0,1]\).

The fixed-order minimizer rule is a well-defined deterministic stationary policy. Its actions attain equality at each step, establishing discounted loss exactly \(\Phi(\mu^0)\). Subtracting this loss from \(1/(1-\gamma)\) proves the asserted value formula.

• The complete policy characterization.

Any stationary policy selecting a minimizer at every distribution attains the same stepwise equalities, so the sufficiency claim covers every such policy.

Conversely, at a distribution where a policy selects a nonminimizer, the lower bound on all continuations and the strict inequality in (7) imply strictly excessive loss. Because optimality is required from every initial distribution, this proves necessity at every state. The argument applies to arbitrary real distributions; rationality is needed only for the computational evaluation claim.

• Polynomial construction and exact evaluation.

With an explicitly supplied table, its \(N^2\) entries are part of the input length. Scanning them and computing the \(Nm\) distance minima therefore requires polynomial time and space in the stated encoding. The additional work on ranking labels is polynomial in \(m\) per entry.

Evaluation uses \(m\tau\) score contributions. The proposed common denominator has bit length bounded by the aggregate denominator encoding length. Each score numerator is an integer between zero and \(BD\), so its bit length is polynomial in \(L\). The products, exact divisions, additions, and comparisons consequently have polynomial bit complexity.

Winner evaluation requires neither computing future trajectories nor constructing transition selectors. The finite procedure implementing the score rule therefore satisfies the requested construction and evaluation requirements.

The finite-electorate theorem is mentioned only for comparison. No step relies on it or identifies deterministic mass evolution with stochastic evolution, so there is no unverified external theorem application.

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩