Friday, February 24, 2012

Game Theory for Gamers

This week I have been covering Game Theory with a chunk of my students. They take a course called "Management Science" as required by the Business school at University of San Diego. In this course they do a very loose survey of many topics related to Management Science, one of which is Game Theory. I was a Management Science major in school, so basically each "module" of their course was a entire course or series of courses for me. This is how I ended up with the tutoring gig. I attended UCSD, and had friends at all the neighboring universities. One friend (may or may not have been an attractive female) asked me for some help with her Management Science class because, "That's, like, your major, right?" Well, we got her through that class, and the next semester some of her friends needed help, and I started charging a nominal fee. As time went on, and demand increased, pricing and marketing plans changed. Now, 8 years later, I get approximately 20% of the students taking this course meeting with me at least once a semester, most on a weekly basis.

Earlier this week, I tweeted a link to an example I covered this week. I saw that a solid handful of people "favorited" it, maybe because they wanted to explore the topic further at a later time. Since I didn't get any direct feedback, maybe the example was too simple, or maybe they never got around to it, or maybe it was too unfamiliar or challenging to warrant a comment or question. I want to give those people a little more of this type of content, and maybe spark interest in others. Today, I thought, "Why is it I hear so many Game Theory terms in Magic, but so few actual Game Theory discussions?" The linked example has some pretty good parallels to Magic, and I want to talk about them. Part of that, will force me to discuss the linked example to some degree, so you may want to scope it out, but if academic minutia is absolutely abhorrent to you, you could probably get the gist by reading on.

Game Theory models typically are presented in a matrix (or grid) as shown in the linked example. Each row represents a strategy that you may select once the game begins, and each column represents a strategy your opponent could select. Where each column and row intersects, we see the outcome that you would receive. In the linked example, If the row player (you) chooses Strategy A, and the column player (opponent) chooses Strategy C, you would receive an outcome of +13, while your opponent would receive an outcome of -13 (because this is a zero-sum game, anything you gain, your opponent must lose, and vice versa).

While, I don't intend on exploding about "strictly better" here (like i've done previously), there is a good example in this problem. For the Row Player, Strategy B is dominated by Strategy A and also by Strategy C. Meaning, that Strategy A is strictly better than B, and C is also strictly better than B. Regardless of what the opponent chooses, the row player will always prefer the outcomes in Row A or C to those in Row B. Once you identify Row B as a dominated strategy, you know you won't take it as the Row player, but the column player also knows you won't take it. It could essentially be removed from the matrix, leaving us with only two rows (A,C) and 3 columns (A,B,C). This is where the commonly used term "Next Level" comes in. If we know what our opponent won't do, we plan our strategy around that, and plan for what they will do.
 
A
B
C
A
2
10
13
B
-4
-6
-10
C
14
4
8


Now let's look at what options the column player has, with that row removed. Now remembering that each outcome represents the gain to the row player, the column player wants a smaller (or preferably negative) outcome. After removing Row B, there are no negative outcomes, only Positive, so Column player will want to get the least possible outcome for the Row Player. With the Row B values eliminated, Column C is now dominated by Column B. All of the remaining outcomes in Column B are now lower than the remaining outcomes in Column C. We can now eliminate this column from our matrix, as both players are aware of this.

 
A
B
C
A
2
10
13
B
-4
-6
-10
C
14
4
8

Now, we have a simple 2 options for each team, and it can be left to a guessing game (or not) what is the best choice. In reality, with some algebra, we determine that a mixture of strategies is best. In magic that might mean a portion of your team chooses A while the other portion chooses C (as the row team).

Academic Aside
To those interested in what this academic solution looks like, it takes a small amount of algebra, and also some assumptions about Gaming. The assumptions we make is that both sides are equally intelligent and have the same information available to them. This is rarely true in Magic. Especially with Pro Tours typically following the release of a new set, there is always the possibility one team or player is considering a deck that no one else is considering. Further, there's always some type of discrepency in general intelligence and in-game skill. Regardless, we want to determine what % of our strategy should be commited to A and what % to C. We'll assign Probability 'P' to selecting A and therefore (1-'P') to selecting C. We also assume our opponent is doing something similar, with what we'll call Q and (1-Q). Using weighted averages, we find the best solution is to select A 5/9 of the time and C 4/9 of the time. While our opponent will select A 1/3 of the time and B 2/3 of the time. If anyone is curious enough to want to see the algebra behind this, let me know, but I fear I may already be reaching the TL;DR threshold.
/Aside

In Magic, the initial Grid is actually much simpler, with each row/column being a deck option. Each outcome (or payoff) is the win% against that opponents choice. I've always been most interested in the fact that a format (or metagame) can be "solved" in Magic. And given enough time (a lot), man power (a lot), and resources (a lot), I think a team could realistically test enough to get statistically significant win% (as opposed to Mr Derp saying, "I'm 75% against RDW" because he won 3/4) for each individual matchup. Then if the team had, lets say, 10 people, they'd be able to mix their strategies approximately according to the appropriate mix that the Game Matrix solution provides for a given Pro Tour Event. While Game Theory provdies some untrue assumptions, these can actually be exploited slightly. As when it comes time to assign each team member a deck according to the suggested ratio, personal preference and playstyle can be used to put people with better skill at that particular strategy holding the appropriate deck. I dont know how closely this resembles what the "top teams" do in preparation, but i'm sure it has some paralels, even if not approached using the same academic means.

Game On!

1 comment:

  1. My main problem with people talking about decks and their win percentages is that we really don't have the data to say if one will win significantly more often (as in your Mr Derp example). So I get tired of hearing how something is a 75% favorite

    ReplyDelete