Parameterized Complexity of Hotelling-Downs with Party Nominees

1 Introduction

The Hotelling-Downs model [Downs, 1957; Hotelling, 1929] is probably the most well-established framework in studying strategic positioning on spatial competition. In the original model, there are two ice cream sellers on a beach and they want to choose a position for their shop in order to maximize their customers, under the assumption that a customer will choose the seller that is closer to their location. The simplicity and the elegance of this framework served as a basis for numerous other models and applications ranging from spatial design, to strategic candidacy [Eiselt et al., 1993; Eiselt, 2011].

In fact, in [Downs, 1957] it was argued that the equilibrium of the game above, could be potentially used to predict the positions of the parties within the political spectrum. However, the original model has two strong assumptions: there are only two agents and every agent can choose every possible location in the spectrum; the unique equilibrium of the game is when both vendors choose the median of the beach. In reality though, several political parties are involved. In addition, the available positions of a party in the political spectrum are constrained from two crucial factors: the ideology of the party and the available candidates or policies, it can choose from.

In order to bypass the aforementioned limitations, a new model that is closer to reality was recently proposed [Harrenstein et al., 2021]. In this model, there are many parties, each of whom is associated with a set of candidates on a line. In addition, there is a set of voters distributed in an arbitrary way over the line. To play the game, every party should choose one nominee from their set of candidates, while again they are trying to maximize the number of voters that are closer to their nominee compared to the nominees of the remaining parties. The authors showed that these games do not always possess a pure Nash equilibrium and in fact it is NP-complete to decide if an equilibrium exists.

Indeed the extended model is closer to reality, albeit in the current political spectrum there are further extra constraints within the parties. In many cases, the ideology of a party dictates a high level position of the party on the spectrum, which is usually a priori fixed, while the different candidates and policy adoptions correspond to the fine grained position of the party. For example, it is not uncommon that the spread of the candidates of a party within the political spectrum is not too wide. Furthermore, not many parties share the same ideology; usually the parties target a specific demographic of voters within the political spectrum and the overlap of this range with the remaining parties is limited. Inspired by these constraints of real-life politics we study the following question for the generalized Hotelling-Downs model.

What is the complexity of equilibrium computation under natural constraints on the candidates?

Our contribution. Our contribution is twofold: (a) we further extend the Hotelling-Downs framework of Harrenstein et al. [2021] by associating each candidate with a cost and (b) we study the equilibrium computation problem for the extended model through the lens of parameterized complexity. In real-life politics, many times, every position at the political spectrum comes at a different cost. In fact, it is not uncommon that even candidates on the same position come at a different cost for different parties. For example, this can be due to preexisting positions, investments, and advertisements of the party towards specific campaigns. For this extended model, we study the parameterized complexity of the equilibrium-computation problem under several parameters that capture natural constraints over the candidates of the parties. We denote the corresponding computational problem HOTELLINGDOWNS-NE (HD-NE). More specifically, we focus on the overlap the parties have due to their candidates, and the span, the discrepancy, and the number of different positions of the candidates. The overlap parameter intuitively captures the maximum number of parties that have overlapping ideologies, if we assume that the ideology of a party is expressed via the spread of its candidates. The span is the difference between the leftmost candidate of any party and the rightmost candidate of any party; observe that the span parameter naturally bounds the number of candidate positions. Finally, the discrepancy of the candidates of a party is the difference between the leftmost and the rightmost candidate the party has; the discrepancy parameter is the maximum discrepancy over the parties.

