Participatory Budgeting with Project Groups
- URL: http://arxiv.org/abs/2012.05213v1
- Date: Wed, 9 Dec 2020 18:23:04 GMT
- Title: Participatory Budgeting with Project Groups
- Authors: Pallavi Jain, Krzysztof Sornat, Nimrod Talmon, Meirav Zehavi
- Abstract summary: We study a generalization of the standard approval-based model of participatory budgeting (PB)
We show that the problem is generally intractable and describe efficient exact algorithms for several special cases.
Our results could allow, e.g., municipalities to hold richer PB processes that are thematically and geographically inclusive.
- Score: 27.39571821668551
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a generalization of the standard approval-based model of
participatory budgeting (PB), in which voters are providing approval ballots
over a set of predefined projects and -- in addition to a global budget limit,
there are several groupings of the projects, each group with its own budget
limit. We study the computational complexity of identifying project bundles
that maximize voter satisfaction while respecting all budget limits. We show
that the problem is generally intractable and describe efficient exact
algorithms for several special cases, including instances with only few groups
and instances where the group structure is close to be hierarchical, as well as
efficient approximation algorithms. Our results could allow, e.g.,
municipalities to hold richer PB processes that are thematically and
geographically inclusive.
Related papers
- Exploring Welfare Maximization and Fairness in Participatory Budgeting [1.6317061277457001]
Participatory budgeting (PB) is a voting paradigm for distributing a divisible resource, usually called a budget, among a set of projects by aggregating the preferences of individuals over these projects.
This PhD dissertation studies the welfare-related and fairness-related objectives for different PB models.
arXiv Detail & Related papers (2024-10-26T10:51:22Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball.
We propose a new algorithmic framework, ProjUnit, for private mean estimation.
Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
arXiv Detail & Related papers (2023-06-07T14:07:35Z) - Participatory Budgeting With Multiple Degrees of Projects And Ranged
Approval Votes [0.0]
In an indivisible participatory budgeting (PB) framework, we have a limited budget that is to be distributed among a set of projects.
Each voter approves a range of costs for each project, by giving an upper and lower bound on the cost that she thinks the project deserves.
The outcome of a PB rule selects a subset of projects and also specifies their corresponding costs.
arXiv Detail & Related papers (2023-05-18T13:39:56Z) - Beyond Submodularity: A Unified Framework of Randomized Set Selection
with Group Fairness Constraints [19.29174615532181]
We introduce a unified framework for randomized subset selection that incorporates group fairness constraints.
Our problem involves a global utility function and a set of group utility functions for each group.
Our aim is to generate a distribution across feasible subsets, specifying the selection probability of each feasible set.
arXiv Detail & Related papers (2023-04-13T15:02:37Z) - Maxmin Participatory Budgeting [1.1602089225841632]
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.
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)
arXiv Detail & Related papers (2022-04-29T07:45:44Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework.
It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions.
In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
arXiv Detail & Related papers (2022-01-18T11:16:40Z) - Sample Complexity of Tree Search Configuration: Cutting Planes and
Beyond [98.92725321081994]
State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm.
We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
arXiv Detail & Related papers (2021-06-08T00:57:59Z) - Participatory Budgeting with Donations and Diversity Constraints [31.521771465733057]
Participatory budgeting (PB) is a democratic process where citizens jointly decide on how to allocate public funds to indivisible projects.
This paper focuses on PB processes where citizens may give additional money to projects they want to see funded.
We introduce a formal framework for this kind of PB with donations. Our framework also allows for diversity constraints, meaning that each project belongs to one or more types, and there are lower and upper bounds on the number of projects of the same type that can be funded.
arXiv Detail & Related papers (2021-04-30T15:48:25Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
We give efficient differentially private algorithms for basic clustering problems.
Our results imply an improved algorithm for the Sample and Aggregate privacy framework.
One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
arXiv Detail & Related papers (2020-08-18T16:22:06Z) - Planning in Markov Decision Processes with Gap-Dependent Sample
Complexity [48.98199700043158]
We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process.
We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability.
arXiv Detail & Related papers (2020-06-10T15:05:51Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions.
We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
arXiv Detail & Related papers (2020-02-12T18:59:18Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.