論文の概要: Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

• arxiv url: http://arxiv.org/abs/2604.19851v1
• Date: Tue, 21 Apr 2026 15:25:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.652587
• Title: Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections
• Title（参考訳）: 4つで十分か? 自動推論アプローチと2つの境界
• Authors: Itai Zilberstein, Ratip Emin Berker, George Li, Ruben Martins,
• Abstract要約: 我々は混合整数線形プログラムを用いて、予想される境界に対する反例となる選挙を探索する。 大規模な検索にもかかわらず、サイズ3より大きい委員会を必要とする選挙は見つからなかった。 我々の結果は、あらゆる選挙のコンドルチェット次元が、現在知られている上限よりも小さいかもしれないという強い実証的な証拠を提供する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: n$の有権者が$m$の候補者をランク付けする選挙では、コンドルセットが$k$の候補者からなる委員会である。 コンドルチェットのパラドックスは、ある選挙ではコンドルチェットの勝利集合が1つの候補(すなわち$k=1$)で認められないことを示し、同じことを$k=2$で示せる。 一方、最近の研究では、選挙毎に1組の$k=5$が存在することが証明されている。 このことは、最もよく知られた下界$(k\geq 3)$と上界$(k \leq 5)$の間に重要な理論的ギャップを残している。 コンドルチェットの勝利集合の存在保証と不可能な結果のギャップを埋めることを目的としている。 これらの境界を厳格化するための自動推論手法を探索する。 我々は、予測境界に対する反例となる選挙を探索する混合整数線形プログラム(MILP)を設計する。 我々は, 対称性の破れ, サブサンプリング, 制約生成などの最適化を施し, 探索とモデルを効果的に無限のエレクトロレートに拡張する。 さらに、線形プログラミング緩和の双対を、新しい上界を得るための経路として分析する。 中規模の選挙を徹底的に調査したにもかかわらず、サイズ3より大きい委員会を必要とする選挙は見つからなかった。 この方向の実験結果に触発され、双対線型プログラムを単純化し、もし真であれば、大きさ 4 の入賞集合は常に存在するという予想を定式化する。 我々の自動推論結果は、あらゆる選挙のコンドルチェット次元が、少なくとも小さな場合において、現在知られている上限よりも小さいかもしれないという強い実証的な証拠を提供する。 我々は、ランク付けされた投票における選挙を探索するための汎用的な枠組みと、より小さな委員会が十分であることを示すための双対性による新しい具体的な分析経路を提供する。

関連論文リスト

• 3+ Seat Risk-Limiting Audits for Single Transferable Vote Elections [56.12949230611067]
  本稿では,3人以上の議席を持つSTV選挙において,完全ないし部分的RLAを実施するためのアサーションベースのアプローチを提案する。 私たちはしばしば、報告された勝者のほとんど、時にはすべてを検証する部分的な監査を作成することができることを示しています。 我々は,2017年と2022年のスコットランド地方議会選挙から,500人以上の3席と4席のSTV選挙のデータセットを用いて評価を行った。
  論文  参考訳（メタデータ） (2025-03-19T00:29:53Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)は、勝利者の集合を変えるために操作される必要のある最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
  論文  参考訳（メタデータ） (2025-01-24T13:39:23Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。 我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。 本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
  論文  参考訳（メタデータ） (2024-12-20T19:58:55Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。 本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
  論文  参考訳（メタデータ） (2024-07-23T13:28:00Z)
• On Efficient Computation of DiRe Committees [2.741266294612776]
  i) 任意のグループに分けられる候補者の組から成る委員会選挙について考えてみましょう。 多様性制約は、各グループから$atleast$1の候補を選択することを規定している。 表現制約は、承認された候補の非無効なセットを持つ各集団から$atleast$1の候補を選択することを規定している。
  論文  参考訳（メタデータ） (2024-02-29T17:13:30Z)
• Breaking the Metric Voting Distortion Barrier [10.143374372425757]
  社会選択における計量歪みの問題を考察する。 歪み3-epsilon$を保証するランダム化ルールを見つけることは、計算社会選択において大きな課題である。 歪みを2.753ドル未満で保証する規則を与えます。
  論文  参考訳（メタデータ） (2023-06-30T17:56:33Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。 我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。 一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
  論文  参考訳（メタデータ） (2021-04-19T08:26:40Z)
• Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
  シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。 私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
  論文  参考訳（メタデータ） (2021-03-05T22:27:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。