論文の概要: Maxmin Participatory Budgeting

• arxiv url: http://arxiv.org/abs/2204.13923v1
• Date: Fri, 29 Apr 2022 07:45:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-02 15:11:51.062726
• Title: Maxmin Participatory Budgeting
• Title（参考訳）: マックスミン参加予算
• Authors: Gogulapati Sreedurga, Mayank Ratan Bhardwaj, Y. Narahari
• Abstract要約: PB(Participatory Budgeting, Participatory Budgeting)は、プロジェクトに対する有権者の選好に基づいて、限られた予算を一連のプロジェクトに分けられる人気投票方法である。 PBの重要な目的である平等主義は、未分化PBの文脈ではあまり注目されていない。 本稿は、自然平等主義的ルール、最大参加予算(MPB)の詳細な研究を通して、このギャップに対処する。
• 参考スコア（独自算出の注目度）: 1.1602089225841632
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Participatory Budgeting (PB) is a popular voting method by which a limited budget is divided among a set of projects, based on the preferences of voters over the projects. PB is broadly categorised as divisible PB (if the projects are fractionally implementable) and indivisible PB (if the projects are atomic). Egalitarianism, an important objective in PB, has not received much attention in the context of indivisible PB. This paper addresses this gap through a detailed study of a natural egalitarian rule, Maxmin Participatory Budgeting (MPB), in the context of indivisible PB. Our study is in two parts: (1) computational (2) axiomatic. In the first part, we prove that MPB is computationally hard and give pseudo-polynomial time and polynomial-time algorithms when parameterized by certain well-motivated parameters. We propose an algorithm that achieves for MPB, additive approximation guarantees for restricted spaces of instances and empirically show that our algorithm in fact gives exact optimal solutions on real-world PB datasets. We also establish an upper bound on the approximation ratio achievable for MPB by the family of exhaustive strategy-proof PB algorithms. In the second part, we undertake an axiomatic study of the MPB rule by generalizing known axioms in the literature. Our study leads to the proposal of a new axiom, maximal coverage, which captures fairness aspects. We prove that MPB satisfies maximal coverage.
• Abstract（参考訳）: PB(Participatory Budgeting, Participatory Budgeting)は、プロジェクトに対する有権者の選好に基づいて、限られた予算を一連のプロジェクトに分けられる人気投票方法である。 PBは、分割可能なPB(プロジェクトが少数実装可能であれば)と分割可能なPB(プロジェクトがアトミックであれば)に分類される。 PBの重要な目的である平等主義は、未分化PBの文脈ではあまり注目されていない。 本稿では,このギャップを,不可分PB(Indivisionible PB)の文脈において,自然平等主義的法則(Maxmin Participatory Budgeting,MPB)の詳細な研究を通じて解決する。 本研究は,(1)計算(2)公理の2つの部分からなる。 第一部では, mpb が計算が困難であることを証明し, パラメータによってパラメータ化される場合, 擬似多項時間と多項式時間アルゴリズムを与える。 本稿では,MPBに対して,インスタンスの制限された空間に対する加法近似を保証するアルゴリズムを提案し,実世界のPBデータセットに対して,我々のアルゴリズムが正確な最適解を与えることを実証的に示す。 また,総括的戦略耐性PBアルゴリズムにより,MPBに対して達成可能な近似比の上限を確立した。 第2部では,文献上の既知の公理を一般化し,mpb規則の公理的研究を行う。 本研究は, 公平性を考慮した新しい公理, 最大カバレッジの提案につながる。 mpbが最大カバレッジを満たすことを証明します。

関連論文リスト

• Exploring Welfare Maximization and Fairness in Participatory Budgeting [1.6317061277457001]
  PB(Participatory budgeting)は、予算と呼ばれる様々なリソースを、これらのプロジェクトに対する個人の嗜好を集約して配布する投票パラダイムである。 この博士論文は、様々なPBモデルに対する福祉関連および公正関連目的について研究している。
  論文  参考訳（メタデータ） (2024-10-26T10:51:22Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Indivisible Participatory Budgeting under Weak Rankings [0.6853165736531939]
  参加型予算設定(PB)は、社会的選択設定に広く適用できるため、近年で注目されている。 本稿では,分類の弱いPBの分類法を提案し,そのアルゴリズム的および公理的問題について検討する。 本論文は,これらの規則の実践的魅力,計算複雑性,公理的遵守のトレードオフを明らかにするのに役立つ。
  論文  参考訳（メタデータ） (2022-07-16T16:46:12Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• What Should We Optimize in Participatory Budgeting? An Experimental Study [28.76045220764571]
  PB(Participatory Budgeting)は、有権者が共通の予算を割り当てる方法を決定するプロセスである。 最新のPBアグリゲーション技術はユーザの期待と大きく異なることを示す。 非専門家が望ましくないと考えるものと、PB文脈における「公正」の概念をどのように知覚するかの間には、いくつかの相違点が存在する。
  論文  参考訳（メタデータ） (2021-11-14T10:46:03Z)
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits [8.136957953239254]
  本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。 各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。 最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-09-20T21:40:12Z)
• Participatory Budgeting with Project Groups [27.39571821668551]
  参加予算(PB)の標準承認に基づくモデルの一般化について検討する。 この問題は一般に難解であり,いくつかの特殊な場合に対して効率的な厳密アルゴリズムを記述する。 私たちの結果は、例えば、自治体は、テーマ的に、地理的に包括的であるより豊かなPBプロセスを保持することができます。
  論文  参考訳（メタデータ） (2020-12-09T18:23:04Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)

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

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