論文の概要: Query-efficient winner prediction in district-based elections

• arxiv url: http://arxiv.org/abs/2610.00577v1
• Date: Wed, 30 Sep 2026 18:46:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.718643
• Title: Query-efficient winner prediction in district-based elections
• Title（参考訳）: 地方選挙における問合せ効率の予測
• Abstract要約: 選挙区ベースの選挙では、Nの有権者はkの選挙区に分けられ、各有権者はmの候補者の1人に投票する。 本研究では,クエリ複雑性モデルにおいて,地区ベースの選挙の勝者を予測する問題について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e. the candidate getting the largest number of votes is declared the winner, breaking ties as per some fixed rule), and the overall winner is determined by applying plurality to the district winners; we assume that there is a unique winner amongst the district winners. The margin of victory of such an election is the minimum number of votes that must be altered so that the current winner ceases to be the unique district winner. We study the problem of predicting the winner of a district-based election in the query complexity model, where one has query access to individual votes. The objective is to minimise the number of queries. This setting captures exit polling, where queries correspond to interviewing voters, and is closely related to problems in query complexity and property testing. Assuming that the margin of victory of the election is at least eps N, Dey, Kar and Sanyal (AAMAS 2023) gave algorithms for the case of two candidates with error probability del and query complexity tilde{O}(1/eps^6 log^2 1/del), which improves to tilde{O}(1/eps^4 log^2 1/del) under the additional assumption that district populations are balanced. Our main result is an adaptive randomised algorithm that, for an arbitrary district-based election and any error parameter del, with probability at least 1-del, predicts the winner correctly using tilde{O}(1/eps^2 log m/del log 1/del) queries. In particular, we improve the bounds of Dey et al. for arbitrary district populations and extend their results to any number of candidates. Furthermore, for constantly many candidates, our algorithm nearly matches a lower bound of Omega(1/eps^2 log 1/del) on the query complexity that holds even for two candidates and a single district.
• Abstract（参考訳）: 選挙区ベースの選挙では、Nの有権者はkの選挙区に分けられ、各有権者はmの候補者の1人に投票する。 各地区は、複数のルールを用いて勝者を選定する(すなわち、最も多くの票を得た候補者を勝者と宣言し、一定の規則に従って関係を断ち切る)。 このような選挙の勝利率の限界は、現在の勝利者が唯一の選挙区の勝者になるのをやめるために変更しなければならない最小限の票数である。 本研究では,個別の投票に対するクエリーアクセスが可能なクエリー複雑性モデルにおいて,地域ベースの選挙の勝者を予測する問題について検討する。 目的はクエリの数を最小限にすることである。 この設定は、クエリが投票者へのインタビューに対応するエグジットポーリングをキャプチャし、クエリの複雑さとプロパティテストの問題に密接に関連している。 選挙の勝利率が少なくとも eps N であると仮定すると、Dey, Kar と Sanyal (AAMAS 2023) は、エラー確率 del とクエリ複雑性 tilde{O}(1/eps^6 log^2 1/del) の2つの候補に対してアルゴリズムを与え、これは、地域人口が均衡しているという追加の仮定の下で tilde{O}(1/eps^4 log^2 1/del) に改善される。 我々の主な結果は、任意の地区ベースの選挙と任意の誤差パラメータ del に対して、少なくとも 1-del の確率で tilde{O}(1/eps^2 log m/del log 1/del) クエリを用いて、勝者を正しく予測する適応的ランダム化アルゴリズムである。 特に、任意の地域人口に対するDey et alの限界を改善し、その結果を任意の数の候補者に拡張する。 さらに、常に多くの候補に対して、我々のアルゴリズムは2つの候補と1つの地区でさえ持つクエリの複雑さに基づいて、Omega(1/eps^2 log 1/del)の下位境界にほぼ一致する。

関連論文リスト

• Algorithms for Structured Elections under Thiele Voting Rules [50.74668888214481]
  我々は、ティーレ投票規則の下での承認ベース委員会選挙における勝者決定問題の計算複雑性について検討する。 まず、各候補者を承認する有権者の集合に基づいて最適解の構造を分析する。 ここでは、VI 上のすべてのティーレ則が FPT であり、問題が一般のインスタンス上でNP-hard であるパラメータであることを示す。
  論文  参考訳（メタデータ） (2026-07-30T17:37:14Z)
• Drawing a Map of Elections [53.92343633736932]
  選挙の地図は、選挙のデータセット、選挙間の類似性を測定する方法、および2Dユークリッド空間における選挙の表現の3つの主要な要素で構成されている。 様々な基準に従って地図上で選挙を彩色することは、多くの実験の結果を分析するのにどう役立つかを示す。
  論文  参考訳（メタデータ） (2025-04-04T11:44:56Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)は、勝利者の集合を変えるために操作される必要のある最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
  論文  参考訳（メタデータ） (2025-01-24T13:39:23Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。 本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
  論文  参考訳（メタデータ） (2024-07-23T13:28:00Z)
• 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)
• Determining Winners in Elections with Absent Votes [26.675597212113658]
  我々は、投票が最上位の場合に、不在の投票問題で決定的な勝者を調査する。 単一の投票でWAV問題はNP完全であることを示す。 本稿では、時間内に問題を計算できるように、位置スコアリングルールの特別な場合を提案する。
  論文  参考訳（メタデータ） (2023-10-11T02:52:16Z)
• Sampling-Based Winner Prediction in District-Based Elections [6.241494296494433]
  選挙区ベースの選挙では、各選挙区の勝者を決定するために$r$の投票ルールを適用し、最大数の選挙区で当選する候補者が勝者となる。 そこで我々は,これらの地区ベースの選挙システムの勝者を予測するために,効率的なサンプリングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T20:32:48Z)

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

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