How Hard Is the Manipulative Design of Scoring Systems?

Dorothea Baumeister, Tobias HogrebeIJCAI 2019 · DOI

TL;DR

This paper investigates the computational complexity of designing scoring systems for elections and competitions, specifically focusing on how easy it is to manipulate outcomes by altering the scoring rules. They introduce and analyze two decision problems, "Scoring System Existence" and "Close Scoring Systems," and demonstrate that while some scenarios are computationally tractable, others are NP-complete, highlighting the potential for subtle manipulation in real-world systems.

What Problem Does This Paper Address?

In many situations, from political elections to sports tournaments like Formula 1, a winner is determined by aggregating individual preferences or performance rankings. Scoring systems are a common method for this, assigning points to different ranks (e.g., 1st place gets more points than 2nd). The crucial question this paper tackles is: how easy is it for someone to design or subtly alter a scoring system to ensure a specific candidate wins, even if that candidate wouldn't naturally win under a standard system? This "manipulative design" is a concern when the scoring system itself can be influenced, potentially by external agents with vested interests. The authors explore the computational difficulty of such manipulation, both in theory and through a case study of Formula 1 data.

Methods

The paper approaches this problem from two angles: theoretical complexity analysis and experimental evaluation.

Theoretical Analysis: * Decision Problems: They formally define two decision problems: * SCORING SYSTEM EXISTENCE: Given a set of election profiles, can we find a scoring system that makes a specific candidate the unique winner? * D-CLOSE SCORING SYSTEM: Given an existing scoring system and a distance metric (like Manhattan or Euclidean distance), can we find a nearby scoring system that makes a specific candidate the unique winner? * Complexity Classes: They analyze the computational complexity of these problems using standard classes like P (polynomial time) and NP (non-deterministic polynomial time), and also delve into parameterized complexity (FPT and W[2]-hardness) to understand how complexity scales with specific parameters like the number of candidates or the distance limit. * Reductions: They use reductions from known NP-complete problems (like DOMINATING SET) to prove hardness results for their defined problems. * Linear Programming (LP): They leverage linear programming formulations to characterize the conditions under which a scoring system can achieve a desired outcome, showing that unrestricted cases are in P.

Experimental Evaluation: * Case Study: They apply their theoretical findings to real-world Formula 1 data from 1961 to 2008. * Distance Metrics: They use Minkowski distances (D¹, D², D∞) to measure how "close" a new scoring system is to the original one. * Restrictions: They test various natural restrictions on scoring systems (e.g., points must be non-increasing, last place gets zero points) to see how these affect the possibility of manipulation.

Datasets

The paper uses real-world data from Formula 1 seasons spanning 1961 to 2008. This dataset consists of race results for each season, where each result is a strict ordering of drivers. The authors note that they treat each season as a single election profile and do not consider special events like exclusions or penalties. They also mention using data available at PrefLib.org.

Key Insights and Ideas

  • The "Sweet Spot" of Manipulation: While some scoring system design problems are computationally easy (solvable in polynomial time), others become NP-complete or even W[2]-hard when certain constraints are introduced or when the "distance" of manipulation is considered. This suggests that there's a delicate balance: overly simple systems might be too rigid, but overly complex or unconstrained systems can be highly susceptible to manipulation.
  • "Perfect Winners" vs. System-Dependent Winners: In their Formula 1 case study, they identify "perfect winners" – candidates who would win under any reasonable scoring system that meets minimal criteria. Conversely, they find many instances where a different winner emerges with only a small change to the scoring system, demonstrating that the actual winner in many competitions is not inherently obvious but depends significantly on the chosen scoring rules.
  • The Importance of Constraints: The complexity of manipulative design is highly sensitive to the constraints placed on the scoring system. For instance, fixing a specific score value at a particular position can make the problem tractable, whereas allowing that value to vary can lead to NP-completeness. This highlights how specific design choices in scoring systems can either bolster or undermine their robustness.
  • Real-World Vulnerability: The Formula 1 case study provides empirical evidence that, in practice, small changes to scoring systems can indeed lead to different unique winners. This suggests that the theoretical findings about manipulative design have practical implications for the fairness and perceived legitimacy of competitions.

Key Results

  • Unrestricted SCORING SYSTEM EXISTENCE is in P: If there are no restrictions on the scoring vector (beyond basic monotonicity and non-negativity), it can be determined in polynomial time whether a scoring system exists to make a candidate win.
  • Restricted SCORING SYSTEM EXISTENCE is NP-complete: When natural restrictions are imposed (e.g., a fixed value at a specific position), the problem becomes NP-complete. Further, it can be W[2]-hard with respect to certain parameters like the distance limit.
  • D-CLOSE SCORING SYSTEM is NP-complete for integer scores: When trying to find a nearby scoring system (using integer scores and distance metrics), the problem is NP-complete. However, it remains in P for rational or real-valued scores.
  • Formula 1 Case Study:
    • For 43 out of 48 Formula 1 seasons analyzed (1961-2008), it was possible to find a different unique winner by slightly altering the scoring system, even with mild restrictions.
  • The minimum distance required to change the winner varied significantly across seasons, indicating varying degrees of "robustness" for the actual winner.
  • They identified "perfect winners" in some seasons, whose victory was independent of the specific scoring system used (as long as it met basic criteria).

Limitations and Future Work

  • Limitations:
    • The theoretical analysis often focuses on specific, sometimes simplified, restrictions on scoring vectors.
  • The Formula 1 case study, while insightful, treats each season as a single election profile and simplifies the real-world scoring system evolution.
  • The paper primarily focuses on unique winners; the non-unique winner case is mentioned as less interesting but could have its own nuances.
  • Future Work:
    • Investigate distributions of profiles based on predictions to maximize manipulation chances.
  • Explore axiomatic and game-theoretical aspects of manipulative design.
  • Consider the increasing influence of scoring systems in professional sports due to converging performance levels, making competitions more vulnerable.
  • Further analyze the parameterized complexity with respect to the distance limit K for D-CLOSE SCORING SYSTEM.

Summary updated

BibTeX
@inproceedings{baumeister2019how,
  author = {Dorothea Baumeister and Tobias Hogrebe},
  title = {{How Hard Is the Manipulative Design of Scoring Systems?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/11},
}
Figure