Using Weighted Matching to Solve 2-Approval/Veto Control and Bribery

Zack Fitzsimmons, Edith Hemaspaandra
5/26/2023
cs.GTcs.CCcs.MA

No confident code implementation found for this paper.

Abstract

Determining the complexity of election attack problems is a major research direction in the computational study of voting problems. The paper "Towards completing the puzzle: complexity of control by replacing, adding, and deleting candidates or voters" by Erdélyi et al. (JAAMAS 2021) provides a comprehensive study of the complexity of control problems. The sole open problem is constructive control by replacing voters for 2-Approval. We show that this case is in P, strengthening the recent RP (randomized polynomial-time) upper bound due to Fitzsimmons and Hemaspaandra (IJCAI 2022). We show this by transforming 2-Approval CCRV to weighted matching. We also use this approach to show that priced bribery for 2-Veto elections is in P. With this result, and the accompanying (unsurprising) result that priced bribery for 3-Veto elections is NP-complete, this settles the complexity for $k$-Approval and $k$-Veto standard control and bribery cases.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{fitzsimmons2023using,
  title  = {Using Weighted Matching to Solve 2-Approval/Veto Control and Bribery},
  author = {Zack Fitzsimmons and Edith Hemaspaandra},
  year   = {2023},
  eprint = {2305.16889},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2305.16889v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2305.16889.svg)](https://codeofpaper.com/paper/2305.16889)

Discussion