# Core-Stable Data Exchange

<summary>Table of Contents</summary>
<ol>
<li>
    <a href="#about-the-project">About The Project</a>
</li>
<li><a href="#dataset">Dataset</a></li>
<li><a href="#prerequisites">Prerequisites</a></li>
<li><a href="#parameters">Parameters</a></li>
<li><a href="#running-the-algorithm">Running the Algorithm</a></li>
</ol>


## About The Project
In this repository, we apply pivoting algorithm (["The Core of An N Person Game" by Scarf (1967)](https://www.jstor.org/stable/1909383?seq=1)) to construct an approximate core-stable data exchange. 

## Dataset
The repo uses the following datasets as the input graph:
* [Street network of New York](https://www.kaggle.com/datasets/crailtap/street-network-of-new-york-in-graphml): 
    * The graphML file is put in `manhatten.graphml`.

## Prerequisites
Install Python with version `3.12`. Install the required dependencies with 
```shell
$ pip3 install numpy==1.26.4 scipy==1.13.0 networkx==3.3
```

## Parameters
The following is a list of parameters used in our experiment:

| Parameter            | Description                                                                 |
|----------------------|-----------------------------------------------------------------------------|
| `M`                  | A large value used to initialize the coalition matrix $\mathbf{C}$          |
| `N`                  | Number of agents (nodes or participants in the exchange)                    |
| `num_of_replication` | Number of repeated runs for robustness evaluation                           |
| `epsilon` | Small noise to make all the `M` slightly different |
| `graphml_file` | Path to the graph file


## Running the Algorithm

### Constructing the Coalition Matrix
Run the following command to construct a set of colaition matrices with `n` agents.
```shell
$ python3 CoalitionM.py --n [number of agents]
```
It might take a bit long time to generate the matrics for lager number of agents, like $n=27$. We provide the pre-generated matrices in the `coalition/` directory.
The file `20-1.csv` contains the first replicated matrix for the case of $n=20$ and the file `summary-20-1.csv` contains the information of cost for generating the matrix.

### Running the Pivoting Algorithm
Run the following command to run the Pivoting algorithm for a particular number of agents
```shell
$ python3 PA.py --n [number of agents]
```
The results are saved to directory `out/`. Note that we use a randomized selection for pivoting out a column during the cardinal pivoting update, which may cause slight variations in running time depending on the random seed.

