Celso C. Ribeiro
Sebastián Urrutia
FUTMAX:
Play-offs elimination in
soccer tournaments
Summary







Motivation
Related work
Problem definition
Formulation
FUTMAX in the WWW
FUTMAX in the press
Results
April 2004
FUTMAX Chile
FUTMAX 2/25
Motivation
 Guaranteed Qualification Problem:
How many points a team has to make in a
tournament to be able to be qualified for the
finals (or play-off games)?
 Brazilian Soccer Championship:
Press broadcasts already at the first round the
“chances of qualification” for the play-offs, based
in very obscure statistics and estimates.
 Predictions loudly announced are often wrong!
April 2004
FUTMAX Chile
FUTMAX 3/25
Motivation
 Interesting application of Operations Research
and Integer Programming in sports.
 Soccer is the most popular sports in most
countries.
 Soccer can even make researchers from
Argentina and Brazil to work together, instead of
trying to prove which of them is the best...
 … or arguing about who is the second best
player ever!
#1
April 2004
FUTMAX Chile
FUTMAX 4/25
Motivation
 Three teams fight for two places in the play-offs.
 Each of them has two games to play: Flamengo
against Vasco and Bahia, Cruzeiro against
Grêmio and Santos, and Bahia against
Flamengo e Fluminense.
 How many points Cruzeiro has to make to be
Flamengo
37
sure of being qualified?
Cruzeiro
37
4 points!
Bahia
April 2004
FUTMAX Chile
36
FUTMAX 5/25
playing?
São Paulo
São
34 Ponte Preta 26 Fluminense 21
32 Figuerense 24 Vasco
20
Santos
Juventude
32 Atlético-PR
31 Grêmio
24 Goiás
20
24 Portuguesa 20
Corinthians
Guarani
Vitória
Coritiba
Atlético-MG
31
28
27
27
27
23
22
22
22
21
April 2004
Cruzeiro
Gama
Internacional
Botafogo
Bahia
FUTMAX Chile
Paysandu
Flamengo
Palmeiras
Paraná
19
19
19
17
FUTMAX 6/25
Motivation
 Brazilian soccer championship (2002 edition)
 26 teams
 First phase: qualification
• Each team plays every other team exactly once.
• The eight teams in the first positions are qualified.
• The four teams in the last positions do not play next
year.
 Second phase: play-offs
• Eliminatory games
 Points:
• win: 3 pointstie: 1 point loss: 0 point
April 2004
FUTMAX Chile
FUTMAX 7/25
Motivation
 Brazilian championship:
• 29 rounds from August to December
• The press publishes since the first round (!) the
probabilities of qualification of each team.
• The press also makes use of very simple statistics
from obscure sources to announce very early that a
team with a certain number of points (41 in 2002)
can be sure to be qualified (often based on
estimates or average results).
• These predictions are loudly announced and often
false!
• Trainers also very often make erroneous predictions.
April 2004
FUTMAX Chile
FUTMAX 8/25
Related work
 Schwartz 1966: mathematical elimination
from play-offs in the Major League Baseball
(MLB) solved with maximum flow algorithm
 Robinson 1991: integer programming
models and further results for the play-offs
elimination problem
 McCormick 2000: elimination from the p-th
position is NP-complete.
 Adler et al. 2003: ILP models for MLB
 Bernholt et al. 1970: first place elimination
is
NP-complete
the {(3,0),(1,1)}
April 2004
FUTMAX under
Chile
FUTMAX 9/25
Related work
 Berkeley’s RIOT project posts the number
of wins each team needs to have a chance
of qualification in the MLB:
•
•
•
•
No ties
Easier {(1,0)} rule
Small groups with 5 or 6 teams
A team has to finish in the first position within
its group to be qualified.
• Each team plays up to 160 games!
• Problems in each group are easily solvable.
April 2004
FUTMAX Chile
FUTMAX 10/25
Problem definition
Play-offs qualification problems:
How many points a team should make to:
 … be sure of finishing among the p=8 teams in
the first positions? (sufficient condition for playoffs qualification)
 … have a chance of finishing among the p=8
teams in the first positions? (necessary
condition for play-offs qualification)
April 2004
FUTMAX Chile
FUTMAX 11/25
Problem definition
Elimination problems:
How many points a team should make to:
 … be sure of finishing among the p=22 teams in
the first positions? (sufficient condition for nonelimination)
 … have a chance of finishing among the p=22
teams in the first positions? (necessary condition
for non-elimination)
April 2004
FUTMAX Chile
FUTMAX 12/25
Problem definition
 In this talk, we consider only the
