Jul. 04, 2018

​​​The papers are:
1. Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. When Rigging a Tournament, Let Greediness Blind You.

2. Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Winning a Tournament by Any Means Necessary.

About the papers:
In a (cup) tournament, we have a set N of n players who enter the competition. In each round, the players are paired-up to compete against each other. Losers are thrown away, while winners proceed to the next round, until only one lucky player is left. This is a standard form of competition in sports, popular culture, elections and decision making schemes. The inherent highly competitive nature of a tournament makes it attractive for manipulators. 

Our first paper addresses the Tournament Fixing problem, where we seek a way to pair up the players so that our favorite player wins (if such a way exists). We obtained a parameterized algorithm for this problem that outperforms a previous one by having a substantially faster running time, being simpler and being combinatorial rather than algebraic. In the second paper, we study the same question but in the presence of manipulations (say, bribery) of outcomes of matches. In particular, we study structural properties and characterizations of manipulation strategies.