論文の概要: Differentially Private Condorcet Voting
- arxiv url: http://arxiv.org/abs/2206.13081v1
- Date: Mon, 27 Jun 2022 06:55:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 15:52:10.977305
- Title: Differentially Private Condorcet Voting
- Title（参考訳）: 極端にプライベートなコンドルセット投票
- Authors: Zhechen Li, Ao Liu, Lirong Xia, Yongzhi Cao, Hanpin Wang
- Abstract要約: 本稿では,よく知られたCondorcet法に基づくランダム化投票規則の3つのクラスを提案する。
ランダム性によって引き起こされる誤差を正確に推定することにより、ほとんどの場合、$CMEXP_lambda$が最も正確なメカニズムであることを示す。
我々は、差分プライバシーを投票公理とみなし、他の公理との関係について議論する。
- 参考スコア（独自算出の注目度）: 26.959251649951103
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Designing private voting rules is an important and pressing problem for
trustworthy democracy. In this paper, under the framework of differential
privacy, we propose three classes of randomized voting rules based on the
well-known Condorcet method: Laplacian Condorcet method ($CM^{LAP}_\lambda$),
exponential Condorcet method ($CM^{EXP}_\lambda$), and randomized response
Condorcet method ($CM^{RR}_\lambda$), where $\lambda$ represents the level of
noise. By accurately estimating the errors introduced by the randomness, we
show that $CM^{EXP}_\lambda$ is the most accurate mechanism in most cases. We
prove that all of our rules satisfy absolute monotonicity, lexi-participation,
probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion,
and approximate SD-strategyproofness. In addition, $CM^{RR}_\lambda$ satisfies
(non-approximate) probabilistic Condorcet criterion, while $CM^{LAP}_\lambda$
and $CM^{EXP}_\lambda$ satisfy strong lexi-participation. Finally, we regard
differential privacy as a voting axiom, and discuss its relations to other
axioms.
- Abstract（参考訳）: 民間の投票規則を設計することは、信頼できる民主主義にとって重要かつ差し迫った問題である。
本稿では,よく知られたcondorcet法に基づくランダム化投票ルールの3つのクラスを提案する: laplacian condorcet method (cm^{lap}_\lambda$), exponential condorcet method (cm^{exp}_\lambda$), randomized response condorcet method (cm^{rr}_\lambda$), ここで$\lambda$はノイズレベルを表す。
ランダム性によって生じる誤差を正確に推定することにより、ほとんどの場合、$CM^{EXP}_\lambda$が最も正確なメカニズムであることを示す。
これらの規則は, 絶対単調性, 語彙参加性, 確率論的パレート効率, 近似確率論的コンドルチェット基準, 近似SD安定度を満たす。
さらに、$CM^{RR}_\lambda$は(非近似的な)確率的コンドルセットの基準を満たす一方、$CM^{LAP}_\lambda$と$CM^{EXP}_\lambda$は強い語彙参加を満たす。
最後に,ディファレンシャルプライバシを投票公理とみなし,他の公理との関係について論じる。
関連論文リスト
- Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - Proportional Aggregation of Preferences for Sequential Decision Making [20.374669324368625]
投票者の選好を適度に決定する問題について検討する。
各ラウンドにおいて、決定ルールは、各投票者が承認した選択肢のどれかを報告する一連の選択肢から決定を選ばなければならない。
比喩的正当化表現に基づく公理を用いて、この目的を定式化する。
論文 参考訳（メタデータ） (2023-06-26T17:10:10Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-16T00:10:35Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - PAC Mode Estimation using PPR Martingale Confidence Sequences [5.623190096715942]
離散分布 $mathcalP$ のモードを十分に高い確率で正確に同定する問題を考える。
モード推定の一般化を提案し、$mathcalP$は$K geq 2$値を取ることができる。
結果,PPR-MEと表される停止規則は,対数係数までのサンプル複雑性において最適である。
論文 参考訳（メタデータ） (2021-09-10T18:11:38Z) - The Smoothed Satisfaction of Voting Axioms [34.65163653153113]
我々は,2つのよく研究された投票公理(コンドルチェット基準と参加)の円滑な満足度を特徴付けることに重点を置いている。
我々は1994年にベルクとレペリーによるこれらのルールに関するオープンな質問に回答し、以下のハイレベルなメッセージを確認した。
論文 参考訳（メタデータ） (2021-06-03T15:55:11Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。