Answer: \(\mathrm P\)
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a majoritarian Condorcet extension that refines BP and is still P K-strategyproof. As a consequence, BP is not even a finest majoritarian Condorcet ex- tension satisfying P K-strategyproofness.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For \(m=5\), \(A\) fixed, and a generic society \(\mu\in\Delta(\mathcal L(A))\), decide whether there exists a neutral rule \(F_\infty:\Delta(\mathcal L(A))\to2^A\setminus\{\varnothing\}\) depending only on the strict pairwise-majority tournament \(T_\mu\), selecting the unique Condorcet winner when one exists, satisfying \(F_\infty(\mu)\subseteq BP(T_\mu)\), and obeying \(\neg(F_\infty(\mu')P_t^K F_\infty(\mu))\) for every true type \(t\) and mass transfer \(\mu'=\mu-\delta e_t+\delta e_{t'}\) with \(0<\delta\leq\mu_t\).
Fix an alternative set \(A\) with \(m=5\), and let \(\mathcal L(A)\) denote its strict linear orders. Let \(D\subseteq\Delta(\mathcal L(A))\) consist of societies with no pairwise-majority ties; masses are nonnegative and sum to \(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 \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. State running times in \(m,\tau,L\), with \(m=5\) fixed.
For \(\nu\in D\), define \(aT_\nu b\) precisely when \(\sum_{t:a\succ_t b}\nu_t>\sum_{t:b\succ_t a}\nu_t\).
For a tournament \(T\), \(BP(T)\) is the support of the unique equilibrium strategy of the symmetric zero-sum game with actions \(A\) and payoff \(1\) for beating the opponent in \(T\), \(-1\) for losing, and \(0\) for identical actions.
For nonempty sets \(X,Y\), define \(XR_t^K Y\) by \(x\succeq_t y\) for every \(x\in X,y\in Y\), and let \(P_t^K\) be its asymmetric part; \(\succeq_t\) is the reflexive closure of \(\succ_t\).
Given \(\mu\in D\), decide whether there exists \(F:D\to2^A\setminus\{\varnothing\}\) depending only on \(T_\nu\), neutral under every permutation of \(A\), with \(F(\nu)\subseteq BP(T_\nu)\) for every \(\nu\in D\), and uniquely selecting any Condorcet winner.
Require \(\neg(F(\mu')P_t^K F(\mu))\) for every \(t\) with \(\mu_t>0\), every reported order \(t'\in\mathcal L(A)\), and every real \(0<\delta\leq\mu_t\) for which \(\mu'=\mu-\delta e_t+\delta e_{t'}\in D\); \(e_t\) is the unit mass at type \(t\).
Is this rule-existence decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite electorates with strict rankings and odd voter counts, a neutral majoritarian Condorcet extension strictly refining \(BP\) and satisfying Kelly-strategyproofness exists on \(m=5\) alternatives. [Brandt–Geist](https://doi.org/10.1613/jair.4959).
No source establishing the exact continuous decision problem above was identified in the searches performed.
The decision problem is in \(\mathrm P\) for the fixed number \(m=5\) of alternatives.
The proof uses the manipulation requirement exactly as stated: it applies at the supplied society \(\mu\). The rule’s dependence on majority tournaments, neutrality, bipartisan-set containment, and Condorcet-winner selection apply throughout \(D\).
Two reductions make the decision finite and tractable:
Write \(\mathcal T_m\) for the labelled tournaments on \(A\). Its cardinality is \(N=2^{\binom m2}\), so \(N=1024\) when \(m=5\).
Every tournament belongs to the majority domain. To prove this, fix a tournament \(T\). For each edge \(aTb\), list the remaining alternatives as \(c_1,\ldots,c_{m-2}\), and use the two rankings
\(a\succ b\succ c_1\succ\cdots\succ c_{m-2}\)
and
\(c_{m-2}\succ\cdots\succ c_1\succ a\succ b\).
Their combined majority margin is \(2\) for \(a\) against \(b\), and zero for every other pair: comparisons involving a remaining alternative cancel between the two rankings, as do comparisons between remaining alternatives. Combining these two rankings for every edge of \(T\), and assigning equal mass to all occurrences, therefore realizes exactly \(T\), with no majority ties.
Consequently, a rule depending only on the majority tournament is equivalent to a table
\(f:\mathcal T_m\longrightarrow 2^A\setminus\{\varnothing\}\),
with \(F(\nu)=f(T_\nu)\).
Let \(G\) be the permutation group of \(A\). Neutrality means \(f(\pi T)=\pi f(T)\) for every \(T\in\mathcal T_m\) and \(\pi\in G\).
For a tournament \(R\), define its automorphism group by
\(\operatorname{Aut}(R)=\{\pi\in G:\pi R=R\}\).
A neutral table must choose a set \(Y=f(R)\) invariant under this group: \(\pi Y=Y\) for every \(\pi\in\operatorname{Aut}(R)\).
Conversely, any such invariant choice determines a neutral table on the entire orbit of \(R\), by setting \(f(\pi R)=\pi Y\). This is well-defined: if \(\pi R=\sigma R\), then \(\sigma^{-1}\pi\in\operatorname{Aut}(R)\), and hence \(\pi Y=\sigma Y\).
Let \(M_T\) be the payoff matrix of \(T\). Its equilibrium strategy is the unique vector in
\(\mathcal E_T=\{p\in\mathbb R^m:p\geq 0,\ \sum_a p_a=1,\ M_Tp\leq 0\}\).
Indeed, skew-symmetry gives \(p^{\mathsf T}M_Tp=0\). The inequality \(M_Tp\leq 0\) says every pure strategy earns at most zero against \(p\). Also, for every mixed strategy \(q\),
\(p^{\mathsf T}M_Tq=-(M_Tp)^{\mathsf T}q\geq 0\).
Thus \(p\) guarantees zero and prevents its opponent from earning more than zero, so it is an equilibrium strategy. The converse follows from the same equilibrium inequalities.
The stated uniqueness allows exact computation by finite rational linear algebra. There are \(2m\) inequalities, besides the normalization equality. At the unique feasible point, their active equations, together with normalization, have rank \(m\). Otherwise a nonzero direction preserving all active equations would permit sufficiently small perturbations in both directions while preserving the inactive inequalities, contradicting uniqueness. Therefore, enumerating choices of \(m-1\) active inequalities, solving the resulting systems, and checking feasibility finds the equilibrium exactly. Its positive coordinates determine \(BP(T)\).
Relabelling the payoff matrix relabels its unique equilibrium strategy, so
\(BP(\pi T)=\pi BP(T)\).
If \(c\) is a Condorcet winner, its unit vector satisfies the equilibrium inequalities: the coordinate for \(c\) is zero and every other coordinate of \(M_Te_c\) is \(-1\). Uniqueness therefore gives \(BP(T)=\{c\}\). Thus nonempty bipartisan-set containment already enforces the required Condorcet-winner selection.
For each tournament representative \(R\), define its candidate sets by
\(\mathcal C(R)=\{Y:\varnothing\neq Y\subseteq BP(R),\ \pi Y=Y\text{ for every }\pi\in\operatorname{Aut}(R)\}\).
There are at most \(2^m-1\) candidates. The preceding arguments show that the globally admissible neutral tables are precisely the independent choices of one candidate for each tournament orbit, transported by permutations.
We now determine, for each supported true type \(t\) and destination tournament \(T\), whether some permitted report and transfer reach \(T\).
Fix an enumeration of \(A\), and consider pairs \(a<b\). Define \(s_t(a,b)=1\) if \(a\succ_t b\), and \(s_t(a,b)=-1\) otherwise.
Write each supplied mass as \(\mu_t=p_t/q_t\). Let \(Q\) be the product of the supplied denominators, and put \(w_t=Q\mu_t\). These are positive integers, and \(\sum_t w_t=Q\). The integer majority margin for a pair is
\(g_{ab}=\sum_{t:\mu_t>0}w_t s_t(a,b)\).
Hence its normalized margin is \(g_{ab}/Q\).
Fix a true type \(t\), a report \(t'\), and a transfer \(\delta\). Put
\(k_{ab}=s_{t'}(a,b)-s_t(a,b)\in\{-2,0,2\}\).
After the transfer, the margin becomes \(g_{ab}/Q+k_{ab}\delta\).
For a proposed destination tournament \(T\), let \(\varepsilon_{ab}(T)=1\) if \(aTb\), and \(\varepsilon_{ab}(T)=-1\) otherwise. Set \(z=2Q\delta\). The transfer reaches exactly \(T\), with no ties, precisely when
\(0<z\leq 2w_t\)
and, for every pair,
\(\varepsilon_{ab}(T)(2g_{ab}+k_{ab}z)>0\).
These conditions also ensure that the resulting society belongs to \(D\): masses remain nonnegative because \(\delta\leq\mu_t\), their sum remains one, and all pairwise margins are nonzero.
The inequalities admit a particularly simple exact test:
Every \(h_{ab}\) is an integer because nonzero \(k_{ab}\) equals \(2\) or \(-2\).
Let \(\ell\) be the maximum of zero and all strict lower bounds. Let \(u\) be the minimum of \(2w_t\) and all strict upper bounds. Provided the zero-slope conditions hold, feasibility is equivalent to \(\ell<u\).
For necessity, every feasible \(z\) satisfies \(z>\ell\) and \(z\leq u\). For sufficiency, \(z=(\ell+u)/2\) satisfies every bound, including the possibly weak bound \(z\leq 2w_t\).
Thus the test handles the real quantifier exactly. In fact, whenever a real transfer exists, a rational transfer exists.
Define the Boolean relation
\(E(t,T)\Longleftrightarrow\text{some report }t'\text{ and some permitted transfer reach }T\).
Compute it by applying the interval test to all \(m!\) reports and all \(N\) destination tournaments.
For any tournament table \(f\), the required manipulation condition is now exactly
\(\neg\bigl(f(T)P_t^K f(T_\mu)\bigr)\)
for every supported \(t\) and every \(T\) with \(E(t,T)\).
This equivalence holds because the preference comparison uses the true order \(t\), while the rule’s outcome depends only on the destination tournament. Consequently, report and transfer details can be discarded after reachability is established.
We use the specified asymmetric Kelly relation literally: \(YP_t^KX\) holds exactly when \(YR_t^KX\) holds and \(XR_t^KY\) does not. Both relations can be checked with at most \(m^2\) comparisons of alternatives.
Let \(T_0=T_\mu\). Enumerate tournament orbits, choosing \(R_0=T_0\) as the representative of its orbit and representatives \(R_1,\ldots,R_{r-1}\) for the others.
For each tournament \(T\), store its orbit index \(j(T)\) and a permutation \(\pi_T\) satisfying \(T=\pi_TR_{j(T)}\).
Compute all candidate lists \(\mathcal C(R_j)\), and the reachability relation \(E\).
For each \(X\in\mathcal C(R_0)\), perform the following checks.
Source-orbit check. Require
\(\neg\bigl((\pi_TX)P_t^KX\bigr)\)
for every supported \(t\) and every reachable \(T\) in the orbit of \(T_0\).
Other-orbit checks. For each \(j\neq 0\), seek a candidate \(Y_j\in\mathcal C(R_j)\) such that
\(\neg\bigl((\pi_TY_j)P_t^KX\bigr)\)
for every supported \(t\) and every reachable \(T\) in that orbit.
Accept if some \(X\) passes the source-orbit check and every other orbit has a passing candidate. Otherwise reject.
The other-orbit checks are independent because every manipulation constraint compares its destination outcome with the single source outcome \(X=f(T_0)\). No such constraint compares outcomes from two different destination orbits.
Suppose the algorithm accepts \(X\) and candidates \(Y_j\). Set \(Y_0=X\), and define
\(f(T)=\pi_TY_{j(T)}\), \(F(\nu)=f(T_\nu)\).
Automorphism invariance makes this definition well-defined and neutral. Each chosen set is nonempty and contained in its representative’s bipartisan set. Bipartisan-set equivariance therefore gives \(f(T)\subseteq BP(T)\) for every tournament. Condorcet winners are selected uniquely by the singleton property proved above.
Now consider any deviation quantified in the task, with true type \(t\) and destination tournament \(T\). Its existence implies \(E(t,T)\). The applicable orbit check gives
\(\neg\bigl(f(T)P_t^KX\bigr)\).
Because \(f(T_0)=X\), this is exactly the required absence of a profitable deviation. Thus the constructed rule satisfies every condition.
Conversely, suppose a required rule exists, and let \(f\) be its tournament table.
Neutrality and bipartisan-set containment imply \(f(R_j)\in\mathcal C(R_j)\) for every representative. Take \(X=f(T_0)\) and \(Y_j=f(R_j)\).
Whenever \(E(t,T)\) holds, there is an admissible deviation reaching \(T\). The assumed manipulation condition implies
\(\neg\bigl(f(T)P_t^KX\bigr)\).
Neutrality gives \(f(T)=\pi_TY_{j(T)}\). Therefore \(X\) passes the source-orbit check, and each \(Y_j\) passes its other-orbit check. The algorithm accepts.
This proves both directions.
Let \(N=2^{\binom m2}\), \(H=m!\), and \(S=2^m-1\).
The common denominator \(Q\), the integers \(w_t\), and the margins \(g_{ab}\) have bit length \(O(L)\): the sum of the supplied denominator bit lengths is bounded by \(L\), and the masses sum to one.
The reachability computation uses \(O(\tau HNm^2)\) exact integer operations on numbers of \(O(L)\) bits. Computing the scaled masses and margins also takes polynomial time without expanding masses into voters.
Tournament orbit construction uses \(O(HNm^2)\) elementary operations. Candidate construction enumerates at most \(S\) subsets per representative. Across all candidate source choices, the manipulation checks require \(O(S^2\tau Nm^2)\) preference comparisons: summing destination counts across orbits gives \(N\).
The bipartisan-set computation enumerates at most \(2^{2m}\) systems per tournament. Their coefficients belong to \(\{-1,0,1\}\), so exact linear-system computation and feasibility checking have bit complexity polynomial in \(m\), independent of \(L\).
A conservative bound for the complete algorithm is
\(O\!\left(2^{\binom m2+2m}\,m!\,m^{10}\,(\tau+1)(L+1)^2\right)\)
bit operations. The polynomial factor in \(m\) accommodates exact linear algebra and the remaining finite-table operations.
With \(m=5\) fixed, this becomes \(O((\tau+1)(L+1)^2)\), hence is polynomial in the support-encoded input length. Also, \(\tau\leq 5!=120\).
The continuous rule-existence problem is therefore polynomial-time solvable. This classification follows directly from the specified model and does not require extending the finite-electorate existence theorem.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the stated decision problem is in \(\mathrm P\) for fixed \(m=5\). The algorithm handles real-valued deviations exactly and correctly enforces neutrality across the entire domain. I found no major or minor mathematical issues.
The count \(\lvert\mathcal T_m\rvert=2^{\binom m2}\) is correct, giving \(1024\) labelled tournaments for \(m=5\).
The tournament-realization construction is valid. For each desired edge \(aTb\), both displayed rankings place \(a\) above \(b\). Every other comparison cancels:
Thus this pair contributes margin \(2\) only to the designated edge. Combining the pairs and normalizing their masses realizes the desired tournament without ties. Repeated rankings can simply have their masses aggregated.
Consequently, every tournament occurs in \(D\), and a tournament-dependent rule is indeed equivalent to the stated finite table.
The characterization of neutral tables by automorphism-invariant choices on orbit representatives is also correct. If \(\pi R=\sigma R\), then \(\sigma^{-1}\pi\) fixes \(R\), so invariance of the chosen set gives \(\pi Y=\sigma Y\). This establishes well-defined transport. The same construction enforces neutrality under every permutation.
The equilibrium inequalities have the correct sign convention. Since \(M_T\) is skew-symmetric, a feasible \(p\) satisfies
\[
p^{\mathsf T}M_Tp=0,\qquad
q^{\mathsf T}M_Tp\leq0,\qquad
p^{\mathsf T}M_Tq\geq0
\]
for every probability vector \(q\). Thus \(p\) is an equilibrium strategy.
Conversely, skew-symmetry forces the game value to be zero, and an equilibrium strategy satisfies \(M_Tp\leq0\). The uniqueness used here is expressly supplied in the problem’s definition of \(BP\), rather than being an unsupported external theorem.
The exact linear-algebra computation is justified. If normalization and all active inequalities had rank below \(m\), a nonzero direction preserving those equations would exist. A sufficiently small displacement in either direction preserves every inactive inequality because each has positive slack. This would contradict uniqueness.
Therefore normalization can be completed to a rank-\(m\) system using \(m-1\) active inequalities. Enumerating these systems, solving the nonsingular ones, and checking feasibility finds the unique equilibrium exactly.
Relabelling preserves the equilibrium inequalities and hence transports the unique equilibrium and its support. The claimed equivariance of \(BP\) follows.
For a Condorcet winner \(c\), the calculation \(M_Te_c\leq0\) is correct: its coordinates are zero at \(c\) and \(-1\) elsewhere. Consequently \(BP(T)=\{c\}\). Nonempty containment therefore already enforces unique Condorcet-winner selection.
The candidate lists precisely express all remaining global restrictions. Choices for distinct tournament orbits are independent until the manipulation constraints are imposed.
The scaling is correct. With \(Q\) the product of input denominators, each \(w_t=Q\mu_t\) is an integer, and the normalized majority margin is \(g_{ab}/Q\).
A transfer changes that margin to
\[
\frac{g_{ab}}Q+k_{ab}\delta.
\]
Substituting \(z=2Q\delta\) and multiplying by \(2Q>0\) gives exactly
\[
\varepsilon_{ab}(T)(2g_{ab}+k_{ab}z)>0.
\]
The permitted transfer range becomes \(0<z\leq2w_t\).
These conditions enforce all required domain restrictions: mass nonnegativity, total mass one, and absence of majority ties. They also cover reporting the original order.
The interval test is correct:
The treatment of strict endpoints is sound. Every feasible \(z\) satisfies \(z>\ell\) and \(z\leq u\), implying \(\ell<u\). Conversely, when \(\ell<u\), the midpoint lies strictly above every lower bound, strictly below every strict upper bound, and below the permitted weak upper bound.
Thus the real quantifier is handled exactly; no approximation or discretization assumption is introduced.
The relation \(E(t,T)\) has the correct quantifiers: it existentially aggregates reports and transfer amounts separately for each supported true type and destination tournament.
This aggregation loses no relevant information. Once \(t\) and \(T\) are fixed, the outcome comparison depends only on \(t\), \(f(T)\), and \(f(T_\mu)\). Therefore universally excluding profitable deviations is equivalent to checking every reachable destination.
The asymmetric Kelly relation is used exactly as defined:
\[
YP_t^KX
\quad\Longleftrightarrow\quad
YR_t^KX\ \text{and}\ \neg(XR_t^KY).
\]
The stated comparison bound is correct up to a constant factor: checking both directions requires at most \(2m^2\) alternative comparisons.
The source-orbit check is necessary because neutrality links every outcome in the orbit of \(T_\mu\) to the chosen source set \(X\).
For each other orbit, all its constraints involve its candidate set and the same fixed source outcome \(X\). No constraint couples two distinct destination orbits. Therefore the independent candidate checks are sufficient.
Both correctness directions are complete:
An orbit with no reachable destination imposes no manipulation restriction, while its candidate requirement still enforces the global conditions. This case is handled correctly.
The integer bit-length claim is valid. The bit length of \(Q\) is bounded by the sum of input denominator lengths. Moreover, \(w_t\leq Q\), \(\lvert g_{ab}\rvert\leq Q\), and all interval endpoints have \(O(L)\) bits.
The reachability enumeration and manipulation-check counts are correct. Exact arithmetic on these integers is polynomial in \(L\). Tournament enumeration, automorphism testing, candidate enumeration, and equilibrium computation depend only on \(m\).
The displayed conservative bound accommodates these operations. For fixed \(m=5\), it yields the claimed polynomial bound \(O((\tau+1)(L+1)^2)\). The observation \(\tau\leq120\) is also correct.
The conclusion addresses the exact local manipulation requirement at the supplied society. It does not rely on the finite-electorate existence theorem. No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.