Because I am grouchy and legitimately sick of theoretically knowledgeable and competent people calling inverse game theory a “new AI paradigm” and similarly inane nonsense, I decided to implement fundamental game structures and solvers inside of a probabilistic programming language in only a few hundred lines of C++. (“New paradigm!!!11!!1!”) Because this implementation lets you define and solve games inside of a generative probabilistic program, inverse game theory is now Real Easy; you just post an observed game outcome as evidence and hit the big red infer button. Because the probabilistic programming language is fmcs, inference is very fast and is very considerate of your computational resources. Because it is written in header-only, standard-library-only C++, you can use it anywhere.
Ugh. Lots of reasons, so skip to the next section if you hate words. In economics we often model strategic situations using game theory – we define a solution concept (many of which are quite elegant and do a pretty good job describing real decision scenarios), define a game (ideally with payoffs that are somehow connected with the real world – more on that momentarily), solve the game, and contemplate the equilibria. This is all well and good, and indeed I think (editorial! lack of evidence presented here! I’m not writing a scientific paper and it feels SO GOOD!) that this does a better job of describing the world than many non-economists will claim, but it’s still not perfect. In particular, one beautiful and intricate failure mode is the hierarchical and sequential nature of strategic (= game-theoretic) analysis. We will define a game, e.g., between Red and Blue (making things easy by dichotomizing!), and then we will solve it, and then we will actually take an action based on the solution, which is not the same as seeing what the optimal solution is. Suppose we are Blue and perform the actions just described; meanwhile, Red has set up a similar game, or maybe even the same one if we are very lucky and good at our jobs (order of words intentional), and then Red will solve it, and then Red will take an action too, and then we will observe each others’ actions and set up more games and solve them, etc. In all but the most extreme scenarios, which thankfully have never been observed in the post-1945 world, there is no such thing as a purely simultaneous game, but almost never do we actually contemplate the hierarchical sequential nature of things, let alone write it down and attempt to reason about it…
I have endless anecdotes about the above, some of which are suitable for public consumption.
Well, what I implemented is certainly not the first tilt at the windmills I just described – systematically, that might have been done with mutually recursive (in the infinite recursion limit reaches strategic reasoning) probabilistic programs implemented as test cases in Anglican and Church (thanks, Kathleen!), and from discussions with Avi Pfeffer (now roughly five years ago…) I infer that he was thinking about similar things in the 1990s – but it is probably the simplest (just define a game and sample from a distribution) and almost certainly the lowest-resource way to do so. In a real sense, considering generative probabilistic programs in the tradition of pymc3, pyro, and (ahem) fmcs, this is kind of as close as we come to reality while still in silico: the probabilistic program is an encoding of a data generating process (= how the data we observe actually comes to be, not just what it is); and so, one can define scatter-gather patterns of multiple players solving similar, but not identical, versions of the same game and then create a probabilistic model of their interactions post-game solution; one can define an open-universe program over nested games (modeling the “rabbit-holes” down which one often tentatively treads or plunges headlong); one can define complicated or complex probabilistic programs that return payoff values of a dynamic game; etc. As far as I know there is no other easy way to do any of these things today, and there is almost certainly no single platform that gives you a way to do all of them.
Brief primer (really, truly brief, since if you’ve made it this far you almost certainly have more than passing familiarity with at least one of game theory and probabilistic programming, and have more than a vague inkling of what the complementary set is). I defined very simple game structures and equilibrium concepts, defined as-simple-as-possible solvers for solving those games for those equilibrium concepts, and then wrapped those games in the fmcs machinery required to create a “probability distribution” (you’ll see why the quotes) out of those games. The fmcs machinery that already exists takes care of the rest – conditioning on observed gameplay if desired, performing statistical inference, and querying a posterior for values that are related to gameplay.
You can do a few things. You can define a noncooperative game in two ways: simultaneous and dynamic. To define a simultaneous game (two players only, sorry!) you might write, e.g., C++ std::vector<std::vector<double>> mp_row = { {1.0, -1.0}, {-1.0, 1.0} }; std::vector<std::vector<double>> mp_col = { {-1.0, 1.0}, {1.0, -1.0} }; auto g = NormalFormGame(mp_row, mp_col, 2.0); to define the matching pennies game with λ = 2.0 in a subsequent quantal response equilibrium (cry more) solution. You can also define a dynamic game with N ≥ 2 players, with perfect information, and with “no limit” on number of moves per player or overall. You might define, e.g., a two-player dynamic coordination game as follows:
auto left = Node::decision(1, {"A", "B"},
{Node::terminal_node({2, 2}), Node::terminal_node({0, 0})});
auto right = Node::decision(1, {"A", "B"},
{Node::terminal_node({0, 0}), Node::terminal_node({2, 2})});
auto tree = Node::decision(0, {"A", "B"}, {left, right});Here, tree is the game tree that will be eventually solved and the numeric values in Node::terminal_node are the payoffs.
You can solve a noncooperative game. Simultaneous games are solved per the quantal response equilibrium concept. The equilibrium state depends on a real-valued free parameter λ ≥ 0 which governs the level of “rationality” of the game (λ → 0 connotes random chance; λ → ∞ connotes “rationality”). You solve simultaneous games by initializing them, which calls a .solve() method. solve uses a fixed point iteration algorithm that is not guaranteed to converge but, in my biased testing, does converge much of the time. Dynamic games are solved for Nash equilibria in pure strategies for philosophical reasons into which I will not get currently, but will eventually, and will link back here when I do get to them. You solve dynamic games by calling a solve method or, for more information, calling eq_path, e.g., eq_path(tree). This uses the backward induction algorithm and returns only the single Nash equilibrium found by that algorithm, again on purpose, and again for philosophical reasons that I will explain sometime.
So far, yawn. Stay awake – you can sample from games. (That’s better.) For a simultaneous game, you do a typical fmcs sample statement:
auto game = NormalFormGame(u, u, 4.0);
sample(r, "play", game, rng, observed_play);to sample a value from the NormalFormGame with identical row and column player payoffs u and λ = 4.0 into a record r whose DTypes contain at least the distribution type NormalFormGame. What does this mean? It means that, on initialization, the normal form game that’s defined by row and column player payoffs is solved using the fixed point iteration method, and then when the higher-level fmcs logic gets to the actual sampling action, a strategy pair is sampled according to the probability distribution that is generated by the fixed point iteration method. For a dynamic game, you do something similar, e.g.,
auto left = Node::decision(1, {"A", "B"},
{Node::terminal_node({2, 2}), Node::terminal_node({0, 0})});
auto right = Node::decision(1, {"A", "B"},
{Node::terminal_node({0, 0}), Node::terminal_node({2, 2})});
auto tree = Node::decision(0, {"A", "B"}, {left, right});
sample(r, "decision", DynamicGame(tree), rng);to sample a value from the DynamicGame into a record r whose DTypes contain at least the distribution type DynamicGame. This really is very boring because it just returns the single Nash equilibrium found by the backward induction algorithm.
You can observe values against games. For the simultaneous game that’s sort of easy, because, for any value of λ ∈ (0, ∞) every strategy is played with positive probability, it’s just a lookup and return of the corresponding log-probability. For dynamic games with the solution concept I’ve settled on that doesn’t make sense – there’s only one “right answer” – but that also doesn’t correspond with our notion of how the world works (and, also, hard constraints are very challenging for sample-based probabilistic programming languages to handle). So, in the dynamic case, we accumulate log probability essentially according to the graph edit distance from the observed game play to the Nash equilibrium gameplay returned by backward induction. Observation of values also occurs according to typical fmcs syntax, e.g.,
observe(r, "decision", DynamicGame(game), observed_play);where observed_play is a dynamic_play_t type.
Maybe – depends on your definition. You can definitely do any of the things I described in the third paragraph of this piece. Here’s a very simple example. Suppose you think that two firms might engage in duopolistic competition to produce…stuff. There are a few factors at play, two of which might be the amount of productivity that a firm gets from scaling production up massively (learning!) and the amount of net drag (or gain) a government imposes on a firm via taxation or subsidy. We might observe only the firms’ decisions and not really know anything about the productivity gain experienced by one firm and might not believe statements made by one government (Red?) regarding subsidy or taxation imposed on a firm resident in it. That’s okay, because Probabilistic Programming Is Here To Help. To wit:
template<bool Print>
double profit_model(
record_t<DTypes<Gamma, Normal, DynamicGame>>& r,
dynamic_play_t observed_play
) {
auto prod_high = sample(r, "prod/high", Gamma(2.0, 1.0), rng);
auto prod_low = sample(r, "prod/low", Gamma(2.0, 1.0), rng);
auto gov_lots = sample(r, "gov/lots", Normal(0.0, 1.0), rng);
auto gov_little = sample(r, "gov/little", Normal(0.0, 1.0), rng);
auto game = Node::decision(
0, {"high", "low"}, {
Node::decision(
1, {"lots", "little"}, {
Node::terminal_node({prod_high, 1.0 - gov_lots}),
Node::terminal_node({prod_high * 0.75, 0.25 - gov_little})
}
),
Node::decision(
1, {"lots", "little"}, {
Node::terminal_node({prod_low * 0.25, 0.75 - gov_lots}),
Node::terminal_node({prod_low * 1.25, 1.25 - gov_little})
}
)
}
);
if constexpr (Print) print_tree(game);
observe(r, "decision", DynamicGame(game), observed_play);
return (prod_high + prod_low) / 2.0;
}The nice part – truly, without sarcasm – about being able to specify dynamics in this way is that it’s perfectly transparent and extensible. Of course this example is overly simplistic – that’s why you can (and should), for example, replace the prod_high call with a call to another probabilistic program that is a conditional probability distribution of how productivity increases in the case where production is high; or you should replace {"lots", "little"} by the result of a call to a depth-N DynamicGame that returns actual production values as a function of other strategic considerations; etc. Hopefully it is clear that all of the above is possible without any drama whatsoever.
Anyway, now you want to actually do the inference about which I bloviated. If you just want to see the game being played a little bit, you can do that:
dynamic_play_t observed_play = {{0, "low"}, {1, "little"}};
pp_t<dynamic_play_t, double, Gamma, Normal, DynamicGame> f = profit_model<true>;
auto q = weighted_record<double, Gamma, Normal, DynamicGame>();
auto opts = inf_options_t(3);
auto infer = inference<LikelihoodWeighting>(f, *q, opts);
auto results = infer(observed_play);
for (auto& rec : results->_v) {
std::cout << display(rec) << std::endl;which gets you the pleasant output
(P0)
├─ high ── (P1)
│ ├─ lots *─ * [ 0.0788621, 1.21228 ]
│ └─ little ── [ 0.0591466, -0.15832 ]
└─ low *─ (P1)
├─ lots *─ * [ 0.316003, 0.962276 ]
└─ little ── [ 1.58002, 0.84168 ]
(P0)
├─ high ── (P1)
│ ├─ lots *─ * [ 0.52571, 1.55959 ]
│ └─ little ── [ 0.394283, -0.0499256 ]
└─ low *─ (P1)
├─ lots *─ * [ 0.625619, 1.30959 ]
└─ little ── [ 3.12809, 0.950074 ]
(P0)
├─ high *─ (P1)
│ ├─ lots *─ * [ 0.890572, 3.31359 ]
│ └─ little ── [ 0.667929, 0.0311359 ]
└─ low ── (P1)
├─ lots *─ * [ 0.542185, 3.06359 ]
└─ little ── [ 2.71093, 1.03114 ]
record_t(
address=prod/high, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=0.078862, logprob=-2.618917, obs=false)
address=prod/low, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=1.264014, logprob=-1.029722, obs=false)
address=gov/lots, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=-0.212276, logprob=-0.941469, obs=false)
address=gov/little, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=0.408320, logprob=-1.002301, obs=false)
address=decision, node=node_t(distribution=DynamicGame(...), value=[ (0, low) (1, little) ], logprob=-10.000000, obs=true)
)
record_t(
address=prod/high, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=0.525710, logprob=-1.168715, obs=false)
address=prod/low, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=2.502476, logprob=-1.585195, obs=false)
address=gov/lots, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=-0.559590, logprob=-1.075509, obs=false)
address=gov/little, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=0.299926, logprob=-0.963916, obs=false)
address=decision, node=node_t(distribution=DynamicGame(...), value=[ (0, low) (1, little) ], logprob=-10.000000, obs=true)
)
record_t(
address=prod/high, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=0.890572, logprob=-1.006463, obs=false)
address=prod/low, node=node_t(distribution=Gamma(k=2.000000, theta=1.000000), value=2.168741, logprob=-1.394594, obs=false)
address=gov/lots, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=-2.313588, logprob=-3.595283, obs=false)
address=gov/little, node=node_t(distribution=Normal(loc=0.000000, scale=1.000000), value=0.218864, logprob=-0.942889, obs=false)
address=decision, node=node_t(distribution=DynamicGame(...), value=[ (0, low) (1, little) ], logprob=-20.000000, obs=true)
)Of the three samples requested, we’re seeing first the games generated by each (formatted with the help of print_tree) and then the full record corresponding to each run of the probabilistic program.
If you wanted to actually run inference you’d stop being so noisy and just get on with it:
// with real sampling
f = profit_model<false>;
// this is just to show We Can Do It -- the actual posterior will be
// egregiouisly multimodal (since, in non-probabilistic treatment -- just consider as
// linear algebra -- the problem is underconstrained with four parameters for a two-move,
// two-player game)
auto q2 = ProductGenerator<WeightedMean, double, double, Gamma, Normal, DynamicGame>::generate(
{"prod/high", "prod/low", "gov/lots", "gov/little"}
);
auto opts2 = inf_options_t(1000);
auto infer2 = inference<LikelihoodWeighting>(f, q2, opts2);
auto results2 = infer2(observed_play);
for (const auto& [k, v] : results2.values) {
std::cout << "E[" << k << " | gameplay] = " << v << std::endl;
}which helpfully provides the requested means of the inferred marginals:
E[prod/high | gameplay] = 1.44347
E[prod/low | gameplay] = 2.52908
E[gov/lots | gameplay] = 0.486267
E[gov/little | gameplay] = -0.35106This result intuitively makes sense – if we are ASSUMING that the players play a Nash eq strategy in pure strategies found by backward induction, then based on the non-probabilistic portion of the payoffs the government would have to subsidize player 1 a little bit and the productivity of player 0 producing a low amount would have to exceed the productivity of producing a high amount. And that’s what we find. Great.
Sure: code (will attempt a download to your machine, and of a full git repo to boot – I no longer trust github, gitlab, bitbucket, etc., and you can’t have access to my private git repo); docs on this website. Enjoy.