Research map / Learning theory and algorithms / Submodular and game algorithms
On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting
Ratip Emin Berker, Emanuel Tewolde, Vincent Conitzer, Mingyu Guo, Marijn Heule, Lirong Xia
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| search over vote distributions with a MILP rather than over fixed profiles with SAT | core stability existence checking · m<=7 candidates, any k | core non-emptiness verified | Improved |
| use vote distributions to remove dependence on number of voters | MILP formulation · core stability | voter-count independence | Improved |
| compare MILP optimal values across m for fixed k | MILP · Table 1, m 4 to 7 | optimal MILP value: -1/(k(k+1)) for every m | No clear effect |
| switch quota from Hare (k) to Droop (k+1) (ablation) | MILP to DrMILP · Table 1 values of m, k | optimal objective: converges to 0 | Improved |
| restrict deviations to singletons or add one non-singleton deviation (ablation) | DLP upper bound · any m, k | DLP upper bound | Improved |
| set m = k+1 (large committee) | DLP · any k, Droop quota | core non-emptiness | Improved |
| use MILP with priceability dual constraints to find counterexamples | Droop core vs priceability · m=5,k=3 weak; m=4,k=2 Lindahl | implication of priceability by core | Hurt |
| scale MILP to larger candidate sets (m=8, k=4) | MILP with Gurobi · m=8, k=4 | solver termination: no termination within 72h | Hurt |
Closest papers by meaning
- Approval-Based Committee Voting under Incomplete Information (AAAI 2022 · similarity 0.90)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.88)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.88)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.88)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.87)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · 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.
