Research map / Learning theory and algorithms / Submodular and game algorithms
Welfare Maximization in Perpetual Voting (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 computational complexity of maximizing utilitarian, egalitarian, and Nash welfare in perpetual voting, showing UTIL is easy while EGAL and NASH are hard, with parameterized, approximation, strategyproofness, and proportionality results.
Problem
Maximizing welfare objectives (utilitarian, egalitarian, Nash) over sequential multi-round collective decisions in the perpetual voting framework, where existing work focused on fairness and proportionality.
Approach
Formalizes p-mean welfare for perpetual voting outcomes and analyzes computational hardness, parameterized complexity, approximation, and strategyproofness for utilitarian, egalitarian, and Nash welfare; shows a greedy algorithm maximizes utilitarian welfare and yields a floor-based proportional outcome.
Key results
- EGAL and NASH are NP-complete even for λ=1 and m=2 candidates (Theorem 1), while UTIL is solvable greedily.
- EGAL is FPT in the number of agents n, and EGAL and NASH are XP in the number of timesteps ℓ but W[2]-hard in ℓ (Theorems 2-4).
- A 1/(4 log n)-approximation for egalitarian welfare under augmented utilities 1+u_i(o) (Theorem 5); GREEDYUTIL is strategyproof (Theorem 6), while egalitarian/Nash maximizers are not (Theorem 7).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| maximize utilitarian welfare by selecting the candidate with the most approvals at each timestep | Perpetual voting · Perpetual voting | computational complexity | Helped |
| maximize egalitarian welfare | Perpetual voting with two candidates and λ = 1 · Perpetual voting | computational complexity | Hurt |
| maximize Nash welfare | Perpetual voting with two candidates and λ = 1 · Perpetual voting | computational complexity | Hurt |
| parameterize by the number of agents n | Egalitarian welfare maximization · Perpetual voting | parameterized complexity | Helped |
| parameterize by the number of timesteps ℓ | Egalitarian welfare maximization · Perpetual voting | parameterized complexity | Helped |
| parameterize by the number of timesteps ℓ | Nash welfare maximization · Perpetual voting | parameterized complexity | Helped |
| parameterize by the number of timesteps ℓ | Egalitarian welfare maximization · Perpetual voting | parameterized hardness | Hurt |
| parameterize by the number of timesteps ℓ | Nash welfare maximization · Perpetual voting | parameterized hardness | Hurt |
| augment each agent's utility to 1 + ui(o) | Egalitarian welfare maximization · Perpetual voting | approximation ratio: 1/(4 log n)-approximation | Helped |
| use GREEDYUTIL | Utilitarian welfare maximization · Perpetual voting | strategyproofness | Helped |
| maximize egalitarian welfare with a deterministic mechanism | Perpetual voting · Perpetual voting | strategyproofness | Hurt |
| maximize Nash welfare with a deterministic mechanism | Perpetual voting · Perpetual voting | strategyproofness | Hurt |
Surprising findings
- EGAL and NASH are NP-complete even with only two candidates and each agent guaranteed utility 1.
- Proportionality in its standard form is not always achievable, so a floor-based relaxation is needed; a polynomial greedy algorithm achieves it.
Limitations
- FPT in n for NASH remains open.
- Egalitarian and Nash welfare maximization are intractable, so only approximations or restricted-parameter algorithms are available.
- Proofs are omitted in the student abstract.
Experimental setup
Metrics: welfare objective value computational complexity class
Builds on: perpetual voting (Lackner 2020) proportionality in perpetual voting (Bulteau et al. 2021) temporal multiwinner voting survey (Elkind, Obraztsova, Teh 2023)
Closest papers by meaning
- Truthful and Near-Optimal Mechanisms for Welfare Maximization in Multi-Winner Elections (AAAI 2018 · similarity 0.90)
- Iterative Calculus of Voting under Plurality (AAAI 2022 · similarity 0.89)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.88)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.88)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.87)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.87)
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.