This repository hosts our algorithms for computing the Shapley value and Banzhaf value in polynomial time in matching games over bounded treewidth graphs. This code is for research only purposes. If you decide to use it, please cite our work:
Greco, Lupia, Scarcello: Coalitional games induced by matching problems: Complexity and islands of tractability for the Shapley value. Artif. Intell. 278 (2020)
@article{DBLP:journals/ai/GrecoLS20,
author = {Gianluigi Greco and
Francesco Lupia and
Francesco Scarcello},
title = {Coalitional games induced by matching problems: Complexity and islands
of tractability for the Shapley value},
journal = {Artif. Intell.},
volume = {278},
year = {2020},
url = {https://doi.org/10.1016/j.artint.2019.103180},
doi = {10.1016/j.artint.2019.103180},
timestamp = {Thu, 19 Dec 2019 09:27:15 +0100},
biburl = {https://dblp.org/rec/journals/ai/GrecoLS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
git clone https://github.com/fras3c/ag-shapley-mso.git
unzip sequoia-core.zip
docker build -t ag-shapley-mso .
docker run -i -t ag-shapley-mso:latest /bin/bash
chmod +x ag-sv-mso.py
./ag-sv-mso.py -b outdir agents goods expected_goods # builds an allocation game [INPUT] outdir and CSV files; [OUTPUT] an allocation game (LEDA format)
./ag-sv-mso.py -s instance_name # builds and solves a MSO counting problem by taking in INPUT the resource allocation graph built in the previous step (to do that we use Sequoia MSO Solver)
./ag-sv-mso.py -c outdir instance_name # computes the Shapley Value of the Resource allocation game by exploiting the solutions (histograms) computed in the previous step.
All of those steps can be performed together using the switch "-a" as follows:
./ag-sv-mso.py -a outdir agents goods expected_goods instance_name
./ag-sv-mso.py -a "/home/sequoia/out" "examples/roma30res.csv" "examples/roma30val.csv" "examples/roma30expectedpub.csv" 30
You will find more instances in the "example" folder.