I continue the discussion from last post. We are trying to add unpredictability to tennis by looking for a monotone, transitive and balanced function $f$ such that $E_p(f)$ has a wide threshold window, that is, we want the range of $p$ where $E_p(f)$ is, say, between 0.01 and 0.99, to be as large as possible. A formal treatment of this problem could be found in the seminal paper of Kalai and Freidgut. The major simplifying step we take is to look at the derivative of $E_p(f)$ at the point $p=1/2$ as a proxy for the width of the window. Think of it as the first order linear approximation for the (inverse of the) width of the threshold window: the smaller the derivative the wider the window.

The main tool to help us reason about the derivative is Russo’s formula, but first a definition: given ${x_1,.. ,x_n}$ we say that bit $x_i$ is pivotal if flipping $x_i$ changes the value of $f$.  The total influence of the function is the expected number of pivotal bits when $x_1,..,x_n$ are drawn uniformly at random. Russo’s formula states  that for monotone functions the derivative of $E_p(f)$ at $p=1/2$ is exactly the total influence of $f$!

One way to see why Russo’s formula makes sense is to think about the definition of a derivative and observe that increasing $p$ by a small amount could be thought of as picking a bit at random and setting it to 1. Now, the probability that $f$ changes its value is proportional to the number of pivotal bits.

We now face a well-defined challenge of coming up with a function satisfying our constraints and with small total influence. As a sanity check it is easy to observe that the total influence of the majority function is indeed roughly $\sqrt n$. The reason is that with probability about $1/\sqrt n$ the majority is by exactly one point, in which case half the bits are pivotal.

What about majority of majorities, or better yet , recursive-majority of three values? Well, the total influence of recursive majority can be computed to be roughly $n^{0.37}$, which is an improvement over simple majority (not surprising since simple majority could be shown to have the maximal total influence of all monotone Boolean functions). But is it the best?

The answer is given in the celebrated theorem by Kahn, Kalai and Linial which implies in our case that the total influence is $\Omega(\log n)$. A tight example was provided by Ben-Or and Linial in the TRIBES function. In the TRIBES function the bits are partitioned to sets (‘tribes’) of roughly $\log n$ –  $\log{ \log n}$ bits each. Player ‘1’ wins if there is a tribe with all its bits set to 1. Player ‘0’ wins otherwise. The function is clearly transitive and monotone. Exact parameters can be set so that  it is approximately balanced. To see that the total influence is small observe that for a bit to be pivotal it has to belong to a tribe where all the other bits are 1, which happens with probability about $\log n/ n$ so the total influence is $O(\log n)$.

So is TRIBES a good candidate for an athletic game? I don’t think so, for several reasons.  First, it is not exactly balanced, I can’t imagine an athlete happy with a game where he is unlikely to win even when competing on equal grounds point by point. Second, there is a difference between the role of player 1, which plays offense trying to obtain a tribe, and player 0 which plays defense trying to block player 1. Both problems are rectified by adding another requirement. We want the function  to be symmetric, that is $f(1-x)=1-f(x)$. This means that when flipping all bits the outcome also flips and since $f$ is also monotonic it also means it is balanced.

Cycle-Run

Here is a suggestion for a transitive, monotone, symmetric function, with low total influence. We call it Cycle-Run and it could be viewed as a symmetric version of TRIBES.  Call a consecutive sequence of ‘1’’s  a 1-run. Similarly a consecutive sequence of zeros is a ‘0-run’. We allow runs to wrap around, so if a run reaches $x_n$ it may continue with $x_1$.  The value of $f$ is determined as follows:

1. Check which player has the longest run.
2. In case of tie check which player has a larger number of maximal runs.
3. In case of tie check the total length of segments between maximal runs, where a segment starting from a 1-run clockwise is counted for the 1-player and a segment starting at a  0-run clockwise is counted for the 0-player. The player that has a larger total count is declared the winner.

In the example below both players have a single maximal run of length 3, but player 0 wins the tie breaker 9-2.

Monotonicity and  symmetry are readily verifiable. Transitivity is obtained via rotations of the cycle. Why is the total influence logarithmic? One way to see it is to observe that the expected number of runs of length $k$ is $n2^{-k}$, so the expected number of runs longer than $\log n$ is smaller than 1. Further work is required, but basically this is the reason. If you want to do the calculations yourself you may find this survey useful.

So is this useful? In practice most tennis matches consist of roughly 200-400 points. Below we plot Majority, Recursive Majority and Cycle-Run for n=243.

We see that indeed Majority  has the narrowest threshold window and Cycle-Run the widest. The difference between Cycle-Run and Recursive-Majority is not that big. When $p=0.4$ the probability of an upset rises from roughly 3% to 5.3%. Asymptotics however don’t lie and when n is increased to 2187 the differences are quite striking.

Now, when $p=0.45$, for simple majority the probability of an upset is negligible. For recursive majority it is less than 2% and for cycle run it is more than 11%.

What about real life? I have the data of three tennis matches.

In these three examples all rules have the same result. An anecdotal observation is that at least in these cases the winning run tends to be very close to the end of the match, suggesting that the mental aspect of the game plays an important role.

So should we petition the ATP for a rule change?

Credits:

This post is the outcome of discussions with Parikshit Gopalan, Yuval Peres, Omer Reingold and Kunal Talwar.

The data was given to me through the generosity of Daniele Paserman and the facilitation of Ran Abramitzky.

Professional tennis is a good setting for researching human decision-making when payoffs are well defined. If you want to read some cool papers checkout a paper by Daniele and a paper by Ran.

November 17, 2012 12:04 am

Excellent posts, Udi.

One thing slightly complicating the tennis application is that the player serving has an advantage, so it is a bit too simplistic to simply say that the game consists of a sequence of “same” bits x_i, as the decision must be made who is serving for each i. I suppose one simple rule is to make the players alternate their serves, although this is slightly not nice as people like to serve for a while; gives them a sense of continutiy. To fix this, we can play n/2 points as follows: have player 1 start serving, and then the winner of the point serves the next point. Then, after n/2 points the same is repeated with player 2 starting. And then compare the maximum runs in both cases with something ugly in case of a tie. (Or, more generally, have have 2t “sets” of n/2t point each with something to aggrgate the 2t maximal runs.) This is also nice as it gives explicit reward for “keep holding my serve”. Another advantage of this is that the rules become very clean. Serve until you lose serve, and try to maximize the number of points you win consecutively. (Here I ignore a slight asymetry at the beginning, but I suspect it’s effect if negligible if n is large.)

With these tules, we get something VERY similar to badminton and voleyball (where new set has a different player starting, or maybe a loser, I forgot). The main differences are: (a) maximum total number of sets is odd, not even (so no need for “ugly” rule 3); (b) more importantly, you are trying to maximize the length of the run, not the number of sets you win (which is important for incluence); (c) not important, but in both badminton and voleyball the server is actually at DISADVANTAGE, so the runs are likely very short, even when one polayer is much better. (does it mean we should change it, and the winner receives in these games? Not sure…)

Overall, the main question is if your simplified analysis through influence stills holds when there are two probabilities involved (Pr(servring 1 wins)=p and Pr(receiving 1 wins)=q).

What do you think?
Yevgeniy