Control complexity in Bucklin and fallback voting: An experimental analysis

Gábor Erdélyi, Michael R. Fellows, Jörg Rothe, Lena Schend

    Research output: Contribution to journalArticle

    8 Downloads (Pure)

    Abstract

    Control in elections models situations in which an external actor tries to change the outcome of an election by restructuring the election itself. The corresponding decision problems have been shown NP-hard for a variety of voting systems. In particular, in our companion paper [16], we have shown that fallback and Bucklin voting are resistant (in terms of NP-hardness) to almost all of the common types of control. While NP-hardness results for manipulation (another way of tampering with the outcomes of elections) have been challenged experimentally (see, e.g., the work of Walsh [38,37]), such an experimental approach is sorely missing for control. We for the first time tackle NP-hard control problems in an experimental setting. Our experiments allow a more fine-grained analysis and comparison - across various control scenarios, vote distribution models, and voting systems - than merely stating NP-hardness for all these control problems.

    Original languageEnglish
    Pages (from-to)661-670
    Number of pages10
    JournalJournal of Computer and System Sciences
    Volume81
    Issue number4
    DOIs
    Publication statusPublished - 1 Jun 2015

      Fingerprint

    Cite this