Rigging TournamentsMotivationOur ApproachRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachRigging Tournament Brackets for WeakerPlayersIsabelle Stanton and Virginia Vassilevska WilliamsUC BerkeleyJuly 18, 2011RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachBalanced Single-Elimination TournamentsRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingIf we had a tournament between n players, and knew all of thematch outcomes in advance, could we pick a bracket for asingle-elimination tournament so that our favourite player wins?RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachWhy Study This Problem?SE tournaments are an incredibly popular form ofcompetitionFrom an election stand point, SE tournaments areequivalent to binary cup votingWe inherently think that tournaments are ‘fair’. It isimportant to confirm or deny this.RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingThis problem is a specific instance of agenda control.If we only have probabilities of each player winning anymatch, it is NP-hard to find a bracket that maximizes theprobability of a fixed player winning. It is hard to evenapproximate within a constant.If we even know each match is either a win, loss, or 50-50,it is still NP-hardIf the matches are deterministic, the hardness is still open.Finding the most ‘interesting’ tournament whendeterministic matches have an ‘interestingness’ rating isNP-hardGuaranteeing that certain players appear in prespecifiedrounds is NP-hardRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingThis problem is a specific instance of agenda control.If we only have probabilities of each player winning anymatch, it is NP-hard to find a bracket that maximizes theprobability of a fixed player winning. It is hard to evenapproximate within a constant.If we even know each match is either a win, loss, or 50-50,it is still NP-hardIf the matches are deterministic, the hardness is still open.Finding the most ‘interesting’ tournament whendeterministic matches have an ‘interestingness’ rating isNP-hardGuaranteeing that certain players appear in prespecifiedrounds is NP-hardRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingThis problem is a specific instance of agenda control.If we only have probabilities of each player winning anymatch, it is NP-hard to find a bracket that maximizes theprobability of a fixed player winning. It is hard to evenapproximate within a constant.If we even know each match is either a win, loss, or 50-50,it is still NP-hardIf the matches are deterministic, the hardness is still open.Finding the most ‘interesting’ tournament whendeterministic matches have an ‘interestingness’ rating isNP-hardGuaranteeing that certain players appear in prespecifiedrounds is NP-hardRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingThis problem is a specific instance of agenda control.If we only have probabilities of each player winning anymatch, it is NP-hard to find a bracket that maximizes theprobability of a fixed player winning. It is hard to evenapproximate within a constant.If we even know each match is either a win, loss, or 50-50,it is still NP-hardIf the matches are deterministic, the hardness is still open.Finding the most ‘interesting’ tournament whendeterministic matches have an ‘interestingness’ rating isNP-hardGuaranteeing that certain players appear in prespecifiedrounds is NP-hardRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachTournament FixingThis problem is a specific instance of agenda control.If we only have probabilities of each player winning anymatch, it is NP-hard to find a bracket that maximizes theprobability of a fixed player winning. It is hard to evenapproximate within a constant.If we even know each match is either a win, loss, or 50-50,it is still NP-hardIf the matches are deterministic, the hardness is still open.Finding the most ‘interesting’ tournament whendeterministic matches have an ‘interestingness’ rating isNP-hardGuaranteeing that certain players appear in prespecifiedrounds is NP-hardRiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachWe will focus on the deterministic balanced case and findingconditions that guarantee that we can manipulate easily.RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachGraph Theory ConnectionIn deterministic tournament graphs, the problem of fixing atournament is equivalent to finding a rooted binomialarboresenceThis, in turn, is equivalent to a series of directed matchings.RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachThe Strength of PlayersPrevious work showed the strongest player (by number of wins)can always win an SE tournament.RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachThe Strength of PlayersPrevious work showed the strongest player (by number of wins)can always win an SE tournament.If we look at the ranking by number of wins, what can we sayabout lower ranked players?LemmaThe second highest ranked player can win an SE tournament iffthe highest ranked player is not a Condorcet winner.RiggingTournamentBrackets forWeakerPlayersIsabelleStanton andVirginiaVassilevskaWilliamsRiggingTournamentsMotivationOur ApproachMatchingsThe third ranked player may be unable to win if there does notexist a matching onto the first and second ranked players.x1x2x3x4xkxk−1m1m2m3mk−2mk−1We can extend this example to show that without a perfectmatching onto the k higher ranked players, the k + 1 rankedplayer may