tlabarta / gale-shapley-multilayer

This respository contains an extension to the Gale-Shapley algorithm. The extension was presented in the paper "Safety, Stability, and Efficiency of Taxi Rides" authored by Martin Aleksandrov and Tobias Labarta, and accepted for publication at the 22nd EPIA Conference on Artificial Intelligence, 5-8 September 2023, Horta, Portugal.

Gale-Shapley Extension for two layers of preferences

This respository contains an extension to the Gale-Shapley algorithm. The extension was presented in the paper "Safety, Stability, and Efficiency of Taxi Rides" authored by Martin Aleksandrov and Tobias Labarta, and accepted for publication at the 22nd EPIA Conference on Artificial Intelligence, 5-8 September 2023, Horta, Portugal.

The graphic below shows the code architecture. Required packages can be found in requirements.txt.

main: Calls the benchmark and runtime procedures.

benchmark: For first part of the experiment, investigating efficiency and stability of extended Gale-Shapley algorithm. Defines the parameter n for which benchmarks of n drivers and passengers shall be created using the methods from utilities.py. Finally matches the benchmarks using matching.py and calculates performance indicators with methods from utilities.py. Exports the results as .csv. Below is more documentation regarding the benchmark experiment.

runtime: For second part of the experiment, investigating runtime of extended Gale-Shapley for an increasing set of drivers and passengers.

matching: Contains procedures for executing the matching, calling utility methods for calculating performance indicators and returning the results.

utilities: Contains methods for creating ETA, profit and gender preferences. Also contains methods for matching, calculating blocking pairs and calculating other performance indicators.

Analysis.ipynb: Jupyter Notebook that analyzes the benchmark and run time results and creates plots based on the data.

Benchmark experiment

Columns in the generated data files