論文の概要: Decisive Margins in Differentially Private Voting

• arxiv url: http://arxiv.org/abs/2608.18772v1
• Date: Wed, 19 Aug 2026 10:29:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-20 20:13:55.37572
• Title: Decisive Margins in Differentially Private Voting
• Title（参考訳）: 差分投票における決定的結婚
• Abstract要約: 差分プライバシーは、公表された結果にランダム性を注入することで個々の投票記録を保護するが、このノイズは選挙が終わったときに誤った結果をもたらす可能性がある。 我々は、Plurality、Condorcet、Maximin、Plurality with Runoff、STV(Single Transferable Vote)などの共通投票ルールにおいて、中央の差分プライバシーと局所の差分プライバシーがいかに正確かを検討する。
• 参考スコア（独自算出の注目度）: 20.175634288058166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close. We study how precise central differential privacy and local differential privacy can be for common voting rules, including Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable Vote (STV). Our measure of precision is the margin of victory needed for a private mechanism to return the same winner as the non-private rule with high probability. We give private algorithms for publishing the winner and prove upper bounds on the required margin for these algorithms. We also prove lower bounds showing that nontrivial margins are necessary; many of these bounds match the corresponding upper bounds up to logarithmic factors. For STV, an information-theoretic upper bound matches the lower bound, but we prove that this guarantee cannot be achieved in polynomial time unless NP $\subseteq$ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.
• Abstract（参考訳）: 差分プライバシーは、公表された結果にランダム性を注入することで個々の投票記録を保護するが、このノイズは選挙が終わったときに誤った結果をもたらす可能性がある。 我々は、Plurality、Condorcet、Maximin、Plurality with Runoff、Single Transferable Vote(STV)など、共通の投票ルールにおいて、中央の差分プライバシーと局所の差分プライバシーがいかに正確かを検討する。 我々の精度の尺度は、プライベートなメカニズムが、高い確率で非プライベートなルールと同じ勝者を返すのに必要な勝利のマージンである。 我々は、勝者を公開するためのプライベートアルゴリズムを与え、これらのアルゴリズムに必要なマージンの上限を証明します。 また、非自明な辺は必要であることを示す下界も証明し、これらの境界の多くは対数的因子まで対応する上界と一致する。 STV の場合、情報理論上界は下界と一致するが、NP $\subseteq$ BPP がなければ多項式時間ではこの保証は達成できない。 これは、差分プライバシーとユーティリティを同時に必要とした場合に、計算的に抽出可能なタスクの稀な例である。

関連論文リスト

• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
  論文  参考訳（メタデータ） (2026-02-12T17:49:07Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)は、勝利者の集合を変えるために操作される必要のある最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
  論文  参考訳（メタデータ） (2025-01-24T13:39:23Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
  プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。 これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。 これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。
  論文  参考訳（メタデータ） (2024-10-22T18:33:02Z)
• Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise [7.110450972801578]
  プライベート分散マルチパーティ乗算の問題点を考察する。 Shamirの秘密共有コーディング戦略が、分散計算における完全な情報理論プライバシを実現することは、十分に確立されている。
  論文  参考訳（メタデータ） (2023-09-28T02:13:13Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。 ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。 これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
  論文  参考訳（メタデータ） (2022-06-06T13:49:37Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  本研究は,局所的差分プライバシー(LDP)の制約の下で,集団平均の非パラメトリック,非漸近的統計的推測を行う手法を導出する。 民営化データへのアクセスのみを与えられた場合、$mustar$に対して信頼区間(CI)と時間一様信頼シーケンス(CS)を提示する。
  論文  参考訳（メタデータ） (2022-02-17T16:04:49Z)
• Successive Refinement of Privacy [38.20887036580742]
  本研究は、局所微分プライバシー(LDP)を実現するために、どの程度ランダム性が必要かを検討する。 モチベーションシナリオは、複数のアナリストに複数のレベルのプライバシを提供することである。 各ユーザのプライバシーを維持しながら、ランダムなキーを時間の経過とともに再利用できないことを示す。
  論文  参考訳（メタデータ） (2020-05-24T04:16:01Z)
• Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics [2.614355818010333]
  アナリストが純粋なDP、境界範囲(指数的なメカニズムなど)、集中的なDPメカニズムを任意の順序で選択できる場合、強いプライバシー損失バウンダリを提供する。 また、アナリストが純粋なDPと境界範囲のメカニズムをバッチで選択できる場合に適用される最適なプライバシー損失境界を提供する。
  論文  参考訳（メタデータ） (2020-04-15T17:33:10Z)

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

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