How Hard Is the Manipulative Design of Scoring Systems?

1 Introduction

A common task in diverse situations is to choose a winner among a group of alternatives. If the underlying information consists of linear orders over the alternatives a usual approach is to use scoring systems. Here, each position is associated with a respective score value and the candidates with the highest scores are the winners. This approach is not only useful for elections in the classical sense, but also for other situations such as sports competitions. A Formula 1 season can be seen as an election where the candidates correspond to the drivers and the voters represent the placements for each race. Another example of a competition using scoring systems is the Eurovision Song Contest.

When designing such a scoring system some requirements obviously have to be respected. For example the points should be non-increasing from the first to the last place, and when considering sports tournaments it is often reasonable to have a significant distance between the front positions. Taking the scoring systems for the Formula 1 as an example, it can be observed that there were several changes over the years. When a lot of money and/or prestige is involved, it is particularly important to examine the manipulative design of scoring systems, since an external agent may therefore have an influence on manipulating the outcome.

∗A preliminary version of this paper appeared as an extended abstract in AAMAS2019.

We investigate this problem from two different perspectives. On the one hand we provide a theoretical background for the manipulative design of scoring systems and on the other hand we give an experimental evaluation of data from the Formula 1. We introduce the decision problem SCORING SYSTEM EXISTENCE which captures the simple setting where a manipulator seeks for a scoring system that makes some distinguished candidate win, regardless of any external requirements on the scores. As argued above, the existence of only weird scoring systems may not help, as there is no chance to implement them. So we additionally consider restrictions on the system. A slightly different approach is captured by the problem CLOSE SCORING SYSTEMS, where the choice of a new system is bounded by some given distance. This is especially important when an existing system will be changed since in most cases small changes will be accepted more easily. We study the computational complexity of both problems in several variants. Our results range from hardness results for NP and W[2] to polynomial-time algorithms that are obtained through linear programming approaches. In addition to the theoretical results, we also provide a case study on Formula 1 data. For all seasons from 1961 to 2008, we checked whether there exist scoring systems that result in a different winner. We show that there are years with perfect winners, i.e., the current winner is the only possible unique winner under every other scoring system that fulfills some very mild criteria, whereas in other years very small changes may already lead to a different winner. Hence the obtained results are also a measure of robustness of the actual winner.

2 Preliminaries

Formally an election is a pair (C, V ), with C being the set of candidates and V = (v1, . . . , vn) a profile of voters consisting of n linear orders over C. A scoring system used to define the winner of an election with m candidates is defined through the vector ⃗α = (α1, . . . , αm) ∈ Rm≥0 with α1 ≥ α2 ≥ · · · ≥ αm and α1 > αm. By score⃗α(C,V ) (c) = ∑ni=1 αpos(vi,c) we denote the number of points for candidate c in election (C, V ), where pos(v, c) is the position of candidate c in the linear order v. The candidates having the highest score are the winners. Prominent examples include the plurality rule, where only the first-placed candidate in each vote gets one point and thus has the scoring vector (1, 0, . . . , 0), or the Borda rule defined through the vector (m- 1,m- 2, . . . , 0). Beside usual elections, scoring systems are also used in competitions like the Eurovision Song Contest or the Formula 1. In Section 5 the data from Formula 1 races will be considered in detail with respect to the problems studied in this paper.

The score values are often restricted to natural numbers, however, we also consider the more general case of real numbers or rational numbers. We will show that this choice is crucial for determining the computational complexity. To facilitate our analysis we will use the following lemma that characterizes equivalent scoring rules.

Lemma 1. A scoring system ⃗α ∈ Rm≥0 is equivalent to a scoring system ⃗α′ ∈ Rm≥0 in terms of winner determination if and only if ⃗α′ = a · ⃗α + b with a ∈ R>0 and b ∈ R holds.

