Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

• URL: http://arxiv.org/abs/2604.19851v1
• Date: Tue, 21 Apr 2026 15:25:12 GMT
• Title: Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections
• Abstract summary: We use a mixed-integer linear program to search for elections that would serve as counter-examples to conjectured bounds.<n>Despite extensive search, we fail to find any election requiring a committee larger than size 3.<n>Our results provide strong empirical evidence that the Condorcet dimension of any election may be smaller than currently known upper bounds.
• Score: 6.8947446750832375
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In an election where $n$ voters rank $m$ candidates, a Condorcet winning set is a committee of $k$ candidates such that for any outside candidate, a majority of voters prefer some committee member. Condorcet's paradox shows that some elections admit no Condorcet winning sets with a single candidate (i.e., $k=1$), and the same can be shown for $k=2$. On the other hand, recent work proves that a set of size $k=5$ exists for every election. This leaves an important theoretical gap between the best known lower bound $(k\geq 3)$ and upper bound $(k \leq 5)$ for the number of candidates needed to guarantee existence. We aim to close the gap between the existence guarantees and impossibility results for Condorcet winning sets. We explore an automated reasoning approach to tighten these bounds. We design a mixed-integer linear program (MILP) to search for elections that would serve as counter-examples to conjectured bounds. We employ a number of optimizations, such as symmetry breaking, subsampling, and constraint generation, to enhance the search and model effectively infinite electorates. Furthermore, we analyze the dual of the linear programming relaxation as a path towards obtaining a new upper bound. Despite extensive search on moderate-sized elections, we fail to find any election requiring a committee larger than size 3. Motivated by our experimental results in this direction, we simplify the dual linear program and formulate a conjecture which, if true, implies that a winning set of size 4 always exists. Our automated reasoning results provide strong empirical evidence that the Condorcet dimension of any election may be smaller than currently known upper bounds, at least for small instances. We offer a general-purpose framework for searching elections in ranked voting and a new, concrete analytical path via duality toward proving that smaller committees suffice.

Related papers

• Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling [54.50689440956967]
  LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of-N (BoN)<n>We propose Best-of-Majority (BoM) with a pivotal step that restricts the candidates to the responses with high frequency in the $N$ samples before selecting the top-$k$ rewards.<n>Unlike majority voting and BoN, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing $N$.
  arXiv  Detail & Related papers  (2025-10-03T17:35:45Z)
• 3+ Seat Risk-Limiting Audits for Single Transferable Vote Elections [56.12949230611067]
  We present an assertion-based approach to conducting full or partial RLAs for STV elections with three or more seats.<n>We show that we can quite often form partial audits that verify most, and sometimes all, of the reported winners.<n>We evaluate our method on a dataset of over 500 three- and four-seat STV elections from the 2017 and 2022 local council elections in Scotland.
  arXiv  Detail & Related papers  (2025-03-19T00:29:53Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections.<n>The margin of victory, or simply'margin', is the smallest number of ballots that need to be manipulated to alter the set of winners.<n>Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  We consider a perpetual approval voting method that guarantees that no voter is dissatisfied too many times.<n>We identify a sufficient condition on voter behavior under which a sublinear growth of dissatisfaction is possible.<n>We present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
  arXiv  Detail & Related papers  (2024-12-20T19:58:55Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• On Efficient Computation of DiRe Committees [2.741266294612776]
  Consider a committee election consisting of (i) a set of candidates who are divided into arbitrary groups each of size $atmost$ two.<n>A diversity constraint stipulates the selection of $atleast$ one candidate from each group.<n>A representation constraint stipulates the selection of $atleast$ one candidate from each population who has a non-null set of approved candidates.
  arXiv  Detail & Related papers  (2024-02-29T17:13:30Z)
• Breaking the Metric Voting Distortion Barrier [10.143374372425757]
  We consider the problem of metric distortion in social choice. Finding a randomized rule that guarantees distortion $3 - epsilon$ has been a major challenge in computational social choice. We give a rule that guarantees distortion less than $2.753$.
  arXiv  Detail & Related papers  (2023-06-30T17:56:33Z)
• Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion [11.282341369957212]
  metric distortion framework posits n voters and m candidates are jointly embedded in a metric space. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. We show that a simple voting rule, called Plurality Veto, achieves the same optimal distortion of 3.
  arXiv  Detail & Related papers  (2022-06-14T18:32:32Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
  We study computational aspects of a well-known single-winner voting rule called the Schulze method. Our paper is the first to bring fine-grained complexity into the field of computational social choice.
  arXiv  Detail & Related papers  (2021-03-05T22:27:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.