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.

@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." 

Someone needs to tell the Northeast that Workshops need to be scarce.

@mickey.nobilis said in Mathematical analysis of the metagame (you be the DCI):
Someone needs to tell the Northeast that Workshops need to be scarce.
We can handle that. Just starting playing:
4x ingot chewer
4x ancient grudge
4x dack fayden
4x fragmentize
4x pithing needle
4x shattering spreein every deck. They'll get the message. haha

@Khahan I mean, that seems like overkill, but... yeah. Why don't people just do that to shops...? I mean. Ben Perry is in my metagame, running insano 2 card Monte and I put 1 mainboard Null and at least two more in the side of every tourney I know he's at... why the heck not?
For the life of me I've never understood why players don't just decide to crush certain kinds of decks that they know they will run into.

@Topical_Island said in Mathematical analysis of the metagame (you be the DCI):
For the life of me I've never understood why players don't just decide to crush certain kinds of decks that they know they will run into.
Because no matter how powerful shops is (or is deemed to be), the majority of the Vintage playerbase will always play bluebased decks. So you're asking to get crushed in any tournament if you played a deck with the cards listed above since the majority will be blue players.
So actually that is precisely what people do with their decks and why Misstep, Flusterstorm and such are played in the maindeck, despite being dead versus shops. It's to beat other blue decks that they know they'll face.

@Hrishi I have gone to tourney's where out of aprox. 20 players, I can be certain that 57 of them are on Shops, or something artifact heavy... We act like this is a big data problem when in fact it's much more like a scouting problem. We know what people play. Vintage is the least fluid constructed format. To say nothing of just making a deck that crushes one archetype and plays close to even with some others, which is theoretically quite feasible. I love this thread, and this work is great so I am not trying to create a this vs that sort of false dichotomy... but seriously, decks like Landstill or Monored Hate get way overlooked because they are theoretically underpowered over thousands of games... when we can find out with even a little testing that they will smoke those three decks that keep winning down at your local card shop.

@Topical_Island No, I get what you're saying. What I mean is, most people will play blue. It doesn't matter if monored will beat all other decks in the room. A fair number of people will not even consider playing such a deck because, well, it doesn't run Ancestral Recall or Time Walk or whatever card you want to think of. People don't often switch decks and instead play what they like to, and just try to adjust slots in their deck to consider whatever metagame they expect.
In your example even, 5ish people out of 20 would be on shops. I'd guess most others would be on blue. So most of those blue decks will metagame against each other, and then presumably shops stomps on all the inbred blue decks (using this as an example, of course not all events go this way but you'd be silly to build your deck to beat the minority in the room).

@Topical_Island You are assuming that your metagame is an accurate representation of the rest of the format. It's not...looking at the major events, the average for Shops has been 14.8%. The average in MTGO Power 9s has been 12.8%. Not a single event in this span has reached the 25% to 35% you expect in your local metagame  the largest was 23% in the most recent TMD Open. Would you run a dedicated hate deck against 34 people in your metagame? Or would you try to increase your win % against the other 1516 people?
P.S. How often do you win or top X your local events?

@Hrishi Yeah. I mean, that's the theory anyway. A lot of time not though. Frank Singel just took down just such a tourney with Monored. Before that Ben Perry got there with the Monte Deck I mentioned. The dichotomous layout of the meta seems a little bit like a selffulfilling prophecy to me. I simply wonder why more folks aren't interested in a deck that says... "You know what, I'm gonna go 50/50 with blue and just rip artifacts a new one."
20 decks in a tourney, 6 Shops, 2 Eldrazi, 1 Oath, 10 other blue decks and then you. (That's just going by the macroscopic data. I'm sure there is a card shop on the Atlantic Coast somewhere, in which you could find 10 Shops decks in a field of 20) If you play 6 matches on the day, you'll play 3 against blue 2.5 against Shops, and .5 against something else... roughly. Assuming that the tourney pairs winning decks together for ensuing rounds, and assuming that the inbread blue decks tend to lose to Shops, then you might actually see more Shops on the day.
A deck that can go 50/50 against blue and crush shops looks pretty good in that environment. If you can win early in the tourney against a couple tempo mentor decks, you likely take home some nice prize money. Interestingly, a deck that is 50/50 against Shops and crushes blue (I think the creation of this deck is actually much hard though) would also be a killer deck in these tourneys.

What deck goes 50/50 with blue and crushes shops?

@evouga Shops tuned for the mirror