Yavuz, M., Inan, U.H., Figlali, A. "Fair referee assignments for professional football leagues", Computers and Operations Research, 35: 2937-2951, 2008. [Citation]

[From the abstract] Assignment of referees to football games is an important problem faced in professional football leagues. Despite its importance, the problem has received limited academic attention. This paper presents a model and analysis of the problem for fair referee assignments, and develops a constructive heuristic and a local search procedure for its solution. Results from an extensive computational study show that the methods are effective in solving the problem in a second of computation time and yielding an excellent solution quality.

————-

Recently, I have become interested in scheduling problems related to football, so I have been reading papers and presentations to become more knowledgeable about the types of scheduling issues and the technical challenges involved with solving them.  It's a topic with some academic interest but one that I think is compelling to leagues and confederations.  Scheduling of football matches was addressed in a previous post.  This post will take a look at referee assignments.

I am particularly pleased to review this paper because the lead author is a former co-researcher and friend from my postdoc days.  Mesut Yavuz was a postdoc at the University of Florida's Research and Engineering Education Facility, and our offices were in the same building of the REEF.  (My appointment was with the US Air Force Research Laboratory at Eglin Air Force Base,  but the REEF was located outside the front gates and it was easier to collaborate with civilians there.)  We had collaborated on a research project but we weren't able to get very far (technical challenges and other projects assuming priority).  I never knew that Mesut was also into research projects related to soccer; maybe we should have collaborated there!  At any rate, Mesut is now a business professor at Shenandoah University in western Virginia (not West Virginia as I had originally written).  The other two authors are professors from universities in Turkey, where Mesut is from originally.

The objective of the referee assignment problem is to assign referees fairly; that is, to avoid frequent assignment of referees to a team's matches.  Yavuz et al. set up the problem as a constraint satisfaction model where a referee is assigned to a specific match of a matchday in the competition, under "hard" or "soft" constraints.  Hard constraints are those that have to be met, for example:

• A referee cannot officiate more than one match in a matchday (Yavuz calls this a stage)
• Exactly one referee is assigned to a match.

Soft constraints are ones that are allowed to be violated in order to make the problem feasible:

1. A spacing constraint — minimize the number of consecutive matches a referee officiates
2. Ref-team all assignments — minimize the number of matches a referee officiates that features the same team
3. Ref-team home match assignments — minimize the number of matches a referee officiates that features the same home team
4. Minimum assignment — assign more matches to the "best" referees, therefore requiring certain refs to work a minimum of matches
5. Same game constraint — prevent situations in which the same referee works A vs. B and the return match B vs. A

To solve the optimization problem, we sum up the numbered constraints into a cost function and minimize that function subject to the hard constraints and the state equation, which describes the assignment of a specific referee to a specific match of the matchday.  There is a lot of notation and summation symbols in this formulation, which can be intimidating, but the math isn't particularly difficult.  There are two complicating factors with this formulation, however.  First, the objective function contains max and sign functions, which makes the function nonlinear. Second, the problem is NP-Complete, which means that it's really, really hard to solve by conventional optimization solvers.

(Just to give an indication of how difficult this problem is, say we wanted to assign referees to a four-team group stage from a pool of six referees, which is essentially a typical group stage in the Champions League or the World Cup.  In each matchday, we can assign referees to the two matches in 6!/2! = 360 ways.  Over a six matchday competition, there are 360⁶ = 2.18×10¹⁵ distinct assignments.  If each assignment takes a nanosecond to evaluate, it would still take us almost a month to evaluate them all!)

 Yavuz and his collaborators route around this difficulty by using heuristics.  To simplify the algorithm greatly, a heuristic takes a feasible solution to the optimization problem and makes it better through an iterative process.  For this problem, two different heuristics are considered: a constructive heuristic in which the problem is solved one stage (matchday) at a time, and a local search procedure, in which an initial solution is improved by looking around its neighborhood of alternative solutions for something better. 

The referee assignment approach is tested against the current system of referee designation in the Turkish Süper Lig, in which an independent board selects the referees.  Yavuz et al. first tested the current system against a randomized selection procedure.  They found that the current selection system actually performed worse against the randomized procedure; the only constraints in which the board performed better were the same game constraint and the ref-team home match constraint.  The heuristic methods were better across the board and greatly reduced the number of constraint violations.

Yavuz et al. pointed out a few directions for research, and I have a couple more.  First of all, the current project only considered the central referee.  Further extensions should consider the selection of the central referees, the linesmen, and the fourth official, with the central referee and fourth official drawn from one referee pool and the linesmen from another.  Another extension is the integration of referee performance as adjudged by a review board, which could be used to update the referee selection for future matchdays.  A third extension would be the selection of the most experienced referees to matches of varying levels of criticality, whether derby matches, top-of-table matches, or relegation deciders. It would also be interesting to apply this work to non-round-robin competitions, which will be the case in MLS starting next season.

Yavuz has written a very valuable contribution to the referee assignment problem, in particular the framework for describing the optimization problem.  I believe that this is a compelling issue to the league and its clubs, but it will take some effort to implement this approach in league offices.  Maybe it is already happening.  There are a number of further extensions to the problem, but my friend has provided a good starting point.