Related papers: Submodular Participatory Budgeting

Submodular Participatory Budgeting

URL: http://arxiv.org/abs/2406.13586v1
Date: Wed, 19 Jun 2024 14:22:54 GMT
Title: Submodular Participatory Budgeting
Authors: Jing Yuan, Shaojie Tang,
Abstract summary: We propose a submodular participatory budgeting problem, assuming that the utility function of each individual is a monotone and submodular function over funded projects. We examine three preference elicitation methods, including emphranking-by-marginal-values, emphranking-by-values and emphthreshold approval votes, and analyze their performances in terms of distortion.
Score: 11.528995186765751
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Participatory budgeting refers to the practice of allocating public resources by collecting and aggregating individual preferences. Most existing studies in this field often assume an additive utility function, where each individual holds a private utility for each candidate project, and the total utility of a set of funded projects is simply the sum of the utilities of all projects. We argue that this assumption does not always hold in reality. For example, building two playgrounds in the same neighborhood does not necessarily lead to twice the utility of building a single playground. To address this, we extend the existing study by proposing a submodular participatory budgeting problem, assuming that the utility function of each individual is a monotone and submodular function over funded projects. We propose and examine three preference elicitation methods, including \emph{ranking-by-marginal-values}, \emph{ranking-by-values} and \emph{threshold approval votes}, and analyze their performances in terms of distortion. Notably, if the utility function is addicative, our aggregation rule designed for threshold approval votes achieves a better distortion than the state-of-the-art approach.

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)
Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
arXiv Detail & Related papers (2024-05-31T19:26:05Z)
Revisiting Proposal-based Object Detection [59.97295544455179]
We revisit the pipeline for detecting objects in images with proposals. We solve a simple problem where we regress to the area of intersection between proposal and ground truth. Our revisited approach comes with minimal changes to the detection pipeline and can be plugged into any existing method.
arXiv Detail & Related papers (2023-11-30T12:40:23Z)
Non-monotone Sequential Submodular Maximization [13.619980548779687]
We aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted assortment of $k$ is maximized. The results of this research have implications in various fields, including recommendation systems and optimization.
arXiv Detail & Related papers (2023-08-16T19:32:29Z)
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)
Dense Hybrid Proposal Modulation for Lane Detection [72.49084826234363]
We present a dense hybrid proposal modulation (DHPM) method for lane detection. We densely modulate all proposals to generate topologically and spatially high-quality lane predictions. Our DHPM achieves very competitive performances on four popular datasets.
arXiv Detail & Related papers (2023-04-28T14:31:11Z)
Quantization for decentralized learning under subspace constraints [61.59416703323886]
We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
arXiv Detail & Related papers (2022-09-16T09:38:38Z)
Participatory Budgeting with Project Groups [27.39571821668551]
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.
arXiv Detail & Related papers (2020-12-09T18:23:04Z)
Generalized Inverse Planning: Learning Lifted non-Markovian Utility for Generalizable Task Representation [83.55414555337154]
In this work, we study learning such utility from human demonstrations. We propose a new quest, Generalized Inverse Planning, for utility learning in this domain. We outline a computational framework, Maximum Entropy Inverse Planning (MEIP), that learns non-Markovian utility and associated concepts in a generative manner.
arXiv Detail & Related papers (2020-11-12T21:06:26Z)
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.