On the complexity of schedule control problems for knockout tournaments

ABSTRACT

Knockout tournaments constitute a common format of sporting events, and also model a specific type of election scheme (namely, sequential pairwise elimination election). In such tournaments the designer controls the shape of the tournament (a binary tree) and the seeding of the players (their assignment to the tree leaves). In this paper we investigate the computational complexity of tournament schedule control, i.e., designing a tournament that maximizes the winning probability a target player. We start with a generic probabilistic model consisting of a matrix of pairwise winning probabilities, and then investigate the problem under two types of constraint: constraints on the probability matrix, and constraints on the allowable tournament structure. While the complexity of the general problem is as yet unknown, these various constraints -- all naturally occurring in practice -- serve to push to the problem to one side or the other: easy (polynomial) or hard (NP-complete).

REFERENCES

• 1: D. R. Appleton. May the best man win? The Statistician, 44(4):529--538, 1995.
• 2: J. Bartholdi, C. Tovey, and M. Trick. How hard is it to control an election? Mathematical and Computer Modeling, 16(8/9):27--40, 1992.
• 3: S. J. Brams and P. C. Fishburn. Voting procedures. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare.
• 4: N. Hazon, P. E. Dunne, S. Kraus, and M. Wooldridge. How to rig elections and competitions. In COMSOC'08, 2008.
• 5: Edith Hemaspaandra , Lane A. Hemaspaandra , Jörg Rothe, Anyone but him: The complexity of precluding an alternative, Artificial Intelligence, v.171 n.5-6, p.255-285, April, 2007 [doi>10.1016/j.artint.2007.01.005]
• 6: J. Horen and R. Riezman. Comparing draws for single elimination tournaments. Operations Research, 33(2):249--262, mar 1985.
• 7: F. K. Hwang. New concepts in seeding knockout tournaments. The American Mathematical Monthly, 89(4):235--239, apr 1982.
• 8: J. Lang, M. S. Pini, F. Rossi, K. B. Venable, and T. Walsh. Winner determination in sequential majority voting. In IJCAI, pages 1372--1377, 2007.
• 9: J.-F. Laslier. Tournament solutions and majority voting. Springer, 1997.
• 10: G. C. Loury. Market structure and innovation. The Quarterly Journal of Economics, 93(3):395--410, August 1979.
• 11: J. W. Moon and N. J. Pullman. On generalized tournament matrices. SIAM Review, 12(3):384--399, jul 1970.
• 12: S. Rosen. Prizes and incentives in elimination tournaments. The American Economic Review, 76(4):701--715, sep 1986.
• 13: D. Ryvkin. The predictive power of noisy elimination tournaments. Technical report, The Center for Economic Research and Graduate Education - Economic Institute, Prague, Mar. 2005.
• 14: A. J. Schwenk. What is the correct way to seed a knockout tournament? The American Mathematical Monthly, 107(2):140--150, feb 2000.
• 15: G. Tullock. Toward a Theory of the Rent-seeking Society. Texas A&M University Press, 1980.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Keywords:
complexity, election control, tournament design, voting theory