[Bug]: Matching algorithm stalled out

[JamesPHoughton]

What happened?

The experiment stalled out at dispatch. we paid 14 people who didn't get to play.

We saw the initial message for the dispatcher, but it never completed:

What browsers do you see the problem on?

• Firefox
• Chrome
• Safari
• Microsoft Edge

What operating system do you see the problem on?

• Windows
• Mac
• Linux

How did we discover the bug?

• Reported by participant
• Observed on Sentry
• Found in dev

Priority

Blocking all data collection

[JamesPHoughton]

CPU usage was pegged, luckily memory was not.

[JamesPHoughton]

debugging

1. the last error message was immediately prior to the dispatch call:

  //callbacks.js
  info(`dispatch: ${nPlayersInIntroSequence} in intro steps, ${availablePlayers.length} in lobby, ${nPlayersAssigned} in games`);
  
  const assignments = dispatcher(availablePlayers);

2. The next log message should have happened before the recursive search function is even defined

  // dispatch.js
function dispatch(availablePlayers) {
    const startTime = new Date().getTime();
    const nPlayersAvailable = availablePlayers.length;
    // randomize the order in which we assign participants to remove bias due to arrival time
    const playerIds = shuffle(availablePlayers.map((p) => p.id));

    // check that playerIds are unique
    if (new Set(playerIds).size !== playerIds.length) {
      throw new Error("Duplicate playerIds in availablePlayers", playerIds);
      // todo: should we just log this error, or should we actively fix it?
    }

    const maxPayoff = getUnconstrainedMaxPayoff(
      persistentPayoffs,
      nPlayersAvailable
    );

    const stoppingThreshold = maxPayoff * requiredFractionOfMaximumPayoff;

    info(`Dispatch with ${nPlayersAvailable} players`);

    function recurse({...}){...}

3. We think what happened is that something got stuck in an infinite loop.

[JamesPHoughton]

Turns out that the leftovers function is super inefficient:

export function leftovers(target, factors) {
  // Given an integer `target` and a list of integers `factors`,
  // returns the smallest number needed to add to an arbitrary number of factors
  // to sum to `target`.
  // We use this to figure out how many participants we will not be able to assign
  // to games of sizes in `factors`, even if we have optimum and unconstrained assignment.
  let closest = target;
  for (const factor of factors) {
    if (factor === target) return 0;
  }
  for (const factor of factors) {
    if (factor < target) {
      const leftover = leftovers(target - factor, factors);
      if (leftover < closest) {
        closest = leftover;
      }
    }
  }
  return closest;
}

It works fine when the number of factors are small, but it scales as something like $f^n$, where $f$ is the number of factors, and $n$ is the target. Gets super big super quick.

In our case (12 players, 245 treatments) , it should have returned 0 within 6 iterations. Instead