Isomorphic distances among elections. (English) Zbl 07603913
Fernau, Henning (ed.), Computer science – theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12159, 64-78 (2020).
Summary: This paper is an invitation to study the problem of measuring distances between elections, for the case where both the particular names of the candidates and the voters are irrelevant. In other words, we say that two elections are at distance zero (or, that they are isomorphic) if it is possible to make them identical by renaming their candidates and voters, and we are interested in measuring how far are two given elections from being isomorphic. The study of such distances has just begun and in this paper we outline why we believe that it is interesting and what are the natural research directions.
For the entire collection see [Zbl 1496.68017].
For the entire collection see [Zbl 1496.68017].
MSC:
| 68Qxx | Theory of computing |
Software:
PrefLibReferences:
| [1] | Arvind, V., Köbler, J., Kuhnert, S., Vasudev, Y.: Approximate graph isomorphism. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 100-111. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_12 · Zbl 1365.68464 · doi:10.1007/978-3-642-32589-2_12 |
| [2] | Babai, L., Dawar, A., Schweitzer, P., Torán, J.: The graph isomorphism problem (Dagstuhl seminar 15511). Dagstuhl Rep. 5(12), 1-17 (2015) |
| [3] | Bartholdi III, J., Tovey, C., Trick, M.: The computational difficulty of manipulating an election. Soc. Choice Welfare 6(3), 227-241 (1989) · Zbl 0682.90007 · doi:10.1007/BF00295861 |
| [4] | Bartholdi III, J., Tovey, C., Trick, M.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6(2), 157-165 (1989) · Zbl 0672.90004 · doi:10.1007/BF00303169 |
| [5] | Bartholdi III, J., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Modeling 16(8/9), 27-40 (1992) · Zbl 0757.90008 · doi:10.1016/0895-7177(92)90085-Y |
| [6] | Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016) · Zbl 1436.91001 |
| [7] | Brandt, F., Geist, C., Strobel, M.: Analyzing the practical relevance of voting paradoxes via Ehrhart theory, computer simulations, and empirical data. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2016), pp. 385-393 (2016) |
| [8] | Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R., Skowron, P., Talmon, N.: Robustness among multiwinner voting rules. In: Bilò, V., Flammini, M. (eds.) SAGT 2017. LNCS, vol. 10504, pp. 80-92. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66700-3_7 · Zbl 1403.91129 · doi:10.1007/978-3-319-66700-3_7 |
| [9] | Conitzer, V., Sandholm, T., Lang, J.: When are elections with few candidates hard to manipulate? J. ACM 54(3), Article 14 (2007) · Zbl 1292.91062 |
| [10] | Diaconis, P., Graham, R.: Spearman’s footrule as a measure of disarray. J. Roy. Stat. Soc. Ser. B 39(2), 262-268 (1977) · Zbl 0375.62045 |
| [11] | Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference (WWW-2001), pp. 613-622. ACM Press, March 2001 |
| [12] | Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 299-310. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04645-2_27 · Zbl 1262.91056 · doi:10.1007/978-3-642-04645-2_27 |
| [13] | Elkind, E., Faliszewski, P., Slinko, A.: Distance rationalization of voting rules. Soc. Choice Welfare 45(2), 345-377 (2015). https://doi.org/10.1007/s00355-015-0892-5 · Zbl 1341.91066 · doi:10.1007/s00355-015-0892-5 |
| [14] | Elkind, E., Gan, J., Obraztsova, S., Rabinovich, Z., Voudouris, A.: Protecting elections by recounting ballots. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-2019), pp. 259-265 (2019) · Zbl 1507.91075 |
| [15] | Erdélyi, G., Fellows, M., Rothe, J., Schend, L.: Control complexity in Bucklin and fallback voting: a theoretical analysis. J. Comput. Syst. Sci. 81(4), 632-660 (2015) · Zbl 1320.91055 · doi:10.1016/j.jcss.2014.11.002 |
| [16] | Erdélyi, G., Fellows, M., Rothe, J., Schend, L.: Control complexity in Bucklin and fallback voting: an experimental analysis. J. Comput. Syst. Sci. 81(4), 661-670 (2015) · Zbl 1320.91056 · doi:10.1016/j.jcss.2014.11.003 |
| [17] | Eğecioğlu, Ö., Giritligil, A.: The impartial, anonymous, and neutral culture model: a probability model for sampling public preference structures. J. Math. Sociol. 37(4), 203-222 (2013) · Zbl 1276.91047 · doi:10.1080/0022250X.2011.597012 |
| [18] | Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: How hard is bribery in elections? J. Artif. Intell. Res. 35, 485-532 (2009) · Zbl 1180.91090 · doi:10.1613/jair.2676 |
| [19] | Faliszewski, P., Skowron, P., Slinko, A., Szufa, S., Talmon, N.: How similar are two elections? In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI-2019), pp. 1909-1916 (2019) |
| [20] | Faliszewski, P., Slinko, A., Stahl, K., Talmon, N.: Achieving fully proportional representation by clustering voters. J. Heurist. 24(5), 725-756 (2018). https://doi.org/10.1007/s10732-018-9376-y · doi:10.1007/s10732-018-9376-y |
| [21] | Fishburn, P.: Condorcet social choice functions. SIAM J. Appl. Math. 33(3), 469-489 (1977) · Zbl 0369.90002 · doi:10.1137/0133030 |
| [22] | Goldsmith, J., Lang, J., Mattei, N., Perny, P.: Voting with rank dependent scoring rules. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI-2014), pp. 698-704 (2014) |
| [23] | Grohe, M., Rattan, G., Woeginger, G.: Graph similarity and approximate isomorphism. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018), pp. 20:1-20:16 (2018) · Zbl 1510.68076 |
| [24] | Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J. ACM 44(6), 806-825 (1997) · Zbl 0904.68111 · doi:10.1145/268999.269002 |
| [25] | Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5-6), 255-285 (2007) · Zbl 1168.91346 · doi:10.1016/j.artint.2007.01.005 |
| [26] | Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theoret. Comput. Sci. 349(3), 382-391 (2005) · Zbl 1086.68046 · doi:10.1016/j.tcs.2005.08.031 |
| [27] | Keller, O., Hassidim, A., Hazon, N.: New approximations for coalitional manipulation in scoring rules. J. Artif. Intell. Res. 64, 109-145 (2019) · Zbl 1454.91077 · doi:10.1613/jair.1.11335 |
| [28] | Konicki, C., Vassilevska Williams, V.: Bribery in balanced knockout tournaments. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2019), pp. 2066-2068 (2019) |
| [29] | Mattei, N., Forshee, J., Goldsmith, J.: An empirical study of voting rules and manipulation with large datasets. In: Proceedings of the 4th International Workshop on Computational Social Choice (COMSOC-2012) (2012) |
| [30] | Mattei, N., Walsh, T.: Preflib: a library for preferences. In: Proceedings of the 3nd International Conference on Algorithmic Decision Theory (ADT-2013), pp. 259-270 (2013) |
| [31] | Meskanen, T., Nurmi, H.: Closeness counts in social choice. In: Braham, M., Steffen, F. (eds.) Power, Freedom, and Voting. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-73382-9_15 |
| [32] | Nitzan, S.: Some measures of closeness to unanimity and their implications. Theory Decis. 13(2), 129-138 (1981) · Zbl 0452.90008 · doi:10.1007/BF00134214 |
| [33] | Procaccia, A., Rosenschein, J., Zohar, A.: On the complexity of achieving proportional representation. Soc. Choice Welfare 30(3), 353-362 (2008) · Zbl 1142.91024 · doi:10.1007/s00355-007-0235-2 |
| [34] | Redko, I., Vayer, T., Flamary, R., Courty, N.: Co-optimal transport. Technical report arXiv:2002.03731 [stat.ML], February 2020 |
| [35] | Shiryaev, D., Yu, L., Elkind, E.: On elections with robust winners. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2013), pp. 415-422 (2013) |
| [36] | Skowron, P., Faliszewski, P., Slinko, A.: Achieving fully proportional representation: approximability result. Artif. Intell. 222, 67-103 (2015) · doi:10.1016/j.artint.2015.01.003 |
| [37] | Szufa, S., Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Drawing a map of elections in the space of statistical cultures. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2020) (2020, to appear) |
| [38] | Tideman, T., Plassmann, F.: Modeling the outcomes of vote-casting in actual elections. In: Felsenthal, D., Machover, M. (eds.) Electoral Systems: Paradoxes, Assumptions, and Procedures, pp. 217-251. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-20441-8_9 |
| [39] | Walsh, T.: Where are the hard manipulation problems. J. Artif. Intell. Res. 42(1), 1-29 (2011) · Zbl 1234.68391 |
| [40] | Wang, J., Sikdar, S., Shepherd, T., Zhao, Z., Jiang, C., Xia, L.: Practical algorithms for multi-stage voting rules with parallel universes tiebreaking. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI-2019), pp. 2189-2196 (2019) |
| [41] | Xia, L.: Computing the margin of victory for various voting rules. In: Proceedings of the 13th ACM Conference on Electronic Commerce (EC-2012), pp. 982-999. ACM Press, June 2012 |
| [42] | Yin, Y., Vorobeychik, Y., An, B., Hazon, N.: Optimally protecting elections. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-2016), pp. 538-545 (2016) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