Lemma 1 implies that every scoring system can be transformed into an equivalent scoring system with αm = 0. Therefore, we will generally assume that αm = 0 holds. In our proofs we need to construct profiles that satisfy certain criteria on the scores of the candidates. This can be achieved by the following lemma. This is a slightly adapted version of the lemma by Betzler and Dorn [2010] (see also [Dey and Misra, 2017]), which is formulated over score differences rather than absolute scores. For a given profile V over C and a scoring vector ⃗α ∈ R|C| ≥0 we define the score difference between two candidates a, b ∈ C as sd⃗α(V,C) (a, b) = score⃗α(V,C) (a) - score⃗α(V,C) (b).

Lemma 2. Given a set of candidates C = {c1, c2, . . . , cm-2, p, e} and an integer matrix H = (hi,j)i=1,...,m-2, j=1,...,m-1 with H ∈ Zm-2×m-1 . One can construct a profile V = (v1, . . . , vn) such that evaluated by any scoring system ⃗α = (α1, α2, . . . , αm-1, 0) is satisfying sd⃗α(V,C) (e, p) < 0 and sd⃗α(V,C) (ci, p) = [hi,1]·α1+· · ·+[hi,m-1]·αm-1 for i ∈ {1, . . . ,m-2}, with n ∈ O(ˆh · m3 ) and ˆh = maxi∈{1,...,m-2},j∈{1,...,m-1} |hi,j |.

We assume that the reader is familiar with the basics of computational complexity, such as the classes P and NP. For further information we refer to the textbooks by Papadimitriou [1994] and Arora and Barak [2009]. In addition to classical complexity, we also study the parameterized complexity and obtain FPT results and W[2]-hardness. For further reading we refer to the textbooks by Downey and Fellows [1999] and by Flum and Grohe [2006].

In our constructions, we will make use of the NP-complete problem DOMINATING SET. An instance consists of an undirected graph G = (X, E) and an integer s ≤ |X|. The question is whether there exists a subset X′ ⊆ X with |X′ | ≤ s such that each xj ∈ X is either a member of X′ or shares an edge with a member of X′ . This problem is W[2]-hard with respect to the parameter s, the size of the dominating set (see [Downey and Fellows, 1999]). For our reductions, we will construct ILPs that are similar to the following direct ILP formulation of DOMINATING SET. Given a DOMINATING SET

instance consisting of G = (X, E) with X = {x1, . . . , xℓ} and integer s ≤ |X|. Let N[xj] denote the closed neighborhood of xj . An equivalent ILP is given as follows.

3 Scoring SystemExistence

As an election problem, we model the situation where the chair of the election seeks an alternative scoring system that guarantees the victory of a distinguished candidate for different possible profiles. This is, for example, the case if different opinion polls are known but there is some uncertainty about the real votes. A different application is the evaluation of (online) surveys, where the voting system used is initially unknown to the participants. The initiator may afterwards try to adjust the scores in order to ensure a victory for her preferred candidate or to support her hypothesis. To formally capture the idea of manipulation through the choice of the scoring vector we introduce the problem SCORING SYSTEM EXISTENCE.

We focus on the unique winner case. The non-unique winner case is less interesting, as vectors that assign nearly the same value to all positions are often a solution in the unconstrained case. In general, the approaches in the constrained case are technically more interesting for the unique winner case and can easily be broken down for the non-unique case. This decision problem is contained in NP for all variants considered here since for a given scoring vector the election can be evaluated efficiently. Therefore, we will only refer to the hardness in the later NP-completeness proofs.

Even though the formal definition uses the notions of elections, this problem also captures completely different settings, for example the Formula 1 or the Eurovision Song Contest. The task is again to figure out whether a change of the system, based on suspected placements or a subsequent change based on the actual placements, can guarantee certain outcomes. This question is particularly interesting if people in charge might have an interest in the success of a certain team because of preferences, arrangements, or bets. In Section 5 we will use real-world data to show that it is not unlikely in regular competitions to be able to replace the unique winner by changing the system only slightly. In all these cases, one has to keep in mind that arbitrary systems, which follow no idea or intuition, are suspicious and make a targeted modification of the system very obvious. Therefore, we consider certain restrictions of the scoring systems.