Firstly, we focus on the overlap parameter and we prove that in this case HD-NE admits an XP algorithm (Theorem 1). In fact, the same algorithm yields fixed-parameter tractability by overlap and discrepancy (Corollary 2). In addition, by observing that overlap is trivially bounded by the number of parties, we can get as an immediate corollary that HD-NE is fixed-parameter tractable by discrepancy and the number of parties. We show that the XP algorithm is in fact the best we can hope for since the problem is W[1]-hard when parameterized only by overlap, even when every candidate has zero cost (Theorem 5). In fact, our result shows that our XP algorithm is essentially optimal, assuming the exponential time hypothesis (ETH). This is our main technical result; our hardness reduction is rather intricate and requires a careful design of an instance that utilizes Sidon sequences [Erd¨os and Tur´an, 1941]. Next, we turn our attention to discrepancy and span parameters. In Theorem 6 we derive a fixed-parameter tractable algorithm parameterized by the number of candidate positions for all parties when every party has uniform cost over their candidates. Using this result and the fact that the span bounds the number of different positions of the candidates, we get as corollary that HD-NE is fixed-parameter tractable by span, when every party suffers uniform cost over the candidates (Corollary 7). In our last result, we show that the problem is XP by discrepancy (Theorem 8).

Further Related Work. Since the original HotellingDowns model was introduced, several extensions have been proposed and studied [Brusco et al., 2012; Shen and Wang, 2016; Feldman et al., 2016b]. Two influential studies include [Stokes, 1963] and [Eiselt et al., 1993], which study Hotelling-Downs framework in spatial competition. [Sengupta and Sengupta, 2008] and [Eaton and Lipsey, 1975] study modifications of the model by considering multiple players and different voting rules, while [Ben-Porat and Tennenholtz, 2019] studies the case where each party can choose multiple positions on the line. In algorithmic game theory, our research relates to Voronoi games where every player's utility depends on the points closest to them [Ahn et al., 2004]. This is a highly studied problem on graphs and [D¨urr and Thang, 2007] proved that it is NP-complete to decide whether a Nash equilibrium exists on arbitrary graphs. The Hotelling-Downs model is closely related to other problems from computational social choice [Feldman et al., 2016a; Faliszewski et al., 2016; Ahn et al., 2004; Brusco et al., 2012] and strategic voting [Meir, 2018].

2 Preliminaries

The space of the game we consider is [m] = {1, 2, . . . ,m}, which we view as a path with m positions. There is a set of voters located on [m]; on position i there are vi ∈ N voters.

Parties. There are n parties Π1, . . . ,Πn that correspond to the players of the game. Every party Πi has a set of candidates Ci ⊆ [m], where Ci := {ci1, . . . , ciki } and ci1 < ci2 < . . . < ciki . In addition, every candidate is associated with a cost given by pi : Ci → N. If pi(x) = ai for every x ∈ Ci, then we say that the party suffers uniform cost. To play the game, every party Πi has to nominate a single candidate si ∈ Ci; this is the strategy of Πi. We denote s = (si, s-i) as the strategy profile for the parties, where s-i is the (n-1)-dimensional vector produced by s, after deleting its i-th entry.

Utilities. The utility of party Πi under strategy profile (si, s-i), is denoted ui(si, s-i). At a high level, ui(si, s-i) is the number of voters that are located closest to the candidate si chosen by party Πi compared to the candidates s-i chosen by the rest of the parties, minus the cost pi(si) associated for the chosen candidate. To define formally ui(si, s-i) we will need the auxiliary sets R(si, s-i) and T(si, s-i). R(si, s-i) contains all points of [m] that are closer to si compared to any other sj different than si of s-i; T(si, s-i) contains all points of [m] (at most two of them) that are in equal distance to si and some other sj different than si of s-i. In addition, given a strategy profile s and a j ∈ [m], define nj to be the set of parties i ∈ [n] such that si = j. We are now ready to formally define the utility of any party. So, the utility ui(si, s-i) of party i under strategy profile (si, s-i), where si = j, is

Strategy si ∈ Ci is a best response against s-i, if ui(si, s-i) ≥ ui(s′i , s-i), for every s′i ∈ Ci. A strategy profile is a Nash equilibrium if every party plays a best response; in other words, in a Nash equilibrium no party can increase its utility by unilaterally changing its strategy.

Definiton 1 (HOTELLINGDOWNS-NE (HD-NE)). Input: I = ⟨m, n, C,P, V⟩, where [m] is the space of the game, n is the number of parties, C = {C1, . . . ,Cn} is the set of candidate sets, P = {p1, . . . , pn} are the cost functions, and V = {v1, . . . , vm} are the voters on every position. Question: Is there a Nash equilibrium for I?

