Theory Seminar, Wednesday Nov 12: Hendrik Molter (BGU) - On Manipulation in Knockout Tournaments

[Arnold Filtser]

Hi all,

Next week (Wed Nov 12, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker:  Hendrik Molter (BGU)
Title:  On Manipulation in Knockout Tournaments
Abstract:  A knockout tournament is one of the most simple and popular forms of competition. Here, we are a given binary tournament tree where all leaves are labeled with seed position names. The players participating in the tournament are assigned to the seed positions. In each round, the two players assigned to leaves of the tournament tree with a common parent compete, and the winner is promoted to the parent. The last remaining player is the winner of the tournament.

In the first part, we present results on the following problem: In the standard probabilistic setting, for each pairing of players, one of the players wins the game with a certain (a priori known) probability. Due to their competitive nature, tournaments are prone to manipulation. 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 \emph{adaptive constructive coalition manipulation}. To the best of our knowledge, while coalition manipulation has been studied in the literature, this is the first work to introduce adaptiveness to this context.

In the second part, we present results on the following problem: we study the problem of making knockout tournaments robust against manipulation, where the form of manipulation we consider is changing the outcome of a game. We assume that our input is only the number of players that compete in the tournament, and the number of manipulations against which the tournament should be robust. Furthermore, we assume that there is a strongest player, that is, a player that beats any of the other players (with probability one). However, the identity of this player is not part of the problem input. To ensure robustness against manipulation, we uncover an unexpected connection between the problem at hand and communication protocols that utilize a feedback channel, offering resilience against adversarial noise. We explore the trade-off between the size of the robust tournament tree and the degree of protection against manipulation.

The talk is based on joint work with Juhi Chaudhary, Klim Efremenko, and Meirav Zehavi that appeared at AAAI 2025 and EC 2025, respectively.

[Arnold Filtser]

The seminar starts in one hour!