Related work. Our problem belongs to the group of election problems studied in computational social choice. Comparing it to the existing election problems, it is much closer to the different variants of control (see Bartholdi et al. [1992]), than to manipulation (see Bartholdi et al. [1989]) or bribery (see Faliszewski et al. [2009]), since the influence is on the chair and the election itself rather than on the voters or candidates. Baumeister et al. [2011] considered a special case of our problem, showing that SCORING SYSTEM EXISTENCE for one profile is NP-complete for (α1, ..., αm-4, x1, x2, x3, 0) with xi = 1 for at least one i ∈ {1, 2, 3}, if we a assume that the votes are given in succinct representation, i.e., instead of listing each vote separately the distinct votes are given with their corresponding multiplicity. We will strengthen this result by showing that even without the requirement of succinct representation, the problem is NP-complete for a variety of slightly constrained vectors. On the other hand, our results imply that their problem for unconstrained vectors can be solved efficiently. Elkind and Erd´elyi [2012] considered a related problem, in which the voting rule to be used will be chosen from a given set of rules, and the aim of the manipulator is to find a vote that ensures the victory of some distinguished candidate for all of the possible voting rules. Shiryaev et al. [2013] and Bredereck et al. [2017] studied the robustness of an election taking into account the minimum degree of change necessary regarding the votes to alter the outcome of the election. In contrast, we measure the amount of change in the scoring vector needed by using distances.

Complexity

We briefly outline the scenarios examined in the following. First, we consider the unrestricted case. Then, we investigate the complexity of vectors restricted to natural numbers using one of the simplest constraints: requiring a certain value at a given rear/front position in the vector. Our hardness results are formulated in the most restricted case and therefore also show hardness for the most general cases, e.g. where either the value, the position, or both are part of the input. For this case we also show that the problem is FPT regarding the number of candidates or regarding the total number of voters across all profiles. The main results for SCORING SYSTEM EXISTENCE are summarized in Table 1.

The first result is that without restrictions it can be checked in polynomial-time whether an alternative scoring system exists that makes the distinguished candidate the unique winner of all the elections.

Theorem 1. SCORING SYSTEM EXISTENCE is in P for ⃗α ∈ Rm≥0 , Qm≥0 , and Nm≥0 .

Proof. Let the profiles be Vj = (vj,1, vj,2, . . . , vj,nj ) for 1 ≤ j ≤ N. From the definition of a scoring system and the properties of a scoring vector, the following linear program (LP) can be easily derived. This LP is solvable, if and only if there exists a system in which p becomes the unique winner with a minimum advantage of ϵ > 0 in each of the elections.

The choice of ϵ restricts the possible scoring vectors, but nevertheless, in order to check whether any vector exists at all, the actual value of ϵ is irrelevant: As the advantage is proportional to the scaling of the vector, by Lemma 1 we can always obtain an equivalent vector guaranteeing a minimum advantage of ϵ, if one exists at all. Therefore, ϵ can be chosen arbitrarily and we choose ϵ = 1 by default.

LPs can be solved efficiently depending on the number of variables and on the length of the input (see [Karmarkar, 1984] and [Adler et al., 1989]). The output of these algorithms is always rational for rational inputs, whereby a rational scoring vector exists if there exists one at all. Therefore, by applying Lemma 1, we can also receive an equivalent integer scoring vector by scaling if there exists one at all.

Through Lemma 1, rational vectors can always be reshaped to contain a certain value at a given position. However this does not hold for integer vectors, and this is what we now focus on. In this case, SCORING SYSTEM EXISTENCE is already getting hard if one specific value on some fixed rear position is required in the vector. Note that the position, as well as the specific value, are independent of the actual input.

Theorem 2. Let k ∈ N≥1 and γ ∈ N≥1 be some fixed values. SCORING SYSTEM EXISTENCE is NP-complete if the scoring vector ⃗α ∈ Nm≥0 for m > k candidates has to satisfy αm-k = γ.

