How to create tournaments that favor a player
Virginia Vassilevska is a post-doc at Berkeley, and she works in several aspects of computational complexity. Her main area of expertise is in algorithms for various problems on graphs; for example, she has worked on new algorithms for finding cliques in graphs.
Today I want to talk about some of Virginia’s recent work on “cheating.” I personally love the topic, and I think she has done some quite neat work on this problem.
Her work is on the complexity of “cheating” or “fixing” a single-elimination tournament. This seems especially relevant today, since Wimbledon just started—it is the oldest and perhaps most important of all the Grand-Slam tennis tournaments. More importantly it is a single-elimination tournament: lose one match and you go home.
Virginia’s paper will be presented at this summer’s AAAI. This is a conference of the Association for the Advancement of Artificial Intelligence (AAAI), and this year it is in Atlanta on July 11-15. You might want to look at the list of papers—many of the papers are on exactly the same topics we have at STOC/FOCS. There are papers on various algorithmic problems ranging from games, to economic problems, to routing problems, to approaches to solving SAT, and more.
I have never attended an AAAI conference, but I think I may start. Easy for me this time, since I live in Atlanta. The technical program looks very interesting, and I believe that many of the papers are relevant to complexity theory. I am curious to see how the authors of papers at AAAI think about problems—perhaps they will have some new insights that will help us in our research. Perhaps.
AAAI’s conference does some things differently from how we do them at our main conferences. For example, I noticed they have a senior track. At first I thought great, finally something special for some of us who have been around a while. But the truth is the track is for “survey” type talks. Oh well.
The Senior Member Presentation Track provides an opportunity for established researchers to give a broad talk on a well-developed body of research, an important new research area, or a thoughtful critique of trends in the field.
I wonder if we should have this at STOC/FOCS? Would you like to hear one of the “senior” members talk about new ideas or trends? I am interested to see how these talks go.
Let’s turn to Virginia’s results on cheating.
The names of the key concepts in this area are a bit confusing—this has nothing to do with Virginia, since the names are well established. To make this discussion clearer, I feel I need to change the names a bit. I hope this is okay. I hope it does make it easier to follow.
As you would expect there are players—what other variable could be used for the number of players? A rating is a complete directed graph on the players: for every two distinct players and either
Think of as meaning that player always beats player —always. Thus a rating is the bits of information of who beats whom. Note, a rating is not the method used to decide anything. It is just the name for all the information about who beats whom.
A rating is, of course, a “tournament” in the sense of graph theory. Seems confusing—no? That is why I decided to use slightly different names for this discussion.
Right away there is an idealization here. The assumption that a given player will always beat or lose to another player is clearly not true in real-life. If it were true there would be much less interest in watching Wimbledon. However, there are two reasons for making this assumption:
- For one, if probabilities are added, then the computational complexity of cheating becomes much harder. Even if the probabilities are restricted to be in the set
this and many problems become NP-hard. These results are due to Thuc Vu, Alon Altman and Yoav Shoham.
- For another, even in the deterministic case the questions of how cheating works is already quite involved and interesting.
So we will continue to assume that the ratings are perfect. If , then always beats .
A rating answers the question of whether or not a single player wins or loses to another player in head-to-head play. The central question is to use this information to select the “best” player. This is not easy, since as with voting problems there is no simple method for defining the best player. Clearly, if one player can beat all the others, then there is no problem. But if the rating has no such super-winner, then we need a mechanism to decide who is the best.
One popular method is the single-elimination tournament, which is what is being used right now at Wimbledon. Such a method is just a binary tree: at the leaves are the players, and as they play the winner moves up to the ancestor node. This continues until one player is at the root of the tree, and they are declared the “best.” They get the silver trophy, they get millions in prize money, and they are declared the best.
See Virginia’s paper for the formal definitions, but I hope it is clear what such a tree is. For example if there were just four players, Alice, Bob, Fred, and Eva, then a possible tournament would be
Note Alice is the winner, but it could be that Eva beats Alice in head-to-head play. Since they never play in this tree, Alice still wins. Let’s agree to call such trees tournaments.
Virginia proves a variety of interesting theorems—as usual see her pretty paper for the details. Here I will give a high-level view of her results.
Suppose that is a rating of players. The main question is when can we make a particular player the winner? This means: when is there a tournament so that when we play out the games the player is the winner. Let’s call this fixing the tournament in ‘s favor.
There are two kinds of results that Virginia proves. First, there are necessary conditions on and for this to happen. Clearly, there cannot be any player that beats everyone including . If this were true, then there is no way to fix a tournament in ‘s favor. Moreover, if the tree is balanced, then it is also easy to prove that must beat at least other players.
Second, Virginia proves some nice results about very strong players. She shows that if is a “super-king,” then there always is a way to fix a tournament so that wins. A player is a king provided for all other players either
or for some other player
Then is a super-king if is a king, but when there are at least players such that .
Theorem: Let rate players. If is a king and more over the number of so that
is at least , then there is a tournament where wins. Further this tournament can be constructed in polynomial time.
The main open question is: given a rating , determine if there is a way to fix a tournament so player wins. She leaves open the question of whether or not this is NP-hard, or has a polynomial time algorithm. I have no good intuition on this problem—I do not have a good guess whether the problem is easy or hard.
In the early days right after the discovery of the concept of NP-completeness, there was a “theory” advanced by Ian Munro. He said that given a new problem, whether it was easy or hard was determined by the first person who thought about it. If you looked at it first and tried to prove it was NP-complete, then it was hard; if you first tried to find a polynomial algorithm, then it was easy. According to this theory, it is too bad the first attempts at SAT were to prove that it was NP-complete.
I know Ian was kidding—he has a great sense of humor—but one wonders if there is something to this theory.
Finally, Ken Regan has a question: if the probabilities are “consistent” in the following technical sense, does this make deciding if a tournament can be fixed computationally easy? Assign to each player a skill rating , such as the Elo rating in Chess, which was created by Arpad Elo. Let the probability of depend only on . One can stipulate it to be 50-50 when , and be monotone-increasing in the difference.