Report
The Complexity of Online Bribery in Sequential Elections (Extended Abstract)
| العنوان: | The Complexity of Online Bribery in Sequential Elections (Extended Abstract) |
|---|---|
| المؤلفون: | Hemaspaandra, Edith, Hemaspaandra, Lane A., Rothe, Jörg |
| المصدر: | EPTCS 297, 2019, pp. 233-251 |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory, Computer Science - Computational Complexity, Computer Science - Multiagent Systems |
| الوصف: | Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all voters' votes. But neither of those assumptions always holds. In many real-world settings, votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to bribe/alter a given vote, and at the time of making that decision, the briber may not know what votes remaining voters are planning on casting. In this paper, we introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is polynomial-time computable, an online, sequential setting may vastly increase the complexity of bribery, in fact jumping the problem up to completeness for high levels of the polynomial hierarchy or even PSPACE. On the other hand, we show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems in the online, sequential setting. Comment: In Proceedings TARK 2019, arXiv:1907.08335. arXiv admin note: text overlap with arXiv:1906.08308 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4204/EPTCS.297.16 |
| URL الوصول: | http://arxiv.org/abs/1907.09108 |
| رقم الانضمام: | edsarx.1907.09108 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4204/EPTCS.297.16 |
|---|