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.

Ratings

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 ${n}$ players—what other variable could be used for the number of players? A rating ${R}$ is a complete directed graph on the ${n}$ players: for every two distinct players ${x}$ and ${y}$ either

$\displaystyle x \rightarrow y \mathrm{ \ or \ } y \rightarrow x.$

Think of ${a \rightarrow b}$ as meaning that player ${a}$ always beats player ${b}$—always. Thus a rating ${R}$ is the ${ n \choose 2 }$ 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 ${R}$ 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

$\displaystyle \{ 0, 1/2, 1 \}$

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 ${R}$ are perfect. If ${a \rightarrow b}$, then ${a}$ always beats ${b}$.

Tournaments

A rating ${R}$ 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 ${n}$ 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.

Fixing 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 ${R}$ is a rating of ${n}$ players. The main question is when can we make a particular player ${p}$ the winner? This means: when is there a tournament ${T}$ so that when we play out the games the player ${p}$ is the winner. Let’s call this fixing the tournament in ${p}$‘s favor.

There are two kinds of results that Virginia proves. First, there are necessary conditions on ${p}$ and ${R}$ for this to happen. Clearly, there cannot be any player ${q}$ that beats everyone including ${p}$. If this were true, then there is no way to fix a tournament in ${p}$‘s favor. Moreover, if the tree is balanced, then it is also easy to prove that ${p}$ must beat at least ${\log_2 n }$ other players.

Second, Virginia proves some nice results about very strong players. She shows that if ${p}$ is a “super-king,” then there always is a way to fix a tournament so that ${p}$ wins. A player ${p}$ is a king provided for all other players ${q}$ either

$\displaystyle p \rightarrow q,$

or for some other player ${r}$

$\displaystyle p \rightarrow r \rightarrow q.$

Then ${p}$ is a super-king if ${p}$ is a king, but when ${p \not \rightarrow q}$ there are at least ${\log_2 n}$ players ${r}$ such that ${p \rightarrow r \rightarrow q}$.

Theorem: Let ${R}$ rate ${n}$ players. If ${p}$ is a king and more over the number of ${q}$ so that

$\displaystyle p \rightarrow q$

is at least ${n/2}$, then there is a tournament where ${p}$ wins. Further this tournament can be constructed in polynomial time.

Open Problems

The main open question is: given a rating ${R}$, determine if there is a way to fix a tournament so player ${p}$ 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 ${a \rightarrow b}$ are “consistent” in the following technical sense, does this make deciding if a tournament can be fixed computationally easy? Assign to each player ${p}$ a skill rating ${S(p) \ge 0}$, such as the Elo rating in Chess, which was created by Arpad Elo. Let the probability of ${p \rightarrow q}$ depend only on ${S(p) - S(q)}$. One can stipulate it to be 50-50 when ${S(p) = S(q)}$, and be monotone-increasing in the difference.

June 23, 2010 7:31 am

The senior member presentation track idea is pretty cool.

June 23, 2010 10:10 am

The problem is not limited to cheating. It could have just as easily have been phrased “If players are randomly placed in the tournament, is the probability of p winning non-zero?”

Or one could ask what the probability is. Clearly, it is one iff p beats everyone.

Typically, placement in the tournament is neither random, nor chosen by someone who could “cheat”. More often there are preliminary rounds where each player plays several games. Placement in the single elimination tournament is determined from the results by a fixed algorithm (usually designed to put the best players as far apart in the tree as possible, sometimes eliminating some players completely).

Of course, that just adds a layer of complexity. Is there an arrangement of the preliminary rounds that produces a winning tree for p?

June 23, 2010 6:03 pm

Re: “If players are randomly placed in the tournament, is the probability of p winning non-zero?”
Of course this question is equivalent to the problem my paper is about.
In an older manuscript I did consider actually computing the _number_ of
tournament brackets that p can win; i.e. computing the probability that p wins a random bracket. I was thinking that this might be a new way to rank players in a round-robin tournament. For this counting problem I was able to obtain an O(2^n) time algorithm, and this is already not obvious; with a straightforward dynamic programming approach you just get O(4^n). That algorithm didn’t use any properties of tournament graphs;
it worked for arbitrary digraphs, and it is not hard to see that this counting problem
for arbitrary digraphs is #P-complete, so if you are hoping for a polytime algorithm, you might be asking for too much. (though approximate counting might be possible?)

Our knowledge about tournament graphs is quite limited at this time, and
this is the most likely reason why this problem has remained open. Rigging a single-elimination tournament in polytime is a very exciting problem, and there are several groups of people who currently work on it. Here are some of them: [Vu,Altman,Shoham] (who Dick mentioned), [Hazon,Dunne,Kraus,Wooldridge], [Lang, Pini, Rossi, Venable, Walsh], [Fischer,Procaccia,Samorodnitsky], and Isabelle Stanton and myself.

Contrary to your belief, there is actually some cheating in sports related to bracket rigging: I was involved in Div III tennis a while back. There the match format for two teams was as follows: each team produces a ranking of its players and presents it at the start of the match. Then player i from team one’s ranking plays against player i from the other team’s ranking, and the score is determined by the number of matches each team has won
(there’s also some doubles play but let’s ignore this). Here a team can get an advantage
by “stacking” their ranking — putting their real top players at the bottom of their ranking. If the other team is honest, then the first team can win without actually being better. Needless to say, our team was always honest… 🙂

