Prototype C++ implementation of multi-terminal BDD node-table [2] and symbolic Bellman-Ford for graph games [1].
A graph game is a generalization of a game tree for finite, non-cooperative, complete and perfect information games. In short, a graph game is a directed and weighted graph, where each node corresponds to a players turn, and weights are vectors representing the utilities for all players. The number of players and nodes are always finite.
In this setting, a shortest path from one node to another is also a generalization of a Nash equilibrium, and thus, any shortest path algorithm, such as Bellman-Ford, can compute a game Nash equilibrium.
The code in src/arrayimpl implements the MTBDD node table. Only the basic BDD operations are implemented (see the file src/arrayimpl/ApplyOps.h).
The code in src/booleanmodel builds game graph BDDs from state-transition boolean equations.
Take for exmple, the following two equations:
x1 := x1 & ~x2 : [1.0, 2.0];
x2 := x1 | x2 : [5.0, 4.0];
The first equation can be read as: a transition from states where x1
is true
and x2
is false
to states where x1
is true
, has utility 1.0
for player 1, and 2.0
for player 2.
The second equation can be read as: a transition from states where either x1
or x2
is true
to states where x2
is true
, has utility 5.0
for player 1, and 4.0
for player 2.
Each equation contributes additively, in this example, the two equations build the BDD of the following graph:
Players turns are assigned in order (of appereance) of each variable to each state. In the example, states00
and 10
are player 1 turn, and states01
and 11
are player 2 turn.
For compiling you need a a C++ compiler and cmake.
Clone/download and unpack the source code to you computer and run the following:
cd MTBDD-Prototype/build
cmake ..
make
The executable MTBDD-Proto
takes as an argument the path of a text file containing boolean equations, parses the file, build a BDD, computes the shortest path from all states to the last state (i.e., the state where all variables are true
), and prints the results.
GNU General Public License v. 2
- Góngora PA and Rosenblueth DA. A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria. International Journal of Applied Mathematics and Computer Science. 25:3. 2015.
- Meinel, C. and Theobald, T. (1998). Algorithms and Data Structures in VSLI Design: OBDD-Foundations and Applications, Springer-Verlag, Berlin.