TLDR: This research introduces a temporal voting model where citizens express disapproval for “public chores” (community projects with individual costs, like noise from festivals). It finds that minimizing total disutility (MIN-SUM) is easy, but minimizing maximum individual disutility (MIN-MAX) is computationally hard. While individuals can’t manipulate MIN-SUM, groups can (though it’s hard to find a manipulation). MIN-MAX is not strategyproof for individuals, but manipulation is also hard to find. The paper also explores the cost of fairness and challenges with other fairness concepts like proportionality and equitability in this “Not in My Backyard” context.
Local governments often face a dilemma when planning community projects: initiatives designed to benefit the broader society can sometimes impose significant burdens on nearby residents. This tension, famously known as the “Not in My Backyard” (NIMBY) phenomenon, highlights the challenge of balancing collective good with individual costs. A new research paper, “Not in My Backyard! Temporal Voting Over Public Chores,” delves into this complex issue through the lens of temporal voting, where decisions are made sequentially over time.
The paper, authored by Edith Elkind from Northwestern University, Tzeh Yuan Neoh from Harvard University, and Nicholas Teh from the University of Oxford, introduces a novel variant of the temporal voting model. Unlike traditional models where voters express approval for candidates or projects, this research focuses on “disapproval preferences.” This means voters indicate which projects they object to, a highly relevant perspective in NIMBY scenarios where residents might be indifferent to most projects but strongly oppose those that directly impact their quality of life due to factors like noise, crowding, or traffic.
Optimizing for Welfare: Efficiency vs. Fairness
The researchers investigate two primary welfare objectives: utilitarian and egalitarian. In their context, these translate to:
- MIN-SUM: Minimizing the total sum of disutilities across all agents. This aims for overall efficiency.
- MIN-MAX: Minimizing the maximum disutility experienced by any single agent. This prioritizes fairness, ensuring no one is disproportionately burdened.
Their findings reveal a significant computational difference between these two objectives. Optimizing MIN-SUM is surprisingly straightforward and can be achieved efficiently using a greedy algorithm. However, minimizing MIN-MAX proves to be computationally intractable, even in simplified scenarios. This means finding a perfectly fair outcome is often a very difficult problem for computers to solve. Nevertheless, the paper identifies specific conditions, such as a small number of agents or constraints, where the MIN-MAX problem can be solved more efficiently, either exactly or through approximation algorithms.
The Cost of Fairness and Strategic Behavior
The study also examines the “price of temporal fairness,” which quantifies the trade-off between enforcing fairness constraints and achieving optimal welfare. For MIN-SUM, the cost of fairness scales with the number of agents, suggesting that ensuring fairness can become significantly more expensive as the community grows. For MIN-MAX, this cost depends on the number of constraints or agents, highlighting the need for careful consideration when imposing fairness rules, especially in large groups.
Another crucial aspect explored is strategic manipulation. In any voting system, there’s a risk that individuals or groups might misrepresent their preferences to achieve a better outcome for themselves. The paper shows that while the greedy algorithm for MIN-SUM is “strategyproof” for individuals (meaning a single agent cannot benefit by lying), it is not “group-strategyproof.” This implies that groups could potentially manipulate the system. However, the good news is that identifying such a beneficial group manipulation for MIN-SUM is computationally hard. For MIN-MAX, the situation is more challenging: it is not strategyproof even for individuals, meaning a single agent can benefit by misreporting. Yet, similar to group manipulation in MIN-SUM, finding such an individual manipulation for MIN-MAX is also computationally intractable, making it difficult for agents to exploit the system.
Also Read:
- New Insights into Multi-Winner Voting Through Data Analysis
- Advancing Fair Resource Allocation on Structured Networks
Decisions in Real-Time and Other Fairness Concepts
The research further considers an “online setting,” where decisions must be made without complete information about future projects or preferences, reflecting the dynamic nature of real-world planning. While a greedy approach works optimally for MIN-SUM in this setting, for MIN-MAX, the lack of future information significantly impacts the achievable welfare, demonstrating a substantial competitive ratio.
Finally, the authors discuss other common fairness notions like proportionality and equitability. They argue that proportionality, a widely studied concept in fair division, is often unintuitive or ill-defined in the context of public chores. Equitability, which aims for equal disutilities among agents, is also computationally hard to achieve, and enforcing it comes at a very high cost to overall welfare. This suggests that new, more suitable fairness measures might be needed for this unique setting.
This paper provides valuable insights into the complexities of collective decision-making when dealing with projects that impose individual costs. By highlighting the computational challenges and strategic considerations, it lays the groundwork for designing more robust and fair mechanisms for managing public chores in communities. You can read the full paper here.
