論文の概要: Temporal Elections: Welfare, Strategyproofness, and Proportionality

• arxiv url: http://arxiv.org/abs/2408.13637v2
• Date: Fri, 20 Dec 2024 13:29:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 16:20:15.526846
• Title: Temporal Elections: Welfare, Strategyproofness, and Proportionality
• Title（参考訳）: 臨時選挙:福祉・防衛・比例
• Authors: Edith Elkind, Tzeh Yuan Neoh, Nicholas Teh,
• Abstract要約: 各ラウンドで1つの選択肢が選択されるシーケンシャルな意思決定モデルについて検討する。 実用的福祉(Util)と平等的福祉(Egal)の2つの目的に焦点を当てる。 Util の最大化は簡単だが、Egal の対応する決定問題は制限された場合においてもNP完全である。
• 参考スコア（独自算出の注目度）: 21.36300710262896
• License:
• Abstract: We investigate a model of sequential decision-making where a single alternative is chosen at each round. We focus on two objectives -- utilitarian welfare (Util) and egalitarian welfare (Egal) -- and consider the computational complexity of maximizing these objectives, as well as their compatibility with strategyproofness and proportionality. We observe that maximizing Util is easy, but the corresponding decision problem for Egal is NP-complete even in restricted cases. We complement this hardness result for Egal with parameterized complexity analysis and an approximation algorithm. Additionally, we show that, while a mechanism that outputs an outcome that maximizes Util is strategyproof, all deterministic mechanisms for computing outcomes that maximize Egal fail a very weak variant of strategyproofness, called non-obvious manipulability (NOM). However, we show that when agents have non-empty approval sets at each timestep, choosing an Egal-maximizing outcome while breaking ties lexicographically satisfies NOM. Regarding proportionality, we prove that a proportional (PROP) outcome can be computed efficiently, but finding an outcome that maximizes Util while guaranteeing PROP is NP-hard. We also derive upper and lower bounds on the (strong) price of proportionality with respect to Util and Egal. Some of our results extend to $p$-mean welfare measures other than Egal and Util.
• Abstract（参考訳）: 各ラウンドで1つの選択肢が選択されるシーケンシャルな意思決定モデルについて検討する。 実用的福祉(Util)と平等的福祉(Egal)の2つの目的に焦点をあて、これらの目的を最大化することの計算複雑性と、戦略の保護性と比例性との整合性を考察する。 我々は、Util の最大化は容易であるが、Egal の対応する決定問題は制限された場合においてもNP完全であると考えている。 パラメータ化複雑性解析と近似アルゴリズムでEgalのこの硬さを補完する。 さらに、Util を最大化する結果を生成するメカニズムは戦略的だが、Egal を最大化する計算結果に対する決定論的メカニズムは、NOM (Non-obvious Manipulability) と呼ばれる非常に弱い戦略的変形に失敗することを示した。 しかし, エージェントが各時点に空でない承認セットを持つ場合, 関係を破ってEgal-maximizing結果を選択するとNOMを満足することがわかった。 比例性については、比例(PROP)の結果を効率的に計算できることが証明されているが、PROPを保証しながらUtilを最大化する結果はNPハードである。 我々はまた、Util と Egal に関する比例価格の上下限を導出する。 結果のいくつかは、EgalやUtil以外の平均的福祉対策にも及んでいる。

関連論文リスト

• Anytime-Constrained Reinforcement Learning [6.981971551979697]
  制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。 累積コストを付加した最適決定主義的政策が存在することを示す。 非自明な概略的ポリシーの計算は一般にNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-09T16:51:26Z)
• Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
  不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。 簡便な解と理論的に最適な解との決定論的関係を導出する。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory [30.061707627742766]
  適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。 本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
  論文  参考訳（メタデータ） (2023-04-24T21:51:58Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Tightly Robust Optimization via Empirical Domain Reduction [22.63829081634384]
  提案手法は,解が良好な目的値を持つようなスケールを決定するアルゴリズムである。 いくつかの規則性条件下では、我々のアルゴリズムで得られるスケールは$O(sqrtn)$、標準アプローチで得られるスケールは$O(sqrtd/n)$である。
  論文  参考訳（メタデータ） (2020-02-29T12:24:56Z)

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

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