3. June 23, 2010 12:09 pm

I think this blog serves as a ‘senior member’ track. And many more people get something out of it, I daresay.

June 23, 2010 3:10 pm

Another interesting question is whether, if we admit probabilities into the rating, whether a tournament-tree can be constructed which garuntees a uniform probability of winning (a fair tournament rather than a cheating one) within a factor epsilon and what the computational complexity of an algorithm to construct such a tree from a rating would be.

5. June 23, 2010 9:12 pm

Usually people approach tournaments with the idea that every participant has a single scalar quality level, and eir chance of winning an individual match is a function of the levels. Then probabilities are transitive—if A is favored to beat B and B favored over C, then A should beat C.

However, “ratings” can be multi-dimensional. For instance, suppose we give soccer teams separate numerical ratings for (a) rock-solidness of defense, (b) ability to cover the field, and (c) quality of scissor-like attacks. The scissor skill (c) might beat a spread-out team (b) but get blunted by a rock-approach (a), while (b) might bring enough ball-control smothering to erode (a). This allows non-transitive win probabilities—of course, I’ve grafted “rock-paper-scissors” onto soccer :-). One can make the overall win probabilities a function of numerical differences in the labeled categories (a,b,c)—where the function is not necessarily symmetric. This brings the notion of “rating” into line with its usage in the blog post for a preordained head-to-head results table, i.e. “tournament” in the graph-theory sense.

The question this raises is, given a set of probabilities, how high a “dimension” d is needed to realize them via d-dimensional ratings? Has anyone considered this?

[For a side note, in chess and other circles, it is generally believed that the strongest player/team has a higher chance of prevailing in a round-robin tournament than an elimination tournament, even one with best-of-7 series like the Stanley Cup. With straightforward modeling of win probabilities, this is a theorem for most sets of parameters (size of field, # of games in a series, whether ties are possible…). The main knocks against round-robin are the greater # of games, having many “meaningless” games in later rounds, and the leaders often not meeting in the final rounds.]

6. June 24, 2010 12:15 am

In the probabilistic case, what is the definition of “fixing” the tournament? (Obviously you cannot guarantee a particular player will win…)

June 24, 2010 6:03 pm

Maybe maximizing the probability of player p to be victorious?

June 25, 2010 9:54 pm

In general the problem is referred to as the “agenda control problem for balanced knockout tournaments”.
The restriction when there is an implicit ranking of the players by abilities and the winning probabilities obey the relations (p(i beats j)>= p(i beats j-1)) for all i and j and (p(i,j)>=1/2 when i= p(i beats j-1) for all i and j and some eps>0, then the problem is NP-hard (a result of Vu,Altman,Shoham).

June 25, 2010 9:47 pm

Great post

8. June 26, 2010 12:09 am

Is the answer to the following question, which is a variant, known?

Given a tournament and a node p, what is the probability of p winning when
the contest involves picking two players at random, finding the winner, then
pairing the winner with another random (remaining) player, pairing the
winner of that match with another randomly chosen player, and so on?
(I.e. we do sequential pairwise contests, in a linear fashion, rather than in
tree-structured manner)

• July 5, 2010 8:32 pm

I don’t think this is known. If we allow players to be chosen multiple times (to compete with the current winner), we essentially do a random walk on the tournament. We have a result that says that this random walk quickly reaches the stationary distribution, which in expectation chooses a player with degree at least half the maximum degree (but not much better, which is quite surprising). The result is in the following paper, along with some nice open problems: http://www.tcs.ifi.lmu.de/~fischerf/publications/fps_trees.pdf

July 13, 2010 9:11 pm

I hope I understand the problem correctly:
You are given players 1,…,n and probabilities p(i,j) for every i<j of i beating j (p(j,i)=1-p(i,j)) and player node P. Now, consider a caterpillar tree T rooted at P (this is a tree in which all the nodes
are within distance 1 of a central path.) Think of P as being one end of the central path and the edges as being directed away from P. Any one of your random voting runs can be represented as one of these trees and the number of voting runs that a particular tree represents is Product_i (di-1)! where i ranges over the nodes on the central path and di is the outdegree of each i.
Now, you want to compute the sum over all T of (the product of the probabilities on edges of T)*(number of voting runs T represents).

You can probably get an estimate of the above weighted sum via sampling (though I haven't thought this through). I am not sure how to compute it exactly.

Another slightly related result, besides the one that Felix mentioned, is by Hazon,Dunne,Kraus, and Wooldridge: they showed that if you are given players 1,…,n, probabilities p(i,j) of i<j beating j, a node P and a value v, then determining whether there is a permutation pi of 1,…,n starting with P such that the product of p(pi(i),pi(i+1)) is at least v, is NP-complete. I do think though that your problem may be easier since it is about computing a weighted sum, as opposed to finding a pattern.

10. June 23, 2014 7:25 pm

Regarding the open problem, you may be interested in our recent paper

http://www.cse.unsw.edu.au/~sergeg/papers/AzizGMMSW14.pdf