Introduction
Traditional voting theory typically focuses on selecting candidates or projects that voters desire. However, many real-world governance decisions involve "chores"—socially necessary but individually costly projects. This is often referred to as the "Not In My Backyard" (NIMBY) problem. Examples include the placement of noisy construction projects, music festivals, or waste treatment facilities. While these events may benefit a city as a whole, the residents living in the immediate vicinity bear the brunt of the noise, traffic, and disruption.
This paper explores the framework of Temporal Voting with Undesirable Candidates, where decisions are made sequentially over multiple time steps. The goal is to select one project per round while attempting to balance the "disutility" (the cumulative burden of disliked projects) across the population over the long term.
The Temporal Voting Model
In this model, voters provide "disapproval preferences" for each round, indicating which projects they find objectionable at that specific time. The challenge for the decision-making mechanism is to minimize the negative impact on voters across the entire sequence of rounds. The researchers evaluate this problem through two primary welfare objectives:
- MIN-SUM (Efficiency): This objective seeks to minimize the total sum of disutilities across all agents. It represents a utilitarian approach aimed at reducing the overall "pain" felt by society.
- MIN-MAX (Fairness): This egalitarian approach seeks to minimize the maximum disutility experienced by any single agent, ensuring that no individual is disproportionately burdened by the sequence of decisions.
Computational Complexity
The study reveals a significant divide in the computational feasibility of these two objectives. The researchers found that minimizing the total social cost (MIN-SUM) is computationally efficient and can be solved using a simple greedy algorithm.
In contrast, achieving the fairer MIN-MAX objective is computationally "intractable." The paper proves that the decision problem for MIN-MAX is NP-complete, even in highly restricted scenarios—such as cases involving only two projects and a single global constraint. This suggests that as the number of voters and projects grows, finding a perfectly fair distribution of chores becomes increasingly difficult for automated systems.
Strategic Manipulation and Game Theory
A critical aspect of social choice is Strategyproofness (SP): the assurance that a voter cannot achieve a better outcome for themselves by misreporting their true preferences. The paper’s findings highlight a stark tradeoff between fairness and honesty:
- Greedy Efficiency is Strategyproof: The authors prove that the greedy algorithm used to satisfy the MIN-SUM objective is Strategyproof. An individual voter has no incentive to lie about their dislikes to change the outcome in their favor. However, the objective is not Group-Strategyproof, meaning a coalition of voters could still potentially collude to manipulate the results.
- Fairness Invites Deception: Perhaps the most surprising finding is that the MIN-MAX objective is inherently prone to manipulation. Because the system prioritizes protecting the individual who is suffering the most, voters are incentivized to pretend they are suffering more than they actually are. By reporting disapproval for projects they do not actually mind, they can "game" the system to force the selection of a different project. Consequently, any mechanism that always returns a MIN-MAX outcome is not Strategyproof.
The Efficiency-Fairness Tradeoff
The authors highlight the "κ + 1" problem to illustrate the limitations of the MIN-SUM approach. A simple MIN-SUM mechanism might consistently choose a project that a minority (κ agents) hates, simply because a slightly larger group (κ + 1 agents) hates the alternative. While this is "efficient" in terms of total numbers, it can lead to the systemic marginalization of a minority group.
Conclusion and Future Directions
This research establishes that while minimizing total social disapproval is computationally easy and resistant to individual manipulation, the pursuit of egalitarian fairness (MIN-MAX) introduces both computational complexity and strategic instability.
As a foundational student abstract, the paper suggests several avenues for future work:
- p-mean Welfare: Exploring intermediate objectives that balance the gap between MIN-SUM and MIN-MAX.
- Proportionality: Adapting concepts of proportional representation to the context of "chores" to ensure minority groups are protected without inviting manipulation.
- Mixed Valuations: Expanding the model to handle scenarios where projects may have both positive and negative valuations for different voters simultaneously.
Summary updated