Computational aspects of strategic behaviour in elections with top-truncated ballots
Tóm tắt
Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. Much of this literature, however, makes the assumption that the voters or agents specify a complete preference ordering over the set of candidates. There are many multiagent systems applications, and even real-world elections, where this assumption is not warranted, and this in turn raises a series of questions on the impact of partial voting on the complexity of manipulative actions. In this paper, we focus on two of these questions. First, we address the question of how hard it is to manipulate elections when the agents specify only top-truncated ballots. Here, in particular, we look at the weighted manipulation problem—both constructive and destructive manipulation—when the voters are allowed to specify top-truncated ballots, and we provide general results for all scoring rules, for elimination versions of all scoring rules, for the plurality with runoff rule, for a family of election systems known as Copeland
$$^{\alpha }$$
, and for the maximin protocol. The second question we address is the impact of top-truncated voting on the complexity of manipulative actions in electorates with structured preference profiles. In particular, we consider electorates that are single-peaked and we show how, for many voting protocols, allowing top-truncated voting reimposes the
$$\mathcal {NP}$$
-hardness shields that normally vanish in such electorates.
Tài liệu tham khảo
Barberá, S. (2007). Indifferences and domain restrictions. Analyse & Kritik, 29(2), 146–162.
Bartholdi, J., & Trick, M. A. (1986). Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4), 165–169.
Bartholdi, J. J., Tovey, C. A., & Trick, M. A. (1992). How hard is it to control an election? Mathematical and Computer Modelling, 16(8–9), 27–40.
Bartholdi, J. J, I. I. I., & Orlin, J. B. (1991). Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4), 341–354.
Bartholdi, J. J, I. I. I., Tovey, C. A., & Trick, M. A. (1989). The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3), 227–241.
Baumeister, D., Faliszewski, P., Lang, J., & Rothe, J. (2012). Campaigns for lazy voters: Truncated ballots. In Proceedings of the 11th international conference on autonomous agents and multiagent systems (AAMAS), pp. 577–584.
Black, D. (1948). On the rationale of group decision-making. The Journal of Political Economy, 56(1), 23–34.
Black, D., Newing, R. A., McLean, I., McMillan, A., & Monroe, B. L. (1958). The theory of committees and elections. Berlin: Springer.
Brandt, F., Brill, M., Hemaspaandra, E., & Hemaspaandra, L. A. (2015). Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 53, 439–496.
Briskorn, D., Erdélyi, G., & Reger, C. (2015). Bribery under partial information. In Proceedings of the 2nd workshop on exploring beyond the worst case in computational social choice (EXPLORE).
Cantala, D. (2004). Choosing the level of a public good when agents have an outside option. Social Choice and Welfare, 22(3), 491–514.
Coleman, T., & Teague, V. (2007). On the complexity of manipulating elections. In Proceedings of the 13th Australasian symposium on theory of computing, pp. 25–33.
Conitzer, V., Sandholm, T., & Lang, J. (2007). When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3), 14.
Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of computational social choice. Cambridge: Cambridge University Press.
Copeland, A. H. (1951). A reasonable social welfare function. In Seminar on applications of mathematics to social sciences. University of Michigan
Dey, P., Misra, N., & Narahari, Y. (2016). Complexity of manipulation with partial information in voting. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI), pp. 229–235.
Doignon, J. P., & Falmagne, J. C. (1994). A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms, 16(2), 218–233.
Duggan, J., & Schwartz, T. (2000). Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized. Social Choice and Welfare, 17(1), 85–93.
Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (2001). Rank aggregation methods for the web. In Proceedings of the 10th international conference on world wide web, pp. 613–622
Emerson, P. (2013). The original Borda count and partial voting. Social Choice and Welfare, 40(2), 353–358.
Ephrati, E., & Rosenschein, J. S. (1993). Multi-agent planning as a dynamic search for social consensus. In Proceedings of the 13th international joint conference on artificial intelligence (IJCAI), vol. 93, pp. 423–429.
Erdélyi, G., & Reger, C. (2016). Possible bribery in k-approval and k-veto under partial information. In Proceedings of the international conference on artificial intelligence: methodology, systems, and applications (AIMSA), Berlin: Springer, pp. 299–309.
Erdélyi, G., Lackner, M., & Pfandler, A. (2013). Computational aspects of nearly single-peaked electorates. In Proceedings of the 27th AAAI conference on artificial intelligence (AAAI), pp. 283–289.
Escoffier, B., Lang, J., & Öztürk, M. (2008). Single-peaked consistency and its complexity. In Proceedings of the 18th European conference on artificial intelligence (ECAI), pp. 366–370.
Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2009a). How hard is bribery in elections? Journal of Artificial Intelligence Research, 35, 485–532.
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L. A., & Rothe, J. (2009b). Llull and copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research, 35, 275–341.
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L. A., & Rothe, J. (2009). A richer understanding of the complexity of election systems. In Fundamental problems in computing, Berlin: Springer, pp. 375–406.
Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2010). Using complexity to protect elections. Communications of the ACM, 53(11), 74–82.
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L. A., & Rothe, J. (2011). The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 209(2), 89–107.
Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2014). The complexity of manipulative attacks in nearly single-peaked electorates. Artificial Intelligence, 207, 69–99.
Fishburn, P. C. (1977). Condorcet social choice functions. SIAM Journal on applied Mathematics, 33(3), 469–489.
Fitzsimmons, Z. (2015). Single-peaked consistency for weak orders is easy. In Proceedings of the 15th conference on theoretical aspects of rationality and knowledge (TARK), pp. 127–140.
Fitzsimmons, Z., & Hemaspaandra, E. (2015). Complexity of manipulative actions when voting with ties. In Proceedings of the 4th international conference on algorithmic decision theory (ADT), pp. 103–119.
Fitzsimmons, Z., & Hemaspaandra, E. (2016). Modeling single-peakedness for votes with ties. In Proceedings of the 8th European starting AI researcher symposium (STAIRS), pp. 63–74.
Friedgut, E., Kalai, G., & Nisan, N. (2008). Elections can be manipulated often. In 2008 49th Annual IEEE symposium on foundations of computer science, IEEE, pp. 243–249.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W. H. Freeman & Co.
Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica: Journal of the Econometric Society, 41(4), 587–601.
Hemaspaandra, E., & Hemaspaandra, L. A. (2007). Dichotomy for voting systems. Journal of Computer and System Sciences, 73(1), 73–83.
Konczak, K., & Lang, J. (2005). Voting procedures with incomplete preferences. In Proceedings of the IJCAI-05 multidisciplinary workshop on advances in preference handling.
Lackner, M. (2014). Incomplete preferences in single-peaked electorates. In Proceedings of the 28th AAAI conference on artificial intelligence (AAAI), pp. 742–748.
Lu, T., & Boutilier, C. (2013). Multi-winner social choice with incomplete preferences. In Proceedings of the 23rd international joint conference on artificial intelligence (IJCAI), AAAI Press, pp. 263–270.
Narodytska, N., & Walsh, T. (2014). The computational impact of partial votes on strategic voting. In Proceedings of the 21st European conference on artificial intelligence (ECAI), pp. 657–662.
Niemi, R. G., & Wright, J. R. (1987). Voting cycles and the structure of individual preferences. Social Choice and Welfare, 4(3), 173–183.
Niou, E. M. (1987). A note on Nanson’s rule. Public Choice, 54(2), 191–193.
Pennock, D. M., Horvitz, E., & Giles, C. L. (2000). Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering. In Proceedings of the 17th National conference on artificial intelligence (AAAI), pp. 729–734.
Satterthwaite, M. A. (1975). Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2), 187–217.
Walsh, T. (2007). Uncertainty in preference elicitation and aggregation. In Proceedings of the 22nd AAAI conference on artificial intelligence (AAAI), vol 7, pp. 3–8.
Xia, L., & Conitzer, V. (2011). Determining possible and necessary winners under common voting rules given partial orders. Journal of Artificial Intelligence Research, 41(2), 25–67.
Yang, Y. (2015). Manipulation with bounded single-peaked width: A parameterized study. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS), pp. 77–85.