Not in My Backyard! Temporal Voting Over Public Chores

• URL: http://arxiv.org/abs/2508.08810v1
• Date: Tue, 12 Aug 2025 10:06:56 GMT
• Title: Not in My Backyard! Temporal Voting Over Public Chores
• Authors: Edith Elkind, Tzeh Yuan Neoh, Nicholas Teh,
• Abstract summary: We study a temporal voting model where voters have dynamic preferences over a set of public chores.<n>We investigate the computational complexity of optimizing utilitarian and egalitarian welfare.
• Score: 21.36300710262896
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a temporal voting model where voters have dynamic preferences over a set of public chores -- projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.

Related papers

• Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains [67.71020482405343]
  We study how to design algorithms that can leverage additional information in the form of rating gap.<n>We present new algorithms that can achieve faster statistical rates than DPO in presence of accurate rating gap information.
  arXiv  Detail & Related papers  (2026-01-31T08:38:21Z)
• From Individual to Multi-Agent Algorithmic Recourse: Minimizing the Welfare Gap via Capacitated Bipartite Matching [9.37591403853433]
  We introduce a novel framework for multi-agent algorithmic recourse that accounts for multiple recourse seekers and recourse providers.<n>Our framework enables the many-to-many algorithmic recourse to achieve near-optimal welfare with minimum modification in system settings.
  arXiv  Detail & Related papers  (2025-08-14T21:04:24Z)
• Temporal Elections: Welfare, Strategyproofness, and Proportionality [21.36300710262896]
  We investigate a model of sequential decision-making where a single alternative is chosen at each round.<n>We focus on two objectives -- utilitarian welfare (Util) and egalitarian welfare (Egal)<n>We find that maximizing Util is easy, but the corresponding decision problem for Egal is NP-complete even in restricted cases.
  arXiv  Detail & Related papers  (2024-08-24T17:52:26Z)
• Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime [59.27851754647913]
  Predictive optimization is the precise modeling of many real-world applications, including energy cost-aware scheduling and budget allocation on advertising. We develop a modular framework to benchmark 11 existing PtO/PnO methods on 8 problems, including a new industrial dataset for advertising. Our study shows that PnO approaches are better than PtO on 7 out of 8 benchmarks, but there is no silver bullet found for the specific design choices of PnO.
  arXiv  Detail & Related papers  (2023-11-13T13:19:34Z)
• Causal Fairness for Outcome Control [68.12191782657437]
  We study a specific decision-making task called outcome control in which an automated system aims to optimize an outcome variable $Y$ while being fair and equitable. In this paper, we first analyze through causal lenses the notion of benefit, which captures how much a specific individual would benefit from a positive decision. We then note that the benefit itself may be influenced by the protected attribute, and propose causal tools which can be used to analyze this.
  arXiv  Detail & Related papers  (2023-06-08T09:31:18Z)
• Mathematical Framework for Online Social Media Auditing [5.384630221560811]
  Social media platforms (SMPs) leverage algorithmic filtering (AF) as a means of selecting the content that constitutes a user's feed with the aim of maximizing their rewards. Selectively choosing the contents to be shown on the user's feed may yield a certain extent of influence, either minor or major, on the user's decision-making. We mathematically formalize this framework and utilize it to construct a data-driven statistical auditing procedure to regulate AF from deflecting users' beliefs over time, along with sample complexity guarantees.
  arXiv  Detail & Related papers  (2022-09-12T19:04:14Z)
• Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
  We develop a new framework for off-policy evaluation with a textitpolicy-dependent linear optimization response. We construct unbiased estimators for the policy-dependent estimand by a perturbation method. We provide a general algorithm for optimizing causal interventions.
  arXiv  Detail & Related papers  (2022-02-25T20:25:37Z)
• Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making [21.152377319502705]
  We present an alternative framework for designing equitable algorithms. In our approach, one first elicits stakeholder preferences over the space of possible decisions. We then optimize over the space of decision policies, making trade-offs in a way that maximizes the elicited utility.
  arXiv  Detail & Related papers  (2021-09-18T00:30:43Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. We show that any confidence-adjusted index algorithm is minimax optimal, whether it be optimistic, pessimistic or neutral. We introduce a new weighted-minimax criterion that considers the inherent difficulty of optimal value prediction.
  arXiv  Detail & Related papers  (2021-04-06T05:23:20Z)
• Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
  Algorithmic decision-making in societal contexts can be framed as optimization under bandit feedback. Recent lawsuits accuse companies that deploy algorithmic pricing practices of price gouging. We introduce the well-studied fairness notion of envy-freeness within the context of convex optimization.
  arXiv  Detail & Related papers  (2021-03-16T19:06:28Z)
• A black-box adversarial attack for poisoning clustering [78.19784577498031]
  We propose a black-box adversarial attack for crafting adversarial samples to test the robustness of clustering algorithms. We show that our attacks are transferable even against supervised algorithms such as SVMs, random forests, and neural networks.
  arXiv  Detail & Related papers  (2020-09-09T18:19:31Z)
• 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.