SAS Optimization Challenge

THE PROBLEM

Our team was tasked with building a skill-based matchmaking system (SBMM) using kill-death ratio (K/D) as the sole matchmaking rating (MMR) factor. We were provided a list of 300 players and their respective K/Ds, 3 lobbies and their respective K/D targets, and a list of premade player teams. Our challenge was to create evenly balanced teams in each lobby while also having a short solve time.

METHODS

Our approach was to structure the problem so a Mixed-Integer Linear Program could solve for the optimal placements of players and teams. We set up a 300x300x3 binary decision matrix to store the information of group and team assignments. By recognizing that this matrix was symmetric on the i-j plane we were able to limit our constraints to only the top-right half of this matrix. This essentially limited our constraints and decision variables in half, which in turn, cut solve time in half. One of the criteria that was not set up by the challenge was the definition of a balanced game. We tried 2 different minimization functions for creating fair games: minimizing the sum of the squared difference between teams and minimizing the sum of the absolute difference between teams. These two measures ended up with very good lobby assignments and similar solve times.

RESULTS

We achieved a solve time using this structure of 6.58 seconds, which was the fastest in the competition. This along with our explanation of the business limitation won us 1st place and the $600 prize. If you are interested in learning more about the specifics and math behind the MILP we set up, I would recommend reading our project report below.

LIMITATIONS

One of the main limitations of this challenge is in its set-up. Since the challenge only uses K/D as the sole MMR factor, any pairing made after the first few games will have limited usefulness. This is because as the games play out, if we have made a truly fair and balanced match, we should expect each team to end with a K/D of 1. This will tend to pull everyone's overall K/D toward 1, even though a K/D of 1 in a high skill lobby should mean much more than that same K/D in a low skill lobby. Instead, K/D should be used to modify some other matrix at the end of each game, based on the relative skill of the other players in that lobby.

Link To Project Report Link to SAS Code Link to Presentation

Decision Matrix

Solve Time Differences