Matching

Matching: A Python library for solving matching games - Published in JOSS (2020)

https://github.com/daffidwilde/matching

Keywords

gale-shapley game-theory hospital-residents matching-game matching-problems stable-marriage

Last synced: 6 months ago · JSON representation ·

Repository

A package for solving matching games

Basic Info

Host: GitHub
Owner: daffidwilde
License: mit
Language: Python
Default Branch: main
Homepage: https://daffidwilde.github.io/matching/
Size: 11.5 MB

Statistics

Stars: 162
Watchers: 4
Forks: 43
Open Issues: 9
Releases: 16

Topics

gale-shapley game-theory hospital-residents matching-game matching-problems stable-marriage

Created about 8 years ago · Last pushed 9 months ago

Metadata Files

Readme Changelog Contributing License Citation

A package for solving matching games

Matching games allow for the allocation of resources and partnerships in a fair way. Typically, a matching game is defined by two sets of players that each have preferences over at least some of the elements of the other set. The objective of the game is then to find a mapping between the sets of players in which everyone is happy enough with their match.

In matching, we deal with four types of matching game:

the stable marriage problem (SM);
the hospital-resident assignment problem (HR);
the student-allocation problem (SA);
the stable roommates problem (SR).

Installation

Matching requires Python 3.5 or above, and relies only on NumPy for general use.

The library is most easily installed using pip:

bash $ python -m pip install matching

However, if you would like to install it from source then go ahead and clone the GitHub repository:

bash $ git clone https://github.com/daffidwilde/matching.git $ cd matching $ python -m pip install .

Documentation

Full documentation (including tutorials and discussion material) is available here: https://daffidwilde.github.io/matching/

An academic paper on this library has been included in the Journal of Open Source Software (JOSS) and is available here: https://joss.theoj.org/papers/10.21105/joss.02169

Playing a simple game

With all games, Matching uses a Player class to represent the members of the "applying" party, i.e. residents and students. For HR and SA, there are specific classes to represent the roles of Hospital, Project and Supervisor.

Consider the following instance of SM which is represented on a bipartite graph where the suitors and reviewers are along the left and right respectively.

{.align-center width="10cm"}

We can construct these preferences using dictionaries:

```python

suitorpreferences = { ... "A": ["D", "E", "F"], "B": ["D", "F", "E"], "C": ["F", "D", "E"] ... } reviewerpreferences = { ... "D": ["B", "C", "A"], "E": ["A", "C", "B"], "F": ["C", "B", "A"] ... }

```

Then to solve this matching game, we make use of the StableMarriage class, like so:

```python

from matching.games import StableMarriage game = StableMarriage.createfromdictionaries( ... suitorpreferences, reviewerpreferences ... ) game.solve() {A: E, B: D, C: F}

```

The `Matching` object

This matching is not a standard Python dictionary, though it does largely look and behave like one. It is in fact an instance of the SingleMatching class:

```python

matching = game.matching type(matching)

```

This dictionary-like object is primarily useful as a teaching device that eases the process of manipulating a matching after a solution has been found.

`Player` classes

Despite passing dictionaries of strings here, the matching displays instances of matching.player.Player:

```python

matching = game.matching for suitor in matching: ... print(type(suitor))

```

This is because create_from_dictionaries creates instances of the appropriate player classes first and passes them to the game class. Using dictionaries like this can be an efficient way of creating large games but it does require the names of the players in each party to be unique.

With all games, Matching uses a Player class to represent the members of the "applying" party, i.e. residents and students. For HR and SA, there are specific classes to represent the roles of Hospital, Project and Supervisor.

A note on performance

One of the limitations of this library is the time complexities of the algorithm implementations. In practical terms, the running time of any of the algorithms in Matching is negligible but the theoretic complexity of each has not yet been attained. For example, an instance of HR with 400 applicants and 20 hospitals is solved in less than one tenth of a second:

```python

from matching.games import HospitalResident import numpy as np prng = np.random.defaultrng(0) numresidents, numhospitals = 400, 20 residentprefs = { ... r: np.argsort(prng.random(size=numhospitals)) ... for r in range(numresidents) ... } hospitalprefs = { ... h: np.argsort(prng.random(size=numresidents)) ... for h in range(numhospitals) ... } capacities = {h: numhospitals for h in hospitalprefs} game = HospitalResident.createfromdictionaries( ... residentprefs, hospital_prefs, capacities ... ) _ = game.solve() # 48.6 ms ± 963 µs per loop

```

Get in contact!

I hope this package is useful, and feel free to contact me here with any issues or recommendations. Pull requests are always welcome!

Owner

Name: Henry Wilde
Login: daffidwilde
Kind: user
Location: Cardiff, UK
Company: Dŵr Cymru Welsh Water

Repositories: 29
Profile: https://github.com/daffidwilde

Data scientist and advocate for open-source, sustainably developed software 🛸 🐐 🦆

JOSS Publication

Matching: A Python library for solving matching games

Published

April 17, 2020

DOI

10.21105/joss.02169

Volume 5, Issue 48, Page 2169

Authors

Henry Wilde

School of Mathematics, Cardiff University

Vincent Knight

School of Mathematics, Cardiff University

Jonathan Gillard