Proof. NP-hardness will be shown by a reduction from DOMINATING SET. Assume we are given a DOMINATING SET instance G = (X,E) with X = {x1, x2, . . . , xℓ} and an integer s ≤ |X|. We construct an election with the set of candidates C = {p, e, g} ∪ A ∪ B ∪ D, where A = {a1, . . . , aℓ}, B = {b1, . . . , bℓ}, and dummy candidates D = {d1, . . . , dk+1}. The preferred candidate is p. According to Lemma 2 we construct the profile V that ensures the following score differences, where we choose p and e respectively. For each aj, 1 ≤ j ≤ ℓ: sd⃗α(C,V ) (aj, p) = [γ] · α(m-k)-j - [γ] · α(m-k)-(j-1) - [2] · αm-k, for each bj, 1 ≤ j ≤ ℓ: sd⃗α(C,V ) (bj, p) = [χj(x1)] · α(m-k) - [χj (xℓ)] · α(m-k-l) + ∑ℓ-1 i=1 [χj(xi+1) -χj(xi)] ·α(m-k)-i with χj denoting the characteristic function of N[xj], and sd⃗α(C,V ) (g, p) = [γ] · α(m-k)-ℓ - [s + 1 + γ] · αm-k.

For each dj ∈ D we set sd⃗α(C,V ) (dj, p) to be negative. Therefore, for the candidates in {e} ∪D the score difference to p is less than zero, i.e., they have fewer points than p irrespective of the entries in the scoring vector.

We will now show that a scoring vector of the required form making p the unique winner exists for the constructed instance if and only if a dominating set with at most s vertices exists for the given instance. We begin with equivalences regarding the solvability of the instance. If p is the unique winner of the election, the score difference sd⃗α(C,V ) (c, p) for all candidates c ∈ C \ {p} has to be negative. This already holds for e and the candidates in D, hence we only have to focus on the score differences of the candidates in A ∪ B ∪ {g}. Recall that γ = αm-k holds. For each aj, 1 ≤ j ≤ ℓ, we have: 0 > [γ] · α(m-k)-j - [γ] · α(m-k)-(j-1) - [2] · αm-k ⇔ α(m-k)-(j-1) + 1 ≥ α(m-k)-j. Taking into account the monotonicity, each α(m-k)-j can have exactly two distinct values: α(m-k)-(j-1) or α(m-k)-(j-1) + 1. For each bj, 1 ≤ j ≤ ℓ, we have: 0 > [χj(x1)] · α(m-k) - [χj (xℓ)] · α(m-k-l) + ∑ℓ-1 i=1 [χj(xi+1) -χj(xi)] · α(m-k)-i ⇔ 1 ≤ ∑xi∈N[xj ] (α(m-k)-i - α(m-k)-(i-1) ) . And for g we have: 0 > [γ] ·α(m-k)-ℓ-[s+1+γ] ·αm-k ⇔ s ≥ α(m-k)-ℓ - αm-k. To summarize, a scoring vector of the required form making p the unique winner exists for the constructed instance if and only if there exists a scoring vector fulfilling the following restrictions.

The values not considered so far, namely α1, α2, . . . , α(m-k)-ℓ-1 and α(m-k)+1, α(m-k)+2, . . . , αm, do not have an influence on the score differences between p and the candidates that could prevent p from being the unique winner, hence their actual value is insignificant as long as they comply with the monotonicity of the scoring vector. Note that the above set of inequalities is equivalent to the ILP formulation of DOMINATING SET given previously regarding feasibility: (1) ensures that every α(m-k)-j can have two different values depending on the previous values, namely α(m-k)-(j-1) indicating that xj /∈ X′ or α(m-k)-(j-1) + 1 indicating that xj ∈ X′ . (2) ensures for each vertex xj either xj or at least one of its neighbors is covered by X′ . (3) with α(m-k)-ℓ -αm-k equaling the number of values set to their upper values ensures that |X′ | ≤ s holds.

