{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:14Z","timestamp":1740181574071,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T00:00:00Z","timestamp":1682640000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T00:00:00Z","timestamp":1682640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BA6270\/1-1"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"DOI":"10.1007\/s42979-023-01725-0","type":"journal-article","created":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T16:04:45Z","timestamp":1682697885000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Predicting Election Outcomes and Estimating Their Robustness"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6325-2879","authenticated-orcid":false,"given":"Dorothea","family":"Baumeister","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Hogrebe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,28]]},"reference":[{"key":"1725_CR1","unstructured":"Baumeister D, Hogrebe T. Complexity of Election Evaluation and Probabilistic Robustness: Extended Abstract. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020. p. 1771\u20131773. IFAAMAS."},{"key":"1725_CR2","doi-asserted-by":"crossref","unstructured":"Baumeister D, Hogrebe T. On the Complexity of Predicting Election Outcomes and Estimating Their Robustness. In: Proceedings of the 18th European Conference on Multiagent Systems, Springer; 2021. p. 228\u2013244.","DOI":"10.1007\/978-3-030-82254-5_14"},{"key":"1725_CR3","unstructured":"Ephrati E, Rosenschein J. Multi-Agent Planning as a Dynamic Search for Social Consensus. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence, Morgan Kaufmann; 1993. p. 423\u2013429 ."},{"key":"1725_CR4","doi-asserted-by":"crossref","unstructured":"Dwork C, Kumar R, Naor M, Sivakumar D. Rank Aggregation Methods for the Web. In: Proceedings of the 10th International Conference on World Wide Web, 2001. ACM p. 613\u2013622.","DOI":"10.1145\/371920.372165"},{"key":"1725_CR5","doi-asserted-by":"crossref","unstructured":"Ghosh S, Mundhe M, Hernandez K, Sen S. Voting for movies: the anatomy of a recommender system. In: Proceedings of the 3rd Annual Conference on Autonomous Agents, 1999. ACM p. 434\u2013435.","DOI":"10.1145\/301136.301303"},{"key":"1725_CR6","unstructured":"Cohen W, Schapire R, Singer Y. Learning to Order Things. In: Advances in Neural Information Processing Systems, The MIT Press; 1997. p. 451\u2013457."},{"key":"1725_CR7","unstructured":"Conitzer V, Sandholm T. Complexity of Manipulating Elections with Few Candidates. In: Proceedings of the 18th National Conference on Artificial Intelligence, AAAI Press; 2002. p. 314\u2013319."},{"key":"1725_CR8","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1017\/CBO9781107446984.011","volume-title":"Handbook of computational social choice","author":"C Boutilier","year":"2016","unstructured":"Boutilier C, Rosenschein J. Incomplete information and communication in voting. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia A, editors. Handbook of computational social choice. Cambridge: Cambridge University Press; 2016. p. 223\u201357 (Chap. 10)."},{"key":"1725_CR9","unstructured":"Walsh T. Uncertainty in preference elicitation and aggregation. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence, AAAI Press; 2007. p. 3\u20138."},{"issue":"8","key":"1725_CR10","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1016\/j.jcss.2010.04.002","volume":"76","author":"N Betzler","year":"2010","unstructured":"Betzler N, Dorn B. Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules. J Comput Syst Sci. 2010;76(8):812\u201336.","journal-title":"J Comput Syst Sci"},{"issue":"5","key":"1725_CR11","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.ipl.2011.11.016","volume":"112","author":"D Baumeister","year":"2012","unstructured":"Baumeister D, Rothe J. Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules. Inform Process Lett. 2012;112(5):186\u201390.","journal-title":"Inform Process Lett"},{"key":"1725_CR12","doi-asserted-by":"crossref","unstructured":"Bachrach Y, Betzler N, Faliszewski P. Probabilistic possible winner determination. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI Press; 2010. p. 697\u2013702.","DOI":"10.1609\/aaai.v24i1.7609"},{"issue":"3","key":"1725_CR13","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G Brightwell","year":"1991","unstructured":"Brightwell G, Winkler P. Counting linear extensions. Order. 1991;8(3):225\u201342.","journal-title":"Order"},{"key":"1725_CR14","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1093\/biomet\/44.1-2.114","volume":"44","author":"C Mallows","year":"1957","unstructured":"Mallows C. Non-null ranking models. Biometrika. 1957;44:114\u201330.","journal-title":"Biometrika"},{"issue":"1","key":"1725_CR15","first-page":"3783","volume":"15","author":"T Lu","year":"2014","unstructured":"Lu T, Boutilier C. Effective sampling and learning for Mallows models with pairwise-preference data. J Mach Learn Res. 2014;15(1):3783\u2013829.","journal-title":"J Mach Learn Res"},{"key":"1725_CR16","first-page":"1711","volume":"73","author":"D Tokaji","year":"2004","unstructured":"Tokaji D. The paperless chase: electronic voting and democratic values. Fordham Law Rev. 2004;73:1711.","journal-title":"Fordham Law Rev"},{"key":"1725_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2012.04.009","volume":"189","author":"N Hazon","year":"2012","unstructured":"Hazon N, Aumann Y, Kraus S, Wooldridge M. On the evaluation of election outcomes under uncertainty. Artif Intell. 2012;189:1\u201318.","journal-title":"Artif Intell"},{"key":"1725_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B. Computational complexity: a modern approach. Cambridge: Cambridge University Press; 2009."},{"key":"1725_CR19","volume-title":"Computational Complexity","author":"C Papadimitriou","year":"1994","unstructured":"Papadimitriou C. Computational Complexity. Boston: Addison-Wesley; 1994."},{"issue":"2","key":"1725_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant L. The complexity of computing the permanent. Theor Comput Sci. 1979;8(2):189\u2013201.","journal-title":"Theor Comput Sci"},{"issue":"5","key":"1725_CR21","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda S. PP is as hard as the polynomial-time hierarchy. SIAM J Comput. 1991;20(5):865\u201377.","journal-title":"SIAM J Comput"},{"key":"1725_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02295838","volume":"69","author":"J Doignon","year":"2004","unstructured":"Doignon J, Peke\u010d A, Regenwetter M. The repeated insertion model for rankings: missing link between two subset choice models. Psychometrika. 2004;69:33\u201354.","journal-title":"Psychometrika"},{"key":"1725_CR23","volume-title":"Rank Correlation Methods","author":"MG Kendall","year":"1962","unstructured":"Kendall MG. Rank Correlation Methods. 3rd ed. London: Theory & Applications of Rank Order-Statistics. C. Griffin; 1962.","edition":"3"},{"key":"1725_CR24","doi-asserted-by":"crossref","unstructured":"Baumeister D, Hogrebe T, Rey L. Generalized Distance Bribery. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI Press; 2019. p. 1764\u20131771.","DOI":"10.1609\/aaai.v33i01.33011764"},{"key":"1725_CR25","doi-asserted-by":"crossref","unstructured":"Kenig B Kimelfeld B. Approximate Inference of Outcomes in Probabilistic Elections. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI Press; vol. 33, 2019. p. 2061\u20132068.","DOI":"10.1609\/aaai.v33i01.33012061"},{"key":"1725_CR26","unstructured":"Awasthi P, Blum A, Sheffet O, Vijayaraghavan A. Learning Mixtures of Ranking Models. In: Advances in Neural Information Processing Systems, 2014. p. 2609\u20132617."},{"issue":"4","key":"1725_CR27","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H Hunt","year":"1998","unstructured":"Hunt H, Marathe M, Radhakrishnan V, Stearns R. The complexity of planar counting problems. SIAM J Comput. 1998;27(4):1142\u201367.","journal-title":"SIAM J Comput"},{"issue":"1","key":"1725_CR28","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/s00453-011-9568-4","volume":"64","author":"B Dorn","year":"2012","unstructured":"Dorn B, Schlotter I. Multivariate complexity analysis of Swap Bribery. Algorithmica. 2012;64(1):126\u201351.","journal-title":"Algorithmica"},{"issue":"2","key":"1725_CR29","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(92)90234-7","volume":"102","author":"P Dagum","year":"1992","unstructured":"Dagum P, Luby M. Approximating the permanent of graphs with large factors. Theor Comput Sci. 1992;102(2):283\u2013305.","journal-title":"Theor Comput Sci"},{"key":"1725_CR30","first-page":"104","volume":"34","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig D. Graphok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re. Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi Ertesito. 1916;34:104\u201319.","journal-title":"Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi Ertesito"},{"issue":"3","key":"1725_CR31","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0211043","volume":"11","author":"R Cole","year":"1982","unstructured":"Cole R, Hopcroft J. On edge coloring bipartite graphs. SIAM J Comput. 1982;11(3):540\u20136.","journal-title":"SIAM J Comput"},{"issue":"1","key":"1725_CR32","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0020-0190(02)00455-6","volume":"86","author":"S Kwek","year":"2003","unstructured":"Kwek S, Mehlhorn K. Optimal search for rationals. Inform Process Lett. 2003;86(1):23\u20136.","journal-title":"Inform Process Lett"},{"key":"1725_CR33","doi-asserted-by":"crossref","unstructured":"Lang J. Collective decision making under incomplete knowledge: Possible and necessary solutions. In: 29th International Joint Conference on Artificial Intelligence and 17th Pacific Rim International Conference on Artificial Intelligence, 2020. p. 4885\u20134891. ijcai.org.","DOI":"10.24963\/ijcai.2020\/680"},{"issue":"3","key":"1725_CR34","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1236457.1236461","volume":"54","author":"V Conitzer","year":"2007","unstructured":"Conitzer V, Sandholm T, Lang J. When are elections with few candidates hard to manipulate? J ACM (JACM). 2007;54(3):14 (ACM).","journal-title":"J ACM (JACM)"},{"key":"1725_CR35","doi-asserted-by":"crossref","unstructured":"Wojtas K, Faliszewski P. Possible Winners in Noisy Elections. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI Press; 2012. p. 1499\u20131505.","DOI":"10.1609\/aaai.v26i1.8255"},{"key":"1725_CR36","unstructured":"Imber A, Kimelfeld B. Probabilistic Inference of Winners in Elections by Independent Random Voters. In: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, IFAAMAS; 2021. p. 647\u2013655."},{"key":"1725_CR37","unstructured":"Shiryaev D, Yu L, Elkind E. On elections with robust winners. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, 2013. p. 415\u2013422. IFAAMAS."},{"key":"1725_CR38","doi-asserted-by":"crossref","unstructured":"Boehmer N, Bredereck R, Faliszewski P, Niedermeier R. Winner robustness via swap-and shift-bribery: Parameterized counting complexity and experiments. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021. p. 52\u201358. ijcai.org.","DOI":"10.24963\/ijcai.2021\/8"},{"key":"1725_CR39","unstructured":"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, 2020. p. 1341\u20131349. IFAAMAS"},{"issue":"3","key":"1725_CR40","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2892565","volume":"4","author":"I Caragiannis","year":"2016","unstructured":"Caragiannis I, Procaccia A, Shah N. When do noisy votes reveal the truth? ACM Trans Econ Comput. 2016;4(3):15.","journal-title":"ACM Trans Econ Comput"},{"key":"1725_CR41","unstructured":"de Weerdt M, Gerding E, Stein S. Minimising the Rank Aggregation Error. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, 2016. p. 1375\u20131376. IFAAMAS."},{"issue":"3","key":"1725_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2749463","volume":"16","author":"B Fazzinga","year":"2015","unstructured":"Fazzinga B, Flesca S, Parisi F. On the complexity of probabilistic abstract argumentation frameworks. ACM Trans Comput Logic (TOCL). 2015;16(3):1\u201339.","journal-title":"ACM Trans Computat Logic (TOCL)"},{"key":"1725_CR43","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.artint.2019.08.002","volume":"276","author":"H Aziz","year":"2019","unstructured":"Aziz H, Bir\u00f3 P, de Haan R, Rastegari B. Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artif Intell. 2019;276:57\u201378.","journal-title":"Artif Intell"},{"issue":"5","key":"1725_CR44","doi-asserted-by":"publisher","first-page":"1410","DOI":"10.1007\/s00453-019-00650-0","volume":"82","author":"H Aziz","year":"2020","unstructured":"Aziz H, Bir\u00f3 P, Gaspers S, de Haan R, Mattei N, Rastegari B. Stable matching with uncertain linear preferences. Algorithmica. 2020;82(5):1410\u201333.","journal-title":"Algorithmica"},{"issue":"4","key":"1725_CR45","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.jal.2015.03.004","volume":"13","author":"N Mattei","year":"2015","unstructured":"Mattei N, Goldsmith J, Klapper A, Mundhenk M. On the complexity of bribery and manipulation in tournaments with uncertain information. J Appl Logic. 2015;13(4):557\u201381.","journal-title":"J Appl Logic"},{"key":"1725_CR46","unstructured":"Baumeister D, Hogrebe T. Complexity of Scheduling and Predicting Round-Robin Tournaments. In: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, 2021. p. 178\u2013186. IFAAMAS."},{"issue":"4","key":"1725_CR47","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum J, Grohe M. The parameterized complexity of counting problems. SIAM J Comput. 2004;33(4):892\u2013922.","journal-title":"SIAM J Comput"},{"key":"1725_CR48","unstructured":"Baumeister D, Hogrebe T. On the Average-Case Complexity of Predicting Round-Robin Tournaments (Extended Abstract). In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022. p. 1542\u20131544. IFAAMAS."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-01725-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-023-01725-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-01725-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T15:16:37Z","timestamp":1687014997000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-023-01725-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,28]]},"references-count":48,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["1725"],"URL":"https:\/\/doi.org\/10.1007\/s42979-023-01725-0","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2023,4,28]]},"assertion":[{"value":"2 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"362"}}