論文の概要: Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences

• arxiv url: http://arxiv.org/abs/2604.05953v1
• Date: Tue, 07 Apr 2026 14:46:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-08 17:42:09.889849
• Title: Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
• Title（参考訳）: 声道間隔の選好を考慮したティール投票規則の多項式時間アルゴリズム
• Authors: Pasin Manurangsi, Krzysztof Sornat,
• Abstract要約: 我々は,任意のティーレ投票規則の下で,任意の大きさの委員会を最適に計算するためのリアルタイムアルゴリズムを提案する。 我々の結果は、各投票者が個別の重み(スコアリング)配列を持つ、一般化されたティールルールにまで及んでいる。
• 参考スコア（独自算出の注目度）: 29.61006537058682
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a polynomial-time algorithm for computing an optimal committee of size $k$ under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when voters can be ordered so that each candidate is approved by a consecutive voters). Our result extends to the Generalized Thiele rule, in which each voter has an individual weight (scoring) sequence. This resolves a 10-year-old open problem that was originally posed for Proportional Approval Voting and later extended to every Thiele rule (Elkind and Lackner, IJCAI 2015; Peters, AAAI 2018). Our main technical ingredient is a new structural result -- a concavity theorem for families of intervals. It shows that, given two solutions of different sizes, one can construct a solution of any intermediate size whose score is at least the corresponding linear interpolation of the two scores. As a consequence, on Voter Interval profiles, the optimal total Thiele score is a concave function of the committee size. We exploit this concavity within an optimization framework based on a Lagrangian relaxation of a natural integer linear program formulation, obtained by moving the cardinality constraint into the objective. On Voter Interval profiles, the resulting constraint matrix is totally unimodular, so it can be solved in polynomial time. Our main algorithm and its proof were obtained via human--AI collaboration. In particular, a slightly simplified version of the main structural theorem used by the algorithm was obtained in a single call to Gemini Deep Think.
• Abstract（参考訳）: 本稿では,投票者間領域における選挙に関する任意のティール投票規則の下で,各候補者が連続投票者によって承認されるように有権者を命令できるような,サイズが$k$の最適委員会を計算するための多項式時間アルゴリズムを提案する。 我々の結果は、各投票者が個別の重み(スコアリング)配列を持つ、一般化されたティールルールにまで及んでいる。 これは、元々はプロポーショナル・承認投票(Proportional Approval Voting)のために提案され、後にすべてのティーレルール(Elkind and Lackner, IJCAI 2015; Peters, AAAI 2018)に拡張された10年前のオープンな問題を解決した。 我々の主要な技術的要素は、新しい構造的結果である -- 間隔の族に対する凹凸定理である。異なる大きさの2つの解が与えられた場合、スコアが少なくとも2つのスコアの線形補間である任意の中間サイズの解を構築することができる。その結果、ボタインターバルプロファイルにおいて、最適なトータルティーレスコアは委員会サイズの凹凸関数である。我々は、この凹凸を、自然整数線形プログラムのラグランジアン緩和に基づく最適化フレームワーク内で利用し、その目的に濃度制約を移動させることにより得られる。ボタインターバルプロファイルでは、その制約行列は完全に一様であり、多項式時間で解くことができる。 特に、アルゴリズムが使用する主構造定理のわずかに単純化されたバージョンは、ジェミニ・ディープ・シンクへの単一の呼び出しで得られた。

関連論文リスト

• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。 我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。 本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
  論文  参考訳（メタデータ） (2024-12-20T19:58:55Z)
• On Efficient Computation of DiRe Committees [2.741266294612776]
  i) 任意のグループに分けられる候補者の組から成る委員会選挙について考えてみましょう。 多様性制約は、各グループから$atleast$1の候補を選択することを規定している。 表現制約は、承認された候補の非無効なセットを持つ各集団から$atleast$1の候補を選択することを規定している。
  論文  参考訳（メタデータ） (2024-02-29T17:13:30Z)
• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。 限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
  論文  参考訳（メタデータ） (2024-02-16T22:17:01Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [11.180055556912208]
  条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。 我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
  論文  参考訳（メタデータ） (2022-02-03T16:15:54Z)
• Adaptive Combinatorial Allocation [77.86290991564829]
  割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。 我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
  論文  参考訳（メタデータ） (2020-11-04T15:02:59Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
  論文  参考訳（メタデータ） (2020-10-13T17:26:09Z)

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

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