Mathematical analysis of the metagame (you be the DCI)

Thanks for doing this. I'm interested in looking into how you're doing this (I know both linear algebra and C++ so hopefully I won't need any help). Can you let us know what you input as the win percentages of each archetype / how you arrived at those numbers? There are obviously lots of ways to get a single win percentage out of all the P9 data.

@diophan I'm straight up using the data from your spreadsheet:
9 Shops 0.50 0.50 0.67 0.50 0.40 0.33 0.67 0.60 0.75 Eldrazi 0.50 0.50 0.67 0.33 0.83 0.50 0.50 0.83 0.50 Dredge 0.33 0.33 0.50 1.00 0.50 0.50 1.00 0.60 0.00 Combo 0.50 0.67 0.00 0.50 0.50 0.50 1.00 0.50 0.50 Oath 0.60 0.17 0.50 0.50 0.50 0.83 0.00 1.00 1.00 BigBlue 0.67 0.50 0.50 0.50 0.17 0.50 0.50 0.83 0.00 Mentor 0.33 0.50 0.00 0.00 1.00 0.50 0.50 0.57 0.75 BlueControl 0.40 0.17 0.40 0.50 0.00 0.17 0.43 0.50 0.67 Other 0.25 0.50 1.00 0.50 0.00 1.00 0.25 0.33 0.50
Of course a single P9 is not enough data to draw any firm conclusions about match win percentageWotC of course has reams of data from the dailies and twoman queues.

This post is deleted! 
Evouga, why don't you look at the averages over the past year?

@desolutionist said in Mathematical analysis of the metagame (you be the DCI):
Evouga, why don't you look at the averages over the past year?
Excellent idea. Is there a cutoff date that is especially meaningful? When was the last metagame shift, before the recent restrictions?

It's hard. So much has changed in the last year. Walking ballista was printed in January. Paradoxical Outcome in September. Leovold in August (not as big but I do love Leovold). Last summer grixis pyromancer was fantastic. Now it is unplayable. While a lot has changed I would probably start after the restriction of Lodestone Golem last spring. While it wouldn't be perfect it would give probably the best general idea of matchup percentages.

Paradoxical has been around for almost a year, I'd start with that printing. Unless you want to wait until something else is printed; like you said 1 P9 is not enough and with the current rate of printings, there is something new every other set.

Unfortunately the problem with going back very far is that we've tweaked the classification. Hypothetically someone could go back and change the archetypes around to have a consistent classification (the win rates will update themselves).

@diophan One could just do key cards rather than archetypes (which by their very nature are somewhat arbitrary... #imlookingatyoujoesephcampbell)

So I scraped the metagame reports from Diophan and ChubbyRain from last June until this April, including P9s, Eternal Extravaganzas, the TMD Open and Vintage Champs.
The final matrix (of win counts this time, not win %; to calculate win percentage of deck i against deck j, compute M(i,j) / (M(i,j) + M(j,i))
9 Shops 96 181 58 48 36 63 43 80 40 Gush 138 354 78 96 77 97 99 132 83 Dredge 38 92 17 34 18 23 25 30 25 BigBlue 43 82 27 27 13 30 25 27 28 BlueControl 26 61 10 19 20 24 18 19 17 Combo 34 72 38 21 18 31 25 36 26 Oath 41 80 31 37 14 31 40 45 30 Eldrazi 53 123 47 30 21 42 44 49 32 Other 21 68 26 21 6 20 25 25 12
I plugged this data into my code and got the surprising result:
Equilibrium Metagame: Shops 100% Gush 0% Dredge 0% BigBlue 0% BlueControl 0% Combo 0% Oath 0% Eldrazi 0% Other 0%
Sure enough, according to the aggregated match win data, Shops has a winning match percentage against the entire field... not sure what to make of this.

If your program and theory is good, then I guess it sort of reinforces what we all already know... Shops is the best
edit If you get a chance, can you add in some //comments . I'd like to try and trace the program but cannot decipher it.

@desolutionist said in Mathematical analysis of the metagame (you be the DCI):
If your program and theory is good, then I guess it sort of reinforces what we all already know... Shops is the best
edit If you get a chance, can you add in some //comments . I'd like to try and trace the program but cannot decipher it.
Here is the code with more comments. I'm happy to explain if there are parts that are still confusing.
#include <Eigen/Core> #include <Eigen/Dense> #include <iostream> #include <vector> #include <string> using namespace std; // Calculates whether the metagame is in equilibrium, given a matrix of win probabilities P and a set of dominated decks. // 'dominated' is a bit field encoding whether each deck is present in the metagame, or hated out. A '0' in bit position // i means that the deck is dominated (not present in the equilibrium metagame) and '1' means the deck is present. // // Returns true if an equilibrium exists given the set of dominated decks. If the equilibrium exists, the composition of // the metagame is stored in 'result.' bool hasEquilibrium(const Eigen::MatrixXd &P, int dominated, Eigen::VectorXd &result) { int ndecks = P.rows(); result.resize(ndecks); // constructs a list of nondominated decks. idxmap[i] is the ith nondominated deck. int idx = 0; vector<int> idxmap; while (dominated > 0) { if (dominated % 2 == 1) { idxmap.push_back(idx); } idx++; dominated /= 2; } int subdecks = idxmap.size(); // Extracts from P the submatrix Pn corresponding to only the nondominated decks. Eigen::MatrixXd subP(subdecks, subdecks); for (int i = 0; i < subdecks; i++) { for (int j = 0; j < subdecks; j++) { subP(i, j) = P(idxmap[i], idxmap[j]); } } // solves Pn m = 0.5. Eigen::VectorXd rhs(subdecks); rhs.setConstant(0.5); Eigen::FullPivHouseholderQR<Eigen::MatrixXd> solver(subP); Eigen::VectorXd sol = solver.solve(rhs); // check that the linear system did indeed get solved if ((subP*sol  rhs).norm() > 1e8) { cerr << "Warning: linear solve failed on domination strategy " << dominated << endl; } // the metagame composition m can fail to be an equilibrium metagame for several reasons: //  it requires that one of the decks make up a negative proportion of the metagame; //  it implies that one of the "dominated" decks has a >50% win percentage (in which // case we were incorrect in labeling that deck as dominated.) // check the first condition for (int i = 0; i < subdecks; i++) { if (sol[i] < 1e8) return false; } // check the second. Calculate the win percentage of all decks, given P and m. result.setZero(); for (int i = 0; i < subdecks; i++) { result[idxmap[i]] = sol[i]; } Eigen::VectorXd candidate = P*result; // check all win percentages are <= 50%. // Of course for the nondominated decks we will get a win percentage of exactly 50% // so we only really care about what the value is for the dominated decks. for (int i = 0; i < ndecks; i++) { if (candidate[i]  0.5 > 1e8) return false; } return true; } int main() { // read in the number of decks int ndecks; cin >> ndecks; if (ndecks < 1) { cerr << "Error: you must provide at least one deck win percentage to analyze" << endl; return 1; } if (ndecks > 30) { cerr << "Error: too many decks" << endl; return 1; } if (ndecks > 18) { cerr << "Warning: this analysis runs in exponential time. It may take quite a while to process a metagame with " << ndecks << " decks" << endl; } // read in deck names and win counts Eigen::MatrixXd wins(ndecks, ndecks); vector<string> names; for (int i = 0; i < ndecks; i++) { string name; cin >> name; names.push_back(name); for (int j = 0; j < ndecks; j++) { int nwins; cin >> nwins; wins(i,j) = nwins; } } // contruct the win probability matrix from the win counts. Eigen::MatrixXd P(ndecks, ndecks); for (int i = 0; i < ndecks; i++) { for (int j = 0; j < ndecks; j++) { P(i, j) = double(wins(i, j)) / double(wins(i, j) + wins(j, i)); } } // check for all possible sets of dominated decks. Each integer from 1 to 2^{# decks} encodes a different set // of possible dominated decks, where each '0' bit in the integer represents a dominated deck. // Since it is impossible to have a metagame where all decks are dominated, we skip the dominated=0 case. for (int dominated = 1; dominated < (1 << ndecks); dominated++) { Eigen::VectorXd breakdown; if (hasEquilibrium(P, dominated, breakdown)) { cout << "Equilibrium Metagame:" << endl; for (int i = 0; i < ndecks; i++) { cout << names[i] << " " << 100*breakdown[i] << '%' << endl; } } } }

So assuming we all agree that Vintage is not really a onedeck format, there are a few possible explanations for the above data:

The format's best players play Shops, and its worst play decks that prey on Shops, so that the win percentage of Shops against its predators is not accurately reflected in tournament results;

Even though Shops as a whole has a winning match percentage against all other archetypes as a whole, individual builds of Shops are weak against individual builds of, say, Big Blue, and this finergrained relationship between the decks is not captured in the aggregate data.
I have no idea how to correct for #1 (if it's even true), but #2 could be fixed by going back through Diophan and ChubbyRain's data and doing a more finegrained taxonomy, splitting archetypes that contain multiple, strategicallyvaried builds.
I can try doing this, but as it represents a very significant time investment, I'd like to get your thoughts first about what taxonomy you consider reasonable: if you had to decompose the metagame over the past year into ~15 archetypes so that

decks with similar strategic roles in the metagame (and similar win percentage against other archetypes) are grouped into the same archetype;

decks with different strategic role, but similar core, are classed as different archetypes;
what groups would you pick?


Based on your assumptions and what you input for winrates the second time around the conclusion is clear since shops does not have a sub 50% winrate.
I discussed this a bit with Matt and the assumption that winrates are static is what's giving a lopsided equilibrium in this state. Realistically speaking the higher proportion a deck is of the metagame the more people will tune their deck to beat it. This is why we see so many pyroblasts in a metagame where 60%+ of decks are blue. Note that I'm not criticizing what you did: I think it's interesting and it's also unclear how (or minimally a pain) to model tuning decks.
I'm rolling with the assumption that winrates are static for the remainder:
Since as mentioned before the conclusion that shop becomes 100% of the meta appears to depend on none of its winrates being below 50%. You'll notice in your first set of data that shops had a 40% winrate against oath but in the aggregate it had a record of 4384, or ~51% winrate.
Because of this, a natural question is "how likely is it that shops really has a sub 50% winrate against oath?" The oath versus shops matchup is much discussed, since oath is in many people's eyes the deck to play if you expect a bunch of shops. I do not know much of any stats, but it's fun to learn, so I tried to figure this out. We have a binomial distribution, a sample of n=84 and a winrate of ~51% in the sample size. I had no idea how to figure this out, but based on https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval the first mentioned method seems reasonably accurate. Assuming I know how to use a ztable and didn't mess up the calculation, it's ~9% likely that shops has a sub 50% winrate against oath, which is lower than I expected. Anyone who actually knows stats should feel free to call me out for doing something stupid

I'd like to plot the fluctuations in the actual meta game breakdowns. (From month to month)

Many thanks for doing this analysis. I've always been interested in game theory and the modern vintage metagame is a great case study!
I actually think it's entirely possible that vintage is a 'one deck format'. There are many ,many reasons for this, here are just a few off the top of my head:
We can't assume that everyone has perfect information. With the advent of MODO vintage and analyses like this one, we are trending towards more information, but it is far from perfect. Some players still show up with outdated decks. And I'd argue most don't know the 'win percentage' of archetype A vs. Archetype B.
We can't assume everyone is a rational player, whose sole goal is to win. People have deck and play style preferences that push them towards suboptimal strategies. Some play to have fun, so winning is secondary.
Another hypothesis is it is much easier to 'screw up' playing blue than shops, i.e. blue decks have a larger decision tree and therefore also more opportunities to make mistakes. Given that most vintage players are fairly casual and are not on the pro tour/grand prix/scg tour grind, they are more likely to make mistakes when on a blue deck.
I don't know if there's a solution to this problem outside of more restrictions. The power of shops since printing of lock pieces started in Mirridon has always been that even if you packed a metric ton of hate, you still lose if you can't cast any of them. That problem still exists and will continue to exist as long as there are turn 1 spheres powered out by workshops. We know workshops are not going anywhere, so that leaves thorn or sphere, both of which seem way to underpowered to be restricted.
P.S. Frank Karsten wrote an excellent article examining what makes a good constructed format using game theory, highly recommend everyone to read!: https://www.channelfireball.com/articles/whatcangametheorytelluswillmakeagoodconstructedformat/

@diophan said in Mathematical analysis of the metagame (you be the DCI):
I discussed this a bit with Matt and the assumption that winrates are static is what's giving a lopsided equilibrium in this state. Realistically speaking the higher proportion a deck is of the metagame the more people will tune their deck to beat it. This is why we see so many pyroblasts in a metagame where 60%+ of decks are blue. Note that I'm not criticizing what you did: I think it's interesting and it's also unclear how (or minimally a pain) to model tuning decks.
One thing you can do is to introduce a new hypothetical deck to the metagame with adjusted win percentages. These percentages are inevitably going to be to some extent hypothetical, but for example, say you added a tuned Gush deck with artifact hate, which boosted the matchup against Shops to 55% at the cost of 5% less effectiveness against other blue decks:
10 Shops 0.5 0.567398 0.604167 0.527473 0.580645 0.649485 0.511905 0.601504 0.655738 0.45 Gush 0.432602 0.5 0.458824 0.539326 0.557971 0.573964 0.553073 0.517647 0.549669 0.55 Dredge 0.395833 0.541176 0.5 0.557377 0.642857 0.377049 0.446429 0.38961 0.490196 0.54 BigBlue 0.472527 0.460674 0.442623 0.5 0.40625 0.588235 0.403226 0.473684 0.571429 0.51 BlueControl 0.419355 0.442029 0.357143 0.59375 0.5 0.571429 0.5625 0.475 0.73913 0.48 Combo 0.350515 0.426036 0.622951 0.411765 0.428571 0.5 0.446429 0.461538 0.565217 0.48 Oath 0.488095 0.446927 0.553571 0.596774 0.4375 0.553571 0.5 0.505618 0.545455 0.45 Eldrazi 0.398496 0.482353 0.61039 0.526316 0.525 0.538462 0.494382 0.5 0.561404 0.49 Other 0.344262 0.450331 0.509804 0.428571 0.26087 0.434783 0.454545 0.438596 0.5 0.45 GushPrime 0.55 0.45 0.46 0.49 0.52 0.52 0.55 0.51 0.55 0.5
You get
Shops 29.8689% Gush 29.8689% Dredge 0% BigBlue 0% BlueControl 0% Combo 0% Oath 0% Eldrazi 0% Other 0% GushPrime 40.2621%
Now the new Gush deck (and its original, Shopssoft variant, which preys on the Shopshardened version) take up 70% of the metagame. With enough match data about different variants of the different decks, presumably these percentage adjustments could be made less hypothetical.

I had the same thought, which is why I wanted to look at the change in metagame breakdowns to see exactly what percent of people switch decks as opposed to tweaking their current one.
I plotted the metagame breakdowns from the P9 Challenges since October and the common trend seems to be that an increase in percentage of metagame share for a particular archetype was almost always followed by a decrease the following month and vice versa. There was only one instance in which a deck (Oath) saw a continued decrease in metagame share over two consecutive events.

@evouga going back to the post where you show the Equilibrium Metagame with shops at 100% and everything else at 0% I'm very curious to see what the other deck's charts look like  specifically big blue, blue control, oath and eldrazi.

@evouga said in Mathematical analysis of the metagame (you be the DCI):
So assuming we all agree that Vintage is not really a onedeck format, there are a few possible explanations for the above data:

The format's best players play Shops, and its worst play decks that prey on Shops, so that the win percentage of Shops against its predators is not accurately reflected in tournament results;

Even though Shops as a whole has a winning match percentage against all other archetypes as a whole, individual builds of Shops are weak against individual builds of, say, Big Blue, and this finergrained relationship between the decks is not captured in the aggregate data.
Fascinating and great posts. There's always: Few people can afford the cost of Workshops. This puts a cap on the number of players who can play the deck, so discourages others from adjusting their decks to beat it, and so it lets the few Workshop players do disproportionately well. What happens if we create a rockpaperscissors metagame (with the favorable matchups being, say, 6040) but only let 10% of the people play rock instead of the onethird weβd expect?
That 10% plays rock. 90% play scissors. Rock has a great win percentage, but only because itβs too rare to justify anyone playing paper.
Or, as mentioned, players are not very good at recognizing or switching to the best decks so even if there's a current best deck not everyone switches to it, so it's not worthwhile to build a deck so targeted against it.
An old but relevant post: http://www.archive.themanadrain.com/index.php?topic=21004.msg334559#msg334559
"The price and rarity of Workshops means that Workshop decks are going to be scarce at most sanctioned events (except GenCon and other huge tournaments). This results in Workshop decks not appearing commensurate to their power and makes metagaming against them more difficult." 