资源论文Winning a Tournament by Any Means Necessary

Winning a Tournament by Any Means Necessary

2019-11-05 | |  67 |   31 |   0
Abstract In a tournament, n players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph D), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player w wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when ` < (1 ? ) log n alterations are possible (for any fixed  > 0). For this problem, our contribution is fourfold. First, we present two operations that “obfuscate deceit”: given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to w and “elite players”. Third, we give a closed formula for the case where D is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.

上一篇:When Rigging a Tournament, Let Greediness Blind You

下一篇:Fostering Cooperation in Structured Populations Through Local and Global Interference Strategies

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...