論文の概要: The Price of Proportional Representation in Temporal Voting

• arxiv url: http://arxiv.org/abs/2605.11157v1
• Date: Mon, 11 May 2026 19:05:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:56.375909
• Title: The Price of Proportional Representation in Temporal Voting
• Title（参考訳）: 時間投票における比例表現の価格
• Abstract要約: 本研究では時間的投票モデルにおける比例表現について検討する。 時間的設定における比例代表の付与は、有権者数やラウンド数が増えるにつれて、成長するが、サブリニアな、福祉損失を引き起こす可能性があることを示す。
• 参考スコア（独自算出の注目度）: 11.208733293527795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon. Prior work has extensively investigated how proportional representation axioms from multiwinner voting (e.g., justified representation (JR) and its variants) can be adapted, satisfied, and verified in this setting. However, much less is understood about their interaction with social welfare. In this work, we quantify the efficiency cost of enforcing proportionality. We formalize the welfare-proportionality tension via the worst-case ratio between the maximum achievable utilitarian welfare and the maximum welfare attainable subject to a proportionality axiom. We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases. We further identify a clean separation among axioms: for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically, whereas for stronger axioms this conflict persists even with many rounds. Moreover, we prove that welfare maximization under each axiom is NP-complete and APX-hard, even under static preferences and bounded-degree approvals, and provide fixed-parameter algorithms under several natural structural parameters.
• Abstract（参考訳）: 本研究では時間的投票モデルにおける比例表現について検討する。 先行研究は、マルチウィンナー投票による比例表現公理(例えば、正当化表現(JR)とその変種)をどのように適応し、満足し、この設定で検証するかを広く研究してきた。 しかし、社会福祉との相互作用についてはあまり理解されていない。 本研究では,比例率を強制する効率コストを定量化する。 我々は,最大実用的福祉と最大福祉が比例公理の対象となる場合の最悪のケース比を通じて,福祉・地域間の緊張関係を定式化する。 時間的設定における比例代表の付与は、有権者数やラウンド数が増えるにつれて、成長するが、サブリニアな、福祉損失を引き起こす可能性があることを示す。 また,JRでは時間的水平線が増大し,漸近的に消滅するのに対して,強い公理では多くのラウンドでも継続する。 さらに、各公理の下での福祉最大化は、静的な選好や有界な承認の下でもNP完全かつAPXハードであることが証明され、いくつかの自然な構造パラメータの下で固定パラメータアルゴリズムが提供される。

関連論文リスト

• Geometry of Relaxed Fair Regression: A Unified Framework for Aware and Unaware Settings [0.0]
  緩和された公正性制約の下で正確な予測を得るための原則的手法は、ほとんど失われている。 本フレームワークは,エフェックウェアとエフェナウェアの両方を統一し,最適なトランスポートマップを用いて最適な予測関数を特徴付ける。 これらの理論的特徴に基づいて、実世界のベンチマーク上での最先端のベースラインの実装、計算効率、一貫した整合性、あるいは性能の向上を簡易に行うアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-27T09:45:16Z)
• Fixed Points and Stochastic Meritocracies: A Long-Term Perspective [11.2610829816461]
  本研究は,既成的選択によって引き起こされるフィードバックループの文脈におけるグループフェアネスを,それ自身が付加的な優位性を与えるプログラムに検証する。 プログラムの利点(または、それに入らないことの害)が完全に対称である場合、両集団間の格差が最終的に解消されることが示される。 また、完全に対称な初期条件でさえも、大きな相違が生じる可能性があることも見出した。
  論文  参考訳（メタデータ） (2025-10-08T19:23:57Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。 我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。 本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
  論文  参考訳（メタデータ） (2024-12-20T19:58:55Z)
• Fairness-Accuracy Trade-Offs: A Causal Perspective [58.06306331390586]
  我々は、初めて因果レンズから公正性と正確性の間の張力を分析する。 因果的制約を強制することは、しばしば人口集団間の格差を減少させることを示す。 因果制約付きフェアラーニングのための新しいニューラルアプローチを導入する。
  論文  参考訳（メタデータ） (2024-05-24T11:19:52Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• The Leximin Approach for a Sequence of Collective Decisions [6.3734441349747035]
  ラウンドロビン,最大ナッシュ福祉,レキシミンの3つのメカニズムの公正性を解析した。 オフライン環境では、3つのメカニズムが比例的あるいは近似的な結果を見つからないことを示す。 オンライン環境では、比例性や緩和を保証することは不可能であることを示す。
  論文  参考訳（メタデータ） (2023-05-29T11:28:27Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。 決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。 モデルの拡張が2つあることを示す。
  論文  参考訳（メタデータ） (2023-01-11T07:30:35Z)
• Achieving Proportionality up to the Maximin Item with Indivisible Goods [14.002498730240902]
  我々は、分割不可能な商品をかなり配置する問題を研究し、古典的公平性の概念である比例性に焦点をあてる。 最近の研究で、比例性(PROPx)の近似バージョンでさえ、小さなインスタンスでも達成できないことが証明されている。 最大5つのエージェントが付加価値を持つ場合において、この概念を満たすアロケーションにどのように到達するかを示す。
  論文  参考訳（メタデータ） (2020-09-20T19:21:19Z)
• Fair Influence Maximization: A Welfare Optimization Approach [34.39574750992602]
  我々は、公正な影響アルゴリズムが満たすべき特性を原則的に特徴づける。 この枠組みの下では、公平性と効率性のトレードオフは単一の設計逆転パラメータによって制御できる。 我々の枠組みは、特殊ケースのレキシミンと比例フェアネスを包含する。
  論文  参考訳（メタデータ） (2020-06-14T14:08:10Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)

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

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