Research map / Learning theory and algorithms / Submodular and game algorithms
Learning to Manipulate Under Limited Information
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.
Trains over 100,000 MLPs of 26 sizes to learn profitable strategic voting under six types of limited polling information, measuring manipulability of eight voting methods across probability models.
Problem
Measuring how resistant preferential voting methods are to strategic manipulation when a single voter has only limited information about how others will vote.
Approach
Use the learnability of manipulation by MLPs of varying sizes, given limited information inputs (plurality scores, margin matrices, sincere winners, etc.), as a proxy for manipulation difficulty, and compare the average profitability achieved against an ideal full-information manipulator.
Key results
- Borda is highly manipulable by MLPs with limited information, while IRV-PUT is resistant despite being profitably manipulable by an ideal manipulator.
- Minimax and Split Cycle are the overall least manipulable of the 8 methods across the three probability models.
- With uniform and Mallows models, sufficiently large MLPs profitably manipulate all eight methods using only the majority matrix.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sincere winners as limited information | MLP manipulator against IRV-PUT · Elections with 3–6 candidates and 5–21 voters | profitability relative to ideal manipulator: 30-40% | Helped |
| Use majority-matrix information | MLP manipulators against all eight voting methods · Uniform utility and Mallows models | profitability | Helped |
| Use margin-matrix rather than majority-matrix information | MLP manipulators · Uniform utility and Mallows models | profitability | Mixed |
| Use qualitative margin matrix rather than margin matrix | MLP manipulators against Borda and Black's · Uniform utility and Mallows models | profitability | No clear effect |
| Use plurality ranking rather than plurality scores | MLP manipulator against Plurality · Plurality elections | profitability | No clear effect |
| Use plurality scores as limited information | MLP manipulators against methods other than Plurality · 6-candidate elections | profitability | Hurt |
| Train an MLP manipulator | Borda · Elections under limited information | profitability | Helped |
| Train an MLP manipulator | IRV-PUT · Elections under limited information | profitability | Hurt |
| Train an MLP manipulator | Minimax and Split Cycle · Spatial 2D model | profitability | Hurt |
| Train an MLP manipulator | Nanson · Spatial 2D model | profitability | Hurt |
| Increase the number of candidates | MLP-based manipulators · Elections with 3–6 candidates | profitability relative to ideal manipulator | Hurt |
| Use binary cross-entropy instead of mean-squared error for the loss (ablation) | MLP manipulators under the uniform utility model · Uniform utility model | manipulation performance | No clear effect |
Surprising findings
- IRV-PUT is quite resistant to learned manipulation despite being more manipulable than some methods by an ideal manipulator.
- Stable Voting is barely manipulable with 11 voters but more manipulable with 10 voters.
Limitations
- Classification approach is infeasible for more than 6 candidates.
- Only single-voter manipulation is studied.
- Results depend on the three chosen probability models and hand-tuned training hyperparameters.
Experimental setup
Datasets: simulated elections from uniform utility model Mallows model elections spatial 2D model elections
Benchmarks: simulated elections under three probability models
Metrics: average profitability normalized by utility range ratio of MLP profitability to ideal manipulator profitabilit
Baselines: ideal manipulator with full information
Builds on: Gibbard-Satterthwaite theorem relative utilitarianism Mallows model
Closest papers by meaning
- Manipulative Elicitation — A New Attack on Elections with Incomplete Preferences (AAAI 2018 · similarity 0.86)
- Multi-Party Campaigning (AAAI 2021 · similarity 0.86)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.85)
- Election Control in Social Networks via Edge Addition or Removal (AAAI 2020 · similarity 0.85)
- Learning to Elect (NeurIPS 2021 · similarity 0.85)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.82)
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.