乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T23:26:16Z","timestamp":1708989976213},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,10]]},"abstract":"Abstract<\/jats:title>Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k<\/jats:italic>-king<\/jats:italic> if it can reach every other alternative in the tournament via a directed path of length at most k<\/jats:italic>. In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k<\/jats:italic>-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the range of constant k<\/jats:italic>, with the biggest change being between

$$k=2$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and

$$k=3$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.<\/jats:p>","DOI":"10.1007\/s10458-022-09557-7","type":"journal-article","created":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T09:03:09Z","timestamp":1651050189000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Generalized kings and single-elimination winners in random tournaments"],"prefix":"10.1007","volume":"36","author":[{"given":"Pasin","family":"Manurangsi","sequence":"first","affiliation":[]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,27]]},"reference":[{"key":"9557_CR1","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1613\/jair.4856","volume":"54","author":"H Aziz","year":"2015","unstructured":"Aziz, H., Brill, M., Fischer, F., Harrenstein, P., Lang, J., & Seedig, H. G. (2015). Possible and necessary winners of partial tournaments. Journal of Artificial Intelligence Research, 54, 493\u2013534.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9557_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2018.05.002","volume":"262","author":"H Aziz","year":"2018","unstructured":"Aziz, H., Gaspers, S., Mackenzie, S., Mattei, N., Stursberg, P., & Walsh, T. (2018). Fixing balanced knockout and double elimination tournaments. Artificial Intelligence, 262, 1\u201314.","journal-title":"Artificial Intelligence"},{"key":"9557_CR3","unstructured":"Baumeister, D. & Hogrebe, T.\u00a0A. (2021). Complexity of scheduling and predicting round-robin tournaments. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 178\u2013186."},{"key":"9557_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1017\/CBO9781107446984.004","volume-title":"Handbook of Computational Social Choice, chapter 3","author":"F Brandt","year":"2016","unstructured":"Brandt, F., Brill, M., & Harrenstein, P. (2016). Tournament solutions. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of Computational Social Choice, chapter 3 (pp. 57\u201384). Cambridge: Cambridge University Press."},{"key":"9557_CR5","unstructured":"Brandt, F., Brill, M. & Seedig, H.\u00a0G. (2011). On the fixed-parameter tractability of composition-consistent tournament solutions. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 85\u201390"},{"issue":"2","key":"9557_CR6","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s00199-016-1024-x","volume":"65","author":"F Brandt","year":"2018","unstructured":"Brandt, F., Brill, M., Seedig, H. G., & Suksompong, W. (2018). On the structure of stable tournament solutions. Economic Theory, 65(2), 483\u2013507.","journal-title":"Economic Theory"},{"key":"9557_CR7","doi-asserted-by":"crossref","unstructured":"Brandt, F., & Fischer, F.\u00a0A. (2007). PageRank as a weak tournament solution. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), pages 300\u2013305.","DOI":"10.1007\/978-3-540-77105-0_30"},{"key":"9557_CR8","doi-asserted-by":"crossref","unstructured":"Brandt, F., & Seedig, H.\u00a0G. (2016). On the discriminative power of tournament solutions. In Selected Papers of the International Conference on Operations Research, OR2014, pages 53\u201358.","DOI":"10.1007\/978-3-319-28697-6_8"},{"issue":"19","key":"9557_CR9","doi-asserted-by":"publisher","first-page":"2550","DOI":"10.1016\/j.disc.2010.06.001","volume":"310","author":"D Brcanov","year":"2010","unstructured":"Brcanov, D., & Petrovic, V. (2010). Toppling kings in multipartite tournaments by introducing new kings. Discrete Mathematics, 310(19), 2550\u20132554.","journal-title":"Discrete Mathematics"},{"key":"9557_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103600","volume":"302","author":"M Brill","year":"2022","unstructured":"Brill, M., Schmidt-Kraepelin, U., & Suksompong, W. (2022). Margin of victory for tournament solutions. Artificial Intelligence, 302, 103600.","journal-title":"Artificial Intelligence"},{"key":"9557_CR11","unstructured":"Chatterjee, K., Ibsen-Jensen, R., & Tkadlec, J. (2016). Robust draws in balanced knockout tournaments. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 172\u2013179."},{"key":"9557_CR12","doi-asserted-by":"crossref","unstructured":"Dey, P. (2017). Query complexity of tournament solutions. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 2992\u20132998.","DOI":"10.1609\/aaai.v31i1.10702"},{"issue":"2","key":"9557_CR13","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00355-007-0279-3","volume":"31","author":"M Fey","year":"2008","unstructured":"Fey, M. (2008). Choosing from a large tournament. Social Choice and Welfare, 31(2), 301\u2013309.","journal-title":"Social Choice and Welfare"},{"issue":"3","key":"9557_CR14","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/0133030","volume":"33","author":"PC Fishburn","year":"1977","unstructured":"Fishburn, P. C. (1977). Condorcet social choice functions. SIAM Journal on Applied Mathematics, 33(3), 469\u2013489.","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"2","key":"9557_CR15","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.3190190208","volume":"19","author":"DC Fisher","year":"1995","unstructured":"Fisher, D. C., & Ryan, J. (1995). Tournament games and positive tournaments. Journal of Graph Theory, 19(2), 217\u2013236.","journal-title":"Journal of Graph Theory"},{"issue":"3","key":"9557_CR16","doi-asserted-by":"publisher","first-page":"319","DOI":"10.2307\/1401473","volume":"36","author":"O Frank","year":"1968","unstructured":"Frank, O. (1968). Stochastic competition graphs. Review of the International Statistical Institute, 36(3), 319\u2013326.","journal-title":"Review of the International Statistical Institute"},{"issue":"1","key":"9557_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01718625","volume":"10","author":"IJ Good","year":"1971","unstructured":"Good, I. J. (1971). A note on Condorcet sets. Public Choice, 10(1), 97\u2013101.","journal-title":"Public Choice"},{"key":"9557_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, S., Roy, S., Saurabh, S., & Zehavi, M. (2018). When rigging a tournament, let greediness blind you. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 275\u2013281.","DOI":"10.24963\/ijcai.2018\/38"},{"key":"9557_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, S., Roy, S., Saurabh, S., & Zehavi, M. (2018). Winning a tournament by any means necessary. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 282\u2013288.","DOI":"10.24963\/ijcai.2018\/39"},{"key":"9557_CR20","doi-asserted-by":"crossref","unstructured":"Gupta, S., Saurabh, S., Sridharan, R., & Zehavi, M. (2019). On succinct encodings for the tournament fixing problem. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 322\u2013328.","DOI":"10.24963\/ijcai.2019\/46"},{"issue":"1","key":"9557_CR21","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s11238-018-9676-6","volume":"86","author":"W Han","year":"2019","unstructured":"Han, W., & van Deemen, A. (2019). A refinement of the uncovered set in tournaments. Theory and Decision, 86(1), 107\u2013121.","journal-title":"Theory and Decision"},{"issue":"3","key":"9557_CR22","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.1137\/16M1061783","volume":"31","author":"MP Kim","year":"2017","unstructured":"Kim, M. P., Suksompong, W., & Vassilevska Williams, V. (2017). Who can win a single-elimination tournament? SIAM Journal on Discrete Mathematics, 31(3), 1751\u20131764.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9557_CR23","unstructured":"Kim, M.\u00a0P. & Vassilevska Williams, V. (2015). Fixing tournaments for kings, chokers, and more. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 561\u2013567."},{"key":"9557_CR24","unstructured":"Konicki, C., & Vassilevska Williams, V. (2019). Bribery in balanced knockout tournaments. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2066\u20132068."},{"issue":"1","key":"9557_CR25","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1006\/game.1993.1010","volume":"5","author":"G Laffond","year":"1993","unstructured":"Laffond, G., Laslier, J.-F., & Le Breton, M. (1993). The bipartisan set of a tournament game. Games and Economic Behavior, 5(1), 182\u2013201.","journal-title":"Games and Economic Behavior"},{"issue":"3","key":"9557_CR26","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0166-218X(94)90013-2","volume":"55","author":"G Laffond","year":"1994","unstructured":"Laffond, G., Laslier, J.-F., & Le Breton, M. (1994). The Copeland measure of Condorcet choice functions. Discrete Applied Mathematics, 55(3), 273\u2013279.","journal-title":"Discrete Applied Mathematics"},{"key":"9557_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60805-6","volume-title":"Tournament Solutions and Majority Voting","author":"J-F Laslier","year":"1997","unstructured":"Laslier, J.-F. (1997). Tournament Solutions and Majority Voting. Berlin: Springer-Verlag."},{"issue":"1\u20133","key":"9557_CR28","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0012-365X(94)00279-R","volume":"148","author":"T \u0141uczak","year":"1996","unstructured":"\u0141uczak, T., Ruci\u0144ski, A., & Gruszka, J. (1996). On the evolution of a random tournament. Discrete Mathematics, 148(1\u20133), 311\u2013316.","journal-title":"Discrete Mathematics"},{"key":"9557_CR29","doi-asserted-by":"crossref","unstructured":"Manurangsi, P., & Suksompong, W. (2021). Generalized kings and single-elimination winners in random tournaments. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 328\u2013334.","DOI":"10.24963\/ijcai.2021\/46"},{"issue":"4","key":"9557_CR30","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/j.jal.2015.03.004","volume":"13","author":"N Mattei","year":"2015","unstructured":"Mattei, N., Goldsmith, J., Klapper, A., & Mundhenk, M. (2015). On the complexity of bribery and manipulation in tournaments with uncertain information. Journal of Applied Logic, 13(4), 549\u2013554.","journal-title":"Journal of Applied Logic"},{"key":"9557_CR31","unstructured":"Mattei, N., & Walsh, T. (2016). Empirical evaluation of real world tournaments. CoRR, abs\/1608.01039."},{"issue":"2","key":"9557_CR32","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1080\/0025570X.1980.11976831","volume":"53","author":"SB Maurer","year":"1980","unstructured":"Maurer, S. B. (1980). The king chicken theorems. Mathematics Magazine, 53(2), 67\u201380.","journal-title":"Mathematics Magazine"},{"issue":"2\u20133","key":"9557_CR33","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0304-3975(88)90131-4","volume":"61","author":"N Megiddo","year":"1988","unstructured":"Megiddo, N., & Vishkin, U. (1988). On finding a minimum dominating set in a tournament. Theoretical Computer Science, 61(2\u20133), 307\u2013316.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"9557_CR34","doi-asserted-by":"publisher","first-page":"769","DOI":"10.2307\/2110736","volume":"21","author":"NR Miller","year":"1977","unstructured":"Miller, N. R. (1977). Graph-theoretic approaches to the theory of voting. American Journal of Political Science, 21(4), 769\u2013803.","journal-title":"American Journal of Political Science"},{"issue":"1","key":"9557_CR35","doi-asserted-by":"publisher","first-page":"68","DOI":"10.2307\/2110925","volume":"24","author":"NR Miller","year":"1980","unstructured":"Miller, N. R. (1980). A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting. American Journal of Political Science, 24(1), 68\u201396.","journal-title":"American Journal of Political Science"},{"key":"9557_CR36","unstructured":"Mnich, M., Shrestha, Y.\u00a0R., & Yang, Y. (2015). When does Schwartz conjecture hold? In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 603\u2013609."},{"issue":"1","key":"9557_CR37","doi-asserted-by":"publisher","first-page":"61","DOI":"10.4153\/CMB-1962-010-4","volume":"5","author":"JW Moon","year":"1962","unstructured":"Moon, J. W., & Moser, L. (1962). Almost all tournaments are irreducible. Canadian Mathematical Bulletin, 5(1), 61\u201365.","journal-title":"Canadian Mathematical Bulletin"},{"issue":"4","key":"9557_CR38","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF00292732","volume":"3","author":"H Moulin","year":"1986","unstructured":"Moulin, H. (1986). Choosing from a tournament. Social Choice and Welfare, 3(4), 271\u2013291.","journal-title":"Social Choice and Welfare"},{"issue":"3","key":"9557_CR39","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0012-365X(91)90380-K","volume":"98","author":"V Petrovic","year":"1991","unstructured":"Petrovic, V., & Thomassen, C. (1991). Kings in $$k$$-partite tournaments. Discrete Mathematics, 98(3), 237\u2013238.","journal-title":"Discrete Mathematics"},{"key":"9557_CR40","doi-asserted-by":"crossref","unstructured":"Ramanujan, M.\u00a0S., & Szeider, S. (2017). Rigging nearly acyclic tournaments is fixed-parameter tractable. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 3929\u20133935.","DOI":"10.1609\/aaai.v31i1.11132"},{"issue":"1","key":"9557_CR41","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00355-019-01213-6","volume":"54","author":"C Saile","year":"2020","unstructured":"Saile, C., & Suksompong, W. (2020). Robust bounds on choosing from large tournaments. Social Choice and Welfare, 54(1), 87\u2013110.","journal-title":"Social Choice and Welfare"},{"issue":"2","key":"9557_CR42","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/2216143","volume":"6","author":"T Schwartz","year":"1972","unstructured":"Schwartz, T. (1972). Rationality and the myth of the maximum. No\u00fbs, 6(2), 97\u2013117.","journal-title":"No\u00fbs"},{"issue":"1","key":"9557_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00355-010-0503-4","volume":"38","author":"A Scott","year":"2012","unstructured":"Scott, A., & Fey, M. (2012). The minimal covering set in large tournaments. Social Choice and Welfare, 38(1), 1\u20139.","journal-title":"Social Choice and Welfare"},{"key":"9557_CR44","doi-asserted-by":"crossref","unstructured":"Stanton, I., & Vassilevska Williams, V. (2011). Manipulating stochastically generated single-elimination tournaments for nearly all players. In Proceedings of the 7th International Workshop on Internet and Network Economics (WINE), pages 326\u2013337.","DOI":"10.1007\/978-3-642-25510-6_28"},{"key":"9557_CR45","unstructured":"Stanton, I., & Vassilevska Williams, V. (2011). Rigging tournament brackets for weaker players. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 357\u2013364."},{"issue":"1","key":"9557_CR46","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.orl.2015.12.008","volume":"44","author":"W Suksompong","year":"2016","unstructured":"Suksompong, W. (2016). Scheduling asynchronous round-robin tournaments. Operations Research Letters, 44(1), 96\u2013100.","journal-title":"Operations Research Letters"},{"key":"9557_CR47","doi-asserted-by":"crossref","unstructured":"Suksompong, W. (2021). Tournaments in computational social choice: Recent developments. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 4611\u20134618.","DOI":"10.24963\/ijcai.2021\/626"},{"issue":"21","key":"9557_CR48","doi-asserted-by":"publisher","first-page":"2703","DOI":"10.1016\/j.disc.2006.04.023","volume":"306","author":"BP Tan","year":"2006","unstructured":"Tan, B. P. (2006). On the 3-kings and 4-kings in multipartite tournaments. Discrete Mathematics, 306(21), 2703\u20132710.","journal-title":"Discrete Mathematics"},{"key":"9557_CR49","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V. (2010). Fixing a tournament. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pages 895\u2013900.","DOI":"10.1609\/aaai.v24i1.7617"},{"key":"9557_CR50","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1017\/CBO9781107446984.020","volume-title":"Handbook of Computational Social Choice, chapter 19","author":"V Vassilevska Williams","year":"2016","unstructured":"Vassilevska Williams, V. (2016). Knockout tournaments. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of Computational Social Choice, chapter 19 (pp. 453\u2013474). Cambridge: Cambridge University Press."},{"key":"9557_CR51","unstructured":"Vu, T., Altman, A., & Shoham, Y. (2009). On the complexity of schedule control problems for knockout tournaments. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 225\u2013232."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09557-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09557-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09557-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:49:05Z","timestamp":1667047745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09557-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,27]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["9557"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09557-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,27]]},"assertion":[{"value":"5 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"28"}}