### Abstract

We consider the manipulability of tournament rules, in which n teams play a round robin tournament and a winner is (possibly randomly) selected based on the outcome of all ^{n}_{2} matches. Prior work defines a tournament rule to be k-SNM-α if no set of ≤ k teams can fix the ≤ ^{k}_{2} matches among them to increase their probability of winning by > α and asks: for each k, what is the minimum α(k) such that a Condorcet-consistent (i.e. always selects a Condorcet winner when one exists) k-SNM-α(k) tournament rule exists? A simple example witnesses that α(k) ≥ _{2}^{k}_{k}^{−}_{−}^{1}_{1} for all k, and [22] conjectures that this is tight (and prove it is tight for k = 2). Our first result refutes this conjecture: there exists a sufficiently large k such that no Condorcet-consistent tournament rule is k-SNM-1/2. Our second result leverages similar machinery to design a new tournament rule which is k-SNM-2/3 for all k (and this is the first tournament rule which is k-SNM-(< 1) for all k). Our final result extends prior work, which proves that single-elimination bracket with random seeding is 2-SNM-1/3 [22], in a different direction by seeking a stronger notion of fairness than Condorcet-consistence. We design a new tournament rule, which we call Randomized-King-of-the-Hill, which is 2-SNM-1/3 and cover-consistent (the winner is an uncovered team with probability 1).

Original language | English (US) |
---|---|

Title of host publication | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |

Editors | Thomas Vidick |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771344 |

DOIs | |

State | Published - Jan 2020 |

Event | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States Duration: Jan 12 2020 → Jan 14 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 151 |

### Conference

Conference | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |
---|---|

Country | United States |

City | Seattle |

Period | 1/12/20 → 1/14/20 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Cover-consistence
- Non-manipulability
- Strategyproof-ness
- Tournament design

### Cite this

*11th Innovations in Theoretical Computer Science Conference, ITCS 2020*[3] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 151). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2020.3