Tennis for the People II

~ Udi Wieder

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.

Published by Udi Wieder

4 thoughts on “Tennis for the People II”

  1. 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

    Reply

    1. I agree that the model above simplifies the game considerably, for many reasons. By the way, one technical difficulty with your suggestion is that the number of points is even whereas we must have an odd number of points. Regarding your question, I guess it is possible to push through an analysis with the product space you describe, though I haven’t done it.

      Reply

  2. One nice things about majority (or majority of majorities as in Tennis) is the fact that lopsided games end early. Thus for small p, we do not need to draw out all n tosses. I guess here we might have to do all tosses except O(log n/p) of them. Is there a simple modification to deal with this issue?

    Reply

    1. One way is to end the game if a run of say log n + 3 is obtained. We lose the transitivity property, but in a reasonable way. A more subtle issue I think is the distribution of ‘important points’. I wonder what is a sensible definition for that and what are requirements for a crowd pleasing game.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s