Decomposition of Finite Normal Form Games Based on Combinatorial Hodge Theory

Notes

The implementation is based on

Github repository
candogan-games-decomposition by davidelegacci.

In this version, I made the following changes:

• reduced the code to the decomposition only
• improved runtime (by allowing the game structure to be saved/imported)
• restructered the project such that it can be installed as a python package and reused in other projects

The method is based on the following paper:

Flows and Decompositions of Games: Harmonic and Potential Games
Ozan Candogan, Ishai Menache, Asuman Ozdaglar and Pablo A. Parril
Mathematics of Operations Research, 2011, [Link]

Example

Assume we have a game with 2 agents who have 2 actions each. Then we first create the game structure:

game = Game(n_actions=[2, 2], load_save=True)

This create the response graph and linear mappings we need for the decomposition. For larger instances this might take a while. With the keyword load_save we allow to save these linear maps and load them, if they were saved before. You can also define a path that determines where the matrices are stored/loaded.

After that we can compute the decomposition for a given matrix game, .e.g, the Chicken game. If they payoff is given by payoff matrices, we use

import numpy as np
payoff_matrices = [ 
    np.array([[0, -1], [1, -100]]), 
    np.array([[0, 1], [-1, -100]])
    ]
game.compute_decomposition_matrix(payoff_matrices)

If the payoff is instead given in form of a payoff vector, we can directly use the decomposition method:

payoff_vector = [0, -1, 1, -100, 0, 1, -1, -100] 
game.compute_decomposition(payoff_vector)

The result is saved in form of matrices

game.u  # payoff matrices of game
game.uP # payoff matrices for potential component
game.uH # payoff matrices for harmonic component
game.uN # payoff matrices for nonstrategic component

We also compute a metric, which denotes the potentialness of a game and which is defined by

$$ \text{Potentialness} = \dfrac{\Vert uP \Vert_2}{\Vert uP \Vert_2 + \Vert uH \Vert_2} $$

where $uP$ and $uH$ are the payoff vectors of the potential and harmonic components. In the code you can access the metric by

game.metric     # value of metric for potentialness

Note: If we are only interested in the potentialness of a game, we can also consider the decomposition of the flow and compute the potentialness of this decomposition instead. It is cheaper than the payoff decomposition and it turns out that the potentialness of the flow decomposition is equal to the potentialness of the payoff decomposition.

game.compute_flow_decomposition(payoff_vector)
game.flow_metric

Especially for lager settings the runtime improvement is significant (factor 5-50).

Going back to the payoff decomposition: Using the components of the potential and the harmonic components, we can construct a new matrix game with a predefined potentialness by considering a respective convex combination of both components (if they are nonzero). This can be done in the following way

new_payoff_matrices = game.create_game_potentialness(potentialness=0.5)

You can find this and additional examples also in the notebooks.

Setup

Note: These setup instructions assume a Linux-based OS and uses python 3.11 (or higher).

Install virtualenv (or whatever you prefer for virtual envs)

sudo apt-get install virtualenv

Create a virtual environment with virtual env (you can also choose your own name)

virtualenv -p python3 venv

You can specify the python version for the virtual environment via the -p flag. Note that this version already needs to be installed on the system (e.g. virtualenv - p python3 venv uses the standard python3 version from the system).

activate the environment with

source ./venv/bin/activate

Install all requirements

pip install -r requirements.txt

Install the decomposition package.

pip install -e .

You can also run "pip install ." if you don't want to edit the code. The "-e" flag ensures that pip does not copy the code but uses the editable files instead.

Install pre-commit hooks (for development)

Install pre-commit hooks for your project

pre-commit install

Verify by running on all files:

pre-commit run --all-files

For more information see https://pre-commit.com/.