14 April 2026, Computational Social Choice Seminar, Soumyajit Pyne

The Hotelling-Downs model studies strategic positioning of candidates along an ideological line where voters choose the nearest candidate. While equilibrium structure has been widely analyzed, little is known about the computational complexity of finding equilibria. We provide algorithmic results for computing equilibria in both discrete and continuous variants of the model. For the continuous case, we prove a structural result showing that whenever an equilibrium exists, one also exists with rational positions of bounded complexity, enabling discretization via a notion we call reflection barriers. Using dynamic programming, we show: (i) equilibrium existence is decidable in polynomial time for discrete candidate locations; (ii) in the continuous-candidate and discrete-voter setting, equilibria can be computed in pseudo-polynomial time; and (iii) in the fully continuous setting, an ϵ-equilibrium can be computed in time polynomial in 1/ϵ. This is joint work with Umang Bhaskar.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.