@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

editIf 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 non-dominated decks. idxmap[i] is the ith non-dominated 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 non-dominated 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() > 1e-8)
{
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] < 1e-8)
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 non-dominated 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 > 1e-8)
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;
}
}
}
}
```

**last edited by**