論文の概要: A Linear Theory of Multi-Winner Voting

• arxiv url: http://arxiv.org/abs/2503.03082v1
• Date: Wed, 05 Mar 2025 00:44:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-06 15:50:44.124537
• Title: A Linear Theory of Multi-Winner Voting
• Title（参考訳）: マルチウィンナー投票の線形理論
• Authors: Lirong Xia,
• Abstract要約: 本稿では,複数投票ルールと比例公理を統一する一般線形フレームワークを提案する。 統一表現(JR)、拡張JR(EJR)、強化された変種(PJR+、EJR+)などの重要な比例公理もこの線形構造に収まる。 我々の手法は、Thiele法や順序付き平均規則を含む様々なルールのクラスに対して、ほぼ最適に保証される。
• 参考スコア（独自算出の注目度）: 31.513684347195287
• License:
• Abstract: We introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their sequential variants, and approval-based committee scoring rules-are linear. Similarly, key proportionality axioms such as Justified Representation (JR), Extended JR (EJR), and their strengthened variants (PJR+, EJR+), along with core stability, can fit within this linear structure as well. Leveraging PAC learning theory, we establish general and novel upper bounds on the sample complexity of learning linear mappings. Our approach yields near-optimal guarantees for diverse classes of rules, including Thiele methods and ordered weighted average rules, and can be applied to analyze the sample complexity of learning proportionality axioms such as approximate core stability. Furthermore, the linear structure allows us to leverage prior work to extend our analysis beyond worst-case scenarios to study the likelihood of various properties of linear rules and axioms. We introduce a broad class of distributions that extend Impartial Culture for approval preferences, and show that under these distributions, with high probability, any Thiele method is resolute, CORE is non-empty, and any Thiele method satisfies CORE, among other observations on the likelihood of commonly-studied properties in social choice. We believe that this linear theory offers a new perspective and powerful new tools for designing and analyzing multi-winner rules in modern social choice applications.
• Abstract（参考訳）: 本稿では,複数投票ルールと比例公理を統一した一般線形フレームワークを導入し,Thiele法を含む多くの著名な複数投票ルール,それらの逐次変種,および承認ベースの委員会スコアリングルールが線形であることを示す。 同様に、Justified Representation(JR)やExtended JR(EJR)などの重要な比例公理や、その強化された変種(PJR+、EJR+)も、コア安定性とともに、この線形構造にも収まる。 PAC学習理論を応用し、線形写像の学習の複雑さに関する一般および新奇な上限を確立する。 提案手法は,Thiele法や順序付き重み付き平均規則を含む多種多様なルールに対して,ほぼ最適に保証され,近似コア安定性などの学習比例公理のサンプル複雑性を解析できる。 さらに、線形構造は、事前の作業を活用して、最悪のシナリオを超えて分析を拡張し、線形規則や公理の様々な性質の可能性を研究できる。 承認の選好のためにImpartial Cultureを拡張した分布の幅広いクラスを導入し、これらの分布の下では、高い確率で、Thiele法は絶対的であり、COREは非空であり、Thiele法はCOREを満足していることを示す。 この線形理論は、現代社会選択アプリケーションにおけるマルチウィンナールールの設計と分析のための、新しい視点と強力な新しいツールを提供すると信じている。

関連論文リスト

• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。 学習シナリオにおける同値性に基づく単一のフレームワークを提案する。 我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
  論文  参考訳（メタデータ） (2024-05-09T12:52:22Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  本稿では, 学習モデルを用いて評価したヘッセン行列をトレーニングセットで評価した共分散行列の固有解析と, 深層学習モデルで評価したヘッセン行列を組み合わせた新しい手法を提案する。 本手法は複雑なパターンと関係を抽出し,分類性能を向上する。
  論文  参考訳（メタデータ） (2024-02-14T16:10:42Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption [9.620832983703863]
  線形分類モデルであるQLDSを導入し、低密度分離仮定を2次マージンで実装する。 提案アルゴリズムの特定のケースは、教師付きケースにおける最小二乗支援ベクトルマシン、完全に教師なしシステマにおけるスペクトルクラスタリング、および半教師付きグラフベースアプローチのクラスであることを示す。
  論文  参考訳（メタデータ） (2023-10-20T11:46:12Z)
• Dynamic selection of p-norm in linear adaptive filtering via online kernel-based reinforcement learning [8.319127681936815]
  本研究は, 線形適応フィルタリングにおいて, 最適p-ノルムが外れ値と競合する問題に対して, 動的に選択する問題に対処する。 オンラインおよびデータ駆動型フレームワークはカーネルベース強化学習(KBRL)によって設計される
  論文  参考訳（メタデータ） (2022-10-20T14:49:39Z)
• Revisiting GANs by Best-Response Constraint: Perspective, Methodology, and Application [49.66088514485446]
  ベストレスポンス制約(Best-Response Constraint、BRC)は、ジェネレータのディスクリミネータへの依存性を明示的に定式化する一般的な学習フレームワークである。 モチベーションや定式化の相違があっても, フレキシブルBRC法により, 様々なGANが一様に改善できることが示される。
  論文  参考訳（メタデータ） (2022-05-20T12:42:41Z)
• Rule Generation for Classification: Scalability, Interpretability, and Fairness [0.0]
  制約付き分類のためのルールベースの新しい最適化手法を提案する。 ルールにコスト係数を割り当て、追加制約を導入することにより、解釈可能性と公正性に対処する。 提案手法は,一方の局所的解釈可能性と他方の正当性,他方の精度との間に良好な妥協関係を示す。
  論文  参考訳（メタデータ） (2021-04-21T20:31:28Z)
• MCMH: Learning Multi-Chain Multi-Hop Rules for Knowledge Graph Reasoning [46.68583750992613]
  多重ホップ規則の一般化形式を考えると、各規則は関係連鎖の集合である。 そこで本研究では,まず,少数の関係連鎖をルールとして選択し,対象関係の信頼度を評価する2段階のアプローチを提案する。 その結果,MCMH(Multi-chain multi-hop)ルールは,標準の単一チェーン方式よりも優れた結果が得られた。
  論文  参考訳（メタデータ） (2020-10-05T01:32:20Z)
• On Connections between Regularizations for Improving DNN Robustness [67.28077776415724]
  本稿では,ディープニューラルネットワーク(DNN)の対角的ロバスト性を改善するために最近提案された正規化条件を解析する。 入力勾配正則化,ジャコビアン正則化,曲率正則化,クロスリプシッツ関数など,いくつかの有効な方法間の接続性について検討する。
  論文  参考訳（メタデータ） (2020-07-04T23:43:32Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  まず、自動妥当性決定(ARD)について検討し、スパースモデルを実現するために、追加の正規化やしきい値設定の必要性を解析的に実証する。 次に、正規化ベースとしきい値ベースという2つの手法のクラスについて論じる。
  論文  参考訳（メタデータ） (2020-05-18T14:08:49Z)

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

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