Parameterized Complexity of Hotelling-Downs with Party Nominees

Parameterized Complexity of Hotelling-Downs with Party Nominees

Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 244-250. https://doi.org/10.24963/ijcai.2022/35

We study a generalization of the Hotelling-Downs model through the lens of parameterized complexity. In this model, there is a set of voters on a line and a set of parties that compete over them. Each party has to choose a nominee from a set of candidates with predetermined positions on the line, where each candidate comes at a different cost. The goal of every party is to choose the most profitable nominee, given the nominees chosen by the rest of the parties; the profit of a party is the number of voters closer to their nominee minus its cost. We examine the complexity of deciding whether a pure Nash equilibrium exists for this model under several natural parameters: the number of different positions of the candidates, the discrepancy and the span of the nominees, and the overlap of the parties. We provide FPT and XP algorithms and we complement them with a W[1]-hardness result.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Noncooperative Games