# War Story: Fantasy Movie League

Bart Massey

## Fantasy Movie League

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 add v' to v 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|) spaceThis easy time bound is terrible: for |T| = 15, gives 10

^{10}stepsSquinting 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?

Start with zero screens and work up?

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)`

## FMLL-PB: This solution is out there

Some variant must be used by e.g.

FML itself, for computing perfect lineup

## 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