Guaranteed Qualification Problem: How
many points a team k should make to be
sure of finishing among the p=8 in the first
positions?
 Instead, we compute the maximum number
of points a team can make and still not be
qualified in the p=8 first positions.
 Then, we add 1 to the above number to
determine the minimum number of points
for guaranteed qualification: GQS(k)
April 2004
FUTMAX Chile
FUTMAX 13/25
Formulation
 n = number of teams = 26
 M = maximum difference of points between any
two teams (all wins vs. all losses) = 3*(n-1) = 75
 k = team under consideration
April 2004
FUTMAX Chile
FUTMAX 14/25
Formulation
½
xi j =
1; if t eam i wins over t eam j
0; ot herwise
pj = point s already accumulat ed by t eam j
t j = point s won by t eam j at t he end of t he t ournament
½
yj =
April 2004
1; if t j ¸ t k (i.e. if t eam k is not ahead j )
0; ot herwise
FUTMAX Chile
FUTMAX 15/25
Formulation
GQS (k )  1  max tk
subject to:
xij  x ji  1
i, j to be played
t j  p j  3 i  j x ji   i  j 1  ( xij  x ji ) 
tk  t j  M (1  y j )

April 2004
j k
j
j
t j  tk  y j  0
yj  8
xij {0,1}
i, j to be played
y j {0,1}
j
FUTMAX Chile
FUTMAX 16/25
Formulation
 Ties in the number of points are broken in
favor of teams with more wins.
 In the previous model, add up a very small
amount (necessarily smaller than one) to the
tnumber
 p of
(3points:
)
x 
[1  ( x  x )]
j
j

i j
ji

i j
ij
ji
  0.01
 Use e.g.
 With a similar model, we can also compute
April
2004
FUTMAX Chileof points for
FUTMAX 17/25
PQS(k):
minimum number
Formulation
 When is team k “mathematically qualified” for the
play-offs?
Team k is mathematically qualified if the previous
problem is infeasible!
 When does a team k depend only on itself to be
qualifed?
Team k depends only on itself if GQS(k) is less
than or equal to the total number of points it can
make.
 When is team k “mathematically eliminated” from
the
April
2004 play-offs?
FUTMAX Chile
FUTMAX 18/25
FUTMAX in the WWW
 FUTMAX project
 Results of the games are collected from the
web.
 Model are generated (four problems for
each team).
 All problems are solved with CPLEX 9.0
 HTML file is automatically built from the
results.
 Automatic publication in the web:
April 2004
FUTMAX Chile
FUTMAX 19/25
http://www.futmax.org
2006 World
FUTMAX in the press
 September 24, 2002: FUTMAX web site
launched
 September 29: round table interview to Radio
Globo (major sports radio station, program
“Enquanto a bola não rola”)
 September 30: article in the Internet section of
Jornal do Brasil
 October 24: interview for TV Campus
 December 18: article in Jornal da PUC
 October 2003: talks with SPORTV (TV Globo)
and
“chances”
of qualification
April
2004 computations ofFUTMAX
Chile
FUTMAX 20/25
Results
 Already at the 11th round, some teams did not
depend only on themselves to be qualified.
 At this time, Vasco was in a difficult situation and
fans were complaining.
 The trainer of Vasco met the press and said that
“if we win the next ten games, then we will be
qualified”.
 FUTMAX was able to prove to the press that this
was not true.
April 2004
FUTMAX Chile
FUTMAX 21/25
Results
 October 31, 2002: São Paulo won Ponte Preta
and made a total of 43 points.
 The press (Folha de São Paulo) announced that
“São Paulo was mathematically qualified for the
play-offs”.
 FUTMAX was able to prove to the press that this
was not true.
 November 3, 2002: São Caetano made a total of
42 points and the press also announced it was
qualified.
AprilAgain,
FUTMAX was
able to prove to the
press
2004
FUTMAX Chile
FUTMAX 22/25
Results
April 2004
FUTMAX Chile
FUTMAX 23/25
Results
FUTMAX can be used to follow the situation of each team:
Possible
points
FLUMINEN
Points for guaranteed
SE
qualification
Points for possible
qualification
Points accumulated
April 2004
FUTMAX Chile
FUTMAX 24/25
Results
 Spin-offs: followed by HockeyPlex project (same
idea for National Hockey League, USA) based
on FUTMAX
 Motivation for students
 Activities of our research group made public
 New web page: http://www.esportemax.org
 Slides available at:
http://www.inf.puc-rio.br/~celso/talks.htm
 Papers (OR/MS Today 2004; ITOR to appear)
April 2004
FUTMAX Chile
FUTMAX 25/25
available at: