352 precisely specified entries and 324 recorded connections. Rule-property statuses are axiomatic assertions, not computational complexity labels. Click a computational classification to open its matching results and filter checkboxes on the map.
Entries
Stable Voting
Winner-membership decisions and the distinct search task, with the quantified-formula reduction source.
A polynomial-size quantified-formula construction supplies PSPACE-hardness. A depth-first recursive evaluation stores polynomially many candidate/edge indices, giving membership in PSPACE.
Margin weights are majority differences, not weights attached to voters. The classification here is for the stated distinct-margin domain.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Theorem 5.8 plus Section 2 and Appendix A
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
A polynomial-size quantified-formula construction supplies PSPACE-hardness. A depth-first recursive evaluation stores polynomially many candidate/edge indices, giving membership in PSPACE.
Margin weights are majority differences, not weights attached to voters. The classification here is for the stated distinct-margin domain.
No individual voters in the input; majority margins are not voter weights
Candidates
Variable; not a fixed two-candidate election
Output
Unique by the distinct-margin promise
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Nonempty candidate set. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
One candidate index, O(log(N + 1)) bits; N is the number of candidates.
Reduction convention
Polynomial-time nonadaptive function-oracle reductions: polynomially many valid election queries, all fixed before any winner answers are returned.
The depth-first winner recursion uses polynomial space and outputs one candidate index. Every polynomial-space function with polynomial output can be recovered by asking polynomially many PSPACE predicates for its output length and bits. The original Boolean-election construction converts each predicate to a promised election with two known possible winners. All those elections are prepared nonadaptively, and their returned winners recover the output. For one-call metric reductions, unrestricted winner computation instead has the sharper FP^PSPACE[O(log s)] completeness classification (s is total input length), proved by tournament substitution.
FPSPACE(poly) restricts output length to a polynomial. This result does not claim completeness for functions with exponentially long outputs.
The displayed FPSPACE(poly) completeness allows polynomially many nonadaptive calls. It is not an FPSPACE(poly) one-call metric completeness claim.
A separate one-call theorem classifies this unrestricted winner function as FP^PSPACE[O(log s)]-complete; FPSPACE(log)-completeness is an equivalent useful formulation for its logarithmic output, not an identification of the two function classes.
All voters are unweighted in the ballot encoding; matrix entries are pairwise majority margins, not voter weights.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; H.1–H.2, pp. 50–51; Theorem H.6, p. 52
A polynomial-size quantified-formula construction supplies PSPACE-hardness. A depth-first recursive evaluation stores polynomially many candidate/edge indices, giving membership in PSPACE.
Margin weights are majority differences, not weights attached to voters. The classification here is for the stated distinct-margin domain.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Theorem 4.1 plus Section 2 and Appendix A
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
A polynomial-size quantified-formula construction supplies PSPACE-hardness. A depth-first recursive evaluation stores polynomially many candidate/edge indices, giving membership in PSPACE.
Margin weights are majority differences, not weights attached to voters. The classification here is for the stated distinct-margin domain.
Closed prenex Boolean formula, each variable bound once, with explicit CNF matrix. Variables, clauses and quantifier alternations are unbounded.
Ballots
Not applicable
A complete quantified truth problem remains PSPACE-complete in CNF: introduce Tseitin variables existentially after the original prefix. For each complete assignment to the original variables, the CNF has an extension exactly when the original matrix is true.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Construction 3.1 and Theorem 4.1
Tally margins. For each rival q, test whether q has a positive margin over p and p has no return path to q whose edges all meet that margin. Reject if any such defeat exists. Threshold reachability gives a polynomial-time algorithm; all-pairs max–min paths give O(m³) comparisons after tallying.
The full Split Cycle winner set can contain several candidates. Membership is a necessary condition for Stable Voting membership, not an equivalent decision problem.
Majority margins are graph edge labels, not individual voter weights.
Candidates
Any nonempty finite candidate set; candidate count is part of the input.
Output
Membership in the full undefeated set; all undefeated candidates win
Ties
Pairwise ties are not victories; a weakest edge tied with another edge on a cycle is removed as well.
Input
Nonempty candidate set, explicit skew-symmetric integer matrix with zero diagonal, and designated candidate p. Entries use binary encoding.
Ballots
No ballot list is supplied. The rule is applied directly to the margin-weighted graph.
For every rival q with M(q,p)>0, test reachability from p to q using edges of weight at least M(q,p). Candidate p wins exactly when every such return path exists. An all-pairs max–min recurrence needs O(m³) comparisons of input-sized integers.
Zero and repeated margins are allowed. Unlike the Stable Voting hardness nodes, this node imposes no distinct-margin promise.
The graph definition needs only the ordering of margins. It does not require an explicit ballot realization.
Any nonempty finite candidate set; at least one voter
Output
p must be the only winner
Ties
At the first majority level retain maximum support. If nobody reaches a majority, use maximum total approval; tied maxima all win.
Input
Explicit nonempty list of ranked approved subsets of a specified nonempty candidate set C, and designated p∈C. Empty and full approved subsets are allowed.
Ballots
Ranked approved subsets; unlisted candidates are disapproved
Scan cumulative approved-rank counts for support from strictly more than half of all voters. If no candidate reaches that threshold, use total approval counts. Accept exactly when p alone attains the applicable maximum.
P is an algorithmic upper bound, not a completeness classification.
Any nonempty finite candidate set; at least one voter
Output
p may tie for maximum score
Ties
Pairwise wins score 1, pairwise ties ½, losses 0; all maximum-total candidates win
Input
Explicit nonempty list of strict complete rankings of a common nonempty candidate set C, and designated p∈C. The pairwise-tie parameter is fixed at α=1/2, not part of the input.
Ballots
Strict complete rankings
Compute every pairwise majority. Using integer doubled scores, add 2 per win and 1 per tie, sum, and accept exactly when p attains the maximum.
P is an algorithmic upper bound, not a completeness classification.
Compute N(a,b), take min over b≠a for each a, and select the maximum. For a sole candidate, accept immediately without taking a minimum over an empty set.
Hardness already holds with four voters. Ask all disagreement thresholds for the original profile and its p-deleted residual in parallel. Compare the overall optimum with the best p-first cost. A singleton candidate set is answered directly.
Theorem 6.5 establishes Δ₂ᵖ-completeness. Binary search uses polynomially many sequential NP queries even when total disagreement is exponentially large.
Equivalent here to binary-weighted Kemeny winner determination. This does not justify expanding exponentially many ballots in a polynomial-time reduction.
An ordering is a polynomial certificate. NP-hardness follows from Slater score threshold by a two-ballot-per-arc construction explained on the connecting edge.
Compute the optimum with an NP threshold oracle, then choose successive first candidates whose fixed-prefix cost plus residual optimum still equals the optimum.
This label is an upper bound only. No function-class completeness claim is made. The score-threshold edge separately gives decision hardness via a solver for this search task.
Explicit nonempty finite tournament vertex set; no voter list
Output
Threshold for an ordering, not Slater-winner membership
Ties
No pairwise ties; multiple optimum orderings allowed
Input
Explicit complete asymmetric tournament and nonnegative integer k.
Ballots
Not applicable; one directed edge for every pair of candidates
Theorem 3 reduces MAXSAT to an agreement threshold t. For M=m(m−1)/2 tournament arcs, at least t agreements is equivalent to at most M−t disagreements. A guessed ordering is polynomially checkable.
Slater counts pairwise contest disagreements. Kemeny weights them by ballot support; these are different objectives.
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean winner-membership answer.
Ties
No pairwise ties. Multiple optimum rankings and multiple selected candidates are allowed; no final tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete asymmetric tournament encoded by its adjacency matrix, and a designated candidate p. No edge weights or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
Theorem 3 gives Θ₂ᵖ-hardness under a polynomial-time many-one reduction from the maximum-Hamming-weight satisfying-assignment problem of Lemma 2. For the upper bound, query all disagreement thresholds for T and T without p nonadaptively. If d⁻(p) is the number of candidates beating p, the best p-first ranking has cost d⁻(p) + OPT(T−p). Candidate p wins exactly when that equals OPT(T). The single-candidate case is answered directly.
The NP-complete ranking-disagreement threshold is a different decision task from Θ₂ᵖ-complete winner membership.
The source paper orients arcs toward the winner. The atlas reverses all arcs to its standard winner-to-loser convention; this is an encoding convention, not a different rule.
Exactly seven explicit voters, each with weight 1.
Candidates
Variable nonempty candidate set; only the number of voters is fixed.
Output
One Boolean winner-membership answer.
Ties
Seven strict ballots exclude majority ties. All optimum-ranking winners are retained without tie-breaking.
Input
Explicit candidates, exactly seven unweighted strict complete ballots, and a designated candidate p.
Ballots
Exactly seven strict complete rankings on the same candidate set.
Theorem 5 refines the hardness construction using Lemma 4 and explicitly constructs seven linear orders realizing each tournament. Its designated membership answer is preserved. Tallying the majority tournament followed by the parallel-NP upper-bound algorithm places the profile problem in Θ₂ᵖ.
With only c! ballot types, enumerate how many voters of each type move p upward by each possible number of positions. This is polynomial in the explicit voter count for fixed c.
Guess the retained subset for NP membership. Equation (2.1) gives score(c)=2κ(S)+1, transferring Set Packing threshold hardness after adjoining three disjoint dummy sets.
The threshold direction is ≥ because this node counts retained voters, not deletions. Zero score is used when no nonempty feasible subset exists.
One explicit score ballot per voter, all voters of weight 1.
Candidates
Variable nonempty finite candidate set; at least one explicit voter.
Output
One Boolean membership answer.
Ties
Equal maximum sums produce co-winners. No final tie-breaking or requirement to use either scale endpoint.
Input
Explicit rational score matrix with entries in [0,1], a nonempty candidate set, and designated p.
Ballots
For each voter and candidate, an explicit rational number in [0,1], encoded by binary numerator and positive binary denominator.
Add each candidate’s rational scores exactly and compare the totals. Denominator products have bit length at most the sum of the input denominator lengths, so exact rational addition and comparison take polynomial time in the explicit binary input length. The computation uses submitted scores; interpreting them as true utilities is an additional assumption for property comparisons.
Native score ballots are different from ordinal rankings. No interpersonal-utility or truthful-report claim is needed to calculate their winner.
Formal utilitarianism and range voting Marcus Pivato · 2014 · Primary article abstract and rule definition; explicit rational-encoding bound derived here
Every voter has weight 1 and is listed explicitly.
Candidates
Any nonempty finite candidate set; the number of candidates is variable.
Output
One Boolean winner answer.
Ties
At each round, eliminate one minimum-Borda candidate. If several tie, eliminate the lowest-priority one. Retain the same fixed priority in every round.
Input
Explicit nonempty list of unweighted strict complete ballots, a designated candidate p, and a fixed strict candidate-priority order supplied as part of the instance.
Ballots
Strict complete rankings over the same candidate set.
Restrict all rankings to the remaining candidates, recompute Borda scores, and delete one minimum-score candidate using the fixed priority. At most m−1 rounds occur, each polynomial in the explicit ballot length. This computes a single determined winner; it does not search over possible tie orders.
Manipulation of Nanson’s and Baldwin’s Rules Nina Narodytska, Toby Walsh, Lirong Xia · 2011 · Preliminaries and rule definitions, pp.1–2; complexity bound is the explicit simulation argument
Every voter has weight 1 and is listed explicitly.
Candidates
Any nonempty finite candidate set; the number of candidates is variable.
Output
One Boolean winner answer.
Ties
Delete all candidates strictly below the average Borda score simultaneously. If all remaining scores are equal, select the highest-priority candidate and stop.
Input
Explicit nonempty list of unweighted strict complete ballots, a designated candidate p, and a fixed strict candidate-priority order supplied as part of the instance.
Ballots
Strict complete rankings over the same candidate set.
Recompute the Borda totals on each remaining set. With k candidates and n unweighted ballots, their average is n(k−1)/2, so exact integer comparisons with 2 times each score suffice. If scores are not all equal, at least one candidate lies below average and at least one survives. Otherwise apply the fixed priority. Hence at most m−1 deletion rounds are needed.
This is strict-below-average Nanson. It does not classify the rule that also removes candidates equal to the average.
Manipulation of Nanson’s and Baldwin’s Rules Nina Narodytska, Toby Walsh, Lirong Xia · 2011 · Preliminaries and rule definitions, pp.1–2; complexity bound is the explicit simulation argument
decision · Winner determination
Cup (fixed bracket) · Winner in a fixed bracket · weighted
Positive binary integer voter weights, with one explicit strict ranking per voter.
Candidates
Variable nonempty candidate set. The supplied binary tree has one leaf per candidate and leaf depths differing by at most one.
Output
One Boolean winner answer.
Ties
At each internal node, compare the two surviving candidates by weighted majority. If their contest ties, the higher candidate in the fixed priority advances.
Input
Explicit weighted strict-ranking profile, target p, fixed candidate priority and known balanced binary bracket, with each candidate occurring exactly once among the leaves.
Ballots
Strict complete rankings; each is supplied with its positive binary integer weight.
Tally pairwise weighted majority totals using binary arithmetic and evaluate the bracket from the leaves to the root. The bracket has m−1 internal matches; each tally and comparison uses polynomial bit complexity. Voter weights are added directly rather than expanded into repeated ballots.
The bracket is fixed before voting. This entry does not allow choosing or randomizing the bracket.
TEQ, Banks, the uncovered set, and the top cycle on strict tournaments, plus Smith and Schwartz with explicit pairwise ties. Membership and output tasks retain their own bounds.
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete asymmetric tournament encoded by its adjacency matrix, and a designated candidate p. No edge weights or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
Theorem 2 maps each 3SAT formula to a tournament with a designated candidate that belongs to TEQ exactly when the formula is satisfiable. Compute TEQ(S) by recursively evaluating TEQ of each candidate’s dominator set, then forming the relation x → y exactly when x is selected from y’s dominators. Return the union of all source strongly connected components of that relation. Every recursive set is smaller. With at most m frames, each storing O(m²) bits and polynomial graph-algorithm workspace, this uses polynomial space. It does not assume a unique minimal retentive set.
NP-hard: Polynomial-time many-one reductions
PSPACE: Upper bound only: depth-first evaluation of the recursive definition
The cited result supplies NP-hardness and a polynomial-space algorithm. It does not establish NP-completeness or PSPACE-completeness.
TEQ may select several candidates. Returning one member need not decide whether another designated candidate is selected.
Exactly seven explicitly listed voters, each with weight 1.
Candidates
Variable nonempty candidate set; fixing seven voters does not fix the number of candidates.
Output
One Boolean membership answer.
Ties
Seven strict ballots ensure every pairwise majority contest has a winner. TEQ co-winners are all retained; no final tie-breaking.
Input
Nonempty explicitly listed candidates, exactly seven unweighted strict complete ballots, and a designated candidate p.
Ballots
Exactly seven strict complete rankings over the same candidate set.
Lemma 11 transforms 3SAT into Ordered3SAT. Section 7.2 constructs a tournament whose designated c₀ is selected exactly when the formula is satisfiable. Theorem 3 realizes these tournaments by exactly seven strict unweighted ballots. This proves designated-candidate membership NP-hard for this profile model. Tally the majority tournament in polynomial time, then apply the polynomial-space recursive algorithm.
NP-hard: Polynomial-time many-one reductions
PSPACE: Upper bound: majority tally followed by recursive TEQ evaluation
The cited result supplies NP-hardness and a polynomial-space algorithm. It does not establish NP-completeness or PSPACE-completeness.
TEQ may select several candidates. Returning one member need not decide whether another designated candidate is selected.
k-Majority digraphs and the hardness of voting with a constant number of voters Georg Bachmeier, Felix Brandt, Christian Geist, Paul Harrenstein, Keyvan Kardel, Dominik Peters, Hans Georg Seedig · 2019 · Section 2 pp.3–4; Lemma 11 pp.21–22; Section 7.2, especially designated c₀ on p.26 and Theorem 3 pp.27–29, author PDF
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One candidate index in {1,…,m}, encoded in ⌈log₂(m+1)⌉ bits, hence O(log(m+1)) bits.
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m} and a complete asymmetric tournament adjacency matrix. No designated candidate, edge weights, or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
Compute TEQ(S) by recursively evaluating TEQ of each candidate’s dominator set, then forming the relation x → y exactly when x is selected from y’s dominators. Return the union of all source strongly connected components of that relation. Every recursive set is smaller. With at most m frames, each storing O(m²) bits and polynomial graph-algorithm workspace, this uses polynomial space. It does not assume a unique minimal retentive set. Once the vector is computed, return any set bit’s candidate index. The task is a search relation: different valid outputs are allowed. Membership hardness alone does not supply a hardness theorem for this search relation.
Polynomial-space algorithm: Upper bound for a search relation; no completeness claim
This asks for any selected member. Its output need not reveal whether a different designated candidate is selected. No search-hardness claim is inferred from membership hardness.
A computational analysis of the tournament equilibrium set Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair · 2010 · Definition 2 and nonempty tournament-solution convention, pp.3–4, author PDF; elementary algorithmic consequence
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
Exactly m bits: coordinate i equals 1 if and only if candidate i belongs to TEQ(T).
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m} and a complete asymmetric tournament adjacency matrix. The candidate order fixes the output coordinates.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
Compute TEQ(S) by recursively evaluating TEQ of each candidate’s dominator set, then forming the relation x → y exactly when x is selected from y’s dominators. Return the union of all source strongly connected components of that relation. Every recursive set is smaller. With at most m frames, each storing O(m²) bits and polynomial graph-algorithm workspace, this uses polynomial space. It does not assume a unique minimal retentive set. The complete output contains exactly m bits, so the function lies in FPSPACE(poly). A membership instance (T,p) can be solved using one call to this function and reading bit p. Combined with Theorem 2, this gives an NP-hardness lower bound under polynomial-time one-call decision-to-function oracle reduction, not FPSPACE(poly)-completeness. Conversely, m nonadaptive membership calls recover the entire vector.
NP-hard: Polynomial-time one-call oracle reduction from a decision language to this function
FPSPACE(poly) is an upper bound here, not a completeness classification.
The NP-hardness readout concerns returning the entire set, not merely finding one of its members.
A computational analysis of the tournament equilibrium set Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair · 2010 · Definition 2 p.4 and Theorem 2 pp.8–9, author PDF; output and oracle reductions are explicit Atlas consequences
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete asymmetric tournament encoded by its adjacency matrix, and a designated candidate p. No edge weights or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
By Theorem 1, 3SAT reduces to designated Banks membership. For membership in NP, guess a transitive subset with p at its top. Verify transitivity and that no outside candidate can be added while preserving transitivity. Checking single-candidate extensions suffices: every larger transitive superset would contain such an extension.
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete asymmetric tournament encoded by its adjacency matrix, and a designated candidate p. No edge weights or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
In a complete asymmetric tournament, the strongly connected components are totally ordered by dominance. The top cycle is the unique source component, equivalently the candidates that can reach every candidate by directed paths. Compute reachability from p or compute the source strongly connected component in polynomial time. Every Banks member belongs to this component: otherwise the transitive set witnessing its selection lies outside the top component, and any candidate from the top component can be prepended, contradicting maximality.
The top cycle equals the Smith set on this strict tournament domain. No equivalence for arbitrary tied pairwise relations is assumed.
A computational analysis of the tournament equilibrium set Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair · 2010 · Section 2, definition of top cycle pp.3–4 and Definition 1 p.4; explicit polynomial reachability and inclusion derivations
No voter list or voter weights; input contains only pairwise victory directions.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
No pairwise ties. A set of co-winners is retained without tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete asymmetric tournament encoded by its adjacency matrix, and a designated candidate p. No edge weights or succinct representation.
Ballots
No ballots in this encoding. Exactly one directed victory for each unordered candidate pair.
For each rival y that beats p, search for z with p→z→y. If none exists, every candidate z beaten by p is beaten by y, so y covers p. Conversely, a covering y prevents every such length-two path and p cannot reach y directly. Thus membership is equivalent to passing these tests for all y. A double loop over y,z takes O(m²) time on the explicit adjacency matrix.
This is the uncovered set of a complete asymmetric tournament. The several extensions of covering to tied majority relations are different rule models and are not classified here.
No voter list or voter weights. Input supplies the complete pairwise win/tie relation.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
Pairwise ties are allowed and retained. The complete chosen set is the underlying rule output; no final tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete pairwise outcome matrix with M(x,y) in {−1,0,1} and M(y,x)=−M(x,y), and a designated candidate p. A positive entry is a strict pairwise victory and zero is a known tie, not an unspecified comparison. No succinct encoding or margin magnitudes.
Ballots
No ballots in this encoding. Every unordered pair is supplied as a victory in one direction or a known tie.
The majority-or-tie graph has an edge in at least one direction between each pair. Its component graph is therefore totally ordered and has a unique source component S. Every vertex in S strictly beats every vertex outside S: a tie or a reverse win would create an incoming edge. Conversely any nonempty strictly dominant set must contain S, because a directed path from S could not enter it from outside. Thus S is precisely the Smith set. Search from p in the majority-or-tie graph; p belongs to S exactly when all candidates are reached. This takes O(m²) time.
AC⁰: Log-space-uniform constant-depth, polynomial-size circuits; an upper bound
P: Polynomial-time algorithm upper bound on the supplied pairwise table
Known pairwise ties are not incomplete preferences. This is a decision problem on a supplied relation, not a search over ballot completions.
No voter list or voter weights. Input supplies the complete pairwise win/tie relation.
Candidates
An explicitly enumerated nonempty candidate set {1,…,m}; m is unbounded.
Output
One Boolean membership answer.
Ties
Pairwise ties are allowed and retained. The complete chosen set is the underlying rule output; no final tie-breaking.
Input
Nonempty explicitly listed candidates {1,…,m}, a complete pairwise outcome matrix with M(x,y) in {−1,0,1} and M(y,x)=−M(x,y), and a designated candidate p. A positive entry is a strict pairwise victory and zero is a known tie, not an unspecified comparison. No succinct encoding or margin magnitudes.
Ballots
No ballots in this encoding. Every unordered pair is supplied as a victory in one direction or a known tie.
A source strongly connected component has no incoming strict-majority edge and is inclusion-minimal with this property. Any nonempty undominated set contains a source component; minimality therefore makes it exactly one such component. Compute strongly connected components of the supplied strict-majority graph and mark components with no incoming inter-component edge. Candidate p is selected precisely when its component is marked. The adjacency-matrix algorithm takes O(m²) time. The finer bound is Theorem 6: membership is in NL and directed reachability reduces to it by an AC⁰ many-one reduction. The theorem uses explicitly encoded asymmetric dominance graphs; filling every absent unordered pair with a known tie is a constant-depth encoding into the three-valued table used here.
NL-complete: Completeness under AC⁰ many-one reductions
P: Polynomial-time algorithm upper bound on the supplied pairwise table
Known pairwise ties are not incomplete preferences. This is a decision problem on a supplied relation, not a search over ballot completions.
Returning one winner, working with two supplied possible outputs, or returning all single-deletion winners. Function completeness depends on output length and whether one or several oracle calls are allowed.
Stable and related rules
search · Winner determination
Stable Voting · All single-deletion winners · ballots
A vector of N original candidate indices, O(N log N) bits.
Reduction convention
Polynomial-time metric function reduction: one call returns the entire single-deletion winner vector, then polynomial-time postprocessing recovers the source function.
Evaluate the N child elections in polynomial space, reusing workspace, so the output vector is a polynomial-space function with polynomial output. For hardness, each PSPACE output-bit/length predicate is placed in a Boolean-election module. A selector forces that module to continue while present; deleting the selector exposes its true/false winner. Substitution combines the modules into one election whose parent winner q is known. One returned deletion vector recovers every predicate by testing selected coordinates against q. All remaining coordinates are fixed in advance. This is a one-call metric reduction.
This task returns every immediate-child winner. It does not return only the parent winner, and it does not count winners.
For Stable Voting, include child winners even if the parent election would later exclude them in its Split Cycle eligibility test.
Hardness persists when the parent winner q and the selector-deletion positions are supplied. The different child winners need not lie in one common pair.
FPSPACE(poly) restricts output length to a polynomial. No claim is made about exponentially long-output FPSPACE functions.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(iii), p. 27; definition (10), p. 50; Theorem H.7 and Lemmas H.8–H.9, pp. 52–55; Lemma F.3, pp. 45–46
One candidate index, O(log(N + 1)) bits; N is the number of candidates.
Reduction convention
Polynomial-time nonadaptive function-oracle reductions: polynomially many valid election queries, all fixed before any winner answers are returned.
The depth-first winner recursion uses polynomial space and outputs one candidate index. Every polynomial-space function with polynomial output can be recovered by asking polynomially many PSPACE predicates for its output length and bits. The original Boolean-election construction converts each predicate to a promised election with two known possible winners. All those elections are prepared nonadaptively, and their returned winners recover the output. For one-call metric reductions, unrestricted winner computation instead has the sharper FP^PSPACE[O(log s)] completeness classification (s is total input length), proved by tournament substitution.
FPSPACE(poly) restricts output length to a polynomial. This result does not claim completeness for functions with exponentially long outputs.
The displayed FPSPACE(poly) completeness allows polynomially many nonadaptive calls. It is not an FPSPACE(poly) one-call metric completeness claim.
A separate one-call theorem classifies this unrestricted winner function as FP^PSPACE[O(log s)]-complete; FPSPACE(log)-completeness is an equivalent useful formulation for its logarithmic output, not an identification of the two function classes.
All voters are unweighted in the ballot encoding; matrix entries are pairwise majority margins, not voter weights.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; H.1–H.2, pp. 50–51; Theorem H.6, p. 52; Lemmas F.2–F.3, pp. 45–46
search · Winner determination
Stable Voting · All single-deletion winners · margins
No individual voters in the input; majority margins are not voter weights
Candidates
Variable number N ≥ 2; each query removes exactly one candidate
Output
Unique by the distinct-margin promise
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Candidate set with N ≥ 2. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
A vector of N original candidate indices, O(N log N) bits.
Reduction convention
Polynomial-time metric function reduction: one call returns the entire single-deletion winner vector, then polynomial-time postprocessing recovers the source function.
Evaluate the N child elections in polynomial space, reusing workspace, so the output vector is a polynomial-space function with polynomial output. For hardness, each PSPACE output-bit/length predicate is placed in a Boolean-election module. A selector forces that module to continue while present; deleting the selector exposes its true/false winner. Substitution combines the modules into one election whose parent winner q is known. One returned deletion vector recovers every predicate by testing selected coordinates against q. All remaining coordinates are fixed in advance. This is a one-call metric reduction.
This task returns every immediate-child winner. It does not return only the parent winner, and it does not count winners.
For Stable Voting, include child winners even if the parent election would later exclude them in its Split Cycle eligibility test.
Hardness persists when the parent winner q and the selector-deletion positions are supplied. The different child winners need not lie in one common pair.
FPSPACE(poly) restricts output length to a polynomial. No claim is made about exponentially long-output FPSPACE functions.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(iii), p. 27; definition (10), p. 50; Theorem H.7 and Lemmas H.8–H.9, pp. 52–55
search · Winner determination
Stable Voting · Find winner · two possible outputs
No individual voters in the input; majority margins are not voter weights
Candidates
Variable candidate count N ≥ 2. Two possible winning outputs, not a two-candidate election.
Output
Unique by distinct margins, and promised to be one of the two supplied candidates C,D
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Nonempty candidate set. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices; two distinct designated candidates C,D with the promise that the winner belongs to {C,D}
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
One of the supplied candidate indices C,D; one bit of unresolved choice.
Reduction convention
Polynomial-time metric function reductions. Every oracle query supplies two designated candidates and is promised to have its unique winner among them.
A single yes/no PSPACE query asks whether C wins, and the promise determines the winner from that answer. Conversely, the original Boolean-election construction converts the one PSPACE question made by any FP^PSPACE[1] computation into a valid election whose two designated outputs encode the answer. Polynomial-time postprocessing resumes the source computation. Under polynomially many nonadaptive oracle calls, this same promised winner function is FPSPACE(poly)-complete.
FP^PSPACE[1] means polynomial-time function computation with at most one yes/no PSPACE-oracle query.
This is a promise about two possible winners among a variable number of candidates. Fixing the total election size to two is a different, easy problem.
Under polynomial-time nonadaptive oracle reductions the same promised task is FPSPACE(poly)-complete (Theorem H.2).
Under one-call metric reductions this promised task is not claimed FPSPACE(poly)-complete: such a classification would imply P = PSPACE (Corollary H.5).
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; Proposition H.3 and Corollary H.5, p. 51
search · Winner determination
Simple Stable Voting · All single-deletion winners · ballots
A vector of N original candidate indices, O(N log N) bits.
Reduction convention
Polynomial-time metric function reduction: one call returns the entire single-deletion winner vector, then polynomial-time postprocessing recovers the source function.
Evaluate the N child elections in polynomial space, reusing workspace, so the output vector is a polynomial-space function with polynomial output. For hardness, each PSPACE output-bit/length predicate is placed in a Boolean-election module. A selector forces that module to continue while present; deleting the selector exposes its true/false winner. Substitution combines the modules into one election whose parent winner q is known. One returned deletion vector recovers every predicate by testing selected coordinates against q. All remaining coordinates are fixed in advance. This is a one-call metric reduction.
This task returns every immediate-child winner. It does not return only the parent winner, and it does not count winners.
For Stable Voting, include child winners even if the parent election would later exclude them in its Split Cycle eligibility test.
Hardness persists when the parent winner q and the selector-deletion positions are supplied. The different child winners need not lie in one common pair.
FPSPACE(poly) restricts output length to a polynomial. No claim is made about exponentially long-output FPSPACE functions.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(iii), p. 27; definition (10), p. 50; Theorem H.7 and Lemmas H.8–H.9, pp. 52–55; Lemma F.3, pp. 45–46
One candidate index, O(log(N + 1)) bits; N is the number of candidates.
Reduction convention
Polynomial-time nonadaptive function-oracle reductions: polynomially many valid election queries, all fixed before any winner answers are returned.
The depth-first winner recursion uses polynomial space and outputs one candidate index. Every polynomial-space function with polynomial output can be recovered by asking polynomially many PSPACE predicates for its output length and bits. The original Boolean-election construction converts each predicate to a promised election with two known possible winners. All those elections are prepared nonadaptively, and their returned winners recover the output. For one-call metric reductions, unrestricted winner computation instead has the sharper FP^PSPACE[O(log s)] completeness classification (s is total input length), proved by tournament substitution.
FPSPACE(poly) restricts output length to a polynomial. This result does not claim completeness for functions with exponentially long outputs.
The displayed FPSPACE(poly) completeness allows polynomially many nonadaptive calls. It is not an FPSPACE(poly) one-call metric completeness claim.
A separate one-call theorem classifies this unrestricted winner function as FP^PSPACE[O(log s)]-complete; FPSPACE(log)-completeness is an equivalent useful formulation for its logarithmic output, not an identification of the two function classes.
All voters are unweighted in the ballot encoding; matrix entries are pairwise majority margins, not voter weights.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; H.1–H.2, pp. 50–51; Theorem H.6, p. 52; Lemmas F.2–F.3, pp. 45–46
search · Winner determination
Simple Stable Voting · All single-deletion winners · margins
No individual voters in the input; majority margins are not voter weights
Candidates
Variable number N ≥ 2; each query removes exactly one candidate
Output
Unique by the distinct-margin promise
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Candidate set with N ≥ 2. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
A vector of N original candidate indices, O(N log N) bits.
Reduction convention
Polynomial-time metric function reduction: one call returns the entire single-deletion winner vector, then polynomial-time postprocessing recovers the source function.
Evaluate the N child elections in polynomial space, reusing workspace, so the output vector is a polynomial-space function with polynomial output. For hardness, each PSPACE output-bit/length predicate is placed in a Boolean-election module. A selector forces that module to continue while present; deleting the selector exposes its true/false winner. Substitution combines the modules into one election whose parent winner q is known. One returned deletion vector recovers every predicate by testing selected coordinates against q. All remaining coordinates are fixed in advance. This is a one-call metric reduction.
This task returns every immediate-child winner. It does not return only the parent winner, and it does not count winners.
For Stable Voting, include child winners even if the parent election would later exclude them in its Split Cycle eligibility test.
Hardness persists when the parent winner q and the selector-deletion positions are supplied. The different child winners need not lie in one common pair.
FPSPACE(poly) restricts output length to a polynomial. No claim is made about exponentially long-output FPSPACE functions.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(iii), p. 27; definition (10), p. 50; Theorem H.7 and Lemmas H.8–H.9, pp. 52–55
No individual voters in the input; majority margins are not voter weights
Candidates
Variable; not a fixed two-candidate election
Output
Unique by the distinct-margin promise
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Nonempty candidate set. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
One candidate index, O(log(N + 1)) bits; N is the number of candidates.
Reduction convention
Polynomial-time nonadaptive function-oracle reductions: polynomially many valid election queries, all fixed before any winner answers are returned.
The depth-first winner recursion uses polynomial space and outputs one candidate index. Every polynomial-space function with polynomial output can be recovered by asking polynomially many PSPACE predicates for its output length and bits. The original Boolean-election construction converts each predicate to a promised election with two known possible winners. All those elections are prepared nonadaptively, and their returned winners recover the output. For one-call metric reductions, unrestricted winner computation instead has the sharper FP^PSPACE[O(log s)] completeness classification (s is total input length), proved by tournament substitution.
FPSPACE(poly) restricts output length to a polynomial. This result does not claim completeness for functions with exponentially long outputs.
The displayed FPSPACE(poly) completeness allows polynomially many nonadaptive calls. It is not an FPSPACE(poly) one-call metric completeness claim.
A separate one-call theorem classifies this unrestricted winner function as FP^PSPACE[O(log s)]-complete; FPSPACE(log)-completeness is an equivalent useful formulation for its logarithmic output, not an identification of the two function classes.
All voters are unweighted in the ballot encoding; matrix entries are pairwise majority margins, not voter weights.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; H.1–H.2, pp. 50–51; Theorem H.6, p. 52
search · Winner determination
Simple Stable Voting · Find winner · two possible outputs
No individual voters in the input; majority margins are not voter weights
Candidates
Variable candidate count N ≥ 2. Two possible winning outputs, not a two-candidate election.
Output
Unique by distinct margins, and promised to be one of the two supplied candidates C,D
Ties
All off-diagonal margins nonzero and pairwise distinct over ordered pairs
Input
Nonempty candidate set. Explicit skew-symmetric integer margin matrix; binary integer entries; a supplied enumeration of the candidates fixes the output indices; two distinct designated candidates C,D with the promise that the winner belongs to {C,D}
Ballots
No ballots in this encoding. Nonempty candidate set, explicit skew-symmetric integer margin matrix, binary entries.
Output encoding
One of the supplied candidate indices C,D; one bit of unresolved choice.
Reduction convention
Polynomial-time metric function reductions. Every oracle query supplies two designated candidates and is promised to have its unique winner among them.
A single yes/no PSPACE query asks whether C wins, and the promise determines the winner from that answer. Conversely, the original Boolean-election construction converts the one PSPACE question made by any FP^PSPACE[1] computation into a valid election whose two designated outputs encode the answer. Polynomial-time postprocessing resumes the source computation. Under polynomially many nonadaptive oracle calls, this same promised winner function is FPSPACE(poly)-complete.
FP^PSPACE[1] means polynomial-time function computation with at most one yes/no PSPACE-oracle query.
This is a promise about two possible winners among a variable number of candidates. Fixing the total election size to two is a different, easy problem.
Under polynomial-time nonadaptive oracle reductions the same promised task is FPSPACE(poly)-complete (Theorem H.2).
Under one-call metric reductions this promised task is not claimed FPSPACE(poly)-complete: such a classification would imply P = PSPACE (Corollary H.5).
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 7.1(i)–(ii), p. 27; Proposition H.3 and Corollary H.5, p. 51
Incomplete preferences
Possible- and necessary-winner decisions over partial ballots.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
Maximize p’s feasible first-place count, then use capacitated bipartite matching to assign remaining first places without exceeding that count.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited theorem gives NP-hardness. A profile of linear extensions is a polynomial-size certificate, and winners can be checked in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
Minimize p’s feasible veto count, then use a feasible flow with lower bounds to distribute last places so every rival has at least that many vetoes.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited theorem gives NP-hardness. A profile of linear extensions is a polynomial-size certificate, and winners can be checked in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded; electorate nonempty
Output
Candidate p may share victory with another candidate
Ties
All candidates with the earliest majority level win. No comparison of their support counts at that level.
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking. There is at least one voter.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited theorem gives NP-hardness. A profile of linear extensions is a polynomial-size certificate, and winners can be checked in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
This is not the score-tiebroken Bucklin rule used by the control nodes.
Candidate count is part of the input and unbounded; electorate nonempty
Output
Candidate p may share victory with another candidate
Ties
All candidates with the earliest majority level win. No comparison of their support counts at that level.
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking. There is at least one voter.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
This is not the score-tiebroken Bucklin rule used by the control nodes.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Pairwise ties score ½ each; all candidates with maximum Copeland score win.
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited theorem gives NP-hardness. A profile of linear extensions is a polynomial-size certificate, and winners can be checked in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
The proof uses odd-size electorates, so pairwise ties never occur in the hard instances; the result applies to the fixed ½ convention.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Pairwise ties score ½ each; all candidates with maximum Copeland score win.
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The theorem proves coNP-hardness. A completion in which p loses certifies the complement in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
The proof uses odd-size electorates, so pairwise ties never occur in the hard instances; the result applies to the fixed ½ convention.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited theorem gives NP-hardness. A profile of linear extensions is a polynomial-size certificate, and winners can be checked in polynomial time.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit list of unweighted partial orders, each given by pairwise comparisons; candidate set C and designated p. Each order is extended independently to a strict total ranking.
Ballots
Arbitrary partial orders completed to strict total rankings; incomparability is missing information, not indifference
The cited algorithm tests whether any rival can defeat p in some completion; if none can, p is a necessary co-winner.
Possible and necessary refer to missing preference information, not to choosing a voting rule.
Put p in every top-k set. A flow network assigns each manipulator k−1 distinct rivals, with each rival’s capacity equal to its allowed extra score. Integral maximum flow decides feasibility.
k is supplied as part of the instance. The flow proof also covers this uniform family, beyond fixed-k statements.
Never veto p. Each rival requires max(0, vetoes(p)−vetoes(rival)) added vetoes. A manipulation exists exactly when the total required is at most the coalition size.
Positive binary integer weights, explicit voter list
Candidates
variable, at least 2
Output
Target must be excluded from the winner set
Ties
All maximum-score candidates are winners; no external tie-breaker.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate. At least two candidates are present.
All maximum-score candidates win; no external tie-breaker
Input
Explicit unweighted fixed ballots, one new manipulator, candidate p.
Ballots
Strict complete rankings; no preference-domain restriction
Put p first. Rank rivals from lowest to highest existing Borda score. Check p against the resulting maximum. Moving p upward cannot hurt it. For two rivals with scores a≥b and assigned points x≥y, replacing (a+x,b+y) with (a+y,b+x) cannot increase the pair's maximum. Repeated exchanges give the stated order, so this order minimizes the largest rival score.
All maximum-score candidates win; no external tie-breaker
Input
Explicit unweighted fixed ballots, two new manipulators, candidate p.
Ballots
Strict complete rankings; no preference-domain restriction
Permutation Sum is encoded by two ballots; their assigned scores must meet all target gaps exactly. Proposed ballots can be checked in polynomial time.
The reduction constructs an actual polynomial-size unweighted profile, not merely an arbitrary score vector. Ties favor the manipulators, exactly matching co-winner semantics.
Positive binary integer weight per voter; explicit voter list
Candidates
exactly 3
Output
Co-winner allowed: p may tie for maximum score
Ties
All maximum-score candidates win; no external tie-breaker
Input
Three candidates, explicit list of fixed rankings and binary positive integer weights, explicit list of manipulator weights, candidate p.
Ballots
Strict complete rankings; no preference-domain restriction
Reduce Partition to splitting weighted manipulators between p>a>b and p>b>a. The construction makes p strictly win for an equal split and strictly lose for every unequal split.
The source uses unique-winner success, but the proof separates strict wins from strict losses, so co-winner membership is equally hard. Fixed ballot multiplicities are represented as weights, not expanded in unary.
Positive binary integer weights, explicit voter list
Candidates
exactly 3
Output
Winner of the specified deterministic tie-resolved rule
Ties
The top two first-place candidates advance; break qualification ties by retaining higher-priority candidates. In a tied final choose the higher-priority candidate. Use the same fixed priority as the STV node.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Positive binary integer weights, explicit voter list
Candidates
exactly 3
Output
The deterministic winner must differ from target h
Ties
The top two first-place candidates advance; break qualification ties by retaining higher-priority candidates. In a tied final choose the higher-priority candidate. Use the same fixed priority as the STV node.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Winner of the specified deterministic tie-resolved rule
Ties
Single seat. In each round eliminate a candidate with the lowest first-place total; among tied lowest candidates eliminate the lowest-priority one. In a tied final choose the highest-priority candidate. Priority is fixed before ballots are chosen.
Input
Explicit unweighted fixed ballots; explicit list or unary number of manipulators; target candidate.
Exact-cover reduction; one proposed ranking is a polynomial certificate.
This is single-seat IRV, not a multiwinner STV counting rule. The reduction’s successful elimination choices are strict; arbitrary fixed tie priority is compatible.
Winner of the specified deterministic tie-resolved rule
Ties
Single seat. In each round eliminate a candidate with the lowest first-place total; among tied lowest candidates eliminate the lowest-priority one. In a tied final choose the highest-priority candidate. Priority is fixed before ballots are chosen.
Input
Explicit unweighted fixed ballots; explicit list or unary number of manipulators; target candidate.
Winner of the specified deterministic tie-resolved rule
Ties
Single seat. In each round eliminate a candidate with the lowest first-place total; among tied lowest candidates eliminate the lowest-priority one. In a tied final choose the highest-priority candidate. Priority is fixed before ballots are chosen.
Input
Explicit unweighted fixed ballots; explicit list or unary number of manipulators; target candidate.
Positive binary integer weights, explicit voter list
Candidates
exactly 3
Output
Winner of the specified deterministic tie-resolved rule
Ties
Single seat. In each round eliminate a candidate with the lowest first-place total; among tied lowest candidates eliminate the lowest-priority one. In a tied final choose the highest-priority candidate. Priority is fixed before ballots are chosen.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Positive binary integer weights, explicit voter list
Candidates
exactly 3
Output
The deterministic winner must differ from target h
Ties
Single seat. In each round eliminate a candidate with the lowest first-place total; among tied lowest candidates eliminate the lowest-priority one. In a tied final choose the highest-priority candidate. Priority is fixed before ballots are chosen.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Winner of the specified deterministic tie-resolved rule
Ties
Strict Nanson: remove all candidates strictly below average Borda score in each round. If all remaining scores tie, select by a fixed priority favouring p.
Input
Explicit unweighted fixed ballots; explicit list or unary number of manipulators; target candidate.
Published one-manipulator NP-completeness theorem.
The conference version states this theorem but refers its detailed proof to the technical report. Do not conflate strict-below-average Nanson with the weak variant.
Positive binary integer weights, explicit voter list
Candidates
exactly 4
Output
Winner of the specified deterministic tie-resolved rule
Ties
Strict Nanson: remove all candidates strictly below average Borda score in each round. If all remaining scores tie, select by a fixed priority favouring p.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Positive binary integer weights, explicit voter list
Candidates
exactly 3
Output
Winner of the specified deterministic tie-resolved rule
Ties
Strict Nanson: remove all candidates strictly below average Borda score in each round. If all remaining scores tie, select by a fixed priority favouring p.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate.
Positive binary integer weights, explicit voter list
Candidates
variable, at least 2
Output
Target must be excluded from the winner set
Ties
Candidate score is the minimum pairwise support N(x,y), not a margin normalized by opponent. All maximum-score candidates win.
Input
Explicit fixed ballots with positive binary integer weights; explicit list of positive binary manipulator weights; target candidate. At least two candidates are present.
all candidates with maximum plurality score are winners; no external tie-breaker
Input
one explicit ballot per voter; not compressed by binary multiplicities
Ballots
Strict complete rankings; no preference-domain restriction
Polynomial algorithm even with arbitrary binary prices.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Section 2.2, pp. 6–7; Theorem 3.3, p. 12; detailed algorithm via Theorem 3.8, pp. 18–20
all candidates with maximum plurality score are winners; no external tie-breaker
Input
one explicit ballot per voter; not compressed by binary multiplicities
Ballots
Strict complete rankings; no preference-domain restriction
Polynomial algorithm even with binary voter weights.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Section 2.2, pp. 6–7; Theorem 3.3, p. 12; detailed algorithm via Theorem 3.8, pp. 18–20
Candidate count is part of the input and unbounded
Output
p may tie for maximum score
Ties
Pairwise ties score ½; all maximum-score candidates win
Input
Explicit unweighted complete strict rankings over C, designated p, nonnegative integer k. Choose at most k voters and freely replace each chosen complete ranking.
Candidate count is part of the input and unbounded
Output
p must not be a co-winner
Ties
Pairwise ties score ½; all maximum-score candidates win
Input
Explicit unweighted complete strict rankings over C, designated p, nonnegative integer k. Choose at most k voters and freely replace each chosen complete ranking.
Candidate count is part of the input and unbounded
Output
Candidate p may share victory with another candidate
Ties
Every highest-scoring candidate wins; no external tie-breaker
Input
Explicit unweighted 0/1 approval vectors, a nonnegative binary integer cost for flipping each voter-candidate entry, designated p, and binary integer budget B.
Ballots
Complete approval vectors; each chosen 0↔1 flip is charged separately
For each target score of p, take its cheapest necessary approval gains and each rival’s cheapest necessary approval losses. Minimize across the polynomially many target scores.
The weight of each voter is 1. Binary-encoded voter weights are not covered by this node.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Definition 4.3; Theorem 4.4, pp. 23–24 (unit-weight specialization)
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Qualified candidates C containing p, disjoint candidate pool D, explicit unweighted ballots over C∪D, and nonnegative integer k. Choose at most k candidates from D; restrict ballots to the resulting set. The registered electorate is nonempty.
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k candidates from C\{p}; remove them from every ballot. The registered electorate is nonempty.
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Qualified candidates C containing p, disjoint candidate pool D, explicit unweighted ballots over C∪D, and nonnegative integer k. Choose at most k candidates from D; restrict ballots to the resulting set. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The cited result proves NP-hardness. Guess the chosen subset and evaluate the resulting election in polynomial time to obtain NP membership.
Destructive success uses the unique-winner model: tying p is sufficient.
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k candidates from C\{p}; remove them from every ballot. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The cited result proves NP-hardness. Guess the chosen subset and evaluate the resulting election in polynomial time to obtain NP membership.
Destructive success uses the unique-winner model: tying p is sufficient.
all candidates with maximum plurality score are winners; no external tie-breaker
Input
Explicit registered ballots V and unregistered ballots W over the same candidate set C; p ∈ C.
Ballots
Strict complete rankings; no preference-domain restriction
Add only available ballots ranking p first, stopping when its score exceeds every rival or the budget is exhausted.
How hard is it to control an election? John J. Bartholdi III, Craig A. Tovey, Michael A. Trick · 1992 · Theorem 9, PDF pp. 13 and 26; later at-most-k formulation in HHR07
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. An explicit pool W of additional voters with already fixed ballots. Add at most k voters from W, respecting multiplicity. The registered electorate is nonempty.
Candidate count is part of the input and unbounded
Output
p must not be the unique winner; a co-win counts as successful control
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. An explicit pool W of additional voters with already fixed ballots. Add at most k voters from W, respecting multiplicity. The registered electorate is nonempty.
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k listed voters, respecting multiplicity. The registered electorate is nonempty. Assume k<|V|, so at least one voter remains.
The cited result proves NP-hardness. Guess the chosen subset and evaluate the resulting election in polynomial time to obtain NP membership.
Destructive success uses the unique-winner model: tying p is sufficient.
This entry excludes deleting the entire electorate; the hardness construction already has k<|V|, and the polynomial algorithm remains valid on this restriction.
Candidate count is part of the input and unbounded
Output
p must not be the unique winner; a co-win counts as successful control
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k listed voters, respecting multiplicity. The registered electorate is nonempty. Assume k<|V|, so at least one voter remains.
The primary theorem states a polynomial algorithm for destructive deletion, obtained by adapting the addition algorithm. Its detailed deletion proof is omitted. Standard Bucklin inherits this upper bound by approving every candidate.
Destructive success uses the unique-winner model: tying p is sufficient.
The later report has an adding/deleting wording error in Theorem 3.20; the earlier explicit deletion theorem and the Bucklin restriction supply the cited upper bound.
This entry excludes deleting the entire electorate; the hardness construction already has k<|V|, and the polynomial algorithm remains valid on this restriction.
The source states the deletion classification and adaptation without a complete deletion algorithm.
Control Complexity in Fallback Voting Gábor Erdélyi, Lena Piras, Jörg Rothe · 2010 · Theorem 3.12, p. 16; deletion case noted after the addition proof, p. 19
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. An explicit pool W of additional voters with already fixed ballots. Add at most k voters from W, respecting multiplicity. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The cited result proves NP-hardness. Guess the chosen subset and evaluate the resulting election in polynomial time to obtain NP membership.
Destructive success uses the unique-winner model: tying p is sufficient.
Candidate count is part of the input and unbounded
Output
p must not be the unique winner; a co-win counts as successful control
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. An explicit pool W of additional voters with already fixed ballots. Add at most k voters from W, respecting multiplicity. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The cited algorithm examines candidates and majority levels to find a successful attack, if one exists, in polynomial time.
Destructive success uses the unique-winner model: tying p is sufficient.
Candidate count is part of the input and unbounded
Output
p must be the unique winner
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k listed voters, respecting multiplicity. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty. Assume k<|V|, so at least one voter remains.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The cited result proves NP-hardness. Guess the chosen subset and evaluate the resulting election in polynomial time to obtain NP membership.
Destructive success uses the unique-winner model: tying p is sufficient.
This entry excludes deleting the entire electorate; the hardness construction already has k<|V|, and the polynomial algorithm remains valid on this restriction.
Candidate count is part of the input and unbounded
Output
p must not be the unique winner; a co-win counts as successful control
Ties
At the earliest rank level with a strict majority, retain only candidates with maximum support at that level; equal support yields multiple winners. If no majority exists at any level, use maximum approval score.
Input
Explicit unweighted profile over C, designated p, and nonnegative integer budget k. Delete at most k listed voters, respecting multiplicity. Ballots specify approved sets and strict rankings within those sets; approval status of retained candidates is unchanged. The registered electorate is nonempty. Assume k<|V|, so at least one voter remains.
Ballots
A strict ranking of each voter’s approved subset. Unlisted candidates are disapproved, not missing preferences. Empty/full approval sets are permitted.
The primary theorem states a polynomial algorithm for destructive deletion, obtained by adapting the addition algorithm. Its detailed deletion proof is omitted.
Destructive success uses the unique-winner model: tying p is sufficient.
The later report has an adding/deleting wording error in Theorem 3.20; the earlier explicit deletion theorem and the Bucklin restriction supply the cited upper bound.
This entry excludes deleting the entire electorate; the hardness construction already has k<|V|, and the polynomial algorithm remains valid on this restriction.
The source states the deletion classification and adaptation without a complete deletion algorithm.
Control Complexity in Fallback Voting Gábor Erdélyi, Lena Piras, Jörg Rothe · 2010 · Theorem 3.12, p. 16; deletion case noted after the addition proof, p. 19
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed.
Selects the strict pairwise-majority winner.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 4, Proposition 4 and Corollary 1; section opening includes SSV
property · Rule properties
Stable Voting · Reject Condorcet loser
Satisfies
Does Stable Voting satisfy reject condorcet loser under these assumptions?
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings; the stated rule, output, and tie model.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings; the stated rule, output, and tie model.
Stable Voting returns only Split Cycle winners. A strict Condorcet loser has incoming majority edges and no outgoing edge, so no cycle removes its incoming defeats. It is therefore excluded.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 2, Stable Voting definition; Section 4, Smith criterion
property · Rule properties
Stable Voting · Majority winner
Satisfies
Does Stable Voting satisfy majority winner under these assumptions?
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. The paper states failure on the general strict-profile domain. This entry does not assert a counterexample restricted to uniquely-weighted margins.
Ballots
Complete strict rankings of all candidates
Conditions
The paper states failure on the general strict-profile domain. This entry does not assert a counterexample restricted to uniquely-weighted margins.
Raising a winner can change recursive subelections against it.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 5, paragraph before Figure 4
property · Rule properties
Stable Voting · Clone independence
Violates
Does Stable Voting satisfy clone independence under these assumptions?
Retain every maximum-margin qualifying pair at each recursion. No final priority and no PUT perturbation of equal margin orders.
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile correspondence with tied margins: union the first coordinates of all maximum-margin qualifying pairs (simultaneous tied-margin convention). This is not an assertion about PUT over globally tie-broken margin orders or a distinct-margin promise.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile correspondence with tied margins: union the first coordinates of all maximum-margin qualifying pairs (simultaneous tied-margin convention). This is not an assertion about PUT over globally tie-broken margin orders or a distinct-margin promise.
A clone can break tied-margin symmetry and change outsider co-winners.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"winnerBefore": [
"a",
"b",
"c"
],
"winnerAfter": [
"a"
],
"cloneOf": "a",
"marginsBefore": {
"ab": 1,
"ac": -1,
"bc": 1
},
"marginsAfter": {
"ab": 1,
"ac": -1,
"az": 3,
"bc": 1,
"bz": -1,
"cz": 1
},
"profile": [
[
1,
"abc"
],
[
1,
"bca"
],
[
1,
"cab"
]
],
"modified": [
[
1,
"azbc"
],
[
1,
"bcaz"
],
[
1,
"cazb"
]
],
"result": "The cycle abc, bca, cab has all three co-winners. Adding z next to a on every ballot as azbc, bcaz, cazb leaves only a winning. Outsiders b and c lose their winning status."
}
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 2 and tied-margin convention in footnote 7; explicit witness derived from the rule
property · Rule properties
Stable Voting · Participation
Violates
Does Stable Voting satisfy participation under these assumptions?
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed.
Selects the strict pairwise-majority winner.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 4, Proposition 4 and Corollary 1; section opening includes SSV
property · Rule properties
Simple Stable Voting · Reject Condorcet loser
Satisfies
Does Simple Stable Voting satisfy reject condorcet loser under these assumptions?
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings; the stated rule, output, and tie model.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings; the stated rule, output, and tie model.
Induct on the number of candidates. With two candidates, the strict pairwise loser does not win. With at least three, deleting any opponent leaves the Condorcet loser as a Condorcet loser in a smaller election. It cannot win any required subelection, so no recursive qualifying pair can select it.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 2, Simple Stable Voting definition; Section 4 applies its properties to SSV too
property · Rule properties
Simple Stable Voting · Majority winner
Satisfies
Does Simple Stable Voting satisfy majority winner under these assumptions?
Retain every maximum-margin qualifying pair at each recursion; no final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile SSV correspondence with tied margins, using every maximum-margin qualifying pair. The eight-voter witness does not establish failure under the distinct-margin promise.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile SSV correspondence with tied margins, using every maximum-margin qualifying pair. The eight-voter witness does not establish failure under the distinct-margin promise.
Raising a co-winner can remove it from the winning set.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"winnerBefore": [
"b",
"c",
"d"
],
"winnerAfter": [
"c"
],
"raised": "d",
"oldBallot": "bdca",
"newBallot": "dbca",
"marginsBefore": {
"ab": 2,
"ac": -4,
"ad": -2,
"bc": 0,
"bd": 2,
"cd": 0
},
"marginsAfter": {
"ab": 2,
"ac": -4,
"ad": -2,
"bc": 0,
"bd": 0,
"cd": 0
},
"profile": [
[
1,
"bdca"
],
[
3,
"cabd"
],
[
1,
"cbda"
],
[
2,
"dabc"
],
[
1,
"dbca"
]
],
"modified": [
[
3,
"cabd"
],
[
1,
"cbda"
],
[
2,
"dabc"
],
[
2,
"dbca"
]
],
"result": "Co-winners are {b,c,d}. One voter raises d in bdca to obtain dbca. The new unique winner is c, so d disappears from the winning set."
}
Retain every maximum-margin qualifying pair at each recursion. No final priority and no PUT perturbation of equal margin orders.
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile correspondence with tied margins: union the first coordinates of all maximum-margin qualifying pairs (simultaneous tied-margin convention). This is not an assertion about PUT over globally tie-broken margin orders or a distinct-margin promise.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile correspondence with tied margins: union the first coordinates of all maximum-margin qualifying pairs (simultaneous tied-margin convention). This is not an assertion about PUT over globally tie-broken margin orders or a distinct-margin promise.
A clone can break tied-margin symmetry and change outsider co-winners.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"winnerBefore": [
"a",
"b",
"c"
],
"winnerAfter": [
"a"
],
"cloneOf": "a",
"marginsBefore": {
"ab": 1,
"ac": -1,
"bc": 1
},
"marginsAfter": {
"ab": 1,
"ac": -1,
"az": 3,
"bc": 1,
"bz": -1,
"cz": 1
},
"profile": [
[
1,
"abc"
],
[
1,
"bca"
],
[
1,
"cab"
]
],
"modified": [
[
1,
"azbc"
],
[
1,
"bcaz"
],
[
1,
"cazb"
]
],
"result": "The cycle abc, bca, cab has all three co-winners. Adding z next to a on every ballot as azbc, bcaz, cazb leaves only a winning. Outsiders b and c lose their winning status."
}
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 2 and tied-margin convention in footnote 7; explicit witness derived from the rule
property · Rule properties
Simple Stable Voting · Participation
Violates
Does Simple Stable Voting satisfy participation under these assumptions?
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings; the stated rule, output, and tie model.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings; the stated rule, output, and tie model.
A Condorcet loser has no outgoing majority edge, so no directed majority cycle contains any incoming edge to it. Those incoming wins are never removed as weakest cycle edges, so the candidate has incoming Split Cycle defeats.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Profile: 3 voters a>b>c, 2 voters b>c>a, 2 voters c>b>a. First-place counts are a:3, b:2, c:2, so a is the unique winner. Both b and c beat a by 4 votes to 3.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Ballots
Complete strict rankings of all candidates
Conditions
Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. 1 ≤ k < m. Condorcet consistency requires the strict Condorcet winner to be the sole winner. The negative k=1 witness uses m=3; each k≥2 fails for every m>k.
Ballots
Complete strict rankings of all candidates
Conditions
1 ≤ k < m. Condorcet consistency requires the strict Condorcet winner to be the sole winner. The negative k=1 witness uses m=3; each k≥2 fails for every m>k.
For k=1, take 3 a>b>c, 2 b>c>a, 2 c>b>a: b is the strict Condorcet winner (4–3 over a and 5–2 over c), but plurality selects a. For every k≥2 and m>k, one unanimous ranking with a first gives a a strict pairwise victory over every rival, but all k approved candidates tie as co-winners. Thus a is not the only winner.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. For each fixed k≥1 a witness exists; this does not assert failure on every fixed pair (m,k), such as the two-candidate majority special case.
Ballots
Complete strict rankings of all candidates
Conditions
For each fixed k≥1 a witness exists; this does not assert failure on every fixed pair (m,k), such as the two-candidate majority special case.
For k=1 use 3 a>b>c, 2 b>c>a, 2 c>b>a: a wins uniquely but loses both pairwise contests 3–4. For k=2, m=3, use 2 b>a>c, 2 c>a>b, 1 c>b>a: a scores 4 and b,c score 3, but a loses both contests 2–3. For k≥3 set m=k+1 with candidate a and k others. For each rival y, include one ballot listing every rival except y above a, followed by y. Candidate a is approved on all k ballots, while each rival is last once and scores k−1. Thus a uniquely wins, but loses to each rival by k−1 votes to 1.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. For every m>k≥2 the criterion fails; k=1 satisfies it. The displayed witness uses m=4,k=2.
Ballots
Complete strict rankings of all candidates
Conditions
For every m>k≥2 the criterion fails; k=1 satisfies it. The displayed witness uses m=4,k=2.
For m>k≥2, use three identical rankings a>b>… and two identical rankings b>…>a. Candidate a has a strict first-place majority but only three approval points, while b has five.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"profile": [
[
3,
"abcd"
],
[
2,
"bcda"
]
],
"result": "For k=2, a has a first-place majority but scores a=3, b=5, c=2, d=0."
}
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. k stays fixed across the clone deletion. Each fixed k≥1 has a counterexample within the domain 1≤k<m. All co-winners are returned.
Ballots
Complete strict rankings of all candidates
Conditions
k stays fixed across the clone deletion. Each fixed k≥1 has a counterexample within the domain 1≤k<m. All co-winners are returned.
For k=1: 2 a>b>c, 2 b>a>c, 3 c>a>b have clone block {a,b}; c wins 3–2–2, but deleting b makes a win 4–3. For k≥2, use m=k+2 candidates: a,b,c,z plus k−2 dummy candidates. Put all dummies first in every ballot, then use 2 a>b>c>z and 1 b>c>a>z. The block {b,c} is contiguous. Before deletion a has 2 points and b has 3, so a loses; after deleting c, a and b both have 3 and a becomes a co-winner. Every dummy always has 3, which does not affect this change in a’s membership. Both candidate sets satisfy k<m.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Ballots
Complete strict rankings of all candidates
Conditions
Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed priority a before b before c before any dummy candidates
Input
The specified voting rule on its whole stated domain, not a single election instance. For every fixed k≥1 there is a finite candidate set and a two-voter manipulation. Final co-winner ties use the stated fixed priority, unchanged by a report. Names can be chosen relative to any exogenous priority.
Ballots
Unrestricted complete strict rankings
Conditions
For every fixed k≥1 there is a finite candidate set and a two-voter manipulation. Final co-winner ties use the stated fixed priority, unchanged by a report. Names can be chosen relative to any exogenous priority.
For k=1 with priority a before b before c: the other ballot is b>a>c, and the manipulator truly prefers c>a>b. A truthful c vote ties b with c, electing b. Reporting a>b>c instead ties a with b, electing a, which the voter prefers to b. For k≥2, use k−2 dummy candidates plus a,b,c and give all dummies lower final priority than a,b,c. Put dummies first in both rankings. The other ballot ends a>b>c, and the manipulator’s true ranking ends b>a>c. The original winners include a,b and the dummies, so priority chooses a. Reporting a tail b>c>a leaves b and the dummies tied on top, so b wins. The voter strictly prefers b to a.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
With 2 voters a>b>c and 1 voter b>c>a, a beats both rivals 2–1 and has a first-place majority. Veto scores are a:2, b:3, c:1, so b wins alone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
With 2 voters b>a>c, 2 voters c>a>b, and 1 voter c>b>a, veto scores are a:4, b:3, c:3. Thus a is the unique winner, although b and c each beat a by 3 votes to 2.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
With 2 voters a>b>c and 1 voter b>c>a, the adjacent block {b,c} consists of clones. Veto scores (a,b,c)=(2,3,1), hence b alone wins. Delete c: the profile becomes 2 a>b and 1 b>a. Two-candidate veto is plurality, so a wins. The outsider a changes from losing to winning, and the clone block loses its winner.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Ballots
Complete strict rankings of all candidates
Conditions
Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted strict rankings, two voters and three candidates; the fixed priority is explicitly a before b before c. Candidate names may be relabelled for any fixed priority.
Ballots
Unrestricted complete strict rankings
Conditions
Unrestricted strict rankings, two voters and three candidates; the fixed priority is explicitly a before b before c. Candidate names may be relabelled for any fixed priority.
Let final ties use fixed priority a before b before c. One voter reports a>b>c; the other truly prefers b>a>c. Both a and b receive 2 points, so a wins the tie. If the second voter reports b>c>a, b receives 2 while a and c receive 1, so b wins. The manipulating voter strictly prefers b to a.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
The Borda score of x equals the sum, over rivals y, of the number of voters ranking x above y. If x is a strict Condorcet loser, each summand is less than n/2, so x scores less than n(m−1)/2. This is the mean score of all candidates, so x is not a score maximizer.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Manipulation of Nanson’s and Baldwin’s Rules Nina Narodytska, Toby Walsh, Lirong Xia · 2011 · Nanson’s and Baldwin’s Rules, p.2, Borda’s Condorcet-loser property; counting proof
property · Rule properties
Borda · Majority winner
Violates
Does Borda satisfy majority winner under these assumptions?
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Ballots
Complete strict rankings of all candidates
Conditions
Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Set of possible winners or simultaneous-elimination winners, as specified
Ties
Compare (i) removing one tied minimum at a time with PUT or fixed priority and (ii) removing all tied minima, returning all survivors if every remaining candidate is tied.
Input
The specified voting rule on its whole stated domain, not a single election instance. PUT or fixed-priority one-at-a-time elimination satisfies the criterion. Simultaneous elimination with all surviving candidates returned when all tallies tie can violate it.
Ballots
Complete strict rankings
Conditions
PUT or fixed-priority one-at-a-time elimination satisfies the criterion. Simultaneous elimination with all surviving candidates returned when all tallies tie can violate it.
In every one-at-a-time elimination path, a Condorcet loser either leaves earlier or reaches a two-candidate final and loses there. With simultaneous elimination, consider abc, bca, cba: all first-place tallies equal 1, so the terminal-tie convention returns all candidates, although a loses 1–2 to both b and c.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. The displayed witness has no elimination or final ties.
Ballots
Complete strict rankings of all candidates
Conditions
The displayed witness has no elimination or final ties.
Raising the winner can change the elimination order against it.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"profile": [
[
10,
"abc"
],
[
9,
"bca"
],
[
8,
"cab"
]
],
"modified": [
[
13,
"abc"
],
[
6,
"bca"
],
[
8,
"cab"
]
],
"result": "Initially c is eliminated and a wins 18–9. Three bca voters raise a to first; then b is eliminated and c wins 14–13."
}
Set of possible winners or simultaneous-elimination winners, as specified
Ties
Compare parallel-universe tie-breaking (eliminate one tied minimum at a time, union all possibilities) with simultaneous elimination of all tied minima
Input
The specified voting rule on its whole stated domain, not a single election instance. PUT removes one tied minimum at a time and unions possible winners. Simultaneous elimination removes every tied minimum together.
Ballots
Complete strict rankings
Conditions
PUT removes one tied minimum at a time and unions possible winners. Simultaneous elimination removes every tied minimum together.
PUT satisfies this criterion; simultaneous elimination need not.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. Single-seat IRV, complete strict rankings, fixed survival priority a > b > c at every tied elimination; one voter joins a three-voter electorate.
Ballots
Complete strict rankings of all candidates
Conditions
Single-seat IRV, complete strict rankings, fixed survival priority a > b > c at every tied elimination; one voter joins a three-voter electorate.
A voter can get a preferred winner by abstaining.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"winnerBefore": [
"b"
],
"winnerAfter": [
"a"
],
"entrant": "cba",
"roundsBefore": [
{
"scores": {
"a": 1,
"b": 1,
"c": 1
},
"delete": [
"c"
]
},
{
"scores": {
"a": 1,
"b": 2
},
"delete": [
"a"
]
}
],
"roundsAfter": [
{
"scores": {
"a": 1,
"b": 1,
"c": 2
},
"delete": [
"b"
]
},
{
"scores": {
"a": 2,
"c": 2
},
"delete": [
"c"
]
}
],
"profile": [
[
1,
"abc"
],
[
1,
"bac"
],
[
1,
"cba"
]
],
"modified": [
[
1,
"abc"
],
[
1,
"bac"
],
[
2,
"cba"
]
],
"tiePriority": "a > b > c",
"result": "Without the entrant, eliminate c from the three-way first-place tie and elect b. Adding one cba voter makes b the eliminated tied minimum, then a wins the final 2–2 tie. The entrant prefers b to a."
}
Fixed candidate-priority order at every elimination tie: eliminate the lowest-priority tied minimum.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
At every elimination tie, branch over eliminating one candidate with maximal last-place count; return union of all possible majority-stop winners.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The explicit profile gives strict Condorcet winner a but winner set a,e.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > b > d > c > e; 1 × a > d > e > b > c; 1 × b > a > e > c > d; 1 × b > e > a > d > c; 1 × d > a > b > e > c; 1 × d > c > a > e > b; 1 × e > a > c > d > b; 1 × e > b > c > a > d; 1 × e > b > c > d > a. Winners: a, e."
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
At every elimination tie, branch over eliminating one candidate with maximal last-place count; return union of all possible majority-stop winners.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
While a Condorcet loser remains, it still loses pairwise to every other remaining candidate and cannot have a majority of first places. If it survives to two candidates, the rival has a strict first-place majority and wins before the next elimination.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
At every elimination tie, branch over eliminating one candidate with maximal last-place count; return union of all possible majority-stop winners.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The first-level majority check elects this candidate immediately; two candidates cannot both have more than half the first-place votes.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
At every elimination tie, branch over eliminating one candidate with maximal last-place count; return union of all possible majority-stop winners.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The before/after profiles differ only by raising d. Exact evaluation removes that candidate from the winner set.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > b > c > d; 2 × a > c > d > b; 1 × b > a > d > c; 1 × b > d > a > c; 1 × c > a > b > d; 1 × c > d > b > a; 1 × d > a > c > b; 1 × d > b > a > c. Winners: a, d. After: 1 × a > b > c > d; 2 × a > c > d > b; 1 × b > a > d > c; 1 × b > d > a > c; 1 × c > a > d > b; 1 × c > d > b > a; 1 × d > a > c > b; 1 × d > b > a > c. Winners: a. Exact scores: {}. New exact scores: {}."
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
At every elimination tie, branch over eliminating one candidate with maximal last-place count; return union of all possible majority-stop winners.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Every inserted candidate is adjacent to its original in every ballot, so it is a clone. The recorded winner sets change the winning status of an outsider or the existence of a winning clone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > b > c > d; 1 × a > c > b > d; 1 × b > a > c > d; 1 × c > a > b > d; 1 × c > b > a > d; 1 × c > d > a > b. Winners: a, c. After: 1 × a > b > z > c > d; 1 × a > c > z > b > d; 1 × b > a > c > z > d; 1 × c > z > a > b > d; 1 × c > z > b > a > d; 1 × c > z > d > a > b. Winners: c."
Unweighted; all nonempty subelectorates of an electorate of arbitrary size
Candidates
At least four candidates; all nonempty subelectorates of a pool of at least twelve voters.
Output
One winner
Ties
Fixed exogenous candidate-priority selects one member of the complete Coombs (PUT) winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Resolve the listed final winner sets by fixed alphabetic priority. The added voter prefers the original winner to the resulting winner, which is the no-show paradox.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > b > e > c > d; 1 × a > c > b > e > d; 1 × a > d > c > b > e; 1 × c > e > d > b > a; 1 × d > a > c > e > b; 1 × d > c > b > e > a; 1 × e > b > a > d > c; 1 × e > c > b > a > d. Winners: c. Add one voter d > c > a > b > e. New winner set: a, c. Resolve all final ties by a before b before c before d before e before z."
Fixed exogenous candidate-priority selects one member of the complete Coombs (PUT) winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings; the stated rule, output, and tie model.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings; the stated rule, output, and tie model.
A strict first-place majority makes the candidate a strict Condorcet winner. At every round, a Condorcet winner has Borda score strictly above the average and therefore survives either deletion procedure.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Ballots
Complete strict rankings of all candidates
Conditions
The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Raising a winner can change which rival survives the Borda eliminations.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Ballots
Complete strict rankings of all candidates
Conditions
The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Adding a contiguous clone can change the winning status of an outsider.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
Fixed candidate-priority order at every elimination tie: eliminate the lowest-priority tied minimum.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed candidate-priority order at every elimination tie: eliminate the lowest-priority tied minimum.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings; the stated rule, output, and tie model.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings; the stated rule, output, and tie model.
A strict first-place majority makes the candidate a strict Condorcet winner. At every round, a Condorcet winner has Borda score strictly above the average and therefore survives either deletion procedure.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Ballots
Complete strict rankings of all candidates
Conditions
The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Raising a winner can change which rival survives the Borda eliminations.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
{
"winnerBefore": [
"a"
],
"winnerAfter": [
"c"
],
"raised": "a",
"oldBallot": "cba",
"newBallot": "cab",
"roundsBefore": [
{
"scores": {
"a": 5,
"b": 5,
"c": 5
},
"terminal-tie": [
"a",
"b",
"c"
]
}
],
"roundsAfter": [
{
"scores": {
"a": 6,
"b": 4,
"c": 5
},
"delete": [
"b"
]
},
{
"scores": {
"a": 2,
"c": 3
},
"delete": [
"a"
]
}
],
"profile": [
[
2,
"abc"
],
[
1,
"bca"
],
[
1,
"cab"
],
[
1,
"cba"
]
],
"modified": [
[
2,
"abc"
],
[
1,
"bca"
],
[
2,
"cab"
]
],
"tiePriority": "a > b > c > z, restricted unchanged after deletion",
"result": "a wins initially. Moving a above b in the cba ballot changes the winner to c."
}
Fixed exogenous candidate priority, unchanged across profiles and restricted unchanged when candidates are deleted. Eliminate the lowest-priority tied minimum in Baldwin or IRV; choose the highest-priority terminal co-winner in Nanson.
Input
The specified voting rule on its whole stated domain, not a single election instance. The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Ballots
Complete strict rankings of all candidates
Conditions
The witness uses fixed priority a > b > c > z. Baldwin eliminates the lowest-priority tied minimum; strict Nanson deletes scores strictly below average and uses priority only at a terminal tie. These are three original candidates and, for cloning, four after adding z.
Adding a contiguous clone can change the winning status of an outsider.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The explicit profile gives strict Condorcet winner a but winner set a,d.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > c > d > b; 2 × a > d > b > c; 1 × a > d > c > b; 1 × b > c > d > a; 1 × b > d > a > c; 1 × c > a > b > d; 1 × d > a > b > c; 1 × d > c > a > b. Winners: a, d."
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
In the displayed profile, c loses every pairwise contest but belongs to the computed winner set. Exact scores or counts are included.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 2 × a > b > c; 2 × a > c > b; 1 × b > a > c; 3 × b > c > a; 1 × c > a > b. Winners: a, b, c. Exact scores: {}."
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The first-level majority check elects this candidate immediately; two candidates cannot both have more than half the first-place votes.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Let x win at depth k. Raising x never reduces its support at any depth and never increases any rival’s support. If the first majority depth moves earlier, only x can newly attain a majority there. Otherwise x remains maximum at depth k.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Every inserted candidate is adjacent to its original in every ballot, so it is a clone. The recorded winner sets change the winning status of an outsider or the existence of a winning clone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × b > a > c > d; 1 × b > c > d > a; 1 × b > d > c > a; 1 × c > d > a > b; 1 × c > d > b > a; 1 × d > b > c > a; 1 × d > c > a > b. Winners: d. After: 1 × b > z > a > c > d; 1 × b > z > c > d > a; 1 × b > z > d > c > a; 1 × c > d > a > b > z; 1 × c > d > b > z > a; 1 × d > c > a > z > b; 1 × d > z > b > c > a. Winners: d, z."
Unweighted; all nonempty subelectorates of an electorate of arbitrary size
Candidates
At least four candidates; all nonempty subelectorates of a pool of at least twelve voters.
Output
One winner
Ties
Fixed exogenous candidate-priority selects one member of the complete Bucklin winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Resolve the listed final winner sets by fixed alphabetic priority. The added voter prefers the original winner to the resulting winner, which is the no-show paradox.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > c > d > b; 1 × a > d > c > b; 1 × b > a > c > d; 2 × b > a > d > c; 1 × b > d > c > a; 1 × d > c > b > a. Winners: b. Add one voter d > c > b > a. New winner set: a. Resolve all final ties by a before b before c before d before e before z."
Fixed exogenous candidate-priority selects one member of the complete Bucklin winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Under Copeland ½, a strict Condorcet loser x loses every comparison and gets zero. Every rival beats x, giving that rival at least one point; remaining win/tie points are nonnegative. Thus x cannot maximize the score.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
If more than half the voters rank x first, more than half rank x above each rival. Hence x is a strict Condorcet winner. Apply this rule’s recorded Condorcet guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Use four candidates a,b,c,L with margins M(a,b)=M(b,c)=M(c,a)=4 and M(a,L)=M(b,L)=M(c,L)=2. Maximin scores are a:−4, b:−4, c:−4, L:−2, so L wins uniquely despite losing to every rival. These margins are realizable by 18 unweighted strict ballots. For every desired +2 contribution to M(x,y), use the two ballots x>y>rest and reverse(rest)>x>y. They add +2 only to that pair and cancel all other margins; repeating this for the six positive margins yields the recorded profile.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
If more than half the voters rank x first, more than half rank x above each rival. Hence x is a strict Condorcet winner. Apply this rule’s recorded Condorcet guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted clone blocks; Maximin’s failure requires at least three clones.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted clone blocks; Maximin’s failure requires at least three clones.
Deleting a clone can change who wins.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Condorcet consistency implies unanimity: if every voter ranks x first, x wins every pairwise contest and is the unique winner. The refinement is anonymous in voter identities, so with n≥2 it cannot be a dictatorship. The Gibbard–Satterthwaite theorem therefore rules out strategyproofness for unrestricted strict rankings over m≥3 candidates.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Let L lose to every rival. Each rival has a positive-margin direct path to L. Any path leaving L begins with a negative-margin edge, so it cannot match that positive strength. Thus L is defeated in the strongest-path comparison. Equivalently, apply the Smith criterion with the other candidates as the dominating set.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
If more than half the voters rank x first, more than half rank x above each rival. Hence x is a strict Condorcet winner. Apply this rule’s recorded Condorcet guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
A strict Condorcet loser L has no outgoing positive-margin edge. Consequently each positive edge y→L can be locked without creating a directed cycle: such a cycle would need an outgoing path from L. At least one such incoming edge is locked, so L is never a source and cannot win under any equal-margin order. Returning the union over all tie-break orders does not change this.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
If more than half the voters rank x first, more than half rank x above each rival. Hence x is a strict Condorcet winner. Apply this rule’s recorded Condorcet guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Equal margins are allowed. This is the original all-tie-breaks correspondence, not Zavist–Tideman’s modified tie-break.
Ballots
Complete strict rankings of all candidates
Conditions
Equal margins are allowed. This is the original all-tie-breaks correspondence, not Zavist–Tideman’s modified tie-break.
PUT Ranked Pairs can fail clone independence.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The first branch of Black’s definition returns the strict Condorcet winner alone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A Condorcet loser is not a Condorcet winner. Its Borda score is the sum of its pairwise support counts, each below n/2, so its score is below the average n(m−1)/2 and cannot maximize Borda.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A strict majority’s first choice beats each rival pairwise. Apply the rule’s Condorcet-winner guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
If x is Condorcet winner, raising x preserves that. Otherwise x is Borda-maximal; raising x preserves Borda maximality and cannot create another Condorcet winner, since only comparisons involving x change, in x’s favor. A newly created Condorcet winner can only be x.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Every inserted candidate is adjacent to its original in every ballot, so it is a clone. The recorded winner sets change the winning status of an outsider or the existence of a winning clone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × b > a > c > d; 1 × b > c > d > a; 1 × b > d > c > a; 1 × c > d > a > b; 1 × c > d > b > a; 1 × d > b > c > a; 1 × d > c > a > b. Winners: c, d. After: 1 × b > a > c > z > d; 1 × b > d > c > z > a; 1 × b > z > c > d > a; 1 × c > z > d > b > a; 1 × d > b > c > z > a; 1 × d > c > z > a > b; 1 × z > c > d > a > b. Winners: c."
Unweighted; all nonempty subelectorates of an electorate of arbitrary size
Candidates
At least four candidates; all nonempty subelectorates of a pool of at least twelve voters.
Output
One winner
Ties
Fixed exogenous candidate-priority selects one member of the complete Black winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Ballots
Complete strict rankings of all candidates
Conditions
At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority selects one member of the complete Black winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. The stated rule model and complete strict ballots.
Ballots
Complete strict rankings of all candidates
Conditions
The stated rule model and complete strict ballots.
If an optimal ranking placed a strict Condorcet winner x below any candidates, moving x to first would improve the pairwise agreement sum, a contradiction.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Suppose an optimal Kemeny ranking puts a strict Condorcet loser L first. Move L to last, keeping all other candidates in their previous order. For each rival y, the pair’s agreement contribution increases because more voters prefer y to L than L to y. Other pairs are unchanged, so total disagreement strictly decreases, a contradiction.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Ballots
Complete strict rankings of all candidates
Conditions
Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
If more than half the voters rank x first, more than half rank x above each rival. Hence x is a strict Condorcet winner. Apply this rule’s recorded Condorcet guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. The stated rule model and complete strict ballots.
Ballots
Complete strict rankings of all candidates
Conditions
The stated rule model and complete strict ballots.
Fix an optimal ranking with x first. Raising x weakly improves its agreement advantage over every rival ranking: it already places x above every other candidate.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Unweighted; all nonempty subelectorates of a voter pool of at least twelve voters
Candidates
A fixed set of m ≥ 4 candidates
Output
One winner
Ties
A fixed exogenous candidate-priority order resolves final co-winner ties, unchanged across profiles and electorates
Input
The specified voting rule on its whole stated domain, not a single election instance. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Ballots
Complete strict rankings of all candidates
Conditions
Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority order resolves final co-winner ties
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Condorcet consistency implies unanimity: if every voter ranks x first, x wins every pairwise contest and is the unique winner. The refinement is anonymous in voter identities, so with n≥2 it cannot be a dictatorship. The Gibbard–Satterthwaite theorem therefore rules out strategyproofness for unrestricted strict rankings over m≥3 candidates.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A strict Condorcet winner has swap score zero. Every other candidate loses to it and needs at least one swap.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
In the displayed profile, d loses every pairwise contest but belongs to the computed winner set. Exact scores or counts are included.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 8 × b > c > a > d; 7 × c > a > b > d; 10 × d > a > b > c; 4 × d > c > a > b. Winners: d. Exact scores: {\"a\": 5, \"b\": 7, \"c\": 4, \"d\": 3}. "
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A strict majority’s first choice beats each rival pairwise. Apply the rule’s Condorcet-winner guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
The before/after profiles differ only by raising a. Exact evaluation removes that candidate from the winner set.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 5 × a > b > c > d > e; 2 × b > a > d > e > c; 4 × b > e > d > a > c; 8 × d > a > c > e > b. Winners: a. After: 5 × a > b > c > d > e; 2 × a > b > d > e > c; 4 × b > e > d > a > c; 8 × d > a > c > e > b. Winners: d. Exact scores: {\"a\": 3, \"b\": 4, \"c\": 17, \"d\": 4, \"e\": 18}. New exact scores: {\"a\": 3, \"b\": 6, \"c\": 17, \"d\": 2, \"e\": 18}. "
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Every inserted candidate is adjacent to its original in every ballot, so it is a clone. The recorded winner sets change the winning status of an outsider or the existence of a winning clone.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × a > b > d > c; 1 × a > c > b > d; 1 × b > a > c > d; 1 × b > c > a > d; 1 × b > d > a > c; 1 × c > a > b > d; 1 × c > b > a > d; 1 × c > d > b > a; 1 × d > a > c > b. Winners: a, b, c. After: 1 × a > c > b > z > d; 1 × a > z > b > d > c; 1 × c > a > b > z > d; 1 × c > b > z > a > d; 1 × c > d > z > b > a; 1 × d > a > c > b > z; 1 × z > b > a > c > d; 1 × z > b > c > a > d; 1 × z > b > d > a > c. Winners: c."
Unweighted; all nonempty subelectorates of an electorate of arbitrary size
Candidates
At least four candidates; all nonempty subelectorates of a pool of at least twelve voters.
Output
One winner
Ties
Fixed exogenous candidate-priority selects one member of the complete Dodgson winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Ballots
Complete strict rankings of all candidates
Conditions
At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority selects one member of the complete Dodgson winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A strict Condorcet winner retains all n voters. Every rival loses to it in the full profile, so no rival can have retained-electorate score n.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
In the displayed profile, b loses every pairwise contest but belongs to the computed winner set. Exact scores or counts are included.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Before: 1 × b > a > c > d; 1 × c > d > a > b; 1 × d > a > c > b. Winners: b, c, d. Exact scores: {\"a\": 0, \"b\": 1, \"c\": 1, \"d\": 1}. "
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
A strict majority’s first choice beats each rival pairwise. Apply the rule’s Condorcet-winner guarantee.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
For every retained voter subset, raising x preserves any strict Condorcet victory of x and cannot create a new strict Condorcet victory for a rival. Thus x’s maximum feasible subset size cannot decrease and every rival’s cannot increase.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Arbitrary finite set, at least two unless a record says otherwise
Output
Nonempty set of co-winners
Ties
Return every co-winner; no arbitrary final tie-break
Input
The specified voting rule on its whole stated domain, not a single election instance. Unrestricted complete strict rankings with the exact rule and tie convention above.
Ballots
Complete strict rankings of all candidates
Conditions
Unrestricted complete strict rankings with the exact rule and tie convention above.
Deleting c from the contiguous block {c,y,z} removes outsider a from the winner set. This is an integer, whole-voter Young counterexample, with Young scores obtained by enumerating every voter subset.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
"Clone block {c,y,z}. Before: 1 × a > b > c > y > z; 1 × a > y > z > c > b; 1 × b > a > c > y > z; 1 × y > c > z > a > b; 1 × y > z > c > b > a; 2 × z > c > y > b > a. Winners: a,c,y. Delete c. After: 1 × a > b > y > z; 1 × a > y > z > b; 1 × b > a > y > z; 1 × y > z > a > b; 1 × y > z > b > a; 2 × z > y > b > a. Winners: y. Outsider a loses."
Unweighted; all nonempty subelectorates of an electorate of arbitrary size
Candidates
At least four candidates; all nonempty subelectorates of a pool of at least twelve voters.
Output
One winner
Ties
Fixed exogenous candidate-priority selects one member of the complete Young winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Ballots
Complete strict rankings of all candidates
Conditions
At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Fixed exogenous candidate-priority selects one member of the complete Young winner set; for Coombs, take the union over all tied-elimination branches before this final tie-break.
Input
The specified voting rule on its whole stated domain, not a single election instance. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Ballots
Unrestricted complete strict rankings
Conditions
Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
For any x,y, the pairwise margin equals approval_total(x)−approval_total(y), since only 1-versus-0 voters contribute. Positive margin against every rival is exactly a unique maximum approval total.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
A negative pairwise margin to any rival means a lower approval total, by the same binary-utility identity.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Strictly preferring x to every rival under binary utilities means approving only x. More than half such voters give x more than n/2 approvals and leave every rival fewer than n/2 possible approvals.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Its total weakly increases and every rival’s total stays fixed. A prior maximum remains a maximum.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
All perfect clones have equal totals. Removing one changes no surviving total, so outsiders retain their winning status and any surviving clone wins exactly when a clone won before.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
One candidate selected by fixed external priority among maximum-score candidates
Ties
The same fixed exogenous candidate-priority order across all reports and subelectorates.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Let x maximize old totals S, and let y maximize S+u after the voter joins. Then S(x)≥S(y) and S(y)+u(y)≥S(x)+u(x), so u(y)≥u(x). Fixed priority resolves equal totals consistently.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
One candidate selected by fixed external priority among maximum-score candidates
Ties
The same fixed exogenous candidate-priority order across all reports and subelectorates.
Input
The specified voting rule on its whole stated domain, not a single election instance. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
Ballots
Approval subsets, interpreted as truthful binary utilities u_i(x) in {0,1}. All candidates with utility 1 are equally preferred; all with utility 0 are equally disliked. Empty and full ballots are allowed.
Conditions
Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms.
If truth elects an approved candidate, utility is already maximal. Otherwise a profitable lie must elect an approved x over an unapproved y. Compared with truth, lying cannot raise x’s score or lower y’s. The same fixed priority breaks any surviving equality, so it cannot cause that improvement.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
The explicit two-candidate example has strict pairwise winner a but unique score winner b.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
"Two voters report a=0.51, b=0.49. One reports a=0, b=1. A majority strictly prefers a, so a is the Condorcet and majority winner, while b is the Condorcet loser. Totals are a=1.02 and b=1.98, so b wins."
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
In the same two-candidate example b loses the only pairwise contest, but wins by total score.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
"Two voters report a=0.51, b=0.49. One reports a=0, b=1. A majority strictly prefers a, so a is the Condorcet and majority winner, while b is the Condorcet loser. Totals are a=1.02 and b=1.98, so b wins."
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
The same example has a uniquely best for two of three voters, but b has the larger total.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
"Two voters report a=0.51, b=0.49. One reports a=0, b=1. A majority strictly prefers a, so a is the Condorcet and majority winner, while b is the Condorcet loser. Totals are a=1.02 and b=1.98, so b wins."
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Its total weakly increases and every rival’s total stays fixed. A prior maximum remains a maximum.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Return every maximum-score candidate; participation and strategyproofness instead use a fixed exogenous candidate-priority winner.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
All perfect clones have equal totals. Removing one changes no surviving total, so outsiders retain their winning status and any surviving clone wins exactly when a clone won before.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
One candidate selected by fixed external priority among maximum-score candidates
Ties
The same fixed exogenous candidate-priority order across all reports and subelectorates.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Let x maximize old totals S, and let y maximize S+u after the voter joins. Then S(x)≥S(y) and S(y)+u(y)≥S(x)+u(x), so u(y)≥u(x). Fixed priority resolves equal totals consistently.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
One candidate selected by fixed external priority among maximum-score candidates
Ties
The same fixed exogenous candidate-priority order across all reports and subelectorates.
Input
The specified voting rule on its whole stated domain, not a single election instance. Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
Ballots
One utility report u_i(x) in [0,1] for every candidate. Truthful profiles are utilities themselves; x is strictly preferred to y exactly when u_i(x)>u_i(y). No forced normalization to attain both endpoints.
Conditions
Cardinal utilities and native † criteria. No assumption that voters must use both endpoints of the scale.
With two voters, the first has true utilities (a=.6,b=.4), the second reports (a=.2,b=.8). Truth elects b, with totals .8 and 1.2. If the first reports (1,0), a wins with 1.2 versus .8; its true utility rises from .4 to .6. No tie is involved.
Axiomatic status, not a computational complexity classification. Conditions and output conventions are part of this assertion.
This cell uses the native ballot criterion stated here, not the unrestricted strict-ranking version.
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Ballots
Complete strict rankings of all candidates
Let c beat everyone. The singleton {c} is retentive. In any other nonempty retentive set containing x, c is the Condorcet winner within D(x); induction forces TEQ(D(x))={c}, so the set contains c. It cannot be inclusion-minimal unless it is {c}.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Ballots
Complete strict rankings of all candidates
If more than half the voters rank c first, the same voters rank c above each rival. Thus c is the Condorcet winner and the TEQ Condorcet property applies.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. Unbounded candidate domain, strict complete ballots, odd unweighted electorate, and co-winner membership. This is failure of ordinary mono-raise. The 24-candidate stability example is not being used as a monotonicity witness.
Ballots
Complete strict rankings of all candidates
Laffond–Laslier–Le Breton, Theorem 3.8, equates tournament monotonicity with the uniqueness conjecture for minimal TEQ-retentive sets. Brandt et al. disprove that conjecture, so tournament monotonicity fails. The failure transfers to odd strict profiles: break any enlargement of a winner’s dominion into single-edge reversals and take a step where membership is first lost. Realize the relevant edge y→x with margin 1 and every other edge with sufficiently large odd margin using paired ranking ballots plus a ballot with y immediately above x. Raising x just above y reverses only that edge. This yields the required mono-raise failure without pairwise ties. No small counterexample or candidate bound is asserted here.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
A counterexample to a conjecture of Schwartz Felix Brandt, Maria Chudnovsky, Ilhee Kim, Gaku Liu, Sergey Norin, Alex Scott, Paul Seymour, and Stephan Thomassé · 2013 · Sections 2–3, Schwartz conjecture and its disproof
property · Rule properties
TEQ · Clone independence
Satisfies
Does TEQ satisfy clone independence under these assumptions?
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. Contiguous clones in every strict ballot; delete a member from a block of at least two, leaving at least one clone. Odd unweighted electorate and the full TEQ correspondence. No fixed-priority final choice is imposed.
Ballots
Complete strict rankings of all candidates
A contiguous clone block forms a module of the majority tournament: every outside candidate has the same majority direction against all clones. Composition consistency computes TEQ by choosing winning modules in the quotient tournament and then TEQ winners inside each chosen module. Deleting a clone while leaving a nonempty block does not change the quotient. Outsider membership is unchanged, and the block contributes a winner exactly when its quotient candidate wins, because its internal TEQ remains nonempty.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. The TEQ model in this row is defined only for nonempty odd electorates. Ordinary participation compares electorates differing by one voter, so it requires additional rule values outside this domain.
Ballots
Complete strict rankings of all candidates
Removing one voter from an odd electorate produces an even electorate, for which this model supplies no rule value. Thus ordinary single-voter participation cannot be evaluated on this row. This is a domain limitation, not an unresolved theorem. A pairwise-tie extension and a precise final-choice convention would define a separate rule model; no Condorcet no-show theorem is imported here.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
Three unweighted voters in the displayed counterexample
Candidates
Three candidates in the displayed counterexample
Output
One TEQ winner
Ties
No pairwise ties. Fix an exogenous candidate-priority order a > b > c for the final TEQ co-winner choice.
Input
The specified TEQ model on its whole stated domain, not one election. Three candidates and three unweighted voters suffice. Fixed exogenous candidate-priority order a>b>c selects one element of TEQ. This does not classify set-valued TEQ strategyproofness or the complexity of finding a manipulation.
Ballots
Complete strict rankings of all candidates
With truthful ballots a>b>c, b>c>a, and c>a>b, the majority tournament is a→b→c→a. TEQ is {a,b,c}; priority a>b>c selects a. The second voter reports c>b>a instead. Now c beats both rivals, so TEQ={c}. That voter’s true ranking b>c>a strictly prefers c to a. Both profiles have three unweighted voters and no pairwise ties. This example is only about the specified resolute refinement and does not claim a violation for any particular preference extension over sets.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
Odd electorate and strict rankings exclude pairwise ties. Return all TEQ members; no final tie-break.
Input
The specified TEQ model on its whole stated domain, not one election. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Ballots
Complete strict rankings of all candidates
Let l lose to every other candidate. A retentive set containing l must contain another candidate because TEQ(D(l)) is nonempty. Removing l from that set preserves retentiveness: l is not in D(x) for any other x, so no remaining candidate depends on l. A retentive set containing l is therefore not inclusion-minimal, and l is absent from their union.
Axiomatic status, not a computational complexity classification. Pairwise ties and final-choice conventions are part of the model.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Any fixed finite alternative set; odd n≥3
Output
Transitive strict majority ranking; its top is the unique Condorcet winner
Ties
Odd electorate and strict preferences eliminate pairwise ties.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Strict complete preferences single-peaked with respect to one fixed common candidate axis
For an odd electorate, the median voter peak beats every rival. The same argument on each restricted triple rules out majority cycles, hence the strict majority tournament is transitive.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 2 alternatives; fixed even n≥2
Output
One deterministic winner
Ties
The rule itself must return one winner; tie handling is part of the function.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
At an evenly split profile, swapping a and b produces a voter permutation. Anonymity says the winner stays fixed, while neutrality says it switches. A single deterministic winner cannot satisfy both.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 2 alternatives; any fixed finite n≥1
Output
Prefer a, prefer b, or social indifference
Ties
Equal numbers of opposing strict preferences produce social indifference.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Each voter submits a preference for a, a preference for b, or indifference
Only simple majority: output sign(sum of votes in {−1,0,+1}). At a balanced profile anonymity and neutrality force 0; positive responsiveness settles any imbalance by comparison with a balanced profile.
Positive responsiveness means any nonzero componentwise increase from a nonnegative outcome yields +1, with the reverse by neutrality. The proof below derives the characterization directly from these axioms.
A characterization of binary social preference, not a multi-candidate rule or complexity class.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
A fixed finite alternative set of size at least 3; theorem uniform in its size
Output
Complete transitive social ranking; indifference allowed
Ties
Both voters and the social ranking may have indifferences.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
All complete transitive preferences, including weak rankings
With at least three alternatives, unrestricted complete transitive input rankings and a complete transitive social ranking, Pareto and pairwise independence force a dictator.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 2 alternatives; fixed n≥2 voters
Output
Binary social preference, possibly indifferent
Ties
Equal opposing counts produce social indifference.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Each voter prefers a, prefers b, or is indifferent
Compare the numbers strictly preferring each option. Output the majority ordering and social indifference on equality. With n≥2 this is nondictatorial; transitivity is automatic on two alternatives.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Any fixed finite set with m≥3 and n≥2 voters
Output
One deterministic winner
Ties
The rule itself must return one winner; tie handling is part of the function.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
On all strict preference profiles over at least three alternatives, an onto strategyproof deterministic choice function is dictatorial. This guarantees some manipulation for a nondictatorial rule, not an efficient method to find it.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 2 alternatives; odd n≥3
Output
One deterministic winner
Ties
No tie under the odd-electorate strict-ballot assumption.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
With an odd n≥3, majority voting is onto and nondictatorial. A voter can only move the tally toward the less preferred alternative by lying, so a lie cannot improve the outcome.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 4 alternatives; all nonempty subsets of a fixed set of 11 available voters
Output
One deterministic winner
Ties
The rule itself must return one winner; tie handling is part of the function.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
The primary paper supplies a finite rule through a SAT-derived lookup table. It also depends only on majority margins, is Pareto optimal, and chooses within the top cycle.
The existence proof uses a published million-entry lookup-table certificate.
Possible does not identify a familiar closed-form voting rule or a complexity class.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Exactly 4 alternatives; all nonempty subsets of a fixed set of 12 available voters
Output
One deterministic winner
Ties
The rule itself must return one winner; tie handling is part of the function.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
No such rule exists. A sequence of voter additions and deletions forces incompatible winners. Participation compares the chosen outcome with and without one voter; it is a variable-electorate condition.
The domain includes smaller electorates too. This is not a statement about an isolated election with exactly 12 voters. No anonymity assumption is needed.
Existence impossibility, not algorithmic hardness.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Any fixed finite candidate set and nonincreasing scoring vector; variable finite electorate
Output
One deterministic winner
Ties
One fixed candidate priority independent of profile and electorate size.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Use one fixed priority order to break score ties. If the added voter prefers old winner x over y, their score contribution to x is at least that to y. Since x previously beat y under the same priority, y cannot replace x. Thus any new winner is weakly preferred.
The fixed tie order is essential to this stated proof. Condorcet consistency is not claimed.
This is an axiom guarantee, not a complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Finite set with at least 3 alternatives; at least 2 voters
Output
A social preference relation with a maximal element on each nonempty feasible subset
Ties
Social indifference allowed; every feasible set must have a best alternative.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
All complete transitive individual preferences
Sen’s Theorem II needs only two people, each decisive on one pair in both directions. Their protected comparisons and a unanimous comparison can force a cycle with no maximal choice. Full social transitivity is not required.
“Liberalism” is Sen’s formal pairwise decisiveness condition, not a general claim about political liberalism.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Finite linearly ordered set with m≥3; odd n≥3
Output
One deterministic winner
Ties
The rule itself must return one winner; tie handling is part of the function.
Input
Every profile of peaks on one fixed axis; reports must remain on that axis.
Ballots
Single-peaked strict preferences on a fixed known axis; report only the peak
For odd n≥3, return the median reported peak on the fixed axis. Moving a report can only leave the median fixed or move it away from that voter’s true peak along one side. A report therefore cannot improve the result.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
A fixed closed real interval [L,U], L<U; n≥2
Output
One deterministic winner
Ties
Median of 2n+1 values is uniquely defined even when some values coincide.
Input
A tops-only function [L,U]^n → [L,U].
Ballots
All single-peaked preferences on [L,U]; only peaks are reported
For n voters reporting peaks on [L,U], exactly the median rules obtained by adding n+1 fixed phantom points in [L,U] are anonymous and strategyproof. Tops-only reporting is an explicit modeling assumption.
An existence/axiom statement, not a computational complexity classification.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
Fixed finite m≥3; finite electorate
Output
A nonempty set of candidates
Ties
No tie-breaker is imposed. Set preferences are specified via best/worst members.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Duggan–Schwartz’s stronger sovereignty/nondictatorship variant forbids this combination. Singleton-onto means each candidate is the sole winner somewhere. A weak dictator’s favorite is always included. Optimists compare best members; pessimists compare worst members.
The theorem does not cover every possible preference extension over sets. Singleton-onto and no weak dictator are stronger than the corresponding conditions for the main residual-resoluteness theorem.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
m≥3 alternatives; n≥2 voters
Output
Uniform random voter’s favorite candidate
Ties
No tied input rankings. Output may randomize among several candidates.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Select each of n≥2 voters with probability 1/n and elect their top. Reporting truthfully maximizes the voter’s own lottery contribution; the remaining probability is unchanged. There is no single fixed dictator.
An existence/axiom statement, not a computational complexity classification.
Randomized rules · Ex ante efficiency closes that escape
Impossible
Can an unrestricted strict-ranking lottery rule be nondictatorial, strongly SD-strategyproof, and ex ante Pareto efficient for every compatible utility profile?
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
A fixed finite alternative set of size at least 3; theorem uniform in its size
Output
Probability distribution over candidates
Ties
No tied input rankings.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Gibbard’s Corollary 2 forces a single dictator under these assumptions. Here ex ante efficiency means no other lottery makes every voter strictly better in expected utility, for any utilities inducing the reported strict orders.
Ex ante lottery efficiency is stronger than merely giving zero probability to Pareto-dominated candidates.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
A fixed finite alternative set of size at least 3; theorem uniform in its size
Output
Probability distribution over candidates
Ties
Randomization is the output, not an unspecified tie-breaker.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Exactly fixed mixtures of localized, nonperverse components that are unilateral or duple. Unilateral means only one voter matters; duple means support lies in one fixed pair. The extra component conditions are essential to the converse.
Not the weaker condition merely forbidding a strictly SD-dominating misreport. No unrestricted-domain conclusion for weak ballot orders is claimed.
This is an axiomatic characterization, not a complexity class.
A finite list of voters; no numeric vote weights. Equal treatment is assumed only when anonymity is explicitly required.
Candidates
A fixed finite alternative set of size at least 3; theorem uniform in its size
Output
Choose voter i with fixed probability λ_i, then their top; λ_i≥0 and sum λ_i=1
Ties
Strict rankings give each sampled voter a unique top.
Input
A function defined on every profile in the specified domain, not one election instance.
Ballots
Unrestricted strict complete rankings
Exactly fixed mixtures of dictatorships. From Gibbard’s decomposition, unanimity rules out every positive-weight duple component by unanimously topping an outside candidate. It forces each unilateral component to choose its voter’s top. The converse follows directly.
Unanimity here means a common top candidate receives probability 1. Corollary 1 uses ex post efficiency; the proof below establishes the stated unanimity version.
A mixture of dictators need not have one fixed dictator. No complexity classification.
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives and at least two voters
Output
Distribution with full support on linear extensions of unanimously certain comparisons
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
Definition 2.12 now explicitly applies support-count QCV directly to the reduced ballots, with Ω(x>y) the normalized uniform projection and 0<delta<1/|A|². Let P be the comparisons certain in every marginal. Minority spreading gives positive weight to every ranking consistent with P; unanimity projection leaves exactly these rankings. Every ranking with positive probability in any marginal survives. Thus a pair has positive social probability iff some voter supports it, and it is socially certain iff all voters are certain of it.
Use the manuscript's modified support-count rule, positive uniform support spreading, and 0<delta<1/|A|^2.
This is a narrow support guarantee, not a physical quantum-channel or computational-efficiency claim.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 2.12, printed p.7; Appendix C, Corollary 3.2.1 proof, printed p.16
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives; at least two voters
Output
Diagonal candidate density operator, equivalently a lottery over candidates
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed. Fix a rule parameter 0<delta<1/m², where m is the number of candidates.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
For candidate a, let p_i(a) be the truthful top probability and r(a) the social winning probability. The forbidden events are: p_i(a)=1 and r(a)<1 becoming r′(a)=1; p_i(a)=0 and r(a)>0 becoming r′(a)=0; and p_i(a)>0 and r(a)=0 becoming r′(a)>0. Since positive social support is exactly the union U of individual top supports, another voter preserves the conflicting support in the first two cases; the third cannot start. This proof applies to any welfare rule preserving every individually top-supported candidate before filtering. It covers joint profiles when every other voter’s reduced ballot stays fixed.
Support-boundary incentive compatibility only. It does not prohibit all changes in winning probabilities and is not stochastic-dominance or expected-utility strategy-proofness.
The rule is defined directly from marginal supports and is nonlinear; no physical quantum-channel implementation, efficiency bound, or quantum advantage follows.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Eq. (2), Theorem 3.1, Corollary 3.2.1 and Appendix C, printed pp.10–11 and 15–16
existence · Incentive compatibility
Modified QCV · Pairwise incentive compatibility
Possible
Can one voter force a favorable support-boundary change for a pair?
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
No, under the specified pairwise notion. If the voter is already certain of a>b and society is not, another voter supports b>a and still does after the report. If the voter gives a>b zero support but society gives it positive support, another voter supplies that support and continues to do so. If the voter gives a>b positive support, society already does, so the third manipulation event cannot begin.
The guarantee concerns the manuscript's support-boundary pairwise incentive notion.
This does not imply incentive compatibility after converting rankings to a winner lottery.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Theorem 3.2, printed p.11; revised Appendix C proof, printed p.16
model · Incentive compatibility
Indecisive voting · Winner support incentives
Model
Which changes count as a profitable deviation for a possible winner?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
Finite set of at least three alternatives unless stated otherwise
Output
Distribution over rankings or over alternatives as specified
Ties
Rankings in the support are strict total orders; output uncertainty is a probability distribution, not a ranking tie
Input
Probability distributions over strict rankings; axiomatic setting, no finite-precision algorithmic encoding fixed
Ballots
Distributions over strict complete rankings
Unilateral deviations
One voter changes their report; every other voter’s reduced ballot remains fixed. For ordinary indecisive ballots this means all other submitted distributions remain fixed.
Use the truthful probability p that candidate a is top, and the social winning probability q. The three prohibited transitions are the same boundary events as for pairs: p=1 with q<1 to q'=1; p=0 with q>0 to q'=0; and p>0 with q=0 to q'>0. Being top is a joint event involving all rivals.
This is support-boundary incentive compatibility, not ordinary ordinal, stochastic-dominance, or expected-utility strategy-proofness. Changes strictly inside (0,1) are not prohibited.
Pairwise positive support against every rival need not give positive support for being top.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 3.7 and correlated-deviation convention, printed p.11 (PDF p.12)
model · Incentive compatibility
Indecisive voting · Pairwise support incentives
Model
Which changes count as a profitable deviation for a pair?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
Finite set of at least three alternatives unless stated otherwise
Output
Social probability distribution over full rankings
Ties
Rankings in the support are strict total orders; output uncertainty is a probability distribution, not a ranking tie
Input
Probability distributions over strict rankings; axiomatic setting, no finite-precision algorithmic encoding fixed
Ballots
Distributions over strict complete rankings
Unilateral deviations
One voter deviates; all other submitted ballots held fixed
For a fixed ordered pair a>b, let p be its truthful individual probability and q its social probability. A deviation is forbidden if p=1 and q<1 becomes q'=1; if p=0 and q>0 becomes q'=0; or if p>0 and q=0 becomes q'>0. Changes strictly inside (0,1) are not classified as profitable by this definition.
This is a support-boundary incentive notion. It is not ordinary ordinal strategy-proofness, expected-utility strategy-proofness, or strong stochastic-dominance strategy-proofness.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definitions 2.1 and 3.6, printed pp.3-4 and 10
existence · Non-dictatorship
Top-supported QCV · No fixed sharp or unsharp dictator
Possible
Can any one fixed voter control all top-certainty or top-support events?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives; at least two voters
Output
Diagonal candidate density operator, equivalently a lottery over candidates
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed. Fix a rule parameter 0<delta<1/m², where m is the number of candidates.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
Fix any proposed dictator i. Give i a ballot certainly topped by a, and another voter a ballot certainly topped by b≠a. Both a and b belong to U, so both have positive social probability. Society is not certain of a although voter i is; society supports b although voter i does not. Since this witness exists for each fixed i, neither a sharp nor an unsharp dictator exists. This is a direct proof for the filtered rule, not a generic welfare-to-choice preservation theorem.
Support-boundary incentive compatibility only. It does not prohibit all changes in winning probabilities and is not stochastic-dominance or expected-utility strategy-proofness.
The rule is defined directly from marginal supports and is nonlinear; no physical quantum-channel implementation, efficiency bound, or quantum advantage follows.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 3.8 and Lemma 3.3, printed p.12; Appendix C proof, printed p.17
existence · Onto property
Top-supported QCV · Every candidate can win certainly
Possible
Can each candidate receive winning probability one at some profile?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives; at least two voters
Output
Diagonal candidate density operator, equivalently a lottery over candidates
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed. Fix a rule parameter 0<delta<1/m², where m is the number of candidates.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
For any candidate a, let every voter place a first with certainty. Then U={a}; Eq. (2) assigns a probability one. This is candidate-wise onto under Definition 3.9, not surjectivity onto all lotteries or all density operators.
Support-boundary incentive compatibility only. It does not prohibit all changes in winning probabilities and is not stochastic-dominance or expected-utility strategy-proofness.
The rule is defined directly from marginal supports and is nonlinear; no physical quantum-channel implementation, efficiency bound, or quantum advantage follows.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 3.9 and Theorem 3.4, printed p.12; Appendix C proof, printed p.17
model · Ballot model
Indecisive voting · Distributions as ballots
Model
What changes when voters submit distributions over rankings?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
Finite set of at least three alternatives unless stated otherwise
Output
Distribution over rankings or over alternatives as specified
Ties
Rankings in the support are strict total orders; output uncertainty is a probability distribution, not a ranking tie
Input
Probability distributions over strict rankings; axiomatic setting, no finite-precision algorithmic encoding fixed
Ballots
Distributions over strict complete rankings
Unilateral deviations
One voter deviates; all other submitted ballots held fixed
Each voter submits delta_i in Delta(L(A)); pairwise probabilities are sums over all rankings containing that pair. A point mass recovers an ordinary strict ballot. This is distinct from an ordinary ordinal rule whose output alone is randomized. Classical distributions embed unambiguously as diagonal density matrices.
A change of domain does not invalidate a classical theorem on its original domain.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Sections 1.1, 2, and 2.2, printed pp.1-5
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
Finite set of at least three alternatives unless stated otherwise
Output
A density operator over rankings or candidates; measurement in the designated basis induces a probability distribution.
Ties
Rankings in the support are strict total orders; output uncertainty is a probability distribution, not a ranking tie
Input
Density operators on ranking spaces, or joint tensor-product ranking space; no complexity input encoding fixed
Ballots
Density matrices in a basis of strict complete rankings
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
A ranking basis has dimension |L(A)|. Diagonal density operators encode ranking distributions; general density operators may have coherences. The October 2026 manuscript defines unilateral deviations of a joint profile as replacements preserving every other voter’s reduced ballot, including local trace-preserving operations. The recorded QCV rule depends only on the ranking-basis diagonal probabilities of those marginals.
A diagonal mixture and a coherent pure state with the same measurement probabilities are different states. The recorded QCV and filtered choice rule return the same outcome for them.
The direct support-count rule is nonlinear; these mathematical axiomatic results do not establish a completely positive trace-preserving quantum-channel implementation or a quantum advantage.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definitions 2.5-2.10, printed pp.5-6
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
Finite set of at least three alternatives unless stated otherwise
Output
Distribution over rankings or over alternatives as specified
Ties
Rankings in the support are strict total orders; output uncertainty is a probability distribution, not a ranking tie
Input
Probability distributions over strict rankings; axiomatic setting, no finite-precision algorithmic encoding fixed
Ballots
Distributions over strict complete rankings
Unilateral deviations
One voter deviates; all other submitted ballots held fixed
Given a ranking distribution p_R, set the winning probability of a to sum_{R:top(R)=a} p_R. Equivalently use the diagonal output density matrix sum_a p_a |a><a|. All information below the top position is discarded. The output probability of a is the probability of the intersection of all events a>b, not a function of their individual probabilities alone.
This transformation uses only the welfare output. The top-supported choice rule also uses the submitted profile to determine its support.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definitions 3.2–3.4 and Eq. (1), printed pp.8–9
model · Choice rule construction
Top-supported QCV · Keep candidates with top support
Model
How does top-supported choice turn QCV rankings into a candidate lottery?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives; at least two voters
Output
Diagonal candidate density operator, equivalently a lottery over candidates
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed. Fix a rule parameter 0<delta<1/m², where m is the number of candidates.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
Let p_i(a) be voter i’s top-choice probability, U={a:some p_i(a)>0}, and q_a the top-choice probability in QCV’s welfare output. Eq. (2) sets the winning probability to q_a/sum_{b in U}q_b for a in U, and zero otherwise. Every individually supported ranking survives QCV minority spreading and unanimity projection, so q_a>0 for every a in U and the denominator is positive. The possible winners are exactly U. This filter depends on the submitted profile, not only on the welfare output.
Support-boundary incentive compatibility only. It does not prohibit all changes in winning probabilities and is not stochastic-dominance or expected-utility strategy-proofness.
The rule is defined directly from marginal supports and is nonlinear; no physical quantum-channel implementation, efficiency bound, or quantum advantage follows.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Eq. (2), Theorem 3.1, Corollary 3.2.1 and Appendix C, printed pp.10–11 and 15–16
existence · Incentive comparison
Top-supported QCV · Boundary IC does not imply SD strategy-proofness
Counterexample
Can top-supported choice admit an ordinary stochastic-dominance improvement?
Explicit voters with no external numeric weights; anonymity is not assumed for an arbitrary aggregation function.
Candidates
At least three alternatives; at least two voters
Output
Diagonal candidate density operator, equivalently a lottery over candidates
Ties
Input ranking basis consists of strict complete orders. QCV score ties are completed uniformly over all compatible strict orders; the final lottery is uncertainty, not a ranking tie. No deterministic tie priority is imposed.
Input
Joint density operator over strict-ranking spaces; the rule uses only reduced-ballot diagonal probabilities. Independent ranking distributions are a special case. No finite-precision computational encoding is fixed. Fix a rule parameter 0<delta<1/m², where m is the number of candidates.
Ballots
Ranking distributions or general density operators; only ranking-basis probabilities affect this rule
Unilateral deviations
One voter deviates through a replacement joint profile preserving every other voter’s reduced ballot.
Yes, on the strict-ballot restriction. Take truthful rankings a>b>c and b>a>c, and delta=1/18. The top-supported rule gives lottery (a:1/2,b:1/2,c:0). If voter 1 reports a>c>b, direct QCV followed by Eq. (2) gives (17/32,15/32,0). For truthful a>b>c, probability of the best candidate increases while probability of either top-two candidate remains one, a strict stochastic-dominance improvement. With utilities (1,1/2,0), expected utility rises from 3/4 to 49/64. No support boundary changes: both lotteries have support {a,b}. The change therefore preserves support-boundary incentive compatibility.
Support-boundary incentive compatibility only. It does not prohibit all changes in winning probabilities and is not stochastic-dominance or expected-utility strategy-proofness.
The rule is defined directly from marginal supports and is nonlinear; no physical quantum-channel implementation, efficiency bound, or quantum advantage follows.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 2.12 and Eq. (2), printed pp.7 and 10; atlas derivation of the displayed two-voter example
Hardness sources
Partition and Hitting Set as the sources of documented reductions. Quantified formulas appear with Stable Voting.
Explicit nonempty finite universe B, explicit family of nonempty subsets S₁,…,Sₙ, and binary integer k with 1≤k≤|B|.
Ballots
Not applicable
This is bounded at-least-one Hitting Set. Transposing the incidence relation turns Set Cover into this problem. It is not the exact-one problem called HITTING SET in Karp’s original list. Trivial inputs can be decided first, so this restricted domain remains NP-complete.
Explicit nonempty Boolean formula in conjunctive normal form, each clause containing exactly three literals on distinct variables. No clause contains both a variable and its negation. The numbers of variables and clauses are unbounded.
Ballots
Not applicable
A guessed assignment is checked in polynomial time. Standard 3SAT remains NP-hard with three distinct noncomplementary literals per clause: remove tautologies and repeated literals, then pad clauses with fewer than three literals using fresh variables and both polarities. The cited TEQ and Banks constructions use this convention; the seven-voter theorem additionally converts it to Ordered3SAT through Lemma 11.
Only edges explicitly marked composable participate in decision-reduction paths. Winner inclusion, property application and theorem application have their own stated meanings.
Transfer. A polynomial-time winner-returning algorithm gives a polynomial-time winner-membership algorithm. This decision-to-function link is not a decision many-one path step.
Conditions. Same election and encoding; distinct nonzero margins ensure exactly one winner.
Explanation and sources
Call the unique-winner function on the election, then accept exactly when its output equals the designated candidate.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · H.1–H.2, pp. 50–51
winner-inclusion · Not part of decision many-one paths
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out the source candidate. A target yes-answer need not settle the source. This is not a many-one reduction and transfers no hardness.
Conditions. Keep the same complete strict profile and candidate. Source promise: all induced off-diagonal margins are distinct and nonzero.
Explanation and sources
The Stable Voting winner belongs to the Split Cycle winner set.
Stable Voting Wesley H. Holliday; Eric Pacuit · 2023 · Section 2, equivalent undefeated-candidate definition
Transfer. The rule depends only on margin order, which is preserved. The construction uses O(m^4) unweighted voters, where m is the number of candidates.
Conditions. Distinct nonzero margins. Rank normalization is essential for arbitrary binary-encoded magnitudes.
Explanation and sources
Replace the r-th smallest positive margin by 2r, maintain skew symmetry, then realize each margin with a pair of opposing ballot orders.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Section 2 and Appendix A, p. 30
Transfer. A polynomial-time search algorithm gives polynomial-time winner membership. This single call explains PSPACE-hardness; the stronger FPSPACE(poly)-completeness classification allows polynomially many nonadaptive calls.
Conditions. Same explicit matrix; distinct nonzero margins ensure exactly one winner.
Explanation and sources
Ask for the winner, then test whether it equals the designated candidate.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Theorem 5.8; H.1–H.2, pp. 50–51
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Theorem 5.8; H.1–H.2, pp. 50–51
winner-inclusion · Not part of decision many-one paths
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out the source candidate. A target yes-answer need not settle the source. This is not a many-one reduction and transfers no hardness.
Conditions. Keep the same matrix and candidate. Source margins are nonzero and pairwise distinct; the target accepts this subdomain.
Explanation and sources
Stable Voting selects only Split Cycle-undefeated candidates.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Definition 2.4; discussion immediately following it
function-oracle · Not part of decision many-one paths
Transfer. A polynomial-time single-winner algorithm gives a polynomial-time full deletion-profile algorithm. Polynomially many calls are allowed; this is not a one-call metric reduction.
Conditions. N ≥ 2, same rule and input representation, distinct nonzero margins inherited by every child; all N queries are fixed before receiving answers.
Explanation and sources
Prepare the N elections obtained by deleting one candidate. Ask for all their winners without depending on previous answers, then concatenate the returned original candidate indices in the supplied order.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Definition (10), p. 50; Theorem H.7 membership proof, p. 54
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Compute the pairwise margin matrix from the explicit unweighted ballots. Retain the candidate enumeration; the rule and all its candidate-deletion restrictions see exactly those margins.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Compute the pairwise margin matrix from the explicit unweighted ballots. Retain the candidate enumeration; the rule and all its candidate-deletion restrictions see exactly those margins.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-oracle · Not part of decision many-one paths
Transfer. A polynomial-time single-winner algorithm gives a polynomial-time full deletion-profile algorithm. Polynomially many calls are allowed; this is not a one-call metric reduction.
Conditions. N ≥ 2, same rule and input representation, distinct nonzero margins inherited by every child; all N queries are fixed before receiving answers.
Explanation and sources
Prepare the N elections obtained by deleting one candidate. Ask for all their winners without depending on previous answers, then concatenate the returned original candidate indices in the supplied order.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Definition (10), p. 50; Theorem H.7 membership proof, p. 54
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Replace distinct absolute margins by ranks, double them, and realize each positive margin with cancelling ballot pairs. Candidate labels and every induced-subtournament winner are preserved.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Replace distinct absolute margins by ranks, double them, and realize each positive margin with cancelling ballot pairs. Candidate labels and every induced-subtournament winner are preserved.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
Transfer. An algorithm for unrestricted winner search also solves the two-output restriction. Hardness of the promised source transfers only under the stated function-reduction convention.
Conditions. Distinct nonzero margins and supplied two-winner promise at the source; variable candidate count; same matrix representation.
Explanation and sources
Pass the tournament to the unrestricted unique-winner function and return its answer. Every promised source instance is a valid unrestricted target instance.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Proposition H.3 and Theorem H.6, pp. 51–52
property-application · Not part of decision many-one paths
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects the strict pairwise-majority winner.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 4, Proposition 4 and Corollary 1; section opening includes SSV
property-application · Not part of decision many-one paths
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict first-place majority guarantees victory.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Condorcet property plus elementary implication
Transfer. A polynomial-time winner-returning algorithm gives a polynomial-time winner-membership algorithm. This decision-to-function link is not a decision many-one path step.
Conditions. Same election and encoding; distinct nonzero margins ensure exactly one winner.
Explanation and sources
Call the unique-winner function on the election, then accept exactly when its output equals the designated candidate.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · H.1–H.2, pp. 50–51
Transfer. The rule depends only on margin order, which is preserved. The construction uses O(m^4) unweighted voters, where m is the number of candidates.
Conditions. Distinct nonzero margins. Rank normalization is essential for arbitrary binary-encoded magnitudes.
Explanation and sources
Replace the r-th smallest positive margin by 2r, maintain skew symmetry, then realize each margin with a pair of opposing ballot orders.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Section 2 and Appendix A, p. 30
Transfer. A polynomial-time winner-returning algorithm gives a polynomial-time winner-membership algorithm. This decision-to-function link is not a decision many-one path step.
Conditions. Same election and encoding; distinct nonzero margins ensure exactly one winner.
Explanation and sources
Call the unique-winner function on the election, then accept exactly when its output equals the designated candidate.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · H.1–H.2, pp. 50–51
Transfer. Answers coincide for at most six candidates; they can differ from seven onward. No reduction or complexity transfer is asserted.
Conditions. Same matrix with distinct nonzero off-diagonal margins. The six-candidate agreement is a bounded-domain statement, not general equivalence.
Explanation and sources
SSV and SV coincide through six candidates with distinct margins. A seven-candidate example makes SSV select a Split Cycle-defeated candidate, which SV cannot select.
Transfer. A polynomial-time single-winner algorithm gives a polynomial-time full deletion-profile algorithm. Polynomially many calls are allowed; this is not a one-call metric reduction.
Conditions. N ≥ 2, same rule and input representation, distinct nonzero margins inherited by every child; all N queries are fixed before receiving answers.
Explanation and sources
Prepare the N elections obtained by deleting one candidate. Ask for all their winners without depending on previous answers, then concatenate the returned original candidate indices in the supplied order.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Definition (10), p. 50; Theorem H.7 membership proof, p. 54
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Compute the pairwise margin matrix from the explicit unweighted ballots. Retain the candidate enumeration; the rule and all its candidate-deletion restrictions see exactly those margins.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Compute the pairwise margin matrix from the explicit unweighted ballots. Retain the candidate enumeration; the rule and all its candidate-deletion restrictions see exactly those margins.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-oracle · Not part of decision many-one paths
Transfer. A polynomial-time single-winner algorithm gives a polynomial-time full deletion-profile algorithm. Polynomially many calls are allowed; this is not a one-call metric reduction.
Conditions. N ≥ 2, same rule and input representation, distinct nonzero margins inherited by every child; all N queries are fixed before receiving answers.
Explanation and sources
Prepare the N elections obtained by deleting one candidate. Ask for all their winners without depending on previous answers, then concatenate the returned original candidate indices in the supplied order.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Definition (10), p. 50; Theorem H.7 membership proof, p. 54
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Replace distinct absolute margins by ranks, double them, and realize each positive margin with cancelling ballot pairs. Candidate labels and every induced-subtournament winner are preserved.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
function-representation · Not part of decision many-one paths
Transfer. An algorithm for the target encoding solves the source function by one call and index-preserving postprocessing. Polynomial-time solvability and polynomial-space upper bounds transfer; no decision-path composition is asserted.
Conditions. Same rule, distinct nonzero margins, explicit binary matrix or explicit unweighted strict complete ballots; candidate indices are preserved. Rank normalization gives a polynomial-size ballot representation, rather than expanding raw binary weights.
Explanation and sources
Replace distinct absolute margins by ranks, double them, and realize each positive margin with cancelling ballot pairs. Candidate labels and every induced-subtournament winner are preserved.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Lemmas F.2–F.3, pp. 45–46; H.1, p. 50
Transfer. An algorithm for unrestricted winner search also solves the two-output restriction. Hardness of the promised source transfers only under the stated function-reduction convention.
Conditions. Distinct nonzero margins and supplied two-winner promise at the source; variable candidate count; same matrix representation.
Explanation and sources
Pass the tournament to the unrestricted unique-winner function and return its answer. Every promised source instance is a valid unrestricted target instance.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 · Proposition H.3 and Theorem H.6, pp. 51–52
property-application · Not part of decision many-one paths
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. Full strict-profile domain, including tied margins; no uniquely-weighted restriction is needed. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects the strict pairwise-majority winner.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Section 4, Proposition 4 and Corollary 1; section opening includes SSV
property-application · Not part of decision many-one paths
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict first-place majority guarantees victory.
Stable Voting Wesley H. Holliday and Eric Pacuit · 2023 · Condorcet property plus elementary implication
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects the strict pairwise-majority winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict first-place majority guarantees victory.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Clone deletion preserves outsiders and whether a clone wins.
Transfer. An algorithm for the target solves the source. Hardness of the source transfers forward; an algorithmic upper bound for the target transfers backward. Target hardness alone says nothing about the source.
Conditions. Variable number of voters; strict rankings; plurality only.
Explanation and sources
Add one unweighted ballot ranking p first. Integer scores satisfy score(p)+1 > score(q) exactly when score(p) ≥ score(q). Other rankings on the new ballot are arbitrary.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Use the original profile, target candidate, and bribe budget k = 0.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Elementary embedding from FHH09 Section 2.2 definitions.
Transfer. An algorithm for the target solves the source. Hardness of the source transfers forward; an algorithmic upper bound for the target transfers backward. Target hardness alone says nothing about the source.
Conditions. Explicit ballots and coalition list; co-winner success at both endpoints. The indicated fixed parameter is the only change.
Explanation and sources
Keep the profile and designated candidate; provide an empty manipulator list.
Transfer. An algorithm for the target solves the source. Hardness of the source transfers forward; an algorithmic upper bound for the target transfers backward. Target hardness alone says nothing about the source.
Conditions. Variable number of voters; plurality only.
Explanation and sources
For each rival q add one q-first ballot. Now score(p) ≥ score(q)+1 exactly when the original score(p) > score(q). This adds only m−1 explicit ballots.
Transfer. An algorithm for the target solves the source. Hardness of the source transfers forward; an algorithmic upper bound for the target transfers backward. Target hardness alone says nothing about the source.
Conditions. No promise that p initially loses.
Explanation and sources
Keep the profile and use an empty unregistered pool with budget 0.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Use D = ∅ and retain the election and target. The question is exactly whether p uniquely wins.
How hard is it to control an election? John J. Bartholdi III, Craig A. Tovey, Michael A. Trick · 1992 · Elementary empty-action restriction of BTT92/HHR07 definitions.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Give each nonmanipulator price 1 and each manipulator price 0, using arbitrary initial ballots for manipulators. Set total budget 0. Exactly the manipulators can change their ballots.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · FHH09 Theorem 4.6, p. 26. Same rule, weights, input type and winner convention must be used at both endpoints.
Transfer. An algorithm for the target solves the source. Hardness of the source transfers forward; an algorithmic upper bound for the target transfers backward. Target hardness alone says nothing about the source.
Conditions. Explicit ballots and coalition list; co-winner success at both endpoints. The indicated fixed parameter is the only change.
Transfer. A possible-winner algorithm solves manipulation; manipulation hardness transfers to possible winner.
Conditions. Explicit unweighted coalition, unchanged candidate set of variable size, co-winner objective; no ballot restrictions.
Explanation and sources
Keep nonmanipulators as complete orders; replace each unweighted manipulator with an empty partial order. Linear extensions are precisely the freely chosen manipulator rankings.
Transfer. A weighted-priced bribery solver decides weighted manipulation. This edge does not establish hardness for plurality manipulation.
Conditions. Nonnegative prices permitted; full information; co-winner objective.
Explanation and sources
Retain voter weights. Give fixed voters price 1 and manipulators price 0, with arbitrary initial ballots for the latter. Set budget 0. Exactly the designated manipulators can change their votes.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Assign each voter price 1 and retain the integer budget. Yes answers agree exactly.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Elementary embedding from FHH09 Section 2.2 definitions; not a separately claimed paper theorem.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Assign each voter weight 1 and retain k. Yes answers agree exactly.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Elementary embedding from FHH09 Section 2.2 definitions.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Retain prices and budget, and assign weight 1 to every voter.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Elementary embedding from FHH09 Section 2.2 definitions.
Transfer. A solver for the target gives a solver for the source; hardness of the source would transfer to the target. This does not transfer hardness backwards.
Conditions. Identical winner criterion at both endpoints. All rankings are explicit and strict.
Explanation and sources
Retain weights and assign price 1 to every voter. Use the original bribe-count budget as the money budget.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Elementary embedding from FHH09 Section 2.2 definitions.
Transfer. This changes the question. Neither answer nor complexity transfers automatically.
Conditions. Explicit ballots and coalition list; co-winner success at both endpoints. The indicated fixed parameter is the only change.
Explanation and sources
Keep the voter-addition model but ask to prevent a sole victory instead of creating one. These are not complements: each question has its own existential choice of added voters.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. The most first-place votes can belong to a candidate who loses every head-to-head comparison.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict first-place majority guarantees victory.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a winner cannot reduce its score advantage.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. 1 ≤ k < m. Condorcet consistency requires the strict Condorcet winner to be the sole winner. The negative k=1 witness uses m=3; each k≥2 fails for every m>k.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. The family does not always select only the Condorcet winner.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. For each fixed k≥1 a witness exists; this does not assert failure on every fixed pair (m,k), such as the two-candidate majority special case.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. For every fixed k, the family can elect a Condorcet loser.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a winner cannot reduce its score advantage.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. k stays fixed across the clone deletion. Each fixed k≥1 has a counterexample within the domain 1≤k<m. All co-winners are returned.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Keeping k fixed while deleting a clone can change outsider winners.
Transfer. This compares assumptions or rules. No decision reduction, algorithm transfer, or hardness transfer is asserted.
Conditions. The source has exactly three candidates and unique-winner constructive success; the target permits any number ≥2 and asks to exclude h from every winning tie. These are deliberately different variants, not an identity reduction.
Explanation and sources
Making a specified candidate win and ensuring a specified candidate loses are different tasks; negating the first decision question does not produce the second.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Even a strict first-place majority need not make its candidate the sole winner.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Veto can elect a Condorcet loser even without a final tie.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a winner cannot reduce its score advantage.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Splitting last-place disapproval between clones can change who wins.
Transfer. Winner membership is the zero-manipulator special case. A manipulation algorithm solves winner membership.
Conditions. Target permits zero manipulators. No change in winner semantics.
Explanation and sources
Use the same fixed profile and an empty manipulator list.
Complexity of and Algorithms for Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh · 2011 · Primary definitions in the cited source; explicit elementary transformation stated here.
Transfer. A possible-winner algorithm solves manipulation; manipulation hardness transfers to possible winner.
Conditions. Explicit unweighted coalition, unchanged candidate set of variable size, co-winner objective; no ballot restrictions.
Explanation and sources
Keep nonmanipulators as complete orders; replace each unweighted manipulator with an empty partial order. Linear extensions are precisely the freely chosen manipulator rankings.
Complexity of and Algorithms for Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh · 2011 · Primary definitions in the cited source; explicit elementary transformation stated here.
Transfer. This compares assumptions or rules. No decision reduction, algorithm transfer, or hardness transfer is asserted.
Conditions. Keep the exact ballot, objective, and winner conventions of both nodes.
Explanation and sources
Borda with one unweighted manipulator is tractable; Baldwin repeatedly recomputes Borda and eliminates a candidate. The latter manipulation problem is NP-complete.
Transfer. This changes the question. Neither answer nor complexity transfers automatically.
Conditions. Explicit ballots and coalition list; co-winner success at both endpoints. The indicated fixed parameter is the only change.
Explanation and sources
The number of new strategic ballots changes from exactly one to exactly two. Both use co-winner success. This is a comparison, not a yes/no-preserving reduction between the two variants.
Transfer. This compares assumptions or rules. No decision reduction, algorithm transfer, or hardness transfer is asserted.
Conditions. Keep the exact ballot, objective, and winner conventions of both nodes.
Explanation and sources
Nanson repeatedly eliminates below-average Borda candidates. Its one-voter manipulation classification differs from Borda. Winner conventions are detailed in the endpoints.
Transfer. NP-hardness transfers from the two-voter case to the general case.
Conditions. Identical explicit profile and co-winner semantics.
Explanation and sources
Keep the election and set the coalition list to two voters.
Complexity of and Algorithms for Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh · 2011 · Primary definitions in the cited source; explicit elementary transformation stated here.
Complexity of and Algorithms for Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh · 2011 · Primary definitions in the cited source; explicit elementary transformation stated here.
property-application · Not part of decision many-one paths
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate who loses every pairwise contest scores below the average Borda score.
Manipulation of Nanson’s and Baldwin’s Rules Nina Narodytska, Toby Walsh, Lirong Xia · 2011 · Nanson’s and Baldwin’s Rules, p.2, Borda’s Condorcet-loser property; counting proof
property-application · Not part of decision many-one paths
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a winner cannot reduce its score advantage.
Transfer. Identity many-one reduction. Algorithms and hardness transfer in the indicated direction.
Conditions. Exactly three candidates; eliminate lowest-priority tied losers, retain highest-priority tied finalists, and use that same fixed priority in the head-to-head final.
Explanation and sources
With exactly three candidates, eliminating the lowest-priority candidate among tied lowest plurality totals leaves precisely the two candidates chosen by higher-priority advancement. Both rules then use the same pairwise final and final tie priority.
Transfer. Identity many-one reduction. Algorithms and hardness transfer in the indicated direction.
Conditions. Exactly three candidates; eliminate lowest-priority tied losers, retain highest-priority tied finalists, and use that same fixed priority in the head-to-head final.
Explanation and sources
With exactly three candidates, eliminating the lowest-priority candidate among tied lowest plurality totals leaves precisely the two candidates chosen by higher-priority advancement. Both rules then use the same pairwise final and final tie priority.
Transfer. This compares assumptions or rules. No decision reduction, algorithm transfer, or hardness transfer is asserted.
Conditions. Keep the exact ballot, objective, and winner conventions of both nodes.
Explanation and sources
Single-seat STV is NP-complete even for one manipulator; Schulze admits a polynomial algorithm for an entire unweighted coalition. These are different rule families.
Transfer. Identity many-one reduction. Algorithms and hardness transfer in the indicated direction.
Conditions. Exactly three candidates; eliminate lowest-priority tied losers, retain highest-priority tied finalists, and use that same fixed priority in the head-to-head final.
Explanation and sources
With exactly three candidates, eliminating the lowest-priority candidate among tied lowest plurality totals leaves precisely the two candidates chosen by higher-priority advancement. Both rules then use the same pairwise final and final tie priority.
Transfer. Identity many-one reduction. Algorithms and hardness transfer in the indicated direction.
Conditions. Exactly three candidates; eliminate lowest-priority tied losers, retain highest-priority tied finalists, and use that same fixed priority in the head-to-head final.
Explanation and sources
With exactly three candidates, eliminating the lowest-priority candidate among tied lowest plurality totals leaves precisely the two candidates chosen by higher-priority advancement. Both rules then use the same pairwise final and final tie priority.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict first-place majority guarantees victory.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Borda elimination preserves a strict Condorcet winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict Condorcet loser cannot survive to win.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Borda elimination preserves a strict Condorcet winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. A strict Condorcet loser cannot survive to win.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. Comparison only. Constructive hardness does not transfer to destructive control.
Conditions. Same budget and unique-winner control model.
Explanation and sources
The available actions agree, but the desired outcome changes. Existentially choosing an action to make p uniquely win is not the complement of choosing an action to stop its unique victory.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. Comparison only. Constructive hardness does not transfer to destructive control.
Conditions. Same budget and unique-winner control model.
Explanation and sources
The available actions agree, but the desired outcome changes. Existentially choosing an action to make p uniquely win is not the complement of choosing an action to stop its unique victory.
Transfer. Bucklin hardness transfers to fallback; a fallback algorithm also solves Bucklin. Fallback hardness alone does not imply Bucklin hardness.
Conditions. Standard Bucklin within-level score tie-breaker; full approval on all registered and pool ballots; identical unique-winner control objective.
Explanation and sources
Give each Bucklin voter the same ranking and an approval set containing all candidates, including every candidate in the addition pool. Keep the budget and goal. For every allowed action the resulting winner sets agree.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate losing every pairwise contest can still win.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Adding or removing clones can change an outsider’s outcome.
Transfer. Comparison only. Constructive hardness does not transfer to destructive control.
Conditions. Same budget and unique-winner control model.
Explanation and sources
The available actions agree, but the desired outcome changes. Existentially choosing an action to make p uniquely win is not the complement of choosing an action to stop its unique victory.
Transfer. Comparison only. Constructive hardness does not transfer to destructive control.
Conditions. Same budget and unique-winner control model.
Explanation and sources
The available actions agree, but the desired outcome changes. Existentially choosing an action to make p uniquely win is not the complement of choosing an action to stop its unique victory.
Transfer. The majority theorem identifies the candidate elected by this construction. Strategy-proofness follows from the separately supplied median argument, not from Condorcet consistency alone. No complexity result transfers.
Conditions. Only fixed-axis, odd-electorate domain. Condorcet consistency alone does not imply strategyproofness.
Explanation and sources
The Condorcet winner identified by the majority result is the median peak; the target adds a separate strategyproofness argument.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Strict preferences and odd electorate.
Explanation and sources
A common single-peaked axis excludes the three-cycle obstruction.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Strict ballots in the target; removing indifference from the inputs does not fix the even split.
Explanation and sources
For even n, banning social indifference makes anonymity and neutrality inconsistent at an equal split.
Transfer. A target algorithm solves the source. Source hardness would transfer to the target; target hardness does not transfer back.
Conditions. Same unweighted strict profile and co-winner success; target accepts a binary rational parameter, supplied as numerator 1 and denominator 2.
Explanation and sources
Keep the election and supply rational parameter α=1/2.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects a strict pairwise-majority winner whenever one exists.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A strict Condorcet loser has score zero while every rival has positive score.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate ranked first by a strict majority is the only winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. This compares assumptions or rules. No decision reduction, algorithm transfer, or hardness transfer is asserted.
Conditions. The source has exactly four candidates and unique-winner constructive success; the target permits any number ≥2 and asks to exclude h from all co-winners. No reduction is asserted.
Explanation and sources
The existence of a ballot profile making p win is not the complement of existence of one excluding h.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects a strict pairwise-majority winner whenever one exists.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A Condorcet loser can win when its defeats are smaller than everyone else’s worst defeat.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate ranked first by a strict majority is the only winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out the source candidate. A target yes-answer need not settle the source. This is not a many-one reduction and transfers no hardness.
Conditions. Same strict complete ballots and candidate; both rules use margin strength and full co-winner sets.
Explanation and sources
If q defeats p by Split Cycle, the direct q-to-p edge beats every p-to-q path, so p cannot win Schulze.
Transfer. Polynomial many-one reduction by incrementing coalition size. This relationship is specific to Schulze and cannot be assumed for other voting rules.
Keep the fixed profile and target, and add one new unit-weight manipulator to the coalition. Co-winner success with k voters is equivalent to unique-winner success with k+1.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects the strict pairwise-majority winner.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Every strict Condorcet loser is excluded by the Smith guarantee.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate ranked first by a strict majority is the only winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Clone deletion preserves outsiders and whether a clone wins.
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out the source candidate. A target yes-answer need not settle the source. This is not a many-one reduction and transfers no hardness.
Conditions. Same strict complete ballots and candidate; margin-ranked pairs, existential quantification over valid pair tie orders.
Explanation and sources
Every parallel-universe Ranked Pairs winner belongs to the Split Cycle winner set.
Transfer. A conceptual change in the quantified choice only. No hardness or algorithm transfers along this comparison.
Conditions. Fixed-order P versus all-orders membership NP-complete.
Explanation and sources
The target asks whether some tie order succeeds, whereas the source evaluates a supplied order. Dropping the order is not an answer-preserving reduction.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects the strict pairwise-majority winner.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate with only pairwise defeats cannot be a source of the locked graph.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate ranked first by a strict majority is the only winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. A score oracle determines membership. Polynomially bounded scores yield a Θ₂ᵖ upper bound.
Conditions. Explicit voters; costs are in [0,n·m(m−1)/2]. Polynomial truth-table reduction, not many-one. Empty residual candidate sets are solved directly with cost 0.
Explanation and sources
The best p-first cost is Σ(q≠p)N(q,p) plus the optimum cost of the profile with p removed. Ask every feasible threshold for that residual and the original profile in parallel, then compare optima. For a singleton candidate set, answer yes directly without an empty-candidate oracle query.
Transfer. An NP threshold oracle suffices, giving the displayed FP^NP upper bound.
Conditions. Polynomially many threshold calls on smaller candidate sets. Search oracle reduction, not a decision many-one edge. Empty residual candidate sets are solved directly with cost 0.
Explanation and sources
Compute the current optimum by binary threshold search. For each possible next candidate a, compute the optimum residual after deleting a and add Σ(b≠a)N(b,a). Choose a that preserves the optimum and recurse. At a singleton residual, append its sole candidate and stop.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Selects a strict pairwise-majority winner whenever one exists.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Placing a strict Condorcet loser first cannot minimize total disagreement.
Transfer. The property statement describes the voting rule used by this computational variant. No algorithm, hardness result, or reduction follows from this edge.
Conditions. Complete strict rankings, unweighted voters, all co-winners returned. The assertion concerns the stated rule family on its full finite-profile domain.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate ranked first by a strict majority is the only winner.
Transfer. The axiom remains valid for the input domain of this computational task. No complexity bound transfers.
Conditions. The stated rule model and complete strict ballots. The property concerns the voting rule, not the complexity of deciding an input question.
Explanation and sources
The universal property is valid on the target’s stated input domain. Raising a co-winner preserves its winning status.
Transfer. Slater threshold NP-hardness transfers to Kemeny threshold. A guessed ranking supplies NP membership.
Conditions. m≥2; unweighted explicit output of 2M ballots. Trivial m=1 input can be handled directly.
Explanation and sources
Let M=m(m−1)/2. For each arc a→b add ballots a>b>R and reverse(R)>a>b, with R listing all other candidates. This realizes margin 2 on every tournament arc. Any ranking with b backward arcs has total disagreement M(M−1)+2b. Map k to M(M−1)+2k.
Transfer. A threshold oracle solves the source. This explains the Θ₂ᵖ upper bound, not an NP membership claim.
Conditions. Explicit voters make the number of thresholds polynomial. Oracle (truth-table) reduction, not a many-one reduction.
Explanation and sources
Ask every integer threshold 0,…,n(m−1) for each relevant candidate in parallel. Recover the exact scores and compare score(p) with every rival using ≤.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate losing every pairwise contest can still win.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Adding or removing clones can change an outsider’s outcome.
Transfer. A threshold oracle solves the source. This explains the Θ₂ᵖ upper bound, not an NP membership claim.
Conditions. Explicit voters make the number of thresholds polynomial. Oracle (truth-table) reduction, not a many-one reduction.
Explanation and sources
Ask every integer threshold 1,…,n for each relevant candidate in parallel. If no threshold succeeds its score is 0. Recover the exact scores and compare score(p) with every rival using ≥.
Transfer. A threshold oracle solves the source. This explains the Θ₂ᵖ upper bound, not an NP membership claim.
Conditions. Explicit voters make the number of thresholds polynomial. Oracle (truth-table) reduction, not a many-one reduction.
Explanation and sources
Ask every integer threshold 1,…,n for each relevant candidate in parallel. If no threshold succeeds its score is 0. Recover the exact scores and compare score(p) with score(q) using ≥.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. A candidate losing every pairwise contest can still win.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Unrestricted complete strict rankings with the exact rule and tie convention above.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Adding or removing clones can change an outsider’s outcome.
Transfer. A target algorithm solves the source. Source hardness would transfer to the target; target hardness does not transfer back.
Conditions. Same approval subsets and co-winner convention; source nonempty profile.
Explanation and sources
Assign each existing approval ballot weight 1 and provide an empty manipulator list.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Section 4, p. 22, approval-manipulation discussion preceding Theorem 4.2; direct zero-coalition specialization
Transfer. Comparison only: the NP-completeness of whole-ballot bribery does not transfer to the independent-entry model.
Conditions. Both unweighted and constructive co-winner. Only the price structure changes.
Explanation and sources
Whole-ballot bribery charges once for any number of changes to a voter. Entry bribery charges independently for each approval bit; the feasible sets under a fixed budget differ.
How Hard Is Bribery in Elections? Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra · 2009 · Theorem 4.2; Definition 4.3; Theorem 4.4
Transfer. Comparison only. Constructive hardness does not transfer to destructive control.
Conditions. Same budget and unique-winner control model.
Explanation and sources
The available actions agree, but the desired outcome changes. Existentially choosing an action to make p uniquely win is not the complement of choosing an action to stop its unique victory.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms. Only native approval-bit increase or exact identical-bit clones is asserted, not an underlying ranking property.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Raising only a winner’s score cannot make it lose.
Transfer. This rule property concerns the same winner-set computation. It transfers no complexity bound.
Conditions. Restricted binary-utility preferences. † Cells use explicit native criteria, not unrestricted strict-ranking axioms. Only native approval-bit increase or exact identical-bit clones is asserted, not an underlying ranking property.
Explanation and sources
This assertion is linked only under the exact rule and domain conditions recorded on this edge. Deleting an identical-score clone preserves all outside scores.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Keep unrestricted domain, Pareto, pairwise independence and rational output.
Explanation and sources
Remove nondictatorship; copying one voter now witnesses existence.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. This comparison changes the axioms and output rationality. Arrow does not prove Sen’s theorem; Sen’s independent proof is cited.
Explanation and sources
Both models retain unrestricted preferences and Pareto. Sen instead requires two decisive personal pairs and only a best element on each agenda, dispensing with full social transitivity.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Both domain and odd-electorate assumptions change explicitly.
Explanation and sources
Replace unrestricted preferences by strict single-peaked ones on a common axis, and take odd n≥3. Majority supplies the social ranking.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Binary social indifference permitted; n≥2.
Explanation and sources
The three-alternative premise is removed. Binary majority is a witness.
Transfer. The changed-axiom support guarantee does not refute Arrow's theorem.
Conditions. Original Arrow domain, codomain and IIA are not retained.
Explanation and sources
Replace a single social ordering by a ranking lottery and replace ordinary IIA by boundary-only pairwise independence.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 2.12, p.7 and Appendix F quantum unanimity/IIA definitions; Arrow (1950), general possibility theorem, and Geanakoplos (2005), three proofs with ordinary IIA.
A Difficulty in the Concept of Social Welfare Kenneth J. Arrow · 1950 · October 2026 manuscript: Definition 2.12, p.7 and Appendix F quantum unanimity/IIA definitions; Arrow (1950), general possibility theorem, and Geanakoplos (2005), three proofs with ordinary IIA.
Three Brief Proofs of Arrow’s Impossibility Theorem John Geanakoplos · 2005 · October 2026 manuscript: Definition 2.12, p.7 and Appendix F quantum unanimity/IIA definitions; Arrow (1950), general possibility theorem, and Geanakoplos (2005), three proofs with ordinary IIA.
theorem-application · Not part of decision many-one paths
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Explanation and sources
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Explanation and sources
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes Gibbard–Satterthwaite to this unanimous, anonymous fixed-priority refinement. No efficient manipulation algorithm, running-time bound, or reduction transfers.
Conditions. Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Explanation and sources
Condorcet consistency implies unanimity: if every voter ranks x first, x wins every pairwise contest and is the unique winner. The refinement is anonymous in voter identities, so with n≥2 it cannot be a dictatorship. The Gibbard–Satterthwaite theorem therefore rules out strategyproofness for unrestricted strict rankings over m≥3 candidates.
Transfer. Specializes Gibbard–Satterthwaite to this unanimous, anonymous fixed-priority refinement. No efficient manipulation algorithm, running-time bound, or reduction transfers.
Conditions. Fixed m≥3 and n≥2, unrestricted complete strict rankings, and a fixed exogenous candidate-priority order for final ties. No claim is made for set-valued preference extensions or restricted profile domains.
Explanation and sources
Condorcet consistency implies unanimity: if every voter ranks x first, x wins every pairwise contest and is the unique winner. The refinement is anonymous in voter identities, so with n≥2 it cannot be a dictatorship. The Gibbard–Satterthwaite theorem therefore rules out strategyproofness for unrestricted strict rankings over m≥3 candidates.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Explanation and sources
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Explanation and sources
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed n ≥ 2, m ≥ 3, unrestricted strict rankings, and fixed candidate-priority final tie-break. This does not imply efficient computation of a manipulation.
Explanation and sources
The refinement is unanimous and anonymous in voter identities. With n≥2, anonymity rules out dictatorship on unrestricted rankings. Apply Gibbard–Satterthwaite.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Fixed n ≥ 2 and m ≥ 3, unrestricted strict rankings, and the fixed candidate-priority resolute refinement specified here. This does not label the set-valued correspondence and does not imply efficient manipulation.
Explanation and sources
Every candidate wins a unanimous profile, so the rule is onto. The fixed-priority refinement is anonymous in voter identities; with at least two voters on the unrestricted domain, it cannot be a dictatorship. Gibbard–Satterthwaite therefore implies a profitable unilateral misreport.
Transfer. Specializes Gibbard–Satterthwaite to this onto, nondictatorial, resolute rule on unrestricted strict rankings. No computational hardness transfers.
Conditions. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Explanation and sources
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Transfer. Specializes Gibbard–Satterthwaite to this onto, nondictatorial, resolute rule on unrestricted strict rankings. No computational hardness transfers.
Conditions. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Explanation and sources
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Transfer. Specializes Gibbard–Satterthwaite to this onto, nondictatorial, resolute rule on unrestricted strict rankings. No computational hardness transfers.
Conditions. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Explanation and sources
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Transfer. Specializes Gibbard–Satterthwaite to this onto, nondictatorial, resolute rule on unrestricted strict rankings. No computational hardness transfers.
Conditions. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Explanation and sources
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Transfer. Specializes Gibbard–Satterthwaite to this onto, nondictatorial, resolute rule on unrestricted strict rankings. No computational hardness transfers.
Conditions. Fixed m≥3 candidates and n≥2 unweighted voters; unrestricted strict rankings; fixed candidate-priority final tie-break.
Explanation and sources
The fixed-priority refinement is onto by unanimity and is anonymous, hence nondictatorial for n≥2. On unrestricted strict rankings with m≥3, Gibbard–Satterthwaite implies a profitable manipulation. This concerns a unique outcome, not preferences over sets.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Strict preferences and deterministic output.
Explanation and sources
Remove nondictatorship; the top of a fixed voter is a witness.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Input rankings remain strict and unrestricted. No claim that support-only incentive compatibility is equivalent.
Explanation and sources
Replace deterministic candidates by lotteries and ordinal strategyproofness by non-improvement for every compatible expected-utility scale.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. All four modeling changes are required; this is not plain GS applied to arbitrary ties.
Explanation and sources
Change output to nonempty sets. Replace onto by singleton-onto, dictatorship by weak dictatorship, and use both optimistic and pessimistic incentives.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Changes the output type. A lottery over dictators is still a restricted class, not a deterministic GS counterexample.
Explanation and sources
Allowing lotteries supplies a unanimous strongly SD-strategyproof rule without a single fixed dictator.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Odd n≥3; only admissible peak reports.
Explanation and sources
Change the unrestricted domain to strict single-peaked preferences on a fixed axis.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Also assume odd n≥3 to avoid tie-breaking in this witness.
Explanation and sources
The at-least-three-alternatives premise is removed. Odd-electorate majority is strategyproof.
Transfer. No contradiction to GS and no theorem transfer is implied.
Conditions. Keep every changed assumption explicit.
Explanation and sources
GS concerns deterministic single-winner functions on unrestricted ordinal ballots with ordinal profitable deviations. The indecisive model allows ranking distributions and changes outcome and incentive notions.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 3.7 and Theorem 3.4, printed pp.11–13; Gibbard (1973), deterministic nonmanipulable voting schemes theorem, under its original ordinal domain.
Manipulation of Voting Schemes: A General Result Allan Gibbard · 1973 · October 2026 manuscript: Definition 3.7 and Theorem 3.4, printed pp.11–13; Gibbard (1973), deterministic nonmanipulable voting schemes theorem, under its original ordinal domain.
assumption-change · Not part of decision many-one paths
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Exactly 4 alternatives and resolute Condorcet consistency in both.
Explanation and sources
Increase electorate capacity from 11 to 12 while retaining every smaller profile.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precise rule refinement. No algorithm, complexity classification, or reduction transfers.
Conditions. Unrestricted strict profiles over fixed m ≥ 4 candidates and every nonempty subelectorate of a voter pool with at least twelve voters. The specified fixed-priority resolute rule remains Condorcet-consistent. No claim about set-valued participation is made.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Full strict-profile domain, at least four candidates, and all nonempty subelectorates of a pool of at least twelve voters. Fixed-priority refinement. This is not a claim about set-valued participation or only uniquely-weighted profiles.
Explanation and sources
Apply the no-show theorem to this Condorcet-consistent single-winner refinement. The theorem concerns a rule defined on all subelectorates, not a profile containing exactly twelve voters.
Transfer. Specializes the no-show impossibility to this resolute Condorcet rule. No complexity bound transfers.
Conditions. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Explanation and sources
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Transfer. Specializes the no-show impossibility to this resolute Condorcet rule. No complexity bound transfers.
Conditions. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Explanation and sources
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Transfer. Specializes the no-show impossibility to this resolute Condorcet rule. No complexity bound transfers.
Conditions. At least four candidates; all nonempty subelectorates of an electorate pool with at least twelve voters. Fixed-priority final tie-break; unrestricted strict rankings.
Explanation and sources
The fixed-priority refinement is a resolute Condorcet extension. The Condorcet/participation impossibility applies to the full strict-ranking domain.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Candidate set fixed; voter count may vary.
Explanation and sources
Drop required Condorcet consistency and use a fixed positional vector and a fixed tie order. Participation has a direct proof.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Explanation and sources
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Explanation and sources
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Explanation and sources
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Transfer. Specializes the stated axiom theorem to this precisely specified rule refinement. No running-time bound or reduction transfers.
Conditions. Fixed candidate-priority tie-break. Candidate set and scoring vector stay fixed when a voter joins.
Explanation and sources
Let x win before entry. For any candidate y whom the entering voter ranks below x, the ballot adds at least as many points to x as to y. Thus y cannot overtake x; a fixed priority also cannot newly prefer y when their scores remain tied.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. The target uses continuous interval alternatives, explicitly extending the finite-axis witness. This is a construction correspondence, not an automatic transfer between representations.
Explanation and sources
On a closed interval, the ordinary odd-n median is obtained by placing (n+1)/2 phantoms at each endpoint.
Transfer. This records a change of assumptions or output model. The source conclusion does not automatically transfer. The target's separately stated theorem or witness establishes its classification. No computational hardness transfers.
Conditions. Ex ante lottery efficiency is stronger than ex post candidate efficiency.
Explanation and sources
Demand universal ex ante Pareto efficiency in addition to strong SD strategyproofness and no fixed dictator. Gibbard rules this out.
Transfer. This is a relation between axiom systems or output models. It transfers the stated existence conclusion only, never computational hardness.
Conditions. At least 3 alternatives; fixed mixture weights; full strict domain.
Explanation and sources
Positive-weight duple components cannot honor unanimous tops outside their pair. Each unanimous unilateral component must choose its controlling voter’s top.
Transfer. Gibbard's classification cannot simply be relabeled as a result about this condition.
Conditions. Theorems quantify over different preference and deviation predicates.
Explanation and sources
Strong stochastic-dominance strategy-proofness uses all compatible utility comparisons. The manuscript counts selected support-boundary changes instead.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 3.7, printed p.11; Gibbard (1977), main decomposition theorem for strategy-proof randomized schemes. Different incentive predicates are compared.
Manipulation of Schemes that Mix Voting with Chance Allan Gibbard · 1977 · October 2026 manuscript: Definition 3.7, printed p.11; Gibbard (1977), main decomposition theorem for strategy-proof randomized schemes. Different incentive predicates are compared.
Transfer. The pairwise support guarantee implies pairwise incentive compatibility under the stated definition.
Conditions. Direct marginal-based QCV of Definition 2.12 and support-boundary pairwise criterion; other voters’ marginals remain fixed.
Explanation and sources
Persistent support from unchanged other voters blocks the first two manipulation events; the third cannot start.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 2.12, printed p.7; Theorem 3.2 and Appendix C proof, pp.11 and 16.
construction · Not part of decision many-one paths
Transfer. Constructs a well-defined candidate lottery. This is not a decision reduction or an efficiency claim.
Conditions. Direct QCV on marginals; uniform Ω; 0<delta<1/|A|²; at least three candidates and two voters.
Explanation and sources
Every ranking in a marginal’s support survives QCV; summing its top probability proves positive q_a for each a in U. Eq. (2) then renormalizes exactly these candidates.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Eq. (2), Corollary 3.2.1 and Appendix C, pp.10–11,16
construction · Not part of decision many-one paths
Transfer. Defines a winner lottery. This construction does not preserve every property.
Conditions. Density-operator Natural Extension Eq. (1), interpreted as a candidate lottery; no profile-dependent top-support filter.
Explanation and sources
Push each output ranking probability to its top candidate.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 3.4 and Eq. (1), printed p.9; no Eq. (2) filter is applied on this edge.
non-implication · Not part of decision many-one paths
Transfer. Separates incentive notions while preserving the support-boundary guarantee.
Conditions. Delta=1/18; three candidates; two strict ballots; ordinary SD uses truthful order a>b>c.
Explanation and sources
The exact abc,bac → acb,bac example increases the probability of a within unchanged social support.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Atlas exact calculation from Definition 2.12 and Eq. (2)
Transfer. Supplies a witness for this exact incentive definition only.
Conditions. Indecisive distributions embed diagonally; same boundary criterion and unilateral convention.
Explanation and sources
Top-support union proves all three specified non-manipulation clauses.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 3.7, Theorem 3.1 and discussion after Theorem 3.4
Transfer. A valid witness for this specific axiomatic condition, not for ordinal or expected-utility strategy-proofness.
Conditions. Uniform positive minority spreading followed by unanimity.
Explanation and sources
The modified rule satisfies the stated pairwise boundary criterion.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definitions 2.1 and 3.6; Theorem 3.2 and its Appendix C proof, printed pp.3–4, 10–11 and 16.
model-change · Not part of decision many-one paths
Transfer. Introduces a new incentive criterion, not a reduction.
Conditions. Ranking-distribution ballots and ranking-distribution output.
Explanation and sources
Define preferences by zero, positive and unit probability for a fixed ordered pair.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 2.1 and Definition 3.6, printed pp.3–4 and 10–11.
model-change · Not part of decision many-one paths
Transfer. Changes the compared event; no automatic transfer from pairs to top position.
Conditions. Ranking-distribution ballots and winner-lottery output.
Explanation and sources
Replace the ordered-pair event by the event that a is first.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Definition 3.7, printed p.11; top-event projection in Definition 3.2, pp.8–9.
model-change · Not part of decision many-one paths
Transfer. Embeds ballot representations only; no complexity or incentive guarantee transfers automatically.
Conditions. Fixed ranking basis.
Explanation and sources
Map p_R to sum_R p_R |R><R|.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · October 2026 manuscript: Sections 2.2–2.3 and diagonal embedding after Theorem 3.4, printed pp.3–6 and 12–13.
construction · Not part of decision many-one paths
Transfer. Constructs a profile-dependent candidate lottery; its support-boundary incentive guarantee is established by a separate support argument.
Conditions. The extra filter uses original submitted top supports; it is not a QSCE depending only on welfare output.
Explanation and sources
After taking the top-candidate lottery, discard candidates absent from U and renormalize.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Eq. (1)–(2), printed pp.9–10
Transfer. Proves each candidate can win certainly, not every lottery can be attained.
Conditions. Candidate-wise onto; at least three candidates and two voters.
Explanation and sources
Choose U={a}; normalization gives probability one on a.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 3.9, Theorem 3.4, Appendix C p.17
Transfer. Directly proves both nondictatorship conditions for the filtered choice rule.
Conditions. At least two voters; global sharp and unsharp definitions of Definition 3.8.
Explanation and sources
For any proposed fixed dictator i, assign a different top to another voter. Both tops occur socially.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Lemma 3.3 and Appendix C p.17
Transfer. Establishes support-boundary choice IC, not stochastic-dominance or expected-utility strategy-proofness.
Conditions. Definition 3.7 only; every other voter’s reduced ballot remains fixed.
Explanation and sources
The support is exactly U. Other unchanged voters preserve support in strong-positive and strong-negative cases; positive truthful top support already appears socially.
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Theorem 3.1, Corollary 3.2.1 and Appendix C, pp.11,15–16
Transfer. PSPACE-hardness transfers. The polynomial-space upper bound is a separate part of the completeness proof.
Conditions. Variable total candidate count. Only C or D can win in the constructed family. SV/SSV agreement is proved on that family, not all tournaments.
Explanation and sources
First pad with unused quantified variables if needed to match the paper’s alternating-prefix convention; truth is unchanged. The construction turns the quantified formula into a polynomial-size margin tournament with distinct nonzero margins. Its distinguished candidate C wins exactly when the formula is true.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Construction 3.1; Theorem 4.1
Transfer. PSPACE-hardness transfers. The polynomial-space upper bound is a separate part of the completeness proof.
Conditions. Variable total candidate count. Only C or D can win in the constructed family. SV/SSV agreement is proved on that family, not all tournaments.
Explanation and sources
First pad with unused quantified variables if needed to match the paper’s alternating-prefix convention; truth is unchanged. The construction turns the quantified formula into a polynomial-size margin tournament with distinct nonzero margins. Its distinguished candidate C wins exactly when the formula is true.
Stable Voting is PSPACE-Complete Ethan Dickey; Alexandros Psomas; Athina Terzoglou · Preprint, arXiv v1, 15 July 2026 · Construction 3.1; Lemma 5.7 and Theorem 5.8
Transfer. An algorithm for the target solves the source. Source hardness transfers to target; target hardness does not transfer back.
Conditions. Partition integers are positive and binary; target weight encoding remains binary. The exact target tie convention is preserved.
Explanation and sources
Use the cited polynomial construction. Each source integer becomes a binary manipulator weight; fixed ballot multiplicities are encoded as weighted voters.
Transfer. An algorithm for the target solves the source. Source hardness transfers to target; target hardness does not transfer back.
Conditions. Partition integers are positive and binary; target weight encoding remains binary. The exact target tie convention is preserved.
Explanation and sources
Use the cited polynomial construction. Each source integer becomes a binary manipulator weight; fixed ballot multiplicities are encoded as weighted voters.
Transfer. An algorithm for the target solves the source. Source hardness transfers to target; target hardness does not transfer back.
Conditions. Partition integers are positive and binary; target weight encoding remains binary. The exact target tie convention is preserved.
Explanation and sources
Use the cited polynomial construction. Each source integer becomes a binary manipulator weight; fixed ballot multiplicities are encoded as weighted voters.
Transfer. An algorithm for the target solves the source. Source hardness transfers to target; target hardness does not transfer back.
Conditions. Partition integers are positive and binary; target weight encoding remains binary. The exact target tie convention is preserved.
Explanation and sources
Use the cited polynomial construction. Each source integer becomes a binary manipulator weight; fixed ballot multiplicities are encoded as weighted voters.
Transfer. An algorithm for the target solves the source. Source hardness transfers to target; target hardness does not transfer back.
Conditions. Partition integers are positive and binary; target weight encoding remains binary. The exact target tie convention is preserved.
Explanation and sources
Use the cited polynomial construction. Each source integer becomes a binary manipulator weight; fixed ballot multiplicities are encoded as weighted voters.
Transfer. An algorithm for the target solves Partition. This establishes NP-hardness, with NP membership separately needed for completeness.
Conditions. Positive binary integers, three candidates, explicit weighted ballots. Strict win/loss gap also validates co-winner success.
Explanation and sources
Candidates p,a,b. Fixed voters: a>b>p and b>a>p, each of weight 6K−1. One manipulator of weight 6a_i for each input integer. With p first in all manipulation votes, p scores 24K. If integers assigned to p>a>b sum to x, the rivals score 18K−3+6x and 30K−3−6x. Both are below p iff x=K, while either rival strictly exceeds p if x is an unequal integer. Raising p to first never hurts. Binary weights keep the construction polynomial.
Transfer. Establishes NP-hardness even with two candidates. Guessing changed ballots and checking binary costs/scores establishes NP membership separately.
Conditions. Co-winner success is essential to this exact construction. Binary encoding keeps the election polynomial size.
Explanation and sources
For integers aᵢ totaling 2K, use candidates p and q. Every voter initially ranks q first, and voter i has both weight and price aᵢ. Budget K permits changed weight at most K. Candidate p ties or beats q exactly when changed weight is at least K. Thus success requires a subset of weight exactly K.
Transfer. Hitting Set hardness transfers. Guessing the spoiler subset and tallying proves NP membership.
Conditions. Unweighted explicit ballots; unrestricted subset of supplied spoilers; unique / preclude-unique objective as shown. Source domain 1≤k≤|B|; all sets explicitly listed and nonempty. This bounds the explicit vote construction polynomially.
Explanation and sources
Use registered candidates c,w and spoiler candidates representing elements of B. The HHR construction makes w the unique winner exactly when the chosen spoilers hit every Sᵢ and number at most k; otherwise c uniquely wins. For constructive control designate w; for destructive control designate c. The bound k is encoded in votes, not an addition-budget input.
Transfer. Hitting Set hardness transfers. Guessing the spoiler subset and tallying proves NP membership.
Conditions. Unweighted explicit ballots; unrestricted subset of supplied spoilers; unique / preclude-unique objective as shown. Source domain 1≤k≤|B|; all sets explicitly listed and nonempty. This bounds the explicit vote construction polynomially.
Explanation and sources
Use registered candidates c,w and spoiler candidates representing elements of B. The HHR construction makes w the unique winner exactly when the chosen spoilers hit every Sᵢ and number at most k; otherwise c uniquely wins. For constructive control designate w; for destructive control designate c. The bound k is encoded in votes, not an addition-budget input.
Transfer. A target algorithm solves the source problem after the polynomial transformation. Source NP-hardness transfers to the target; target membership in a complexity class must be proved separately.
Conditions. Explicit 3CNF with three distinct noncomplementary literals per clause. Output is a polynomial-size complete asymmetric tournament; candidate count varies and there are no pairwise ties.
Explanation and sources
Construct the layered tournament Tϕ and designated decision candidate d from Theorem 2. The theorem proves ϕ is satisfiable exactly when d belongs to TEQ(Tϕ).
Transfer. A target algorithm solves the source problem after the polynomial transformation. Source NP-hardness transfers to the target; target membership in a complexity class must be proved separately.
Conditions. Exactly seven unweighted strict complete ballots; variable candidate count; no majority ties. The additional Ordered3SAT preprocessing is part of the reduction.
Explanation and sources
First apply Lemma 11 to obtain Ordered3SAT. Use the TEQ tournament construction whose decision candidate c₀ is selected iff the ordered formula is satisfiable. Theorem 3 constructs exactly seven strict ballots with that majority tournament, preserving c₀.
Transfer. A target algorithm solves the source problem after the polynomial transformation. Source NP-hardness transfers to the target; target membership in a complexity class must be proved separately.
Conditions. Explicit 3CNF under the source convention. Polynomial-size complete asymmetric tournament, variable candidate count, no ties.
Explanation and sources
Construct Tϕ from Definition 4 with designated candidate d. Theorem 1 proves satisfiability iff d tops a maximal transitive subset of Tϕ.
Transfer. A target membership algorithm solves the seven-voter source problem; both instances have the same membership answer.
Conditions. Exactly seven explicit unweighted strict rankings. Odd voter count ensures a complete asymmetric tournament. This direction does not assert that arbitrary tournaments can be realized by seven voters.
Explanation and sources
Compare each pair of candidates in the seven rankings, orient its majority edge, and retain p. TEQ depends only on this orientation.
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out source membership, but a target yes-answer need not decide it. This is not a complexity reduction and transfers no hardness.
Conditions. Use exactly the same explicit tie-free tournament and designated candidate. Co-winner membership is intended.
Explanation and sources
Every TEQ member tops some inclusion-maximal transitive subtournament.
Transfer. A source yes-answer implies a target yes-answer. A target no-answer rules out source membership, but a target yes-answer need not decide it. This is not a complexity reduction and transfers no hardness.
Conditions. Same explicit complete asymmetric tournament and candidate. The claim uses the strict tournament domain.
Explanation and sources
If a Banks member lay outside the tournament’s unique source component, its witnessing transitive subset would also lie outside. Any source-component candidate dominates that whole subset and can be added above it, contradicting maximality.
Transfer. A polynomial-time target solver yields a polynomial-time source solver using the stated calls and postprocessing. This is not a decision many-one reduction and is excluded from decision reduction-path composition. Together with membership NP-hardness this rules out a polynomial-time full-set function unless P = NP.
Conditions. Nonempty explicit tie-free tournament on candidates {1,…,m}; same candidate order. TEQ can have multiple members. The source additionally specifies p. Output contains exactly m bits.
Explanation and sources
Call the full-set function once on T and accept exactly when output coordinate p is 1.
Transfer. A polynomial-time target solver yields a polynomial-time source solver using the stated calls and postprocessing. This is not a decision many-one reduction and is excluded from decision reduction-path composition.
Conditions. Nonempty explicit tie-free tournament on candidates {1,…,m}; same candidate order. TEQ can have multiple members. Exactly m nonadaptive queries; polynomial output length.
Explanation and sources
Prepare membership queries (T,1),…,(T,m) before receiving any answer, then concatenate the m Boolean answers.
Transfer. A polynomial-time target solver yields a polynomial-time source solver using the stated calls and postprocessing. This is not a decision many-one reduction and is excluded from decision reduction-path composition. No converse reduction or search-hardness conclusion is asserted.
Conditions. Nonempty explicit tie-free tournament on candidates {1,…,m}; same candidate order. TEQ can have multiple members. The search output may be any selected candidate; a canonical least-index output is not required.
Explanation and sources
Ask membership for candidates in the supplied order and return the first yes-answer. At most m calls suffice because TEQ of a nonempty tournament is nonempty. Equivalently, ask all m queries nonadaptively and choose a positive answer.
Transfer. A polynomial-time target solver yields a polynomial-time source solver using the stated calls and postprocessing. This is not a decision many-one reduction and is excluded from decision reduction-path composition. An arbitrary single returned member need not reveal the full set, so no converse is asserted.
Conditions. Nonempty explicit tie-free tournament on candidates {1,…,m}; same candidate order. TEQ can have multiple members. Reading a set bit produces an index in ⌈log₂(m+1)⌉ bits.
Explanation and sources
Call the full-set function once and return the index of any 1 bit. The vector is nonzero because the input tournament is nonempty.
Transfer. Transfers the single-Condorcet-winner guarantee to strict first-place majority winners. No computational hardness or algorithmic bound transfers.
Conditions. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Explanation and sources
If more than half the voters rank c first, the same voters rank c above each rival. Thus c is the Condorcet winner and the TEQ Condorcet property applies.
Transfer. The property constrains the selected candidates on this domain. It supplies no running-time bound or complexity reduction.
Conditions. Exactly seven unweighted strict ballots fall within the odd-electorate TEQ correspondence. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Explanation and sources
Let c beat everyone. The singleton {c} is retentive. In any other nonempty retentive set containing x, c is the Condorcet winner within D(x); induction forces TEQ(D(x))={c}, so the set contains c. It cannot be inclusion-minimal unless it is {c}.
Transfer. The property constrains the selected candidates on this domain. It supplies no running-time bound or complexity reduction.
Conditions. Exactly seven unweighted strict ballots fall within the odd-electorate TEQ correspondence. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Explanation and sources
If more than half the voters rank c first, the same voters rank c above each rival. Thus c is the Condorcet winner and the TEQ Condorcet property applies.
Transfer. The property constrains the selected candidates on this domain. It supplies no running-time bound or complexity reduction.
Conditions. Exactly seven unweighted strict ballots fall within the odd-electorate TEQ correspondence. Contiguous clones in every strict ballot; delete a member from a block of at least two, leaving at least one clone. Odd unweighted electorate and the full TEQ correspondence. No fixed-priority final choice is imposed. At least two total candidates remain after the deletion.
Explanation and sources
A contiguous clone block forms a module of the majority tournament: every outside candidate has the same majority direction against all clones. Composition consistency computes TEQ by choosing winning modules in the quotient tournament and then TEQ winners inside each chosen module. Deleting a clone while leaving a nonempty block does not change the quotient. Outsider membership is unchanged, and the block contributes a winner exactly when its quotient candidate wins, because its internal TEQ remains nonempty.
Transfer. The property constrains the selected candidates on this domain. It supplies no running-time bound or complexity reduction.
Conditions. Exactly seven unweighted strict ballots fall within the odd-electorate TEQ correspondence. Complete strict ballots, an odd number of unweighted voters, and the full TEQ co-winner set. Pairwise ties are excluded.
Explanation and sources
Let l lose to every other candidate. A retentive set containing l must contain another candidate because TEQ(D(l)) is nonempty. Removing l from that set preserves retentiveness: l is not in D(x) for any other x, so no remaining candidate depends on l. A retentive set containing l is therefore not inclusion-minimal, and l is absent from their union.
Transfer. Applies the deterministic impossibility theorem to this precise refinement. It does not classify preferences over winner sets or the complexity of finding a manipulation.
Conditions. Three candidates and three unweighted strict voters. Fix a candidate-priority order to choose one member of TEQ; preferences range over all strict rankings.
Explanation and sources
The fixed-priority TEQ rule is onto because it selects each unanimous top. It is anonymous and is not dictatorial: the other two voters can make a different candidate the Condorcet winner. Gibbard–Satterthwaite therefore forces a manipulation. The target gives an explicit three-voter witness.
Transfer. Only winner membership transfers in the indicated direction on the same instance. This is a set inclusion, not a computational reduction; neither hardness nor an algorithm for the smaller set follows from it.
Conditions. The same complete asymmetric tournament and designated candidate. No pairwise ties or final tie-breaking.
Explanation and sources
If a Banks winner p were covered by y, y would beat p and every candidate below p in its transitive witness. Prepending y would enlarge that transitive set, contradicting inclusion-maximality.
A computational analysis of the tournament equilibrium set Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair · 2010 · Banks definition in TEQ_BFHM10 Definition 1; covering definition in Miller1980 p.77; direct inclusion proof
Transfer. Only winner membership transfers in the indicated direction on the same instance. This is a set inclusion, not a computational reduction; neither hardness nor an algorithm for the smaller set follows from it.
Conditions. The same complete asymmetric tournament and designated candidate. No pairwise ties or final tie-breaking.
Explanation and sources
An uncovered candidate reaches every rival in at most two steps by Miller Lemma 6, and hence reaches every rival. It is therefore in the strict tournament top cycle.
Transfer. Only winner membership transfers in the indicated direction on the same instance. This is a set inclusion, not a computational reduction; neither hardness nor an algorithm for the smaller set follows from it.
Conditions. The same explicit complete pairwise win/tie matrix; ties may occur. Schwartz uses strict edges, while Smith adds both directions for a tie.
Explanation and sources
Let S be the Smith set and C a source strongly connected component of the strict graph. If C meets S, strict dominance of S over outsiders prevents paths from outside S back into S, so strong connectivity forces C⊆S. If C is disjoint from S, every s∈S has an edge into C, contradicting the source property.
Transfer. A polynomial-time threshold oracle yields a polynomial-time winner test via polynomially many calls. This is an oracle reduction, not a many-one reduction or a decision-path composition step.
Conditions. Same explicit complete asymmetric tournament. The threshold target asks about some ordering, with no designated candidate. All O(m²) queries are prepared nonadaptively.
Explanation and sources
For m≥2, ask the threshold oracle for every k from 0 to m(m−1)/2 on T and from 0 to (m−1)(m−2)/2 on T−p. Recover both optimum costs. Accept iff OPT(T)=d⁻(p)+OPT(T−p). For m=1 accept directly, without querying an empty tournament.
Transfer. A Kemeny winner-membership algorithm solves Slater winner membership on the constructed profile. This is an exact answer-preserving representation reduction, not identification of Slater and Kemeny on arbitrary profiles.
Conditions. Explicit tie-free tournament; variable candidate count; target has polynomially many unweighted strict ballots and allows all co-winners. Majority margins are uniformly 2, so magnitudes do not bias the optimum.
Explanation and sources
For every victory x→y, add ballots x>y>R and reverse(R)>x>y, where R lists all other candidates. This pair contributes margin +2 only to x over y. With v=m(m−1) voters, any ranking’s total Kemeny disagreement is m(m−1)(v−2)/4 plus twice its Slater disagreement. Optimum rankings and designated membership therefore agree. Map a singleton to its one-ballot singleton profile.
Transfer. A target score-membership algorithm solves the source approval instance. The reverse transformation is not asserted for general fractional scores.
Conditions. Unweighted explicit approval ballots and rational [0,1] score reports; both tasks use co-winner membership.
Explanation and sources
Map each approval ballot to a rational score vector with 1 for approved candidates and 0 for all others. The totals and complete winner set remain identical.
Transfer. With no manipulators, successful constructive manipulation is exactly ordinary winner membership. A target algorithm therefore solves the source instance.
Conditions. The target manipulation model permits an empty coalition. Both models use the same known balanced bracket and positive binary integer weights.
Explanation and sources
Use the complete weighted profile as the fixed ballots, supply no manipulator weights, and retain the same bracket, candidate priority and target p.
Transfer. This explains why polynomial-time winner evaluation is consistent with NP-complete manipulation. No reduction or hardness transfer is asserted.
Conditions. Compare the shared case where fixed priority favours p. The source accepts arbitrary supplied fixed priorities; the target entry uses coalition-favouring priority. Both use unweighted strict complete rankings and the same Baldwin rule.
Explanation and sources
The source evaluates a fully specified profile. The target must choose the additional manipulator’s ranking before evaluating the rule. The target has exactly one manipulator, so an empty-coalition identity reduction is unavailable.
Transfer. This explains why polynomial-time winner evaluation is consistent with NP-complete manipulation. No reduction or hardness transfer is asserted.
Conditions. Compare the shared case where fixed priority favours p. The source accepts arbitrary supplied fixed priorities; the target entry uses coalition-favouring priority. Both use unweighted strict complete rankings and the same strict Nanson rule.
Explanation and sources
The source evaluates a fully specified profile. The target must choose the additional manipulator’s ranking before evaluating the rule. The target has exactly one manipulator, so an empty-coalition identity reduction is unavailable.
Stable Voting is PSPACE-Complete — draft with winner-search results Unpublished author manuscript, September 2026. The related July arXiv version contains the decision results but not these search theorems. Related public version Ethan Dickey; Alexandros Psomas; Athina Terzoglou · 2026 ·
Stable Voting Wesley H. Holliday; Eric Pacuit · 2023 · Section 2 equivalent definition; Section 4 Propositions 2–6; Section 5 monotonicity discussion. The historical open equivalence question in footnote 9 is superseded by HMNPW2026.
Stable Voting and the Splitting of Cycles Wesley H. Holliday; Milan Mossé; Chase Norman; Eric Pacuit; Cynthia Wang · 2026 · Published abstract and preprint definitions, Lemma 8, Theorems 17–18 and Figure 4. The six-candidate result uses a SAT certificate.
Positional scoring
The Complexity of Manipulating k-Approval Elections Andrew Lin · 2012 · Version 3, April 2012. Sections 4–5 definitions; Theorem 5 and Section 9, pp.13–14. The flow derivation is stated with the algorithmic entries.
Condorcet’s principle implies the no show paradox Hervé Moulin · 1988 · The original impossibility is stated in the author’s institutional abstract. The precise finite threshold is cited to Brandt, Geist and Peters (2017).
The computational difficulty of manipulating an election J. J. Bartholdi III, C. A. Tovey, M. A. Trick · 1989 · Winner-set convention p.227; single-manipulator problem p.229; Theorem 1 pp.229–230 and Corollary p.230; explicit Borda application p.230.
Complexity of and Algorithms for Borda Manipulation Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh · 2011 · Tie handling p.1; UCM definition and Theorem 1 p.2; Lemma 1 p.6. Journal pagination 657–662.
When Are Elections with Few Candidates Hard to Manipulate? Vincent Conitzer, Tuomas Sandholm, Jérôme Lang · 2007 · Proposition 1 p.4; scoring definitions p.5; complete-information models pp.6–9; Theorem 1 and footnote 7 p.9; Theorem 6 and Corollary 1 p.15.
Control Complexity in Fallback Voting Gábor Erdélyi, Lena Piras, Jörg Rothe · 2010 · Theorem 3.12 explicitly covers destructive adding and deleting voters in the unique-winner control model.
Control Complexity in Bucklin and Fallback Voting Gábor Erdélyi, Michael Fellows, Jörg Rothe, Lena Schend · 2012 · Sections 2.1–2.2 specify voting and unique-winner control. Theorems 3.5, 3.8, 3.14, 3.16, 3.18 and corresponding corollaries.
Control Complexity in Bucklin and Fallback Voting Gábor Erdélyi, Michael Fellows, Jörg Rothe, Lena Schend · 2015 · Section 2.1, printed pp.5–6: strict rankings, approval, standard Bucklin and fallback definitions.
Pairwise comparisons
On the Rationale of Group Decision-making Duncan Black · 1948 · Section II, odd electorate argument pp.27–28, transitivity p.30, unrestricted-cycle discussion pp.32–33.
A Note on the Complexity of Manipulating Weighted Schulze Voting Julian Müller and Sven Kosub · 2020 · Theorem 2, Lemma 5 and Corollary 9 for unique-winner manipulation; Theorem 10 for co-winner manipulation. Published in Information Processing Letters 162, 105989.
Copeland Voting: Ties Matter Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor · 2008 · Theorem 4.1 p.989 and Theorem 4.2 p.990; three-candidate table p.989. Co-winner hardness proof omitted in this conference version.
Llull and Copeland Voting Computationally Resist Bribery and Control Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe · 2008 · Theorems 3.1–3.4, 4.3, 4.4, 4.9, 4.12. Definitions explicitly distinguish co-winner and unique-winner goals and rational versus irrational ballots.
A Characterization of Black’s Voting Rule Salvador Barberà and Walter Bossert · 2025 · Primary authors’ institutional abstract: strict Condorcet winner, otherwise Borda winner set. Applied below to strict rankings.
Coalitional Manipulation for Schulze’s Rule Serge Gaspers, Thomas Kalinowski, Nina Narodytska, Toby Walsh · 2013 · Section 2 definitions; Section 4 algorithms; Corollary 2, p.7. Margins version of Schulze, explicit voters.
Some Remarks on Dodgson’s Voting Rule Felix Brandt · 2009 · Primary note; Table 3 gives the 29-voter Condorcet-loser example; the displayed scores use the exact adjacent-swap definition.
Socially Desirable Approximations for Dodgson’s Voting Rule Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas and Ariel D. Procaccia · 2014 · Section 3 gives mono-raise definition and explains the failure of Dodgson. An explicit 19-voter witness is given with the corresponding property.
Approval Voting under Dichotomous Preferences: A Catalogue of Characterizations Florian Brandl and Dominik Peters · 2022 · Section 2 defines dichotomous preferences; Proposition 1 proves strategyproofness for Fishburn’s extension. The fixed-priority resolute variant has the direct proof given with the corresponding property.
Formal utilitarianism and range voting Marcus Pivato · 2014 · Primary article abstract defines maximum score-sum on [0,1] reports. All seven cell derivations below are elementary and stated explicitly.
Axioms and models
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem
Indecisive Voting and Bypassing the Gibbard-Satterthwaite Impossibility Theorem Unpublished author manuscript, October 2026. The related arXiv v1 is an earlier version and does not contain the top-supported choice rule. Earlier public version Aidan Casey; Ethan Dickey · 2026 · Definition 2.12, Eq. (1), top-support filter Eq. (2), Definition 3.7, Theorem 3.1, Corollary 3.2.1, Lemma 3.3, Theorem 3.4 and Appendix C.
Manipulation of Schemes that Mix Voting with Chance Allan Gibbard · 1977 · Definitions and strong theorem pp.670–671; Corollaries 1 and 2 pp.677–679. Individual preferences strict; utility-compatible expected-utility nonmanipulability.
The Impossibility of a Paretian Liberal Amartya Sen · 1970 · Definition 3 and U/P/L pp.152–153, Minimal Liberalism and Theorem II p.154, three-state example p.155.
Optimal Bounds for the No-Show Paradox via SAT Solving Felix Brandt, Christian Geist, Dominik Peters · 2017 · Model: Section 3. Theorems 3–4: Section 6. Theorem 3 applies to at least 4 alternatives and at least 12 available voters, including the equality cases.
A Difficulty in the Concept of Social Welfare Kenneth J. Arrow · 1950 · Original possibility theorem. The weak-Pareto formulation is given in Gibbard (1973), p.596, and Geanakoplos’s first proof.
A computational analysis of the tournament equilibrium set
A computational analysis of the tournament equilibrium set Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair · 2010 · Social Choice and Welfare 34(4):597–609. Linked author version dated August 10, 2009: Definitions 1–2 p.4; Proposition 1 pp.4–5; Theorem 1 pp.6–7; Theorem 2 pp.8–9. Monotonicity is addressed by Laffond, Laslier and Le Breton (1993) together with Brandt et al. (2013).
k-Majority digraphs and the hardness of voting with a constant number of voters
k-Majority digraphs and the hardness of voting with a constant number of voters Georg Bachmeier, Felix Brandt, Christian Geist, Paul Harrenstein, Keyvan Kardel, Dominik Peters, Hans Georg Seedig · 2019 · Journal of Computer and System Sciences 105:130–157. Linked author PDF: Section 2 pp.3–4; Lemma 11 pp.21–22; Section 7.2 pp.25–29; Theorem 3 p.27; Table 6 p.41.
Recognizing Members of the Tournament Equilibrium Set is NP-hard
More on the tournament equilibrium set Gilbert Laffond, Jean-François Laslier, and Michel Le Breton · 1993 · Mathématiques et sciences humaines 123, 37–44. Theorem 3.8 (printed p.43) equates monotonicity with uniqueness of the minimal retentive component.
A counterexample to a conjecture of Schwartz
A counterexample to a conjecture of Schwartz Felix Brandt, Maria Chudnovsky, Ilhee Kim, Gaku Liu, Sergey Norin, Alex Scott, Paul Seymour, and Stephan Thomassé · 2013 · Social Choice and Welfare 40, 739–743. Linked author version revised April 8, 2012; Sections 2–3.
Composition-consistent tournament solutions and social choice functions
The Computational Complexity of Choice Sets Felix Brandt, Felix Fischer, and Paul Harrenstein · 2009 · Author PDF: Definitions 2–3 p.4; Theorem 1 pp.6–7; Lemmas 2 and 4 pp.9–10; Theorems 5–6 pp.10–11. Uses explicit dominance graphs, with missing strict edges representing ties.
Determining a Slater Winner Is Complete for Parallel Access to NP
Determining a Slater Winner Is Complete for Parallel Access to NP Michael Lampis · 2022 · STACS 2022, Article 45. Definitions pp.45:1–3; Lemma 2 p.45:4; Theorem 3 pp.45:6–10; Theorem 5 pp.45:11–13. The paper directs edges from loser to winner; the atlas consistently uses winner-to-loser arcs, so globally reverse its graphical convention.