Temporal Elections: Welfare, Strategyproofness, and Proportionality
This work addresses algorithmic and game-theoretic challenges in multi-round voting systems, providing insights for computational social choice and mechanism design, though it is incremental in extending known complexity results to temporal settings.
The paper tackles the computational and strategic aspects of sequential decision-making in temporal elections, focusing on utilitarian and egalitarian welfare objectives, and finds that maximizing utilitarian welfare is easy but maximizing egalitarian welfare is NP-complete, with strategyproofness achievable for utilitarian but not for egalitarian welfare under certain conditions.
We investigate a model of sequential decision-making where a single alternative is chosen at each round. We focus on two objectives -- utilitarian welfare (Util) and egalitarian welfare (Egal) -- and consider the computational complexity of maximizing these objectives, as well as their compatibility with strategyproofness and proportionality. We observe that maximizing Util is easy, but the corresponding decision problem for Egal is NP-complete even in restricted cases. We complement this hardness result for Egal with parameterized complexity analysis and an approximation algorithm. Additionally, we show that, while a mechanism that outputs an outcome that maximizes Util is strategyproof, all deterministic mechanisms for computing outcomes that maximize Egal fail a very weak variant of strategyproofness, called non-obvious manipulability (NOM). However, we show that when agents have non-empty approval sets at each timestep, choosing an Egal-maximizing outcome while breaking ties lexicographically satisfies NOM. Regarding proportionality, we prove that a proportional (PROP) outcome can be computed efficiently, but finding an outcome that maximizes Util while guaranteeing PROP is NP-hard. We also derive upper and lower bounds on the (strong) price of proportionality with respect to Util and Egal. Some of our results extend to $p$-mean welfare measures other than Egal and Util.