School of Mathematics, Cardiff University

Editor

Viviane Pons

Citation (CITATION.cff)

cff-version: 1.2.0
title: 'Matching: A library for solving matching games'
message: >-
  If you use this software, please cite it using the
  metadata from this file.
type: software
authors:
  - given-names: Henry
    family-names: Wilde
    email: henrydavidwilde@gmail.com
    orcid: 'https://orcid.org/0000-0002-3788-7691'
  - given-names: Vince
    family-names: Knight
    orcid: 'https://orcid.org/0000-0002-4245-0638'
  - given-names: Jonathan
    family-names: Gillard
    orcid: 'https://orcid.org/0000-0001-9166-298X'
identifiers:
  - type: doi
    value: 10.5281/zenodo.2553125
    description: Zenodo archive
  - type: doi
    value: 10.21105/joss.02169
    description: JOSS paper
repository-code: 'https://github.com/daffidwilde/matching'
keywords:
  - matching
  - python
  - game
license: MIT

GitHub Events

Total

Issues event: 4
Watch event: 9
Delete event: 3
Issue comment event: 7
Push event: 22
Pull request event: 4
Fork event: 1
Create event: 3

Last Year

Issues event: 4
Watch event: 9
Delete event: 3
Issue comment event: 7
Push event: 22
Pull request event: 4
Fork event: 1
Create event: 3

Committers

Last synced: 7 months ago

All Time

Total Commits: 137
Total Committers: 5
Avg Commits per committer: 27.4
Development Distribution Score (DDS): 0.036

Past Year

Commits: 0
Committers: 0
Avg Commits per committer: 0.0
Development Distribution Score (DDS): 0.0

Top Committers

Name	Email	Commits
Henry Wilde	h**e@g**m	132
Vince Knight	v**t@g**m	2
Nikoleta Glynatsi	g**i@e**e	1
Daiji Fukagawa	d**8@g**m	1
Ben Maxfield	7****x	1

Committer Domains (Top 20 + Academic)

evolbio.mpg.de: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time

Total issues: 40
Total pull requests: 92
Average time to close issues: 4 months
Average time to close pull requests: 14 days
Total issue authors: 24
Total pull request authors: 5
Average comments per issue: 1.55
Average comments per pull request: 0.35
Merged pull requests: 87
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 2
Pull requests: 2
Average time to close issues: about 9 hours
Average time to close pull requests: 3 months
Issue authors: 2
Pull request authors: 1
Average comments per issue: 3.0
Average comments per pull request: 0.5
Merged pull requests: 2
Bot issues: 0
Bot pull requests: 0

View more stats

Top Authors

Issue Authors

daffidwilde (16)
justinrporter (2)
mkleinbort (1)
james016 (1)
zadeoglu (1)
drpventura (1)
sh-cho (1)
dfukagaw28 (1)
SiNa88 (1)
costructuralist (1)
pySRURGS (1)
Abrach-neufeld (1)
MartinMohlenkamp (1)
agt64 (1)
JnBrymn (1)

Pull Request Authors

daffidwilde (90)
drvinceknight (3)
Nikoleta-v3 (1)
BenJMax (1)
dfukagaw28 (1)

Top Labels

Issue Labels

longterm (1) enhancement (1) help wanted (1) pre-review (1)

Pull Request Labels

Packages

Total packages: 2
Total downloads:
- pypi 3,615 last-month
Total docker downloads: 391

Total dependent packages: 0
(may contain duplicates)
Total dependent repositories: 33
(may contain duplicates)
Total versions: 17
Total maintainers: 1

pypi.org: matching

A package for solving matching games

Documentation: https://matching.readthedocs.io/
License: MIT License
Latest release: 1.4.3
published over 2 years ago

Versions: 16
Dependent Packages: 0
Dependent Repositories: 33
Downloads: 3,615 Last month
Docker Downloads: 391

Rankings

Dependent repos count: 2.5%

Downloads: 3.2%

Docker downloads count: 3.9%

Average: 4.9%

Dependent packages count: 10.1%

Maintainers (1)

daffidwilde

Last synced: 6 months ago

conda-forge.org: matching

Matching games allow for the allocation of resources and partnerships in a fair way. Typically, a matching game is defined by two sets of players that each have preferences over at least some of the elements of the other set. The objective of the game is then to find a mapping between the sets of players in which everyone is happy enough with their match.

Homepage: https://github.com/daffidwilde/matching
License: MIT
Latest release: 1.4
published over 4 years ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 0

Rankings

Forks count: 27.1%

Stargazers count: 29.5%

Dependent repos count: 34.0%

Average: 35.5%

Dependent packages count: 51.2%

Last synced: 6 months ago

Matching

Science Score: 100.0%

Keywords

Repository

Basic Info

Statistics

Topics

Metadata Files

README.md

A package for solving matching games

Installation

Documentation

Playing a simple game

The Matching object

Player classes

A note on performance

Get in contact!

Owner

JOSS Publication

Matching: A Python library for solving matching games

Authors

Editor

Tags

Citation (CITATION.cff)

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

pypi.org: matching

Rankings

Maintainers (1)

conda-forge.org: matching

Rankings

Dependencies

The `Matching` object

`Player` classes