論文の概要: Fine-Grained Complexity and Algorithms for the Schulze Voting Method
- arxiv url: http://arxiv.org/abs/2103.03959v1
- Date: Fri, 5 Mar 2021 22:27:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-09 15:17:19.660499
- Title: Fine-Grained Complexity and Algorithms for the Schulze Voting Method
- Title（参考訳）: シュルツ投票法における細粒度複雑さとアルゴリズム
- Authors: Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
- Abstract要約: シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。
私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
- 参考スコア（独自算出の注目度）: 9.399840807973545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study computational aspects of a well-known single-winner voting rule
called the Schulze method [Schulze, 2003] which is used broadly in practice. In
this method the voters give (weak) ordinal preference ballots which are used to
define the weighted majority graph (WMG) of direct comparisons between pairs of
candidates. The choice of the winner comes from indirect comparisons in the
graph, and more specifically from considering directed paths instead of direct
comparisons between candidates.
When the input is the WMG, to our knowledge, the fastest algorithm for
computing all possible winners in the Schulze method uses a folklore reduction
to the All-Pairs Bottleneck Paths (APBP) problem and runs in $O(m^{2.69})$
time, where $m$ is the number of candidates. It is an interesting open question
whether this can be improved. Our first result is a combinatorial algorithm
with a nearly quadratic running time for computing all possible winners. If the
input to the possible winners problem is not the WMG but the preference
profile, then constructing the WMG is a bottleneck that increases the running
time significantly; in the special case when there are $O(m)$ voters and
candidates, the running time becomes $O(m^{2.69})$, or $O(m^{2.5})$ if there is
a nearly-linear time algorithm for multiplying dense square matrices. To
address this bottleneck, we prove a formal equivalence between the well-studied
Dominance Product problem and the problem of computing the WMG. We prove a
similar connection between the so called Dominating Pairs problem and the
problem of verifying whether a given candidate is a possible winner.
Our paper is the first to bring fine-grained complexity into the field of
computational social choice. Using it we can identify voting protocols that are
unlikely to be practical for large numbers of candidates and/or voters, as
their complexity is likely, say at least cubic.
- Abstract（参考訳）: シュルツェ法(Schulze method[Schulze, 2003])と呼ばれる、よく知られた単一勝者投票規則の計算的側面について研究する。
この方法では、有権者は対の候補間の直接比較の重み付き多数決グラフ(wmg)を定義するために使われる順序選好投票(弱)を与える。
勝者の選択は、グラフの間接的比較、およびより具体的には、候補者間の直接比較ではなく、指示されたパスを検討することから来ています。
入力がWMGであるとき、私たちの知識によると、Schulzeメソッドのすべての勝者を計算するための最速のアルゴリズムは、オールペアボトルネックパス(APBP)問題への民話還元を使用し、$O(m^{2.69})$時間で実行され、$m$は候補者の数です。
これが改善できるかどうかは、興味深い疑問である。
最初の結果は、すべての勝者を計算するためにほぼ2倍の実行時間を持つ組合せアルゴリズムです。
可能な勝者問題への入力がWMGではなく優先度プロファイルである場合、WMGの構築は実行時間を大幅に増加させるボトルネックである。特別の場合、$O(m)$有権者および候補者がある場合、実行時間は$O(m^{2.69})$、または$O(m^{2.5})$になる。
このボトルネックに対処するため、よく研究されている支配的製品問題とWMGの計算問題との正式な等価性を証明した。
我々は、いわゆる支配ペア問題と、与えられた候補が勝者であるかどうかを検証する問題との類似性を証明する。
私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
これを使用すると、多数の候補者や有権者にとって実用的ではない投票プロトコルを特定することができます。
関連論文リスト
- Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。
本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
論文 参考訳（メタデータ） (2024-07-23T13:28:00Z) - Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。
限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
論文 参考訳（メタデータ） (2024-02-16T22:17:01Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。
我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
論文 参考訳（メタデータ） (2023-01-08T07:29:38Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - When Can Liquid Democracy Unveil the Truth? [12.198420431487731]
Caragiannis と Micha によって策定されたいわゆる ODP-problem を調査します。
有権者の確率やネットワークの接続性に関するいくつかの仮説の下で、我々は1時間1/2$近似アルゴリズムを得る。
この観察は、ソーシャルネットワークの接続が液体民主主義パラダイムの効率にとって重要な特徴であることを正式に証明している。
論文 参考訳（メタデータ） (2021-04-05T09:45:14Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Resolving the Optimal Metric Distortion Conjecture [27.344649091365067]
以下の計量歪み問題を考察する。
点の有限集合である$V$と$C$は、同じ距離空間にある。
我々はこれらのランキングのみを入力として、$C$のポイントを選択するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-16T04:13:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。