論文の概要: Algorithms for Structured Elections under Thiele Voting Rules

• arxiv url: http://arxiv.org/abs/2607.28575v1
• Date: Thu, 30 Jul 2026 17:37:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.701707
• Title: Algorithms for Structured Elections under Thiele Voting Rules
• Title（参考訳）: ティール投票規則に基づく構造化選挙のアルゴリズム
• Authors: Alexandra Lassota, Krzysztof Sornat,
• Abstract要約: 我々は、ティーレ投票規則の下での承認ベース委員会選挙における勝者決定問題の計算複雑性について検討する。 まず、各候補者を承認する有権者の集合に基づいて最適解の構造を分析する。 ここでは、VI 上のすべてのティーレ則が FPT であり、問題が一般のインスタンス上でNP-hard であるパラメータであることを示す。
• 参考スコア（独自算出の注目度）: 50.74668888214481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.
• Abstract（参考訳）: 我々は、ティーレ投票規則の下での承認ベース委員会選挙における勝者決定問題の計算複雑性について検討する。 これらのルールは固定重みベクトルによってパラメータ化され、投票者の満足度が選出された候補者の数に依存するかを指定する。 まず、各候補者を承認する有権者の集合、すなわち有権者の承認投票が候補者間の依存関係をいかに引き起こすかに基づいて最適解の構造を分析する。 これを用いて, 有権者の適切な順序付けの後, 各候補者が連続投票の間隔で承認される自然制限領域であるVoter Interval(VI)ドメイン上で, PAV(Proportional Approval Voting)およびその他のTieleルールのためのFPTアルゴリズムを設計する。 特に, パラメータが定数値を取る場合であっても, VI 上のすべてのティール規則が一般インスタンス上でNPハードなパラメータに対して FPT であることが示される。 この結果から,Voter Interval インスタンス上での PAV の計算複雑性の理解が促進される。 さらに、各候補が少なくとも2人の投票者によって承認された場合の多項式時間アルゴリズムと、当選委員会の総得点でパラメータ化されたFPTアルゴリズムを提供することで、PAV(および他のティーレ投票規則)に関する文献からの2つのオープンな質問を解決する。

関連論文リスト

• Computing Thiele Rules on Interval Elections and their Generalizations [46.93587966131188]
  ティレ結果の計算は一般にNPハードであることが示される。 候補区間 (CI) では、完全に一様制約行列を持つ線形プログラム (LP) を通して時間計算可能である。 また、VCIに近づき、承認選挙において自然な解釈を持つLCの代替的定義も提供する。
  論文  参考訳（メタデータ） (2026-05-04T18:39:48Z)
• Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences [29.61006537058682]
  我々は,任意のティーレ投票規則の下で,任意の大きさの委員会を最適に計算するためのリアルタイムアルゴリズムを提案する。 我々の結果は、各投票者が個別の重み(スコアリング)配列を持つ、一般化されたティールルールにまで及んでいる。
  論文  参考訳（メタデータ） (2026-04-07T14:46:37Z)
• 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)
• Multiwinner Temporal Voting with Aversion to Change [30.15852603215344]
  我々は、有権者が候補者よりもダイナミックに選好する2段階の委員会選挙を調査する。 各段階において、委員会は所定の投票規則の下で選ばれる。 ティーレ則のクラスに対する完全複雑性二分法を示す。
  論文  参考訳（メタデータ） (2024-08-20T17:16:54Z)
• 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)

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

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