論文の概要: Space reduction techniques for the $3$-wise Kemeny problem

• arxiv url: http://arxiv.org/abs/2305.00140v2
• Date: Tue, 26 Dec 2023 16:45:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-29 23:15:32.987959
• Title: Space reduction techniques for the $3$-wise Kemeny problem
• Title（参考訳）: 3ドルのケメニー問題に対する空間削減技術
• Authors: Xuan Kien Phung and Sylvie Hamel
• Abstract要約: ケメニーの法則は、計算社会選択と生物学に様々な重要な応用がある最も研究されよく知られた投票方式の1つである。 我々は、ミロシュとハメルがケメニーの統治のために得たような、大位数定理のいくつかの一般化を確立する。 我々は、ベッツラーらによるケメニーの法則の有名な3/4ドルのマジョリティルールが、一般的には5ドル以上の選択肢のない選挙に対してのみ有効であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kemeny's rule is one of the most studied and well-known voting schemes with various important applications in computational social choice and biology. Recently, Kemeny's rule was generalized via a set-wise approach by Gilbert et. al. This paradigm presents interesting advantages in comparison with Kemeny's rule since not only pairwise comparisons but also the discordance between the winners of subsets of three alternatives are also taken into account in the definition of the $3$-wise Kendall-tau distance between two rankings. In spite of the NP-hardness of the 3-wise Kemeny problem which consists of computing the set of $3$-wise consensus rankings, namely rankings whose total $3$-wise Kendall-tau distance to a given voting profile is minimized, we establish in this paper several generalizations of the Major Order Theorems, as obtained by Milosz and Hamel for Kemeny's rule, for the $3$-wise Kemeny voting schemes to achieve a substantial search space reduction by efficiently determining in polynomial time the relative orders of pairs of alternatives. Essentially, our theorems quantify precisely the nontrivial property that if the preference for an alternative over another one in an election is strong enough, not only in the head-to-head competition but even when taking into account one or two more alternatives, then the relative order of these two alternatives in all $3$-wise consensus rankings must be as expected. As an application, we also obtain an improvement of the Major Order Theorems for Kememy's rule. Moreover, we show that the well-known $3/4$-majority rule of Betzler et al. for Kemeny's rule is only valid in general for elections with no more than $5$ alternatives with respect to the $3$-wise Kemeny scheme. Several simulations and tests of our algorithms on real-world and uniform data are provided.
• Abstract（参考訳）: ケメニーの法則は、計算社会選択と生物学に様々な重要な応用がある最も研究されよく知られた投票方式の1つである。 近年、ケメニーの法則はギルバートらによる集合的アプローチによって一般化された。 アル このパラダイムは、ペアワイズ比較だけでなく、3つの選択肢のサブセットの勝者間の不一致も、2つのランキングの間の3ドルのケンドール・トー距離の定義において考慮されるため、ケメニーの法則と比較して興味深い利点がある。 In spite of the NP-hardness of the 3-wise Kemeny problem which consists of computing the set of $3$-wise consensus rankings, namely rankings whose total $3$-wise Kendall-tau distance to a given voting profile is minimized, we establish in this paper several generalizations of the Major Order Theorems, as obtained by Milosz and Hamel for Kemeny's rule, for the $3$-wise Kemeny voting schemes to achieve a substantial search space reduction by efficiently determining in polynomial time the relative orders of pairs of alternatives. 基本的に、我々の定理は、選挙における別の選択肢に対する選好が十分に強く、また1つまたは2つの選択肢を考慮に入れたとしても十分であるなら、これら2つの選択肢の相対的な順序は、全ての3$のコンセンサスランキングにおいて期待通りである。 応用として,kememyの法則に対する主要な次数定理の改良も行う。 さらに、betzlerらによるkemenyの法則の3/4ドルの多数派ルールは、3ドルのkemenyスキームに関して5ドル未満の選挙においてのみ有効であることを示した。 実世界のデータと均一なデータに対するアルゴリズムのシミュレーションとテストを行う。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Parameterized Aspects of Distinct Kemeny Rank Aggregation [4.792851066169871]
  パラメータ化複雑性のレンズの下で,異なるケメニーランクの計算問題について検討する。 ランニング時間を大幅に増加させることなく、望ましいケメニーランキングが見つかることもわかりました。
  論文  参考訳（メタデータ） (2023-09-07T06:58:19Z)
• Breaking the Metric Voting Distortion Barrier [10.143374372425757]
  社会選択における計量歪みの問題を考察する。 歪み3-epsilon$を保証するランダム化ルールを見つけることは、計算社会選択において大きな課題である。 歪みを2.753ドル未満で保証する規則を与えます。
  論文  参考訳（メタデータ） (2023-06-30T17:56:33Z)
• Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes [0.0]
  ケンダルタウ距離の3ドルは、古典的なケメニー則と比較して興味深い利点を示す。 3$-wise Kemeny 問題は NP-hard であるので,本研究は空間縮小法として有用である。
  論文  参考訳（メタデータ） (2023-04-28T17:04:14Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [13.207754600697138]
  条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。 我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
  論文  参考訳（メタデータ） (2022-02-03T16:15:54Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。 本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。 凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T03:23:11Z)

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

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