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

• arxiv url: http://arxiv.org/abs/2305.00140v1
• Date: Sat, 29 Apr 2023 01:21:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 16:48:32.809437
• Title: Space reduction techniques for the $3$-wise Kemeny problem
• Title（参考訳）: 3ドルのケメニー問題に対する空間削減技術
• Authors: Xuan Kien Phung and Sylvie Hamel
• Abstract要約: 従来のケメニー法と比較して,3ドル単位のケメニー投票方式が興味深い利点を示すことを示す。 我々の定理は、選挙における代替案の選好が十分強ければ、これらの2つの代替案の相対順序は期待通りでなければならないという非自明な性質を定量化する。
• 参考スコア（独自算出の注目度）: 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. Following this paradigm, we have shown in \cite{Phung-Hamel-2023} that the $3$-wise Kemeny voting scheme induced by the $3$-wise Kendall-tau distance presents interesting advantages in comparison with the classical Kemeny rule. While the $3$-wise Kemeny problem, which consists of computing the set of $3$-wise consensus rankings of a voting profile, is NP-hard, we establish in this paper several generalizations of the Major Order Theorems, as obtained in \cite{Milosz-Hamel-2020} for the classical Kemeny rule, for the $3$-wise Kemeny voting scheme 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 non-trivial 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 consideration one or two more alternatives, then the relative order of these two alternatives in every $3$-wise consensus ranking must be as expected. Moreover, we show that the well-known $3/4$-majority rule of Betzler et al. for the classical Kemeny rule is only valid for elections with no more than $5$ alternatives with respect to the $3$-wise Kemeny scheme. Examples are also provided to show that the $3$-wise Kemeny rule is more resistant to manipulation than the classical one.
• Abstract（参考訳）: ケメニーの法則は、計算社会選択と生物学に様々な重要な応用がある最も研究されよく知られた投票方式の1つである。 近年、ケメニーの法則はギルバートらによる集合的アプローチによって一般化された。 アル このパラダイムに従い、我々は \cite{phung-hamel-2023} において、3ドルのケンドール-タウ距離によって引き起こされる3ドルのケメニー投票スキームが古典的なケメニー規則と比較して興味深い利点を示していることを示した。 投票プロファイルの3ドルのコンセンサスランキングを計算することからなる3ドルのkemeny問題はnp-hardであるが、本論文では、従来のkemenyルールに対するcite{milosz-hamel-2020} で得られた主要な次数定理のいくつかの一般化を、多項式時間で相対次数を効率的に決定することにより、実質的な検索空間削減を達成するための3ドルのkemeny投票スキームのために確立する。 本質的には、我々の定理は、選挙において別の選択肢よりも別の選択肢の選好が十分強く、また1つまたは2つの選択肢を考慮しても十分強い場合、これら2つの選択肢の相対順序が3$のコンセンサスランキングで期待通りである、という非自明な性質を正確に定量化する。 さらに、古典的なケメニー規則に対するベツラーらの有名な3/4ドルのマジョリティルールは、3ドルのケメニー・スキームに関して5ドル以下の選択肢を持たない選挙に対してのみ有効であることを示す。 3ドルのkemenyルールは、古典的なルールよりも操作に抵抗があることを示す例もある。

関連論文リスト

• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  基本方針と最良$n$ポリシーのKL分散は、$log (n) - (n-1)/n.$と等しいことを示す。 KLの発散に対する新しい推定器を提案し、いくつかの例を通して厳密な近似を与えることを実証的に示す。
  論文  参考訳（メタデータ） (2024-01-03T18:39:13Z)
• 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)
• 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)

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

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