論文の概要: 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（参考訳）: 時間投票における比例表現の価格
• Authors: Nicholas Teh,
• 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ハードであることが証明され、いくつかの自然な構造パラメータの下で固定パラメータアルゴリズムが提供される。

関連論文リスト

• Fixed Points and Stochastic Meritocracies: A Long-Term Perspective [11.2610829816461]
  本研究は,既成的選択によって引き起こされるフィードバックループの文脈におけるグループフェアネスを,それ自身が付加的な優位性を与えるプログラムに検証する。 プログラムの利点(または、それに入らないことの害)が完全に対称である場合、両集団間の格差が最終的に解消されることが示される。 また、完全に対称な初期条件でさえも、大きな相違が生じる可能性があることも見出した。
  論文  参考訳（メタデータ） (2025-10-08T19:23:57Z)
• Fairness-Accuracy Trade-Offs: A Causal Perspective [58.06306331390586]
  我々は、初めて因果レンズから公正性と正確性の間の張力を分析する。 因果的制約を強制することは、しばしば人口集団間の格差を減少させることを示す。 因果制約付きフェアラーニングのための新しいニューラルアプローチを導入する。
  論文  参考訳（メタデータ） (2024-05-24T11:19:52Z)
• 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)

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

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