View in EDS

The complexity of online manipulation of sequential elections.

Saved in:
Bibliographic Details
Title: The complexity of online manipulation of sequential elections.
Authors: Hemaspaandra, Edith1, Hemaspaandra, Lane A.2, Rothe, Jörg3
Source: Journal of Computer & System Sciences. Jun2014, Vol. 80 Issue 4, p697-710. 14p.
Subjects: Computational complexity, Table manipulation (Computer science), Polynomials, Online education, Uniqueness (Mathematics), Completeness theorem, Social choice
Abstract: Abstract: Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that here manipulation can be extremely complex even for election systems with simple winner problems. We also show that for some of the most important election systems such manipulation is simple in certain settings. Among our highlights are: Depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first -completeness and -completeness results in computational social choice, in particular regarding 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections. [Copyright &y& Elsevier]
Copyright of Journal of Computer & System Sciences is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 94487613
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: The complexity of online manipulation of sequential elections.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Hemaspaandra%2C+Edith%22">Hemaspaandra, Edith</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Hemaspaandra%2C+Lane+A%2E%22">Hemaspaandra, Lane A.</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Rothe%2C+Jörg%22">Rothe, Jörg</searchLink><relatesTo>3</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Computer+%26+System+Sciences%22">Journal of Computer & System Sciences</searchLink>. Jun2014, Vol. 80 Issue 4, p697-710. 14p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Table+manipulation+%28Computer+science%29%22">Table manipulation (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Online+education%22">Online education</searchLink><br /><searchLink fieldCode="DE" term="%22Uniqueness+%28Mathematics%29%22">Uniqueness (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Completeness+theorem%22">Completeness theorem</searchLink><br /><searchLink fieldCode="DE" term="%22Social+choice%22">Social choice</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that here manipulation can be extremely complex even for election systems with simple winner problems. We also show that for some of the most important election systems such manipulation is simple in certain settings. Among our highlights are: Depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first -completeness and -completeness results in computational social choice, in particular regarding 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Computer & System Sciences is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=94487613
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.jcss.2013.10.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 14
        StartPage: 697
    Subjects:
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Table manipulation (Computer science)
        Type: general
      – SubjectFull: Polynomials
        Type: general
      – SubjectFull: Online education
        Type: general
      – SubjectFull: Uniqueness (Mathematics)
        Type: general
      – SubjectFull: Completeness theorem
        Type: general
      – SubjectFull: Social choice
        Type: general
    Titles:
      – TitleFull: The complexity of online manipulation of sequential elections.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Hemaspaandra, Edith
      – PersonEntity:
          Name:
            NameFull: Hemaspaandra, Lane A.
      – PersonEntity:
          Name:
            NameFull: Rothe, Jörg
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2014
              Type: published
              Y: 2014
          Identifiers:
            – Type: issn-print
              Value: 00220000
          Numbering:
            – Type: volume
              Value: 80
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Journal of Computer & System Sciences
              Type: main
ResultId 1