論文の概要: Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes

• arxiv url: http://arxiv.org/abs/2304.14980v1
• Date: Fri, 28 Apr 2023 17:04:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-01 13:23:52.651242
• Title: Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes
• Title（参考訳）: 集合的ケメニー投票方式の最適多数決ルールと量的コンドルセット特性
• Authors: Xuan Kien Phung and Sylvie Hamel
• Abstract要約: ケンダルタウ距離の3ドルは、古典的なケメニー則と比較して興味深い利点を示す。 3$-wise Kemeny 問題は NP-hard であるので,本研究は空間縮小法として有用である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The important Kemeny problem, which consists of computing median consensus rankings of an election with respect to the Kemeny voting rule, admits important applications in biology and computational social choice and was generalized recently via an interesting setwise approach by Gilbert et. al. Our first results establish optimal quantitative extensions of the Unanimity property and the well-known $3/4$-majority rule of Betzler et al. for the classical Kemeny median problem. Moreover, by elaborating an exhaustive list of quantified axiomatic properties (such as the Condorcet and Smith criteria, the $5/6$-majority rule, etc.) of the $3$-wise Kemeny rule where not only pairwise comparisons but also the discordance between the winners of subsets of three candidates are also taken into account, we come to the conclusion 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. For example, it satisfies several improved manipulation-proof properties. Since the $3$-wise Kemeny problem is NP-hard, our results also provide some of the first useful space reduction techniques by determining the relative orders of pairs of alternatives. Our works suggest similar interesting properties of higher setwise Kemeny voting schemes which justify and compensate for the more expensive computational cost than the classical Kemeny scheme.
• Abstract（参考訳）: 重要なケメニー問題は、ケメニー投票規則に関する選挙の中央値のコンセンサスランキングを計算し、生物学や計算社会選択における重要な応用を認め、最近ギルバートらによって興味深いセットワイズアプローチによって一般化された。 アル まず, 古典的ケメニー中央値問題に対して, ベツラーらによる非アニミティー特性の最適量的拡張と, 3/4$-majority rule が確立された。 Moreover, by elaborating an exhaustive list of quantified axiomatic properties (such as the Condorcet and Smith criteria, the $5/6$-majority rule, etc.) of the $3$-wise Kemeny rule where not only pairwise comparisons but also the discordance between the winners of subsets of three candidates are also taken into account, we come to the conclusion 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. 例えば、いくつかの改良された操作耐性特性を満たす。 3$-wise Kemeny 問題は NP-hard であるため、この結果は対の相対順序を決定することで、最初の有用な空間縮小手法も提供する。 我々の研究は、古典的なケメニー方式よりも高価な計算コストを正当化し補償する、より集合的なケメニー投票方式の興味深い特性を示唆している。

関連論文リスト

• 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)
• Space reduction techniques for the $3$-wise Kemeny problem [0.0]
  ケメニーの法則は、計算社会選択と生物学に様々な重要な応用がある最も研究されよく知られた投票方式の1つである。 我々は、ミロシュとハメルがケメニーの統治のために得たような、大位数定理のいくつかの一般化を確立する。 我々は、ベッツラーらによるケメニーの法則の有名な3/4ドルのマジョリティルールが、一般的には5ドル以上の選択肢のない選挙に対してのみ有効であることを示す。
  論文  参考訳（メタデータ） (2023-04-29T01:21:23Z)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [13.207754600697138]
  条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。 我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
  論文  参考訳（メタデータ） (2022-02-03T16:15:54Z)
• 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)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。 我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。 一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
  論文  参考訳（メタデータ） (2021-04-19T08:26:40Z)
• Fair Set Selection: Meritocracy and Social Welfare [6.205308371824033]
  候補集団から一組の個人を選定する問題を実用的最大化問題として定式化する。 意思決定者の視点からは、期待されるユーティリティを最大化する選択ポリシーを見つけることと等価である。 我々の枠組みは、選択政策に関して個人が期待する限界貢献(EMC)の概念を、長所主義からの逸脱の尺度として導く。
  論文  参考訳（メタデータ） (2021-02-23T20:36:36Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)

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

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