Tag Archives: sports

Major League Baseball scheduling at the German OR Society Conference

Mike Trick talked about his experience setting the Major League Baseball (MLB) schedule at the 2014 German OR Conference in Aachen, Germany. Mike’s plenary talk had two major themes:
1. Getting the job with the MLB
2. Keeping the job with the MLB

The getting the job section summarized advances in computing power and integer programming solvers that have made solving large-scale integer programming (IP) models a reality. Mike talked about how he used to generate cuts for his models, but now the solvers (like CPLEX or Gurobi) add a lot of the cuts automatically as part of pre-processing. Over time, Mike’s approach has become popping his models into CPLEX and then figuring out what the solver is doing so he can exploit the tools that already exist.

Side note: I am amazed at how good the integer programming solvers have become. I recently worked on a variation to the set covering model for which a greedy approximation algorithm exists. The time complexity of the greedy algorithm isn’t great in theory. In practice, the greedy algorithm is slower than the solver (Gurobi, I think) and doesn’t guarantee optimality. I can’t believe we’ve come this far.

Mike also stressed the importance of finding better ways to formulate the problem to create a better structure for the IP solver.  Better formulations can be more complicated and less intuitive, but they can lead to markedly better linear programming bounds. Mike achieved this by replacing his model with binary variables that correspond to team-to-team games (does team i play team j on day t?) with another model whose variables correspond to series (a series is usually 3 games played between teams on consecutive days). Good bounds from the linear programming relaxations help the IP solver find an optimal solution much quicker. Another innovation focused on improving the schedule by “throwing away” much of the schedule (usually about a month) after making needed changes and resolving. Again, this is something that is possible due to advances in computing.

The keeping the job section addressed business analytics and its role in optimization. Mike defined business analytics as using data to make better decisions, something that OR has always done. What is new is using the power of data analytics and predictive modeling to guide prescriptive integer programming models in a meaningful way. The old way was to use point estimates in integer programming models, the new way uses more information (such as the output of a logistic regression) to guide optimization models. The application Mike used was estimating the value of scheduling home games at different times (day vs. night) and day of the week. When embedded in the optimization modeling framework, the end result was that creating a schedule using business analytics could add about $50M to MLB in revenue. 

Mike summed up his talk but talking about how educating the marketing folks is part of the job now. Marketing likes to measure “success” as the number of games that sell out. Operations researchers recognize that sold out games are lost revenue, so the goal has become to schedule games such that games are almost sold out, and making sure that marketing understands this approach.

Related post:

the craft of scheduling Major League Baseball games


Markov chains for ranking sports teams

My favorite talk at ISERC 2014 (the IIE conference) was “A new approach to ranking using dual-level decisions” by Baback Vaziri, Yuehwern Yih, Mark Lehto, and Tom Morin (Purdue University) [Link]. They used a Markov chain to rank Big Ten football teams in their ability to recruit prospective players. Players would accept one of several offers. The team that got the player was the “winner” and the other teams were losers.  We end up with a matrix P where element (i,j) in P is the number of times team j beats team i.

The Markov chain is then normalized so that each row sums to 1 and solved for the limiting distribution. The probability of being in team j in the limit was interpreted as meaning the proportion of time that team j is the best. Therefore, the limiting distribution can be used to rank teams from best to worst.

They found that using this method with 2001 – 2012 data, Wisconsin was ranked fourth, which was much higher than it was ranked by experts and explains why they have been to 12 bowl games in a row. Illinois (my alma mater) was ranked second to last, only above lowly Indiana.

I used this method regular season 2014 Big Ten basketball wins and ended up with the following ranking. I also have the official ranking based on win-loss record for comparison.  We see large discrepancies for only two teams: Michigan State (which is over-ranked according to its win-loss record) and Indiana (which is under-ranked according to its win-loss record). The Markov chain method ranks these two teams differently because Indiana had high quality wins despite not winning so frequently and because Michigan State lost to a few bad teams when they were down a few players due to injuries.

 

Ranking MC Ranking W-L record  Ranking
1 Michigan Michigan
2 Wisconsin Wisconsin
3 Indiana Michigan State
4 Iowa Nebraska
5 Nebraska Ohio State
6 Ohio St Iowa
7 Michigan St Minnesota
8 Minnesota Illinois
9 Illinois Indiana
10 Penn St Penn State
11 Northwestern Northwestern
12 Purdue Purdue

Sophisticated methods are a little more complex than this. Paul Kvam and Joel Sokol estimate conditional probabilities in the transition probability matrix for the logistic regression Markov chain (LRMC) model using logistic regression [Paper link here]. The logistic regression yields an estimate for the probability that a team with a margin of victory of x points at home is better than its opponent, and thus, looks at margin of victory not just wins and losses.

 


subjective scoring in Olympic sports drives me a little crazy

The Olympics are beginning. When I think of the Olympic sports, I think of a lot of sports that scored subjectively. Not so much stronger, faster, and more goals, more of panels of judges picking winners amid controversy. I prefer number crunching and objective scoring. A New York Times article by John Branch [Link] overviews the changes to the winter Olympic sports in the last two decades. In summary, the new sports are mostly those with  subjective scoring (halfpipe, snowboard cross).

A good run early in the contest might receive an 80. A slightly better run might earn an 83. A brilliant run, one that seems unbeatable, might score 95. All of the others are slotted around them. It can frustrate athletes, who ask why their second-place score was 10 points below that of the winner. They struggle to understand that the value means nothing; what matters is how it ranks.

I’ve noticed this, too, and it’s frustrating. Some sports like figure skating and gymnastics have well-established rubrics for scoring, but they are not perfect. On the positive side, the judges do a fairly good job of recognizing the best performances.

Does subjective scoring bother you?

