論文の概要: Computing Voting Rules with Elicited Incomplete Votes
- arxiv url: http://arxiv.org/abs/2402.11104v1
- Date: Fri, 16 Feb 2024 22:17:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 23:24:47.117703
- Title: Computing Voting Rules with Elicited Incomplete Votes
- Title（参考訳）: 不完全投票による投票ルールの計算
- Authors: Daniel Halpern, Safwan Hossain, Jamie Tucker-Foltz
- Abstract要約: 我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。
限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
決定論的アルゴリズムのバウンダリ間にはギャップはないが、ランダム化アルゴリズムの正確なクエリ複雑性を特定することは難しい問題である。
- 参考スコア（独自算出の注目度）: 12.981755656269097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the difficulty of specifying complete ordinal preferences over a
large set of $m$ candidates, we study voting rules that are computable by
querying voters about $t < m$ candidates. Generalizing prior works that focused
on specific instances of this problem, our paper fully characterizes the set of
positional scoring rules that can be computed for any $1 \leq t < m$, which
notably does not include plurality. We then extend this to show a similar
impossibility result for single transferable vote (elimination voting). These
negative results are information-theoretic and agnostic to the number of
queries. Finally, for scoring rules that are computable with limited-sized
queries, we give parameterized upper and lower bounds on the number of such
queries a deterministic or randomized algorithm must make to determine the
score-maximizing candidate. While there is no gap between our bounds for
deterministic algorithms, identifying the exact query complexity for randomized
algorithms is a challenging open problem, of which we solve one special case.
- Abstract（参考訳）: 多数の$m$候補に対する完全順序選好の指定が困難であることに動機づけられ、投票規則について検討し、投票者は$t < m$ 候補について質問する。
本論文は,この問題の具体例に焦点を当てた先行研究を一般化し,任意の 1 ドル t < m$ に対して計算可能な位置スコアリング規則の集合を完全に特徴付ける。
次に、これを拡張して、単一の投票(除票)に対して、同様の不可避結果を示す。
これらの負の結果は、クエリの数に情報理論と非依存である。
最後に、限定的なクエリで計算可能なスコアリングルールに対して、パラメータ化された上位および下位境界を、決定論的あるいはランダム化アルゴリズムがスコア最大化候補を決定するために与える。
決定論的アルゴリズムのバウンダリ間にはギャップはないが、ランダム化アルゴリズムの正確なクエリ複雑性を特定することは難しい問題であり、1つの特別なケースを解決する。
関連論文リスト
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting [13.207754600697138]
条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。
我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
論文 参考訳（メタデータ） (2022-02-03T16:15:54Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-02T10:50:52Z) - Discriminative Learning via Adaptive Questioning [6.378513792050356]
本稿では,候補の能力を複数のカテゴリの1つに最適に分類する,適応的な質問列を設計する問題を考察する。
候補の能力は未知のパラメータとしてモデル化され、質問の難易度とともに、s/h が質問に正しく答えられる可能性を決定する。
論文 参考訳（メタデータ） (2020-04-11T16:50:00Z) - Binary Classification with XOR Queries: Fundamental Limits and An
Efficient Algorithm [15.127728811011245]
未知ラベルのバイナリ分類のための問合せに基づくデータ取得問題を考える。
我々は、選択したオブジェクトのサブセットの「グループ属性」を問う効果的なクエリタイプを考える。
雑音パラメータが未知であっても,この制限を実現する効率的な推論アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-31T11:23:02Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。