Therefore, a scoring vector of the required form making p the unique winner exists for the SCORING SYSTEM EXISTENCE instance if and only if a dominating set with at most s vertices exists for the DOMINATING SET instance.

Note that in this proof only one profile is needed to establish NP-hardness of the problem. In sharp contrast to the previous result, we now show that if some value at some front position is fixed in advance the problem remains solvable in polynomial time. This includes, for example, the case where the maximum number of points to be given has been limited from the outset. However if the value is not fixed in advance but part of the input, this problem is W[2]-hard.

Theorem 3. Let k ∈ N≥1 and γ ∈ N≥1 be some fixed values. SCORING SYSTEM EXISTENCE is in P if the scoring vector ⃗α ∈ Nm≥0 for m ≥ k candidates has to satisfy αk = γ. If γ is not fixed in advance, the problem is NP-complete and W[2]-hard with respect to γ.

The proof is omitted due to space restrictions. For the hardness, the idea is to use additional candidates to enforce the conditions in which one can apply the reduction of Theorem 2. For this, we set γ to be s + 1 whereby the NPand W[2]-hardness follows from the respective hardness of DOMINATING SET. Again, only one profile is necessary to establish the NP- and W[2]-hardness. Now, we will consider the parameterized complexity of the problem with respect to the number of candidates and voters. For this, we consider the more general case of the problem where a specific value and its position itself may be part of the input. Note that an efficiency result for this case also applies to the restricted cases studied before where k and αk or αm-k are fixed.

Theorem 4. SCORING SYSTEM EXISTENCE with ⃗α ∈ Nm≥0 , αk = γ ∈ N≥1 and k ∈ {1, . . . ,m-1} as part of the input is FPT with respect to the number of candidates or with respect to the total number of voters.

