This paper introduces the Minimum Price Markov Game (MPMG), a theoretical model that reasonably approximates real-world first-price sealed-bid public auctions following the minimum price rule. The goal is to provide researchers and practitioners with a framework to study market fairness and regulation in both digitized and non-digitized public procurement processes, amid growing concerns about algorithmic collusion in online markets. Using multi-agent reinforcement learning-driven artificial agents, we demonstrate that (i) the MPMG is a reliable model for first-price market dynamics, (ii) the minimum price rule is generally resilient to non-engineered tacit coordination among rational actors, and (iii) when tacit coordination occurs, it relies heavily on self-reinforcing trends. These findings contribute to the ongoing debate about algorithmic pricing and its implications.
run_all.sh # Run all experiments and plots script for Linux/Mac
run_all.bat # Run all experiments and plots script for Windows
LICENSE # MIT License
.gitignore # Ignore directories and files for Git
README.md # Description and usage guide
requirements.txt # Dependencies list
src/ # Source directory
├── config.yaml # Configuration file for experiments and models' hyperparameters
├── logs/ # Contains experiments' .log files
├── metrics/ # Contains training and evaluation metrics JSON files
├── plots/ # Contains figures
├── modules/ # Module directory
│ ├── agents/ # MARL agents
│ │ ├── mappo_agent.py # Multi-Agent Proximal Policy Optimization
│ │ ├── d3qn_agent.py # Double Deep Q-network
│ │ ├── eg_agent.py # Epsilon Greedy bandit
│ │ ├── ts_agent.py # Thompson Sampling bandit
│ │ └── ucb_agent.py # Upper Confidence Bound bandit
│ ├── mpmg.py # Minimum Price Markov Game environment
│ ├── trainer.py # General trainer class
| ├── plotter.py # Plotting module
│ └── utils.py # Utility methods
└── scripts/ # Scripts directory
├── plot.py # Plotting control script
└── main.py # Experiment control script(Via command line)
Git clone or manual download via https://github.com/IgorSadoune/Algorithmic-Collusion-and-the-Minimum-Price-Markov-Game.git.
On Mac/Linux, execute:
python3 -m venv venv
On Windows, execute:
python -m venv venv
On Mac/Linux, execute:
source venv/bin/activate
On Windows, execute:
.\venv\Scripts\activate
The virtual environment always needs to be activated when executing files from this repository.
The required python libraries are listed in the "requirements.txt" file. Those can directly be downloaded to your virtual environment (or root system if venv not setup) by executing
pip install -r requirements.txt
If for some reason an error occurs with one package, the following commands will allow you to install the subsequent packages in the list:
On Mac/Linux:
while read package; do pip install "$package" || echo "Failed to install $package" >&2 done < requirements.txt
On Windows:
Get-Content requirements.txt | ForEach-Object { pip install $_ || Write-Error "Failed to install $_"}for /f %i in (requirements.txt) do pip install %iI do not provide support for Windows users utilizing PowerShell 5.
To run the experiments, for Linux/Mac users, execute in terminal from the root directory:
bash run_all.shand for Windows users:
run_all.batThis command will produce the log.log, metrics.json, and plot.png files.
There are 24 experiments as each of the 6 agent classes used in the paper are tested on 4 configurations of the MPMG. Among the 24 experiments, 12 are conducted on the 2-player MPMG and 12 on the 5-player MPMG, that is, 84 agents are trained over 100 replications of 100 training episodes, for a total 840,000 training iterations (optimization always uses stochastic gradient ascent).
Default configuration is stored in src/config.yaml, where the file can be accessed and modified.
To run a specific experiment, for example, MAPPO agents playing the 5-player heterogeneous MPMG, use the following command:
python3 src/scripts/main.py --num_agents 5 --sigma_beta 0.5 --agent_name "mappo"for Linux/MAC users and
python src/scripts/main.py --num_agents 5 --sigma_beta 0.5 --agent_name "mappo"for Windows users.
--num_agents: Specifies the number of agents (e.g., 5). Note that increasing the number of agents may significantly increase computation time.--sigma_beta: Controls the level of agent heterogeneity, with values ranging between 0.0 and 0.5. A higher value implies greater heterogeneity among agents.--agent_name: Specifies the type of agent to be used. Options include:
"mappo": MAPPO agents"d3qn": Dueling Double Deep Q-network agents"eg": Epsilon Greedy agents"ts": Thompson Sampling agents"ucb": Upper Confidence Bound agentsThis project is licensed under the MIT License. See the LICENSE file for details.
Igor Sadoune - igor.sadoune@polymtl.ca