論文の概要: Sampling-Based Winner Prediction in District-Based Elections
- arxiv url: http://arxiv.org/abs/2203.00083v1
- Date: Mon, 28 Feb 2022 20:32:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 03:56:46.900810
- Title: Sampling-Based Winner Prediction in District-Based Elections
- Title（参考訳）: 地区選挙におけるサンプリングに基づく勝者予測
- Authors: Palash Dey, Debajyoti Kar, Swagato Sanyal
- Abstract要約: 選挙区ベースの選挙では、各選挙区の勝者を決定するために$r$の投票ルールを適用し、最大数の選挙区で当選する候補者が勝者となる。
そこで我々は,これらの地区ベースの選挙システムの勝者を予測するために,効率的なサンプリングベースアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.241494296494433
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a district-based election, we apply a voting rule $r$ to decide the
winners in each district, and a candidate who wins in a maximum number of
districts is the winner of the election. We present efficient sampling-based
algorithms to predict the winner of such district-based election systems in
this paper. When $r$ is plurality and the margin of victory is known to be at
least $\varepsilon$ fraction of the total population, we present an algorithm
to predict the winner. The sample complexity of our algorithm is
$\mathcal{O}\left(\frac{1}{\varepsilon^4}\log
\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$. We complement this result by
proving that any algorithm, from a natural class of algorithms, for predicting
the winner in a district-based election when $r$ is plurality, must sample at
least $\Omega\left(\frac{1}{\varepsilon^4}\log\frac{1}{\delta}\right)$ votes.
We then extend this result to any voting rule $r$. Loosely speaking, we show
that we can predict the winner of a district-based election with an extra
overhead of
$\mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right)$ over the
sample complexity of predicting the single-district winner under $r$. We
further extend our algorithm for the case when the margin of victory is
unknown, but we have only two candidates. We then consider the median voting
rule when the set of preferences in each district is single-peaked. We show
that the winner of a district-based election can be predicted with
$\mathcal{O}\left(\frac{1}{\varepsilon^4}\log\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$
samples even when the harmonious order in different districts can be different
and even unknown. Finally, we also show some results for estimating the margin
of victory of a district-based election within both additive and multiplicative
error bounds.
- Abstract（参考訳）: 地区ベースの選挙において、各地区の勝者を決定するためにr$という投票規則を適用し、最大数の地区で当選した候補者が選挙の勝者である。
本稿では,このような地区選挙システムの勝者を予測するために,効率的なサンプリングに基づくアルゴリズムを提案する。
r$が複数であり、勝利のマージンが全人口の少なくとも$\varepsilon$分の1であることが知られているとき、勝者を予測するアルゴリズムを提示する。
アルゴリズムのサンプル複雑性は$\mathcal{O}\left(\frac{1}{\varepsilon^4}\log \frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$である。
我々は、この結果を補うために、自然階級のアルゴリズムから、$r$が複数であるときの地方選挙の勝者を予測するアルゴリズムが、少なくとも$\Omega\left(\frac{1}{\varepsilon^4}\log\frac{1}{\delta}\right)$ voteをサンプリングしなければならないことを証明した。
次に、この結果を任意の投票ルールに拡張します。
以下に示すように、地区ベースの選挙の勝者を$\mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right)という余分なオーバーヘッドで予測できることを示します。
勝利の限界が不明な場合のアルゴリズムをさらに拡張するが、2つの候補しか持たない。
次に、各地区の選好セットが単一話者である場合の中央値投票ルールを検討する。
地区ベースの選挙の勝者は、異なる地区の調和順序が異なり未知であっても、$\mathcal{o}\left(\frac{1}{\varepsilon^4}\log\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$サンプルで予測できることを示した。
最後に,加法的および乗算的誤差境界内における地区選挙の勝利率を推定するためのいくつかの結果を示す。
関連論文リスト
- Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Ahead of the Count: An Algorithm for Probabilistic Prediction of Instant Runoff (IRV) Elections [0.0]
Instant Runoff Voting (IRV) 選挙の結果を予測する新しいアルゴリズムを提案する。
アルゴリズムは、各候補ランキングの投票総数を表す離散確率分布の集合を入力として取る。
IRVラウンドで発生する可能性のあるすべての除去シーケンスを計算し、それぞれに確率を割り当てる。
論文 参考訳（メタデータ） (2024-05-15T00:25:51Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。
我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
論文 参考訳（メタデータ） (2023-01-08T07:29:38Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
我々は、Szufa et al.(AAMAS 2020)の「選挙マップ」アプローチを用いて、よく知られた投票分布を分析します。
分布の「スケルトン写像」を描き、その頑健さを評価し、その性質を分析する。
論文 参考訳（メタデータ） (2022-05-16T17:40:22Z) - Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。
私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
論文 参考訳（メタデータ） (2021-03-05T22:27:36Z) - Resolving the Optimal Metric Distortion Conjecture [27.344649091365067]
以下の計量歪み問題を考察する。
点の有限集合である$V$と$C$は、同じ距離空間にある。
我々はこれらのランキングのみを入力として、$C$のポイントを選択するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-16T04:13:06Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。