# War Story: Fantasy Movie League

Bart Massey

## Fantasy Movie League

• https://fantasymovieleague.com/

• An interesting game:

• Each Monday the 15 movies predicted to be US top-grossing on the following weekend are presented. Each movie has a price in "bux" corresponding to its relative predicted gross

• The player is given \$1000 bux to fill an eight screen "cinema". Any combination of movies can be selected as long as the total price of all screens is less than \$1000. Duplicate screens are fine

• Scoring is by actual reported gross of the movies over the following weekend

• Seasons run 13 weeks

• Thus, a prediction game: Can the player make better predictions (usually Thursday night) than the folks running the game, and better than the other players?

## Some FML Twists

• Penalty of \$2M gross per empty screen

• Bonus of \$2M per screen showing the "best performer" for the week: the movie with the best gross/bux ratio

• Bonus of \$5M for showing the "perfect lineup": the eight-screen cinema with the highest possible gross for that week

• Real world cash-equivalent prize each week for the earliest-registered Perfect Lineup pick

• Also cash prizes for best cinema of month, best cinema of season

## Some Obvious Computer Things

• FML Lineup: You have your own unique predictions of gross for each movie for the current week: find the perfect lineup for that week

• FML Expected Lineup: You have some kind of "probability density function" predicting gross for each movie for the current week: find the best expected lineup for that week

• FML Prediction Aggregation: You have a bunch of predictions from various sources for each movie for the current week: use past performance to create an accurate prediction

• FML Season Strategy: You know where you stand relative to others in your league this week and how much time is left: find a probabilistic pick that has the highest expected chance of getting you to a win at the end of the season

## FML Lineup: Formalize the Problem

• Step 1: Formalize the problem. Always best to start with a simplified version: all the details will just crud things up.

``````  Generalized FML Lineup

Given: Set T of titles, with |T| = n. Cost function
c: T → N.  Gross return function g: T → N. Budget b:
N. Screen capacity m: N.

Find: Collection S of showings drawn from T, with
|S| ≤ m and sum[s in S] c(s) ≤ b, maximizing
sum[s in S] g(s).
``````

## FML Lineup: Decide the Complexity

• Step 2: Decide the complexity. Looks like this can be reduced from Integer Programming. Put the IP intgance equations in standard form, and let the x[t] be the number of screens to pick, etc.

I got out an LP solver, and later an IP solver, to try to go the other way: reduce Generalized FML Lineup to IP and use a generic solver. Put a lot of work into it. Learned a lot.

Not going to finish the proof above, because…

## FML Lineup: Add Necessary Detail

• Step 3: Realize that the whole thing is goofy, because we omitted important details. As long as we're doing this, let's just admit that we have a hard problem, and add specific constants.

``````  FML Lineup With Penalties and Bonuses (FMLL-PB)

Given: Set T of titles, with |T| = 15. Cost function
c: T → Z+.  Gross return function g: T → R in
millions. Let T_best be the subset of T
maximizing g(t)/c(t) over all t in T.

Find: Collection S of showings drawn from T, with
|S| ≤ 8 and sum[s in S] c(s) ≤ 1000, maximizing

sum[s in S] g(s) +
2 |{s | s in S, s in T_best}| -
2 (8 - |S|)
``````

Now the problem is constant time (why?), but we have a better description. We can omit the perfect pick bonus, since we will always claim it (LOL).

## FMLL-PB: State Space Search

• Now we need an algorithm for solving FMLL-PB. It looks like an IP solver would work, but that seems like hard mode. Maybe just dumb ol' state space search is fast enough?

``````  FMLL-PB DFS

To solve set of titles T with budget b and n screens:
if T is empty set
return (T, -2 * n)
extract some title t from T
gm <- 0
pm <- None
sm <- None
for p in 0..8
b' <- p * c(t)
if p > n or b' > b
break
v <- p * g(t)
(s, v') <- solve T with budget (b - b') and (n - p) screens
if t in T_best
add 2 * p to v
if pm = None or v > gm
pm <- p
gm <- v
sm <- s
assert pm and sm are not None
insert (p, t) into sm
return (sm, gm)
``````

## FMLL-PB: Correctness and Performance

• Correctness

• Algorithm terminates, since at each recursive call |T| is decreased and the for loop terminates

• Algorithm produces maximum by induction on T

• Base case: produces proper penalty for empty T

• Can never overproduce, since screens and budget are tested at each step

• Must produce maximum for T, by inductive hypothesis

• Performance: O((|T|+1)8) time and O(|T|) space

• This easy time bound is terrible: for |T| = 15, gives 1010 steps

• Squinting at it, can see some bound like 8! * (15 choose 8) ~ 260M steps

• Actual runtime is probably better yet

## FMLL-PB: Variable Ordering

• We have a choice of order for extracting from T

• Let's fix that order by imposing a total order on T and always extracting a least element

• Try most constrained variable first, so most to least expensive title

## FMLL-PB: Value Ordering

• What order to try p in?

• Fill as many screens as possible and work down?

• Can't tell that it matters at this point

## FMLL-PB: Implementation

• Let's write some Python

## FMLL-PB: Memoization

• Now note that we might be solving the same subproblem a lot: some tail of T with given budget and screen count

• Specifically, choosing 0 of some movie

• Add memoization to improve performance

``````  FMLL-PB DFS MEMO

To solve set of titles T with budget b and n screens:
if T is empty set
return (T, -2 * n)
if (T, b, n) in memo:
return memo[(T, b, n)]
...
memo[(T, b, n)] <- (sm, gm)
return (sm, gm)
``````

## To Do

• Recall list of other problems

• Some variant of FMLL-PB can be used for FML Expected Lineup

• FML Prediction Aggregation is a machine learning problem, most likely

• FML Season Strategy is a conceptually and computationally hard problem