קולקוויום מחלקתי 9.5.24

ירצה על

Will lecture on

Profit Optimization and Manipulation of Knockout Tournaments

Knockout tournaments, also known as single-elimination or cup tournaments, are a popular form of sports competitions. Given a mapping from a set of players to the leaves of a complete binary tree (called a seeding), a knockout tournament is conducted as follows: every round, every two players with a common parent compete against each other, and the winner is promoted to the common parent; then, the leaves are deleted. When only one player remains, it is declared the winner. In the standard probabilistic setting, for each pairing of players, one of the players wins the game with a certain (a priory known) probability. In the talk, we present results for two different problems on knockout tournaments.

In the first part, we introduce a new objective, which is very sensible from the perspective of the directors of the competition: maximize the profit or popularity of the tournament. Specifically, we associate a “score” with every possible match, and aim to seed the tournament to maximize the sum of the scores of the matches that take place. We focus on the case where we assume a total order on the players’ strengths, and provide a wide spectrum of results on the (parameterized) computational complexity of the problem.

In the second part, we investigate the computational problem of determining whether, for a given tournament, a coalition has a manipulation strategy that increases the winning probability of a designated player above a given threshold. More precisely, in every round of the tournament, coalition players can strategically decide which games to throw based on the advancement of other players to the current round. We call this setting adaptive constructive coalition manipulation. We show that this problem is hard for every complexity class in the polynomial hierarchy and give a number of parameterized complexity results.

For both problem settings, we discuss open questions and future research directions. The talk is based on joint work with Juhi Chaudhary and Meirav Zehavi.

Short Bio:

Hendrik Molter completed his Ph.D. in computer science with Prof. Rolf Niedermeier at the Algorithmics and Complexity group of the Technical University of Berlin.
His Ph.D. main focus was parameterized algorithms and complexity of temporal graph problems.
Afterward, he joined as postdoctoral researcher to the team of Prof. Danny Hermelin and Prof. Dvir Shabtay at the Department of Industrial Engineering and Management of Ben-Gurion University. During this  period, his research interest was the parameterized complexity of scheduling problems.
Currently, he is a postdoctoral researcher at the team of Prof. Meirav Zehavi and Prof. Klim Efremenko at the Department of Computer Science of the Ben-Gurion University. His main research field is parameterized algorithms and complexity of problems from various areas, including temporal graph, scheduling, and computational social choice.