Min/Maxing

Optimization is the family of problems by which we want to find the maximum or minimum of something. Pretty simple when taken at face value. A lot of times optimization problems focus on finding a part of a curve or a plot that has a global maximum or minimum.

This can be done with various calculus methods, but recently I’ve been interested in trying to apply optimization techniques to tables of data that have multiple criteria. In the above picture, we might have an array of data that makes up the points that describe the function f(x). So what happens if we have multiple arrays?

What Game Should We Play Next?

A common issue with my friends and I are that we don’t know what game we should look into playing next. I wound up taking a stab at this problem by applying an optimization technique built using the friendly Pythagorean theorem:

So how does something usually applied to triangles apply to selecting games or other somesuch criteria? Well the theorem is more or less a way for us to measure an absolute magnitude of a value, given some parameters. What we want to use it for is to minimize the rank of various criteria that we deem of interest to us in order to help selecting what an interesting game to play next ought to be.

• Party size: For any given game, we might be interested in how many players it can support in a group. We tend to play a lot as a group, so having a game that supports 4 people at the same time on the same team would rank better than one that only supports 1 or 2.
• Cost: price is always a factor and the cheaper the better, as is the law of the universe.
• Interest: given our group of gamers, some of us might be more interested in a game than others. Peer pressure is typically a good indicator of whether or not we as a group will at least try a game.

So given these three values, how do we go about ranking games using the Pythagorean theorem? The trick here depends on how we are ranking these individual criteria. Party size should be ranked in decreasing fashion (a party size of 32 might come in at rank 1, for example). Cost is simply ranked by the minimum value (so free or 0 cost would always come in at rank 1). Interest is a little more complex. In this case, I’m taking a binary interest (yes or no, 1 or 0) and summing that across our group of gamers. Then, I’m taking that sum and ranking it in decreasing fashion (a sum of 5 or 6 would be rank 1).

So let’s take a look at some example data:

In this table, we have the maximum party size, the lowest recorded price, and a binary interest per person in our gaming group summed up to a total value. Let’s rank em!

Now the games have their ranks by party size, lowest price, and total interest. A key step here before applying our optimization is to normalize the data first. If we tried applying the Pythagorean theorem to this data, the end numbers would be all out of whack. That’s because we’re squaring the numbers we see above and 25 squared is going to weigh very differently from 1 squared.

Normalization is the process where we just divide whatever number by the total in that column. So for Starcraft 2, we go from a rank of 5 to a rank of 5/(361) = 0.0139. Our Pythagorean rank optimization formula is thus given as:

And we can see the output below:

So now we have an ordered list that is not being screwed up by big squared numbers (thanks to normalization) based on a few key metrics that we’ve defined to be important to us. According to this list, Starcraft 2 is the best bet for the next game for us to play since it supports the most people on the same team, is free (to some extent), and has a general interest in playing.

Other ways we could tinker with this optimization is applying differing weights to our selection criteria. What if price was more important to the group than the party size, for example? Applying weights is simply enough, and would only really change the equation to be something like:

where the coefficients could be determined by taking votes from people and normalizing or something to that effect.