Research map / Learning theory and algorithms / Submodular and game algorithms
Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line
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 additive epsilon-equilibria in Hotelling-Downs spatial competition on the line with m candidates and voter density f, proving nearly tight bounds (1/12, 1/6 for 3 candidates; 1/(m+1) upper and 1/(m+3) lower for m candidates; 1/7 and 1/6 when candidates may co-locate).
Problem
Spatial (Hotelling-Downs) candidate competition on [0,1] has no pure equilibrium for three or more candidates in general; the paper asks how close to equilibrium candidates can get, i.e., the best achievable additive approximation epsilon.
Approach
Derives tight worst-case and best-case additive approximation bounds via votes-counting arguments: for 3 candidates, any profile is at least 1/12-approximate and some distribution forces 1/6; for m candidates, an equipartition profile (computed via Cut queries) is a 1/(m+1)-equilibrium, and a rapidly decaying density gives a lower bound of 1/(m+3).
Key results
- For 3 candidates, every strategy profile is at least a 1/12-approximate equilibrium for any voter distribution, and some distribution forces epsilon >= 1/6, with a 1/6-equilibrium always computable in polynomial time.
- For m candidates, an equipartition profile (via Cut queries) is always a 1/(m+1)-approximate equilibrium computable in polynomial time, while some distribution forces epsilon >= 1/(m+3).
- When candidates may share a location, a 1/7-equilibrium always exists for 3 candidates and this is tight for some distribution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of candidates from 3 to m ≥ 4 | Worst-case voter distributions in Hotelling spatial competition · Line interval [0,1] | epsilon (approximation): 1/6 -> 1/(m+1) | Helped |
| Allow multiple candidates to occupy the same location | Three-candidate Hotelling spatial competition · Worst-case voter distributions | epsilon (approximation): 1/6 -> 1/7 | Helped |
| Place candidates at voter quantiles forming an equipartition | m-candidate Hotelling spatial competition · All voter distributions | epsilon (approximation): ε ≤ 1/(m+1) | Helped |
Surprising findings
- With three candidates, at least 1/12 of the votes are always left on the table for any distribution and profile.
Limitations
- The 1/7 co-location upper bound is not known to be computable in polynomial time with the given oracles.
- Model assumes inelastic demand: every voter votes for the nearest candidate.
- Only additive approximations are studied; multiplicative bounds remain open.
Experimental setup
Metrics: additive epsilon of approximate equilibrium
Builds on: Hotelling model Downs model Eaton and Lipsey nonexistence results Robertson-Webb query model
Closest papers by meaning
- Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium (AAAI 2026 · similarity 0.87)
- Spatial Voting with Incomplete Voter Information (AAAI 2024 · similarity 0.86)
- Replicating Electoral Success (AAAI 2025 · similarity 0.86)
- Voter Priming Campaigns: Strategies, Equilibria, and Algorithms (AAAI 2025 · similarity 0.85)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.84)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.84)
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.