Metraipolis › archive › dc_e938792da419

Continuous Computational Social Choice: A Case Study in Bribery — arXiv:2608.25444

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.25444
License (as archived)
CC0-1.0
Archived
2026-10-18T03:58:07.701Z
SHA-256 of the archived text
62be4741f939d930ec0bc27418182e65d34d4ffa061f6b0233aa6d0059d7115e
Stable URL of this page
https://metraipolis.com/documento/dc_e938792da419

How to cite

Continuous Computational Social Choice: A Case Study in Bribery — arXiv:2608.25444 — arXiv (en), https://arxiv.org/abs/2608.25444 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e938792da419 (Metraipolis archive dc_e938792da419, sha256 62be4741f939d930ec0bc27418182e65d34d4ffa061f6b0233aa6d0059d7115e)
BibTeX
@misc{dce938792da419,
  title = {Continuous Computational Social Choice: A Case Study in Bribery — arXiv:2608.25444},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.25444},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e938792da419; sha256 62be4741f939d930ec0bc27418182e65d34d4ffa061f6b0233aa6d0059d7115e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.25444. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly models societies as composed of discrete agents. We propose to study computational social choice problems in a society continuum} setting, where a society is modeled as a distribution of infinitely many infinitesimal agents of different types. An analogous approach has been very useful in physics (it is the basis of statistical mechanics), economics (mean field games), and other fields. As an initial case study, we focus on election attacks (bribery and control), which have been extensively studied in the discrete setting. We show that a broad class of standard election attacks becomes polynomial-time solvable in the society continuum. The class contains problems that are NP-hard discretely, among them Borda- and Bucklin-CCDV and unit-cost Borda-SWAP BRIBERY. Furthermore, we give polynomial-time algorithms for $k$-Approval-SWAP BRIBERY when $k$ is constant for general costs, and when $k$ varies and the cost function is additively separable. The latter result contrasts with the discrete problem, which we prove NP-complete for additively separable costs and every fixed $k\ge 2$. In contrast, we prove that Borda-SWAP BRIBERY and $k$-Approval-SWAP BRIBERY, both with general costs, remain computationally hard in the society continuum. To obtain these results, we use both continuous and discrete optimization techniques, such as the Configuration LP framework and dynamic programming. Of particular note is the technique underlying our hardness proofs, which shows how to ''reverse the flow of hardness'' between LP formulations and pricing problems.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-27 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.25444 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T03:57:46.502Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-27?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).