Some football wisdom from Dick Karp

 Cropped from S.I. Kids source

John Urschel is a PhD student in the Applied Mathematics program at MIT. He has co-authored two papers with his Penn State Master’s advisor, Ludmil Zikatanov, on spectra-based approximation algorithms for the ${\mathsf{NP}}$-complete graph bisection problem. A followup paper with Zikatanov and two others exploited the earlier work to give new fast solvers for minimal eigenvectors of graph Laplacians. He also plays offensive guard for the NFL Baltimore Ravens.

Today Ken and I wish to talk about a new result by the front linesman of ${\mathsf{NP}}$-completeness, Dick Karp, about football.

Karp—Dick—-is a huge fan of various sports. Recently at Avi Wigderson’s birthday conference, held at Princeton’s IAS, he told me a neat new result on how to play football. It concerns a basic decision that a coach faces after his team scores a touchdown: kick for one extra point or attempt a riskier “two-point conversion” play.

We wonder whether players like Urschel might be useful for blocking out these decisions, more than blocking and opening “holes” for runners. By the way Urschel, who attended Canisius High School in Buffalo before his B.S. and M.S. plus a Stats minor at Penn State, is no stranger to IAS. Here he is with my friend Peter Sarnak there last year:

 AMS Notices feature source

Thus he is doing all the things we would advise a young theorist or mathematician to do: publish, circulate, talk about interesting problems, get on a research team, and open up avenues for deep penetration and advances by teammates.

The Football Rules

After a touchdown is made the team scoring gets 6 points. It then has an option:

1. The team can kick the ball and try to get it through the goal posts. This is worth 1 extra point.

2. The team can try to get the ball into the end zone by running or throwing it. This is worth 2 extra points.

Traditionally the right call in most game situations is (1). Usually the kicker can make the ball go through the posts most of the time, while getting the ball into the end zone is much more difficult. Of course at the end of a game there may be reasons to try for the 2 points. If the game is about over and you need 2 points to tie, that is probably the best play.

Karp’s Insight

Karp set up a basic model of this decision. His model is a bit idealized, but I expect that he can and will make it more realistic in the future. The version I heard over a wonderful dinner that Kathryn Farley, my wife, set up for a small group of friends was not the proper venue to go into various technical details. So I will just relay his basic idea.

In his model we make several assumptions:

1. We assume that the kicker is perfect: every try for the kick option works. Especially now with the kick moved back from the 2 to the 15 yard line, that is a pipe dream for any coach in the NFL, but it makes the discussion cleaner.

2. We assume that the 2-point option succeeds 1/2 the time. That actually was exactly the case over a recent five-year stretch in the NFL.

3. We assume that the team will score many touchdowns and therefore will face many such decisions.

The last clause means that we’re modeling the choice by an infinite walk. If you wish you may subtract 1 so that a kick gives 0, a successful play gives +1, but an unsuccessful one gives -1. Karp’s question is this:

What should the coach do? Always kick or sometimes go for two?

$\displaystyle \dots$

His insight is this:

Theorem 1 (Fundamental Theorem of Football?) The optimal strategy is initially always to go for two. If after some number ${2t-1}$ of tries you have succeeded ${t}$ times, so that you are ahead of what kicking would have brought, switch over to kicking.

Not Gambler’s Ruin?

Ken’s first reaction was to note a difference from “gambler’s ruin” which means to double-down after every lost 50-50 bet. In football this would mean that after you missed one conversion play, the next try would bring +3 points on success but subtract 1 from your score if you missed. Next time you could go for 5 but failure would cost 3. If you think in the +1/-1 terms compared to 0 for kicking, then this is the classic martingale system of doubling the bet 1,2,4,8… until you win and net +1. The ruin for gamblers is the chance of swiftly going bankrupt—but in football you can only lose one game.

However, we are not allowing doubling the bet either. It’s the classic random walk situation: right or left along the number line with equal probability, except that you can elect to stop and stay where you are. With probability 1, such a walk starting at 0 will reach a stage in positive territory at +1 net, and then we stop.

A real game, of course, does not have unboundedly many touchdowns—though some college games I’ve watched have sure felt like it. So if you miss a few two-point tries and the game is deep into the second half, you’re left holding the bag of foregone points.

Toward Deepening the Result

The question comes down to, what is the utility of nosing ahead by the extra point when you succeed, compared to being down more when you fail? How likely are game scenarios where that one extra point is the decider? To be concrete, suppose you score 3 touchdowns in the first three quarters. Following Karp’s strategy nets you an extra point 5/8 of the time: succeed the first time then kick twice, or fail the first time and succeed twice. Just 1/4 of the time you’ve lost a point, but 1/8 of the time you’re net -3 and need an extra field goal to get back to par.

There are late-game situations where the extra point is worth so much that it pays to go for two even with a chance ${s}$ of success that is under 40%. Suppose you are down 14 points and score a touchdown with 4 minutes left. You have enough time to stop the other team and get the ball back again for one more drive, but that’s basically it. You have to assume you will score a touchdown on that drive too, so the only variable is the conversion decision. The issue is that if you kick now and kick again, you’ve only tied the game and have a 50% win chance in overtime. Whereas if you go for two you have an ${s}$ chance of winning based on this figuring, plus if you fail you can still tie and get to overtime after your next TD. Thus your win expectation is

$\displaystyle s + 0.5(1-s)s = 1.5s - 0.5s^2,$

which crosses 50% when

$\displaystyle s = (3 - \sqrt{5})/2 = 2 - \phi = 0.381966\dots$

When ${s = 0.5}$ you have a ${5/8}$ expectation by going for two. Yet for human reasons, this is not on the standard chart of game situations calling for a two-point try. The human bias is toward maximizing your chances of “staying in the game” which is not the same as maximizing winning. There was a neat analysis of a similar situation in chess last year.

The challenging question to deepen Karp’s insight is, how far can we sensibly broaden this kind of analysis? Does this observation apply in real games? It seems to call for a big modeling and simulation effort, guided by theory where we might vary Karp’s simple rule and adjust for different probabilities of success on both the two-point tries and the kicks. This would bring it into the realm of machine learning with high-dimensional data, and per remarks on Urschel’s MIT homepage, perhaps he is headed that way.

Open Problems

What do you think of the insight for football strategy? We could also talk about when (not) to punt…

Urschel missed this season’s first three games but is starting at left guard right now for the Ravens, who are beating up on my Giants 10-0 as we go to post. Oh well. Of course he reminds me I once took classes from an NFL quarterback who similarly “went for two” in football and mathematics. We wish Urschel all the best and will follow his careers with interest. Enjoy the games today and tomorrow night.

[de-LaTeXed numerals for better look]

1. October 16, 2016 5:16 pm

This seems similar to one of the issues that came up with Alpha Go – people thought the games were closer than they were against Hui (and then later against Lee Sedol) because the computer was maximizing win probability not expected different point score which are not necessarily the same thing.

2. October 17, 2016 2:17 am

I just don’t understand how the optimal strategy could only depend on the outcomes of the earlier tries. Shouldn’t it at least depend on the current score difference? Caveat: I know nothing about the rules of the game except for what you’ve described.