{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T04:45:15Z","timestamp":1750394715896,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031228315"},{"type":"electronic","value":"9783031228322"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22832-2_19","type":"book-chapter","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T09:05:33Z","timestamp":1670490333000},"page":"330-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Beyond the\u00a0Worst Case: Semi-random Complexity Analysis of\u00a0Winner Determination"],"prefix":"10.1007","author":[{"given":"Lirong","family":"Xia","sequence":"first","affiliation":[]},{"given":"Weiqiang","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,9]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5) (2008). Article No. 23","key":"19_CR1","DOI":"10.1145\/1411509.1411513"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N Alon","year":"2006","unstructured":"Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20, 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Bai, Y., Feige, U., G\u00f6lz, P., Procaccia, A.D.: Fair allocations for smoothed utilities. In: Proceedings of EC (2022)","key":"19_CR3","DOI":"10.1145\/3490486.3538285"},{"doi-asserted-by":"crossref","unstructured":"Banderier, C., Beier, R., Mehlhorn, K.: Smoothed analysis of three combinatorial problems. In: Proceedings of MFCS (2003)","key":"19_CR4","DOI":"10.1007\/978-3-540-45138-9_14"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J Bartholdi III","year":"1989","unstructured":"Bartholdi, J., III., Tovey, C., Trick, M.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6, 157\u2013165 (1989)","journal-title":"Soc. Choice Welfare"},{"unstructured":"Baumeister, D., Hogrebe, T., Rothe, J.: Towards reality: smoothed analysis in computational social choice. In: Proceedings of AAMAS (2020)","key":"19_CR6"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Math. Oper. Res. 31(1), 85\u2013108 (2006)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"19_CR8","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and Losersin discrete optimization. SIAM J. Comput. 35(4), 855\u2013881 (2006)","journal-title":"SIAM J. Comput."},{"unstructured":"Blum, A.: Some tools for approximate 3-coloring. In: Proceedings of FOCS (1990)","key":"19_CR9"},{"doi-asserted-by":"crossref","unstructured":"Blum, A., G\u00f6lz, P.: Incentive-compatible kidney exchange in a slightly semi-random model. In: Proceedings of EC (2021)","key":"19_CR10","DOI":"10.1145\/3465456.3467622"},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A Blum","year":"1995","unstructured":"Blum, A., Spencer, J.: Coloring random and semi-random k-colorable graphs. J. Algorithms 19(2), 204\u2013234 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000004","volume":"2","author":"A Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Found. Trends Theor. Comput. Sci. 2(1), 1\u2013106 (2006)","journal-title":"Found. Trends Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Boodaghians, S., Brakensiek, J., Hopkins, S.B., Rubinstein, A.: Smoothed complexity of 2-player Nash equilibria. In: Proceedings of FOCS (2020)","key":"19_CR13","DOI":"10.1109\/FOCS46700.2020.00034"},{"unstructured":"Boodaghians, S., Kulkarni, R., Mehta, R.: Smoothed efficient algorithms and reductions for network coordination games. In: Proceedings of ITCS (2020)","key":"19_CR14"},{"doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)","key":"19_CR15","DOI":"10.1017\/CBO9781107446984.002"},{"doi-asserted-by":"crossref","unstructured":"Caragiannis, I., et al.: On the approximability of Dodgson and Young elections. In: Proceedings of SODA (2009)","key":"19_CR16","DOI":"10.1137\/1.9781611973068.115"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Li, Y., Mao, J.: A nearly instance optimal algorithm for top-k ranking under the multinomial logit model. In: Proceedings of SODA (2018)","key":"19_CR17","DOI":"10.1137\/1.9781611975031.160"},{"unstructured":"Ding, K., Weinberg, S.M.: Approximately strategyproof tournament rules in the probabilistic setting. In: Proceedings of ITCS (2021)","key":"19_CR18"},{"doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings WWW (2001)","key":"19_CR19","DOI":"10.1145\/371920.372165"},{"doi-asserted-by":"crossref","unstructured":"Feige, U.: Introduction to semi-random models. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge (2021)","key":"19_CR20","DOI":"10.1017\/9781108637435.013"},{"unstructured":"Feige, U., Kilian, J.: Heuristics for finding large independent sets, with applications to coloring semi-random graphs. In: Proceedings of FOCS (1998)","key":"19_CR21"},{"doi-asserted-by":"publisher","unstructured":"Gehrlein, W.V.: Condorcet\u2019s Paradox. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-33799-7","key":"19_CR22","DOI":"10.1007\/3-540-33799-7"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to np. J. ACM 44, 806\u2013825 (1997)","journal-title":"J. ACM"},{"issue":"3","key":"19_CR24","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2005.08.031","volume":"349","author":"E Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theoret. Comput. Sci. 349(3), 382\u2013391 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10732-007-9068-5","volume":"15","author":"CM Homan","year":"2009","unstructured":"Homan, C.M., Hemaspaandra, L.A.: Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. J. Heuristics 15, 403\u2013423 (2009)","journal-title":"J. Heuristics"},{"issue":"2","key":"19_CR26","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1177\/0048393107299684","volume":"37","author":"A Lehtinen","year":"2007","unstructured":"Lehtinen, A., Kuorikoski, J.: Unrealistic assumptions in rational choice theory. Philos. Soc. Sci. 37(2), 115\u2013138 (2007)","journal-title":"Philos. Soc. Sci."},{"unstructured":"Lu, T., Boutilier, C.: Budgeted social choice: From consensus to personalized decision making. In: Proceeding of IJCAI (2011)","key":"19_CR27"},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00355-007-0282-8","volume":"31","author":"JC McCabe-Dansted","year":"2008","unstructured":"McCabe-Dansted, J.C., Pritchard, G., Slinko, A.: Approximability of Dodgson\u2019s rule. Soc. Choice Welfare 31, 311\u2013330 (2008)","journal-title":"Soc. Choice Welfare"},{"doi-asserted-by":"crossref","unstructured":"Mohajer, S., Suh, C., Elmahdy, A.: Active learning for top-$$k$$ rank aggregation from noisy comparisons. In: Proceedings of ICML (2017)","key":"19_CR29","DOI":"10.1109\/ALLERTON.2016.7852326"},{"key":"19_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03782-9","volume-title":"Voting Paradoxes and How to Deal with Them","author":"H Nurmi","year":"1999","unstructured":"Nurmi, H.: Voting Paradoxes and How to Deal with Them. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-662-03782-9"},{"doi-asserted-by":"crossref","unstructured":"Perrot, K., Pham, T.V.: Feedback arc set problem and np-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs. Ann. Comb, 373\u2013396 (2015)","key":"19_CR31","DOI":"10.1007\/s00026-015-0266-9"},{"issue":"3","key":"19_CR32","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00355-007-0235-2","volume":"30","author":"AD Procaccia","year":"2008","unstructured":"Procaccia, A.D., Rosenschein, J.S.R., Zohar, A.Z.: On the complexity of achieving proportional representation. Soc. Choice Welfare 30(3), 353\u2013362 (2008)","journal-title":"Soc. Choice Welfare"},{"doi-asserted-by":"crossref","unstructured":"Psomas, A., Schvartzman, A., Weinberg, S.M.: Smoothed analysis of multi-item auctions with correlated values. In: Proceedings of EC (2019)","key":"19_CR33","DOI":"10.1145\/3328526.3329563"},{"doi-asserted-by":"crossref","unstructured":"Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36(4), 375\u2013386 (2003)","key":"19_CR34","DOI":"10.1007\/s00224-002-1093-z"},{"doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge (2021)","key":"19_CR35","DOI":"10.1017\/9781108637435"},{"doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3) (2004)","key":"19_CR36","DOI":"10.1145\/990308.990310"},{"issue":"10","key":"19_CR37","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"unstructured":"Xia, L.: The smoothed possibility of social choice. In: Proceedings of NeurIPS (2020)","key":"19_CR38"},{"doi-asserted-by":"crossref","unstructured":"Xia, L.: How likely are large elections tied? In: Proceedings of EC (2021)","key":"19_CR39","DOI":"10.1145\/3465456.3467592"},{"unstructured":"Xia, L.: The semi-random satisfaction of voting axioms. In: Proceedings of NeurIPS (2021)","key":"19_CR40"},{"doi-asserted-by":"crossref","unstructured":"Xia, L., Zheng, W.: The smoothed complexity of computing Kemeny and slater rankings. In: Proceedings of AAAI (2021)","key":"19_CR41","DOI":"10.1609\/aaai.v35i6.16720"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22832-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:48:35Z","timestamp":1710269315000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22832-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031228315","9783031228322"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22832-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"9 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Troy, NY","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 December 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.rpi.edu\/wine2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"126","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19 abstracts in the back matter","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}