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?

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

    • 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

      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

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