~

Look for more Olympics posts from me in the next couple of weeks.

I’ve been blogging for almost 7 years, so I have a few old posts about the Olympics. Here are a few that I recommend reading:


will the New York Times Fourth Down Robot change football?

The New York times runs a twitter account for a “Fourth Down Bot” (@NYT4thDownBot) that analyzes every 4th down call in NFL football games. The bot gives advice and sometimes a short report summarizing the probability of success associated with each of the choices:

The bot has a lot of personality!

Brian Burke provides the methodology, which is here. The recommendations are based on which actions (going for it, punting, or going for a field goal) yields the most expected points. In the last 10 minutes of a game, the bot selects recommendations based on which yields the highest win probability. These concepts are not equivalent – going for it may maximize your points, but if time is running out and you are down by two, it might be better to go for a field goal than try for a touchdown.

The bot is useful because there is such a huge difference what is the best strategy and what coaches actually do. The picture below illustrates the difference. There are a number of explanations for the difference. One is that fans and owners only remember the times it doesn’t work–following the optimal policy may maximize the number of wins on average, but losing a game could mean losing your job. When the objective is to keep your job and not win games, everyone gets used to more conservative and suboptimal play calling.

Fourth Down Bot's recommendations as compared to what most coaches do.

Fourth Down Bot’s recommendations as compared to what most coaches do.

Sports nerds have known about this issue for a long time. I’ve even blogged about it before (here and here).

The Fourth Down Bot is so high profile that it has really raised awareness of this issue, possibly to the point that it may change how the game is played. If the fans know that it is better to go for it on fourth down and if the coaches and owners read the scathing fourth down reports questioning their decision-making, then maybe it will be unacceptable for coaches to cling to sub-optimal policies. Maybe I’m too optimistic about the Fourth Down Bot’s chance at improving scientific literacy to the point when the game changes. It’s possible that coaches and owners will be dismissive of math models and the nerds who make them, but I hope the Fourth Down Bot chips away at our society’s distrust of math.

It’s worth noting that the Fourth Down Bot is genderless and does not have a race. Until I blogged about the bot, all of the sports nerds and number crunchers I’ve read and blogged about are men. I can’t be the only women interested in these issues. Please introduce me to other women and minority sports nerds – I am more than willing to promote sports number crunchers from underrepresented groups.

Has the Fourth Down Bot changed the way you think about football? Do you think the Fourth Down Bot has the potential to change the game?


decision quality and baseball strategy

Miss baseball? Love operations research and analytics? Watch Eric Bickel’s 46-minute webinar called “Play Ball! Decision Quality and Baseball Strategy” here:


before Sabermetrics, there was football analytics

I enjoyed a recent Advanced NFL Stats podcast interview with Virgil Carter [Link], a former Chicago Bears quarterback who is considered to be the “father of football analytics.” During his time in the NFL, Carter enrolled in Northwestern University’s MBA program, and he started to work on a football project that was eventually published in Operations Research in 1971 (before Bill James of baseball analytics and Sabermetrics fame!). Carter even taught statistics and mathematics at Xavier University while on the Cincinnati Bengals.

The paper in Operations Research was co-written with Robert Machol and entitled “Operations Research on Football.” The paper estimates the expected value of having a First-and-10 at different yard lines on the field (see my related post here). Slate has a nice article about Virgil Carter [Link] outlining the work that went into estimating the value associated with field position:

Carter acquired the play-by-play logs for the first half of the 1969 NFL season and started the long slog of entering data: 53 variables per play, 8,373 plays. After five or six months, Carter had produced 8,373 punch cards. By today’s computing standards, Carter’s data set was minuscule and his hardware archaic. To run the numbers, he reserved time on Northwestern’s IBM 360 mainframe. Processing a half-season query would take 15 or 20 minutes—something today’s desktop computers could do in nanoseconds. In one research project, Carter started with the subset of 2,852 first-down plays. For each play, he determined which team scored next and how many points they scored. By averaging the results, he was able to learn the “expected value” of having the ball at different spots on the field.

They found that close to a team’s own end zone (almost 100 years from scoring a touchdown), a team’s expected points was negative, meaning that turnovers from fumbles and interceptions leading an opponent to score an easy touchdown outweighed a team’s own ability to move down the field and score. The paper discusses issues other than expected values, such as Type I and Type II errors using time outs. Here, the a timeout that controls time management has implications on each team’s remaining possessions, and using too much or too little time. The rules of football were quite different 40-something years ago. For example, an incomplete pass in the endzone required the ball to be brought out to the 20 yard line (instead of a mere loss of a down with no change in field position).

Listen to the podcast here.

Read my posts on football analytics here.


the craft of major league baseball scheduling – a journey from 1982 until now

Grantland and ESPN has a short video [12:25] on the couple who created the major league baseball schedules in the pre-Mike Trick era (1982-2004). The husband-and-wife team of Henry and Holly Stephenson used scheduling algorithms to set about 80% of the schedule. They found that the their algorithm could not come up with the entire schedule because the list of scheduling requirements led to infeasibility:

“It couldn’t do the whole schedule. That was where the big companies were falling apart. We analyzed the old schedules and found that none of them met the written requirements that the league gave to us. It turns out it was impossible to meet all of the requirements. So the secret was to really know how to break the rules.”

Watch the video here. The end of the video acknowledges how scheduling has evolved such that the entire schedules can be computer generated using combinatorial optimization software (the Stephensons even mention having to compete with a scheduling team from CMU). The video uses baseball scheduling as an avenue to illustrate how decision making and optimization has evolved in the past 30 years. I would highly recommend the video to operations research and optimization students.

 


Follow

Get every new post delivered to your Inbox.

Join 2,211 other followers