Generalized Kings and Single-Elimination Winners in Random Tournaments

Manurangsi, Pasin; Suksompong, Warut

doi:10.24963/ijcai.2021/46

Generalized Kings and Single-Elimination Winners in Random Tournaments

Pasin Manurangsi, Warut Suksompong

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 328-334.

https://doi.org/10.24963/ijcai.2021/46

Keywords

Agent-based and Multi-agent Systems: Computational Social Choice

Abstract

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-king if it can reach every other alternative in the tournament via a directed path of length at most k. 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-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the regime of constant k, with the biggest change being between k = 2 and k = 3. 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.

Pasin Manurangsi, and Warut Suksompong. 2021. Generalized Kings and Single-Elimination Winners in Random Tournaments. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 328–334. https://doi.org/10.24963/ijcai.2021/46

@inproceedings{ijcai2021p46,
  title     = {Generalized Kings and Single-Elimination Winners in Random Tournaments},
  author    = {Manurangsi, Pasin and Suksompong, Warut},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {328--334},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/46},
  url       = {https://doi.org/10.24963/ijcai.2021/46},
}

TY  - CPAPER
TI  - Generalized Kings and Single-Elimination Winners in Random Tournaments
AU  - Manurangsi, Pasin
AU  - Suksompong, Warut
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 328
EP  - 334
DO  - 10.24963/ijcai.2021/46
UR  - https://doi.org/10.24963/ijcai.2021/46
ER  -