論文の概要: Computing Thiele Rules on Interval Elections and their Generalizations

• arxiv url: http://arxiv.org/abs/2605.03067v2
• Date: Thu, 07 May 2026 21:11:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 16:31:22.734367
• Title: Computing Thiele Rules on Interval Elections and their Generalizations
• Title（参考訳）: 中間選挙に関するティールルールの計算と一般化
• Authors: Dimitris Avramidis, Alexandra Lassota, Ulrike Schmidt-Kraepelin, Adrian Vetta,
• Abstract要約: ティレ結果の計算は一般にNPハードであることが示される。 候補区間 (CI) では、完全に一様制約行列を持つ線形プログラム (LP) を通して時間計算可能である。 また、VCIに近づき、承認選挙において自然な解釈を持つLCの代替的定義も提供する。
• 参考スコア（独自算出の注目度）: 46.93587966131188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Voting (PAV), stand out for desirable properties such as proportional representation, Pareto optimality, and support monotonicity. Their main drawback is that computing a Thiele outcome is NP-hard in general. A glimpse of hope comes from the fact that Thiele rules are better behaved under structured preferences. On the candidate interval (CI) domain, they are computable in polynomial time via a linear program (LP) that has a totally unimodular constraint matrix. Surprisingly, this approach fails for the related voter interval (VI) domain, and the complexity of the problem has repeatedly been posed as an open question. Our main result resolves this question: although the relevant matrix is not totally unimodular, the ``standard'' LP still admits at least one optimal integral solution, and we provide a fast algorithm for finding it. Our technique naturally extends to the voter-candidate interval (VCI) domain, also known as the 1-dimensional voter-candidate range (1D-VCR) domain, and to the linearly consistent (LC) domain, both of which generalize the candidate and voter interval domains. Although both the VCI and LC domains have been studied in social choice, their relationship was unknown. We show, through connections to graph theory, that LC strictly contains VCI. We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections; this equivalence may be of independent interest. Finally, we study an alternative tree-based generalization of VCI and show that Thiele rules become NP-hard to compute on this domain.
• Abstract（参考訳）: 承認ベースの委員会投票は、社会選択コミュニティで大きな注目を集めている。 研究された規則の中では、ティーレ規則、特に比例表現、パレート最適性、単調性のサポートといった望ましい性質について際立っている。 主な欠点は、Thieleの結果の計算が一般にNPハードであることである。 希望を垣間見るのは、ティーレのルールは構造化された好みの下で振る舞うのがよいという事実から来ている。 候補区間(CI)領域では、完全に一様制約行列を持つ線形プログラム(LP)を介して多項式時間で計算可能である。 驚いたことに、このアプローチは関連する投票間隔 (VI) ドメインで失敗し、問題の複雑さは何度もオープンな問題として提起されてきた。 関係行列は完全に一様ではないが、「標準」LPは依然として少なくとも一つの最適積分解を認めており、それを見つけるための高速アルゴリズムを提供する。 我々の手法は自然界において1次元の投票者候補間隔(VCI)領域、すなわち1次元の投票者候補間隔(1D-VCR)領域、および候補と投票者間隔領域を一般化する線形整合(LC)領域にまで拡張されている。 VCIドメインとLCドメインはともに社会的選択で研究されているが、それらの関係は不明である。 グラフ理論との接続を通して、LC は VCI を厳密に含んでいることを示す。 また、VCIに近づき、承認選挙において自然な解釈を持つLCの代替的定義も提供します。 最後に、VCIの代替木に基づく一般化について研究し、Thieleルールがこの領域で計算するNPハードとなることを示す。

関連論文リスト

• Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences [29.61006537058682]
  我々は,任意のティーレ投票規則の下で,任意の大きさの委員会を最適に計算するためのリアルタイムアルゴリズムを提案する。 我々の結果は、各投票者が個別の重み(スコアリング)配列を持つ、一般化されたティールルールにまで及んでいる。
  論文  参考訳（メタデータ） (2026-04-07T14:46:37Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。 我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。 本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
  論文  参考訳（メタデータ） (2024-12-20T19:58:55Z)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [11.180055556912208]
  条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。 我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
  論文  参考訳（メタデータ） (2022-02-03T16:15:54Z)
• Core-Stable Committees under Restricted Domains [27.621521330479208]
  我々は委員会選挙の設定について検討する。そこでは、個人が利用可能な対象の特定の大きさのサブセットをまとめて選択する必要がある。 このモデルは、政治選挙、参加予算、施設配置など、多くの実生活シナリオに関係している。
  論文  参考訳（メタデータ） (2021-08-04T12:04:29Z)
• 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)
• Adaptive Combinatorial Allocation [77.86290991564829]
  割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。 我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
  論文  参考訳（メタデータ） (2020-11-04T15:02:59Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。 我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
  論文  参考訳（メタデータ） (2020-02-08T19:35:01Z)

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

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