Weak transitivity and agenda control for extended stepladder tournaments
- PDF / 548,275 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 103 Downloads / 177 Views
Weak transitivity and agenda control for extended stepladder tournaments Yongjie Yang1
· Dinko Dimitrov1
Received: 25 November 2019 / Accepted: 6 July 2020 © The Author(s) 2020
Abstract A tournament graph over n players is weakly transitive at player p if it contains a Hamiltonian path ( p1 , p2 , . . . , pn ) with p1 = p such that for all odd integers i ≤ n −2 there is an arc from pi to pi+2 . We show that weak transitivity at p suffices to make player p win any extended stepladder tournament of degree at most two. Keywords Agenda control · Extended stepladder · Hamiltonian path · Knockout tournament · Weak transitivity Mathematics Subject Classification C70 · D70 · D71
1 Introduction Knockout tournaments are widely used when it comes to the selection of an alternative from a set of available options. These elimination formats are crucial for collecting important insights in the analysis of electoral systems (cf. Brams and Fishburn 2002; Laslier 1997) and also play a predominant role in sport competitions where one has to determine the winner among a set of players. In such settings it is usually assumed that the tournament organizer possesses reliable information, in the form of a (deterministic) tournament graph over the player set, about who would win the match between every two players. The tournament organizer then specifies a seeding which labels the leaves of a rooted binary tree by players with each internal node being reached by the winner between the two children. The player who reaches the root of the binary tree is the final winner of the knockout tournament.
B
Yongjie Yang [email protected] Dinko Dimitrov [email protected]
1
Chair of Economic Theory, Saarland University, Saarbrücken, Germany
123
Y. Yang, D. Dimitrov
Agenda control has been defined in the work of Bartholdi et al. (1989) as a particular type of manipulation for knockout tournaments. Provided that the tournament organizer has a favorite player, the question of study is whether there exists a seeding in the rooted binary tree which makes this player the final winner of the knockout tournament. This problem has attracted a lot of attention in the literature with the main focus being on balanced rooted binary trees 1 . It is known that the agenda control problem restricted to balanced rooted tree is NP-hard (Aziz et al. 2018). Moreover, the NP-hardness remains even if we further require the tournament organizer’s favorite player to be a king 2 of the tournament graph (cf. Kim and Williams 2015). Strengthening the notion of a king node was shown to allow for efficiently constructible seedings making kings winners in balanced knockout tournaments (cf. Kim et al. 2017; Kim and Williams 2015). We refer the reader to the work of Williams (2016) for an excellent and detailed survey of the recent literature. A well known necessary condition for a player p to win a knockout tournament is that every node in the tournament graph should be reachable from p via a Hamiltonian path, i.e., there should be a Hamiltonian path
Data Loading...
