Name
Abstract | ||
|---|---|---|
We introduce generalized matching games defined on a graph G = (V, E) with an edge weighting w and a partition V = V-1 boolean OR .... boolean OR V-n of V. The player set is N = {1, ..., n}, and player p is an element of N owns the vertices in V-p. The value v(S) of coalition S subset of N is the maximum weight of a matching in the subgraph of G induced by the vertices owned by players in S. If vertical bar V-p vertical bar = 1 for every player p we obtain the classical matching game. We prove that checking core nonemptiness is polynomial-time solvable if vertical bar V-p vertical bar <= 2 for each p and co-NP-hard if vertical bar V-p vertical bar <= 3 for each p. We do so via pinpointing a relationship with b-matching games and also settle the complexity classification on testing core non-emptiness for b-matching games. We propose generalized matching games as a suitable model for international kidney exchange programs, where the vertices in V correspond to patient-donor pairs and each V-p represents one country. For this setting we prove a number of complexity results. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.5555/3306127.3331721 | adaptive agents and multi-agents systems |
Keywords | Field | DocType |
kidney exchanges,matching game,core,computational complexity | Graph,Matching game,Combinatorics,Weighting,Vertex (geometry),Computer science,Artificial intelligence,Partition (number theory),Machine learning,Computational complexity theory | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Péter Biró | 1 | 4 | 1.09 |
| Walter Kern | 2 | 169 | 24.26 |
| Dömötör Pálvölgyi | 3 | 202 | 29.14 |
| Daniël Paulusma | 4 | 712 | 78.49 |