Parameters. We will study the complexity of HD-NE under the following parameters.

• Parties. This is the number of parties n.
• Candidate-positions. This is the number of different positions of the candidates for all the candidates of all the parties, formally |C1 ∪ C2 ∪ . . . ∪ Cn|.
• Discrepancy. This parameter captures the distance between the candidates within every party and is defined as maxi∈[n]{ciki - ci1}. We denote the discrepancy of an instance I as d(I), or d if the instance is clear from the context.

• Span. This parameter captures the distance between the leftmost and the rightmost candidate, formally the span is maxi∈[n] ciki -mini∈[n] ci1.
• Overlap. This parameter captures the maximum number of parties who intersect on the line. For every j ∈ [m], define oj := {i ∈ [n] : j ∈ [ci1, ciki ]}. The overlap parameter is then defined as maxj∈[m] |oj|. We denote the overlap of an instance I as ov(I) or ov if the instance is clear from the context.

Parameterized Complexity. Parameterized complexity studies the running-time of an algorithm with respect to a parameter k ∈ N0 and input size n [Cygan et al., 2015]. The most favorable complexity class is FPT, which contains all problems that can be decided by an algorithm running in time f(k) · nO(1) , where f is a computable function. Algorithms with this running-time are called fixed-parameter (FPT) algorithms. A less favorable, but still positive, outcome is an XP algorithm, which has running-time O(nf(k) ); problems admitting such algorithms belong to the class XP. Showing that a problem is W[1]-hard rules out the existence of a fixed-parameter algorithm under the well-established assumption that W[1] ̸= FPT.

3 Overlap

In this section we study HD-NE under the overlap parameter. We first design an XP algorithm for the problem. Our algorithm in fact allows us to derive fixed-parameter tractable algorithms as corollaries that are parameterized by overlap and discrepancy, or by discrepancy and number of parties.

Theorem 1 (⋆). HD-NE admits an XP algorithm parameterized by overlap and it runs in time O(dO(ov) · ovO(ov) · poly(|I|)), where |I| is the size of the input.

