Research map / Multi-agent systems and games / Games and equilibria
Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies temporal voting where agents submit disapprovals over undesirable projects, showing MIN-SUM is polynomial and strategyproof while MIN-MAX is NP-complete and manipulable.
Problem
Collective decision-making over recurring undesirable projects (chores) in a temporal voting setting, where agents have disapproval preferences and welfare objectives (sum or max disutility) and strategic manipulation are considered.
Approach
Extends temporal voting from approval to disapproval preferences over undesirable candidates, defining MIN-SUM and MIN-MAX welfare objectives and analyzing their computational complexity and strategyproofness/group-strategyproofness.
Key results
- MIN-SUM outcomes can be computed in polynomial time via a greedy algorithm, and the greedy algorithm is strategyproof (Theorem 3.3).
- The MIN-MAX decision problem is NP-complete, even with m=2, γ=2, and τ=1 (Theorem 3.1).
- MIN-SUM is not group-strategyproof (Proposition 3.5) and MIN-MAX is not strategyproof (Proposition 3.6).
Surprising findings
- The MIN-SUM greedy rule is strategyproof, yet MIN-MAX, which targets fairness, is manipulable even under individual strategyproofness.
Limitations
- MIN-MAX is computationally intractable even in restricted cases.
- Results for approval framework do not automatically transfer to disapproval framework.
Experimental setup
Builds on: temporal voting (approval) egalitarian welfare in approval voting
Closest papers by meaning
- Multi-Party Campaigning (AAAI 2021 · similarity 0.90)
- Iterative Calculus of Voting under Plurality (AAAI 2022 · similarity 0.89)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.87)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.87)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.86)
- Network Intervention by Polling Strategic Agents (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.