Proof sketch. Regarding the number of candidates, the corresponding ILP (see proof of Theorem 1, with γ as part of the input and αm = 0, contains only m- 2 variables to be determined.

Regarding the total number of voters, the proof is based on the fact that for the solvability of the instance, one only has to consider the values of the vector on which positions p has been placed in at least one of the votes. All other values can be decreased to γ, 0, or the next of those values, as this only reduces the score of candidates other than p. Therefore, we have to consider an ILP with at most n variables, with n being the total number of voters.

In both cases, ILPs are FPT regarding the number of variables (see [Lenstra, 1983]), the problem is FPT regarding the number of candidates or the total number of voters.

Interestingly, one can show that in the case where the number of profiles is variable, but the number of voters per profile is bounded by a constant depending on γ, the problem is again hard once you fix only one value, even if it is constant at a constant position from the bottom. This special case is motivated by the fact that in (sports) competitions the number of jurors per event or races per season is mostly constant.

4 Closest Scoring System

So far we considered only very mild restrictions on the scoring vectors. However, the manipulator may wish to limit the changes to the scores. Formally this can be modeled by measuring the difference between the original and the new scoring system by some appropriate distance. We will use the following Minkowski distances to compare scoring systems.

Definition 1. The Manhattan distance D1 , the Euclidean distance D2 , and the Chebyshev distance D∞ for two vectors ⃗x, ⃗y ∈ Rm with ⃗x = (x1, x2, . . . , xm) and ⃗y = (y1, y2, . . . , ym) are defined as follows:

In terms of scoring systems, the Manhattan distance measures the total change at given points per position and thereby the overall adjustments to the vector. The Chebyshev distance takes into account only the largest deviation. With regard to this distance, it is advantageous to distribute the adjustments to the scoring vector. The Euclidean distance combines both approaches, measuring the total change while heavily weighting larger deviations of individual entries. This motivates again the minimization of the overall adjustments to the vector while distributing the adjustments to the entire vector.

The problem we will focus on asks whether there is an alternative scoring system making the distinguished candidate the unique winner, while the distance between the two vectors is bounded. For a distance D on arbitrary sized vectors, the problem is formally defined as follows.

D-CLOSE SCORING SYSTEM

Again, the problem D-CLOSE SCORING SYSTEM is contained in NP, for all distances considered here. In the previous section we showed that the unrestricted variant of SCORING SYSTEM EXISTENCE can be solved in polynomial time. For D-CLOSE SCORING SYSTEM this still holds if the vector consists of real numbers or rational numbers.

Theorem 5. D-CLOSE SCORING SYSTEM for ⃗α, ⃗α′ ∈ Qm≥0 or Rm≥0 , and Minkowski distances D1 , D2 , and D∞ is in P.

The proof modifies the LP from the proof of Theorem 1 but is omitted due to space restrictions. In the following, we will show that the problem is hard when the scoring vectors are restricted to natural numbers. Nevertheless, if we want to solve the problem in practice, we can interpret the LP together with the distance optimization used in the proof of Theorem 5 as an ILP.

Theorem 6. D-CLOSE SCORING SYSTEM for ⃗α, ⃗α′ ∈ Nm≥0 and Minkowski distances D1 , D2 , and D∞ is NP-complete.

The proof is omitted due to space restrictions and its similarity to the proof of Theorem 2. For the instances constructed in the proof of Theorem 6 there does always exist a scoring vector making p the unique winner. We have shown that if the instance is not solvable with αm-1 = 1, the necessary distance increases at least by a factor of ℓ. Based on these two arguments, it can be shown that for the problem for D1 , D2 , and D∞, no efficient constant-factor approximation algorithm for the distance can exist, unless P = NP.

Now, we present an analysis of the parameterized complexity of the problemwith respect to the distance limit. Note that the proof of Theorem 6 includes that the problem with respect to D∞ is NP-complete even for a constant distance limit of K = 1. Therefore we will know focus on the parameterized complexity of the problem regarding D1 and D2 .

Theorem 7. Let K ∈ R≥0 be some fixed value. D-CLOSE SCORING SYSTEM for ⃗α, ⃗α′ ∈ Nm≥0 and Minkowski distances D1 and D2 is in P. If K is not fixed in advance, the problem is W[2]-hard with respect to K.

Proof sketch. The proof ofW[2]-hardness is already included in the proof of Theorem 6, as DOMINATING SET is W[2]- hard with respect to s and we used K = s for D1 and D2 . It remains to prove that the problem can be solved efficiently for a constant K. It can be shown that for a constant K, the number of vectors to be considered within D1 or D2 distance K is bounded by a polynomial depending on m. Since those vectors can be efficiently generated, one can check for all the vectors, whether they are monotone and non-negative, and if so whether p becomes the unique winner by one of them.

5 Experiments

In addition to the theoretical results presented so far, we investigated the manipulative design of scoring systems in a case study. Our aim was to identify how relevant the problem presented here is, in other words, how likely it is that with small changes to the system, one can change the outcome of an election or competition.

We consider real-life competition data from the Formula 1 from the seasons 1961 to 2008. To be precise, we use the version of the data available at PrefLib.org [Mattei and Walsh, 2013]. There exists a list of race results for each season, with each race result consisting of a strict order of drivers who have completed the race with all other drivers being tied on the last position. Since we examine fixed results here, not predictions, each instance contains exactly one profile. In the provided seasons the Formula 1 used the following scoring systems: ⃗α = (9, 6, 4, 3, 2, 1, 0, . . . , 0) in 1961-1990, (10, 6, 4, 3, 2, 1, 0, . . . , 0) in 1991-2002, and (10, 8, 6, 5, 4, 3, 2, 1, 0, . . . , 0) in 2003-2008.

Until 1991, not a stand-alone scoring system was used, as only a certain number of the best results of a driver were

1961

1962

1963

1964

1965

1966

1967

1968

1969

1970

1971

1972

1973

1974

1975

1976

1977

1978

1979

1980

1981

1982

1983

1984

(I.) 12 -

- 2 2 12 2 8 21 3 19 11 20 2 34 2 10 5 3 10 1 4 2 2

(II.)

-

-

- 2 2 - 2 -

- 3 -

-

- 2 - 2 10 5 3 10 1 4 2 2

(III.) -

-

- 8 4 - 5 -

-

-

-

-

- 4 - 2 22 - 16 - 6 9 2 -

counted. To keep the results consistent, we will however count all races of a season. In addition, we will also not consider special events such as exclusions or penalties. Thus, we treat the data as it is. The data-set contains 48 seasons, with the number of drivers (candidates) varying between 22 and 62, and the number of races (voters) between 8 and 19.

We used the LP formulation presented in the proof of Theorem 1 to test whether it is possible to change the current winner by using a different integer scoring system. We proposed several natural restrictions on the possible vector while minimizing its Manhattan distance D1 to the original system.

In Table 2 we list the minimum D1 distance from ⃗α to a vector ⃗α′ with another unique winner, and "-" denotes that it is not possible. For this we consider three different strong natural restrictions on the vector.

• (I.) α′j = 0 for each position j ∈ {1, . . . ,m} that is tied with the last position at least once in the given profile.
• (II.) α′j = 0 for each position j ∈ {1, . . . , m} with αj = 0.

Restriction (I.) is a prerequisite and only affects the last positions. All drivers who are tied on the last position must receive 0 points. Restriction (II.) ensures that candidates who get no points in the original system should not get points in the new system. Restriction (III.) enforces that the point differences in between the top positions are non-decreasing. All of these properties are derived from scoring systems used in practice and are basic properties that an appropriate scoring system should fulfill. For the exact solution, we have implemented the LP from the proof of Theorem 1 as an ILP with ϵ = 1 including the D1 formulation from Theorem 5 and additionally added requirement (I.), (II.), or (III.). The ILP was then solved using CPLEX, with the solution requiring only a fraction of a second per profile on a standard machine.

Considering almost unrestricted scoring systems by only requiring property (I.), the unique winner could be replaced in 43 out of 48 seasons. The maximum number of possible other unique winners was 6. Often, drivers who had no chance of winning in the original system could become the unique winner in a system with widely distributed points. Interestingly, even in this unrestricted case, in some years, the winner is determined solely by the decision to use a scoring system, regardless of what the actual system is. For example, in 1991, 1993 and 2002, there was no other system with a unique winner apart from Senna, Prost, and Schumacher respectively. We call these winners perfect winners because they do not depend on the system itself, but only on the minimal requirement from restriction (I.). A weakening of this property is the perfect winner regarding certain restrictions. For example, in 1998, as soon as one demands that only the first 6 drivers get points at all, i.e., we consider restriction (II.), H¨akkinen was the only possible unique winner. If restriction (III.) is demanded, in 27 of the 48 seasons the unique winners are already fixed without considering the actual values. Nevertheless, some of the results were highly dependent on the system used. In 2008, Massa would have been the unique winner if (12, 8, 6, 5, 4, 3, 2, 1, 0, . . . , 0) would have been used instead of (10, 8, 6, 5, 4, 3, 2, 1, 0, . . . , 0) highlighting the first place just slightly more, similar to as it has been done in the previous systems. On the other hand, in 2003 and 2007 the unique winner would have been R¨aikk¨onen and Alonso respectively if (8, 7, 6, 5, 4, 3, 2, 1, 0, . . . , 0) would have been used. To summarize, the experiments show that there is a potential for the manipulative design of scoring systems one should be aware of.

6 Conclusions

In this paper, we provide a general framework to study the manipulative design of scoring systems in diverse situations. A direct extension of the problem would be to consider distributions of profiles based on predictions in which we want to maximize the chances of success. Furthermore, an axiomatic and game theoretical investigation of the problem is very interesting. For the above-mentioned possibilities, the basic complexity usually follows directly from the results presented here. Finally, we assume that with the increasing convergence of performances in professional sports, the influence of the actual scoring system on the outcome of the competitions grows (see [Berthelot et al., 2015]). This also makes the competitions more vulnerable.

Acknowledgments

This work is supported by the DFG-grant BA6270/1-1.