The algorithm is a dynamic programming along the space of the game [m]. For each j ∈ [0,m+ 1] we will compute a table Γj. In order to define Γ0 and Γm+1, we define o0 = om+1 = ∅. The table Γj has entries for some tuples of the form (Nom, #Parties, Left, Right, aft, bef ), where:

• Nom represents overlap nominees, that is for each party i ∈ oj it contains a single candidate si ∈ Ci representing the strategy of the party Πi;
• #Parties contains for each i ∈ oj the number ni ∈ [ov] that represents the number of parties with the strategy si;
• Left contains for each i ∈ oj the position ℓi ∈ [m] ∪ {-∞}, representing the position of a closest nominee selected as a strategy to the left of si;
• Right contains for each i ∈ oj the position ri ∈ [m] ∪ {∞}, representing the position of a closest nominee selected as a strategy to the right of si;
• aft ∈ [j,m] ∪{∞} represents the position of the closest nominee selected as a strategy to the right of j -1 (after j - 1);
• bef ∈ {1, . . . j} ∪ {-∞} represents the position of the closest nominee selected as a strategy to the left of j +1 (before j + 1).

We call each such tuple a configuration for j. We do not care about all configurations for j; we care only about those for which there exists a strategy profile s, called a satisfiability witness, that conforms to the intended meaning of the configuration σ = (Nom, #Parties, Left, Right, aft, bef). A configuration is satisfiable, if it admits a satisfiability witness.

Claim 1 (⋆). Given a configuration σ, we can in polynomial time verify if there exists a satifiability witness of σ.

Claim 2. There are at most O(d3|oj|+2 · ov|oj| ) many satisfiable configurations for j and we can enumerate them in O(d3|oj|+2 · ov|oj| · poly(|I|)) time.

Proof of Claim. Since for each i ∈ oj the party Πi has a candidate at the position si, it follows that there are at most |Ci| ≤ p + 1 possibilities for si for each i ∈ si. To verify that, given si we have at most 2p + 2 many possibilities of ℓi, we observe that it is either -∞ or it is within p positions to the left of si, or there is a party Πi′ such that ci′ ki′ < si and for every party Πi′′ either ci′′ ki′′ ≤ ci′ ki′ or ci′′ ki′′ ≥ si. Since the configuration is satisfiable, we get that ℓi ≥ ci′ 1. Moreover, by the choice of i′ , no party has a candidate between ci′ ki′ and si - p - 1. Finally, since if ℓi ̸= -∞, then at least one party has to have a candidate at the position ℓi, it follows that ℓ ∈ {-∞} ∪ [ci′ 1, ci′ ki′ ] ∪ [si - p, si - 1]. By an analogous argument, we can also show that there are only 2p + 2 positions to consider for ri (i ∈ oj), aft, and bef.

Γj contains an entry for each satisfiable configuration and Γj[(Nom,#Parties, Left,Right, aft)] is either NONE, or it is a single partial strategy profile s that contains a strategy for every party Πi with ci1 ≤ j, such that s satisfies the following conditions:

1. for every i ∈ oj, the strategy of Πi is si;
2. for every i ∈ oj, if si ≤ j, then the number of parties Πi′ such that the strategy of Πi′ is si is exactly ni;
3. for every i ∈ oj, no party has its strategy between ℓi and si, moreover if ℓi ≤ j, then there exists a party with strategy ℓi in s;
4. for every i ∈ oj, no party has its strategy between si and ri, moreover if ri ≤ j, then there exists a party with strategy ri in s.
5. for every si ∈ s, if si ≤ j, then si ≤ bef, moreover there exists a party Πi′ with strategy bef in s;
6. for every party Πi and every s′i ∈ Ci ∩ [j] it holds ui(si, s-i) ≥ ui(s′i , s-i), where the value of ui is computed under the assumption that besides the parties with a strategy in s there are additional parties with strategy aft and the strategies ℓi and ri for i ∈ oj.

It is easy to see that Γm+1 contains at most m + 1 entries, one for each satisfiable configuration σbef = (∅, ∅, ∅, ∅,∞, bef), bef ∈ [m] ∪ {-∞}, and any Nash equilibrium s for the original instance satisfies all the conditions for Γm+1[σbef ], for some satisfiable configuration σbef . Finally, if Γm+1[σbef ] is not NONE, then it contains a strategy profile s that has a strategy for every party in [n], which is a satisfiability witness for σbef . Moreover, from the fact that om+1 = ∅ and Condition 6, it follows that s is a Nash equilibrium. It remains to show that we can correctly compute values for all configurations with a satisfiability witness and all tables Γ0, . . . , Γm+1.

Claim 3 (⋆). We can compute Γ0 in time O(d).

Claim 4 (⋆). Given Γj, we can compute Γj+1 in time O(dO(ov) · ovO(ov) · poly(|I|)).

Proof Sketch of Claim. It follows from Claim 2 that it suffices to compute each entry in Γj+1 in time polynomial in |Γj | and |I|. Let σ = (Nom,#Parties, Left, Right, aft, bef) be a satisfiable configuration for Γj+1. First note that, for each i ∈ oj+1 we can determine whether the utility of j + 1 is at most the utility of si under any satisfiability witness. Hence, we can already now check that ui(j + 1, s-i) ≤ ui(si, s-i) for every i ∈ oj+1. From now on, we assume that it holds that ui(j + 1, s-i) ≤ ui(si, s-i) for every i ∈ oj+1, where utilities are computed under the assumption that aft, bef , and ni′ , ℓi′ , ri′ , for all i′ ∈ oj+1, have their intended meaning in s.

We say that σ′ = (Nom′ ,#Parties′ , Left′ ,Right′ , aft′ , bef ′ ) for Γj is a configuration that is compatible with σ, if the following is satisfied: (a) for every i ∈ oj ∩oj+1, si = s′i , ni = n′i ℓi = ℓ′i , and ri = r′i ; (b) either bef = bef ′ or bef = aft = j + 1; (c) either aft = aft′ or bef ′ = aft′ = j; (d) if si = j+1 for i ∈ oj+1, then ℓi = bef ′ ; and (e) if s′i = j for i ∈ oj, then r′i = aft.

To finish the proof of the claim one only needs to show Γj+1[σ] is not NONE if and only if there exists a compatible configuration σ′ such that Γj+1[σ] is not NONE.

The theorem is proven by applying Claim 3, then Claim 4 m+ 1 times, and finally checking all entries in Γm+1.

The running time of the XP algorithm from Theorem 1 immediately yields the following corollary.

Corollary 2. HD-NE is fixed-parameter tractable parameterized by overlap and discrepancy.

In addition, since overlap is trivially bounded by the number of parties, Corollary 2 gives the following.

Corollary 3. HD-NE is fixed-parameter tractable parameterized by discrepancy and number of parties.

3.1 W[1]-hardness

Next, we derive W[1]-hardness for HD-NE, when parameterized by overlap. To prove our result, we reduce from PARTITIONED SUBGRAPH ISOMORPHISM (PSI), which proves that the XP algorithm from Theorem 1 is essentially optimal, unless the exponential time hypothesis (ETH) fails 1 .

In PSI we are given as input two undirected graphs G and H with |V (H)| ≤ |V (G)| (H is smaller) and a mapping ψ: V (G) → V (H) and the task is to determine whether H is isomorphic to a subgraph of G, i.e., decide if there is an injective mapping ϕ : V (H) → V (G) such that {ϕ(u), ϕ(v)} ∈ E(G) for each {u, v} ∈ E(H) and ψ ◦ ϕ is the identity.

1 ETH states that 3SAT, the canonical NP-complete problem, cannot be solved in subexponential time [Impagliazzo and Paturi, 2001].

Theorem 4 (see [Marx, 2010] and [Eiben et al., 2019]). If there is an algorithm A and an arbitrary function f such that A correctly decides every instance (G,H, ψ) of PSI with the smaller graph H being 3-regular in time f(|V (H)|)|V (G)|o(|V (H)|/ log |V (H)|) , then ETH fails. 2

Theorem 5 (⋆). HD-NE is W[1]-hard parameterized by overlap of the input instance, even when the cost of the each position for each party is zero. Moreover, assuming ETH, there is no (n +m)o(ov)/ log(ov) time algorithm for HD-NE.

Proof Sketch. We give a reduction from an instance (G,H, ψ) of PSI with H being 3-regular to HD-NE, such that n + m is polynomial in the number of vertices of the graph G and overlap is linear in the number of vertices of H.

Let q = |V (H)| and let V1, V2, . . . , Vq be the partition of V (G) given by ψ-1 . Hence, two vertices u, v ∈ V (G) are in the same part if and only if ψ(u) = ψ(v). Let us denote by ψ(Vi), i ∈ [q], the vertex ψ(u) for u ∈ Vi (it is the same for every u ∈ Vi). Moreover, if for i, j ∈ [q] there is an edge between ψ(Vi) and ψ(Vj) in E(H), then let Ei,j denote all the edges with one endpoint in Vi and the other in Vj. Note that the task in PSI is to select exactly one vertex in each of the sets Vi, i ∈ [q], such that if ψ(Vi)ψ(Vj) is an edge in H and we selected vi in Vi and vj in Vj, then vivj is an edge in Ei,j.

We now construct an instance of HD-NE that has a Nash equilibrium if and only if (G, H, ψ) is Yes-instance of PSI.

The instance will have the following parties:

• for each i ∈ [q], there is a party Ri and a party Gi;
• for each i, j ∈ [q] such that there is the set Ei,j (i.e., there is the edge ψ(Vi)ψ(Vj) in H) we have a party Bi j (note that parties Bi j and Bj i are different);
• for each i, j ∈ [q] such that there is the set Ei,j and each ℓ ∈ [|Ei,j | - 1] there is party P ℓ i,j ;
• there are many so-called "dummy" parties, each dummy party will have exactly one candidate and the main purpose of dummy parties is to separate the gadgets we create. We denote the set of dummy parties D.

We will now create |V (H)| + |E(H)| many "gadgets", where each gadget is a path and represents a subinterval of the space of the game. Each gadget will start and end with a candidate from some dummy parties that they have to be selected always as a strategy of these dummy parties. Hence, every non-dummy party that selects a candidate in some gadget, will only get voters inside that gadget. The game space is obtained by putting these gadgets in series in arbitrary order.

To create our gadgets we need to assign to every vertex of G a unique number such that given the sum of values assigned to two different vertices, we can uniquely determine the vertices. That is if we afterwards assign to each edge the sum of its endpoints, then each edge will be assigned a different value. Fortunately, such an assignment always exists. Indeed, a Sidon sequence is a sequence of natural numbers such that the sum of every two distinct numbers in the sequence is unique. Moreover, a result by [Erd¨os and Tur´an,

2 We would like to point out that, as far as we know, it is open whether PSI admits even an f(|V (H)|)·|V (G)|o(|V (H)|) algorithm.

1941] implies that a Sidon sequence containing |V (G)| elements, whose largest element is at most 8|V (G)|2 , can be found in polynomial time. In the following we will assume that we are given such a Sidon sequence S and that for every x, y ∈ S we have |x - y| ≥ 10 and min(x, y) > 10. Finally, before we construct the gadgets, we also need to fix some large number M that is much larger than max(S). Let us fix, for example, M = (10max(S) + 100)2 . Note that M = O(|V (G)|4 ).

Let us assign to every vertex in G a unique number in S. For the sake of exposition, for any i ∈ [q] and x ∈ S, we will denote by vix the vertex of Vi that has been assigned the number x from the Sidon sequence S. For each i ∈ [q], let Si denote the elements of S assigned to vertices in Vi.

We will have two types of gadgets:

Vertex Set Gadget. For every i ∈ [q], we create the following gadget, called the vertex set gadget for Vi, (see Figure 1 for a depiction of the gadget). The gadget has 2M + 4 · max(Si) + 4 positions. We describe the gadget as it was the interval [2M + 4 · max(Si) + 3]. We have two dummy parties, one with a unique candidate at 1 and one with a unique candidate at 2M + 4 · max(Si) + 4. The party Gi has a candidate at position 2. The party Ri has candidates at position 2M + 4x + 3 for each x ∈ Si and a candidate at 2M + 3. Each candidate, besides the candidate at the position 2M + 3, is associated with a single vertex in Vi and we associate the candidate at the position 2M + 4x + 3 with the vertex vix (this is the vertex associated with the number x ∈ S). Each of the parties Bi j has a candidate at position 2M + 4x for each x ∈ Si. The party Ri will not have any other candidate, while Gi and Bi j 's will have also candidate in other gadgets. Finally, there is a single voter at every position in [2M + 4 · max(Si) + 3]. The intention behind this gadget is that in a Nash equilibrium, Gi selects the candidate at position 2, parties Bi j do not choose their candidate inside the vertex set gadget for Vi, and Ri chooses some candidate at position 2M + 4x + 1, for some x ∈ Si, representing the selection of the vertex vix from Vi. Note that in this case the utility of Ri is M + 2max(Si), regardless of the selection of x and the utility of Gi is M + 2x + 1.

Edge Set Gadget. For every Ei,j we create the following edge set gadget. Note that an edge e = vix vjy in Ei,j is associated with the number x + y and each edge is associated with a different number. First, we order the edges in Ei,j in ascending order according to x + y. Let us denote the ℓ-th edge in this ordering eℓi,j . The edge set gadget is split into

|Ei,j| many "edge" gadgets, each starting and ending with a dummy candidate (i.e., a candidate for a dummy party) such that the dummy candidate at the end of the gadget for the edge eℓi,j , ℓ ∈ [|Ei,j| - 1], is the same as the dummy candidate at the start of the gadget for eℓ+1 i,j (see Figure 2 for illustration).

The edge gadget of eℓi,j looks as follows (see Fig. 3 for illustration). It has 199 positions and we describe it as the interval [199]. There are two dummy parties with candidate at 1 and 199. If ℓ > 1, then the party P ℓ-1 i,j has a candidate at position 100. Similarly if ℓ < |Ei,j|, then P ℓ i,j has also candidate at position 100. The party Gi has candidates at 15 and 25 and the party Bi j has the candidate at position 20. Symmetrically, Gj has candidates at 175 and 185 and the party Bj i has the candidate at position 180. The number of voters depends on the two vertices vix and vjy such that eℓi,j = vix vjy . There is 1 voter at positions 11 and 189, there are 2x voters at position 55 and 2y voters at position 145, finally there at M voters at positions 75 and 125. The intention is that each party P ℓ i,j selects one of the two of its candidates in a way that no two of these parties select the same candidate. In this case the utility of P ℓ i,j is 2(M + x + y) for some x, y ∈ S. This leaves precisely one of the edge gadget inside of the edge set gadget for Ei,j empty, in which the parties Bi j and Bj i select their candidate. Bi j gets utility M + 2x + 1, for some x ∈ Si and Bj i gets utility M + 2y + 1, for some y ∈ Sj .

To obtain the game space we just fix an arbitrary ordering of the vertex set and edge set gadgets and identify the candidate for the dummy party at the end of one gadget with the candidate for the dummy party at the start of the next gadget in the ordering. The game space is then [m], where m is the position of the last dummy candidate. Note that each vertex set gadget has length O(M +max(S)) = O(|V (G)|4 ) and each edge set gadget has length O(|Ei,j|) = O(|V (G)|2 ). Hence m = O(|V (H)| · |V (G)|4 ) = O(|V (G)|5 ). This finishes the construction of the instance. It is rather straightforward to verify that each set oj can contain an index of at most one dummy party and at most two from the P j ℓ,i parties. Since the number of remaining parties is O(|V (H)| + |E(H)|) = O(|V (H)|), the overlap of the instance is indeed O(|V (H)|). It only remains to verify that the "intended strategy profile" is the only possible Nash equilibrium of the instance and it exists if and only if the instance (G,H, ψ) of PSI has a solution.

4 Number of Positions, Discrepancy and Span

In this section, we study the number of different positions for the candidates, the discrepancy, and the span. First, we focus on the case where parties suffer uniform cost over the candidates. This allows us to derive a fixed-parameter tractable algorithm by the number of candidates.

Theorem 6 (⋆). When every party suffers uniform cost, HDNE is in FPT parameterized by candidate positions.

Proof Sketch. Let cdp = |C1 ∪ · · · ∪ Cn|. We observe that for every party Πi, we have Ci ⊆ C1 ∪ · · · ∪ Cn and hence there are only 2cdp many different possibilities for the set of the candidates of a party. For this proof, we will call the set Ci the type of the party Πi. Since there are only 2cdp many types and each type has at most cdp many candidates, we can for each type t and each candidate j in the type branch on whether at least one party of type t nominates j as the strategy of the party in an Nash equilibrium. Moreover, for each j ∈ C1 ∪ · · · ∪ Cn, we can branch on whether zero, one, or at least two parties select j as their strategy. This results to 3cdp · 2cdp ·2cdp many branches. Moreover, in each branch, the positions of all strategies in a strategy profile are determined by the branch and this is true even after removing one party strategy from the profile. Given this, and since the parties suffer uniform costs, the position of a best response for each party only depends on the number of parties at each of the positions determined by the branch. Moreover, given two candidates j1 and j2 one can easily derive a linear inequality (with number of parties with strategies j1 and j2, respectively, as variables) that is satisfied if and only if the party is happy with position j1 and switching to j2 would not increase its utility. Moreover, this inequality is exactly the same for every party with strategy j1 and candidate at j2. This allows us to create in each branch an instance of INTEGER LINEAR PROGRAMMING (ILP) that has variables xj, j ∈ C1 ∪ · · · ∪ Cn, representing the number of parties with the strategy j and yt j representing the number of parties of type t with strategy j. The inequalities in the ILP then ensure that any solution to the inequality is consistent with the branch, each party is assigned some strategy and if yt j ≥ 1, then j is a best response for every party of type t. Note that the number of variables in the ILP is at most cdp ·(1+2cdp ), and hence it can be solved in FPT-time [Lenstra, Jr., 1983].

Observe that the number of different positions for the candidates is trivially bounded by the span plus 1.

Corollary 7. When every party suffers uniform cost, HD-NE is in FPT parameterized by span.

Theorem 8 (⋆). HD-NE admits an XP algorithm parameterized by discrepancy.

Proof Sketch. Similarly as in the proof of Theorem 6, we will refer to the set of candidates Ci of the party Πi as the type of the party Πi. The algorithm is again a dynamic programming along the space of the game [m]. For every j ∈ m we have an entry for every tuple (X, Y, aft, bef), where

• X = (xj-d, xj-d+1, . . . , xj+d) and xj ′ ∈ [|oj ′ |]; xj ′ represent the number of parties with strategy j ′ ;
• Y contains a number yt j ′ ∈ [|oj ′ |] for every j ′ in [j - d, j + d] and every t the type of some party Πi with i ∈ oj; yt j ′ represents the number of parties of type t with strategy j ′ .
• aft ∈ [j + d + 1,m] ∪ {∞} represents the position of the closest nominee selected as a strategy to the right of j + d (after j + d).
• bef ∈ {1, . . . , j}∪{-∞} represents the position of the closest nominee selected as a strategy to the left of j +1 (before j+1). In particular if for some j ′ ∈ [j-d, j] we have xj ′ > 0, then bef is the maximum j ′ ∈ [j - d, j] such that xj ′ > 0, else bef < j - d.

Now for every j ∈ [m] we will compute a table Γj that contains for every tuple (X, Y, aft, bef) either NONE or a partial strategy profile s that contains a strategy for every party Πi with ci1 ≤ j that is consistent with the tuple (X, Y, aft, bef). We say that s is consistent with (X, Y, aft, bef) if:

1. for j ′ ∈ [j -d, j], the number of parties with strategy j ′ is precisely xj ′ and for j ′ ∈ [j + 1, j + d] it is at most xj ′ ;
2. for j ′ ∈ [j - d, j, j + d] and type t, if Y contains yt j ′ , then the number of parties of type t with strategy j ′ is precisely yt j ′ ;
3. for every si ∈ s, if si ≤ j, then si ≤ bef, moreover there exists a party Πi′ with strategy bef in s;
4. every party with a strategy in s plays the best response if we assume in addition that the number of parties with strategy j ′ ∈ [j + 1, j + d] is precisely xj ′ , there exist at least xj ′ parties with candidate j ′ , and there is a party with candidate aft.

We finish the proof by showing that we need to consider only (ov+1)(2d+1)(1+22d+1 ) · (2d+1)2 many tuples, we can compute Γ0, and we can compute Γj+1 from Γj .

5 Conclusions

Our results show that natural constraints on the positions of the candidates can, in many cases, yield fixed-parameter tractable algorithms. To this end, there are several interesting questions that stem from our work. First, can we strengthen Theorem 6 by removing the assumption of uniform cost, or does the problem become W[1]-hard? Another question is whether HD-NE is in FPT parameterized by the discrepancy. A different direction is to combine the model from [Ben-Porat and Tennenholtz, 2019], where parties can choose more than one positions, with our model.

Another, really intriguing, question is the computation of mixed Nash equilibria; there each party chooses a candidate according to a probability distribution. Then, a Nash equilibrium always exists. In fact, in this case the problem becomes very interesting even if there are only two parties. If the parties have uniform costs, then the underlying game is constant sum and a Nash equilibrium can be computed via linear programming. On the other hand, if the parties suffer general costs, then it is not clear whether a polynomial-time algorithm exists, or the problem becomes PPAD-complete!