Lower Bound Issues in Computational Social Choice
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Gives concrete complexity boundaries: lobbying on voter-by-issue matrices is FPT via Lenstra-style ILP when parameterized by the maximum number of ones per column and by the number of allowed row changes, but exhibits intermediate hardness captured by log-SNP for intermediate hardness; shift-bribery with scaled prices admits a polynomial-time/FPT regime for practical pricing models; districting/gerrymandering problems are NP-complete via a reduction from Exact Cover by 3-Set even for tiny fixed district sizes, so many natural variants stay intractable.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:29What is Computational Social Choice?
- 1:38Motivation
- 3:57Motivating Example: Sequential Voting!
- 18:11Lobbying: ILP-Based FPT (Lenstra) IV
- 32:31Shift Bribery: FPT Approximation III
- 35:14Combinatorial Shift Bribery: Inapproximability
- 43:09Network-Based Vertex Dissolution: ParaNP-Hardness IV
related talks
01h 01mComplexity and Algorithmic Game Theory I
01h 10mOn Algorithmic Game Theory II
01h 10mComplexity and Algorithmic Game Theory II
52mOn Algorithmic Game Theory I
01h 32mInapproximability of Constraint Satisfaction Problems I
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
20mBeyond Worst-Case Budget-Feasible Mechanism Design
20mA Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems