game_resolver_cpp

This library is internal library for nishino-lab(The University of Tokyo)

http://www.css.t.u-tokyo.ac.jp

A C++20 solver for pure strategy Nash equilibria and Bayesian Nash equilibria, with the same Python interface as game_resolver. Existing code runs by changing the import prefix only.

How to install

pip install game_resolver_cpp

Run your own game

import numpy as np
from game_resolver_cpp.game import Game
from game_resolver_cpp.nash_equilibrium import NashEquilibrium
from game_resolver_cpp.player import Player


class PrisonersDilemma(Game):
    def __init__(self):
        super().__init__()
        actions = np.array(["C", "D"])
        self.add(Player(0, actions=actions, payoff_matrix=np.array([[3, 0], [5, 1]])))
        self.add(Player(1, actions=actions, payoff_matrix=np.array([[3, 5], [0, 1]])))


nash = NashEquilibrium(PrisonersDilemma()).get_nash_equilibrium()
print(nash["index"])     # [(1, 1)]
print(nash["profile"])   # [['D', 'D']]
print(nash["payoff"])    # [[1.0, 1.0]]

All four ways of defining payoffs work, exactly as in game_resolver:

• payoff_function= with a function NumPy can broadcast (Type1)
• payoff_function= with a function called per cell (Type2)
• payoff_matrix= with a NumPy array (Type3)
• payoff= with a Payoff table, or a plain dict (Type4)

Run a Bayesian game

Subclass BayesianGame and implement posterior().

A Bayesian battle of the sexes. Each player has a type A / B, observes their own type, and computes the expected payoff with the posterior over the other player's type.

import numpy as np
from game_resolver_cpp.bayesian_game import BayesianGame
from game_resolver_cpp.bayesian_nash_equilibrium import BayesianNashEquilibrium
from game_resolver_cpp.bayesian_player import BayesianPlayer


class SampleGame(BayesianGame):
    def __init__(self):
        super().__init__()
        actions = np.array(["Boxing", "Ballet"])
        types = np.array(["A", "B"])
        self.add(BayesianPlayer(0, actions=actions, types=types, payoff_function=self.male))
        self.add(BayesianPlayer(1, actions=actions, types=types, payoff_function=self.female))

    def posterior(self, player_id, type_tuple):
        own = type_tuple[player_id]
        other = type_tuple[(player_id + 1) % 2]
        return 1 / 4 if own == other else 3 / 4

    # payoff functions take (own type, each player's action), and must return a number
    def male(self, type, male_action, female_action):
        if male_action != female_action:
            return 0.0
        if type == "A":
            return 2.0 if male_action == "Boxing" else 1.0
        return 1.0 if male_action == "Boxing" else 2.0

    def female(self, type, male_action, female_action):
        if male_action != female_action:
            return 0.0
        if type == "A":
            return 2.0 if female_action == "Boxing" else 1.0
        return 1.0 if female_action == "Boxing" else 2.0


nash = BayesianNashEquilibrium(SampleGame()).get_nash_equilibrium()
print(nash["index"])       # [(0, 0), (1, 2), (2, 1), (3, 3)]
print(nash["profile"][0])  # [{'A': 'Boxing', 'B': 'Boxing'}, {'A': 'Boxing', 'B': 'Boxing'}]
print(nash["payoff"][0])   # [{'A': 2.0, 'B': 1.0}, {'A': 2.0, 'B': 1.0}]

profile and payoff are indexed by [equilibrium][player][type]. The types and actions are handed back exactly as you passed them in, so with np.array they print as np.str_('A'); pass plain lists if you want plain strings.

What gets faster

Against the pure Python game_resolver, on an 11-core Apple M series machine.

Bayesian games are where this pays off, and the gap widens with size. The Python version calls posterior() once per strategy profile, per player, per type; this one caches it and calls it players x type profiles times — 32 calls instead of 209,952 for 3 actions and 4 types.

Complete information games gain little (1.1x to 3.3x). NumPy is already doing that work in C, so only the equilibrium search moves over. Note that within the Python version itself the same game takes 5.8 ms or 750 ms depending only on how the payoffs are written — choosing Type1 or Type3 matters far more than choosing this package.

Results match the Python version

The equilibria of all five sample games are pinned and checked on every test run, and verified against exact rational arithmetic.

One deliberate difference: payoffs are compared with a small relative tolerance instead of an exact ==, because an exact comparison makes genuine ties depend on rounding. The Cournot example has three equilibria on its grid; the Python version reports one of them. Pass tolerance=0 to NashEquilibrium for the Python version's strict behaviour.

Run an extensive form game

Build a game tree and get its pure strategy subgame perfect equilibria. Information sets turn the same tree into a simultaneous move game.

from game_resolver_cpp.extensive_form_game import ExtensiveFormGame

game = ExtensiveFormGame()
entrant = game.add_player("Entrant")
incumbent = game.add_player("Incumbent")

enter = game.node(entrant, "E")
react = game.node(incumbent, "I")
game.edge(enter, game.terminal([0, 2], "out"), "Out")
game.edge(enter, react, "In")
game.edge(react, game.terminal([-1, -1], "fight"), "Fight")
game.edge(react, game.terminal([1, 1], "share"), "Accommodate")
game.auto_information_sets()

print(game.get_subgame_perfect_equilibrium())
# [{'payoff': [1.0, 1.0], 'strategy': {'E': 'In', 'I': 'Accommodate'},
#   'path': ['E', 'I', 'share'], 'outcome': 'share'}]

game.draw_gametree("entry.html")   # self-contained page with the tree and the equilibria

Or draw the tree in the browser and press ▶ 解く:

python -m game_resolver_cpp.web

The editor saves games as JSON, ExtensiveFormGame.load() reads them, and game.edit() opens a game built in code in the editor.

Not supported

• Mixed strategy Nash equilibria (the Python version does not have them either)
• Chance (Nature) nodes in extensive form games

Links

• Source, C++ API, and design notes: https://github.com/nishinolab/game_resolver_cpp
• The original Python version: https://github.com/nishinolab/game_resolver