Parallelising the greedy solver

[nbgl]

Let A and B be datasets of records. Let C ⊂ A × B be the set of candidate pairs. Let s : C → ℝ be an injective similarity function. We explore the problem of finding a matching between A and B.

(The similarity function is injective to reflect our well-defined tiebreaking. This makes the proofs below easier.)

Definition: A matching is a set M ⊂ C that represents an injective partial function from A to B. (Every element of A is matched with at most one element of B and vice versa).

Definition: A matching M is unstable if there exists (a, b) ∈ C∖M such that any of the following hold:

1. a is not matched and b is not matched,
2. a is not matched, b is matched to some a' ∈ A, and s(a, b) > s(a', b),
3. a is matched to some b' ∈ B, b is not matched, and s(a, b) > s(a, b'), or
4. a is matched to some b ∈ B, b is matched to some a' ∈ A, s(a, b) > s(a', b), and s(a, b) > s(a, b').

In other words, a matching is unstable if we can find a pair that is not in the matching and that would produce a more preferable match for both of its members (the state of not being matched is the least preferable).

Definition: A matching is stable if it is not unstable.

Theorem: The greedy solver produces a stable matching.
Proof: Let M ⊂ C be an unstable matching. We show that it cannot have been returned by the greedy solver.

Since the matching is unstable, there exists at least one pair that is in C but not in M and that would produce a more preferable match for both of its members. Let (a, b) be such a pair. There are four cases:

1. a is not matched and b is not matched. The greedy solver would come across this pair since it is in C. At that time neither a and b would be matched since the solver never breaks existing matches. Hence a and b would be matched.
2. a is not matched, b is matched to some a' ∈ A, and s(a, b) > s(a', b). The greedy solver would come across the pair (a and b). At that time a would not be matched. b would not be matched either since it is not matched when the greedy solver comes across it later (the candidate pairs are visited in order of similarity). Hence a and b would be matched.
3. a is matched to some b' ∈ B, b is not matched, and s(a, b) > s(a, b'). By symmetry from 2.
4. a is matched to some b' ∈ B, b is matched to some a' ∈ A, s(a, b) > s(a', b), and s(a, b) > s(a, b'). The greedy solver would come across the pair (a, b). At that time a would not be matched since it is not matched when the greedy solver comes across it later (permitting it to be matched with b'). b would not be matched for an analogous reason. Hence a and b would be matched. ∎

Theorem: There is only one stable matching.
Proof: By contradiction. Let M and M' be two distinct stable matchings. We show that one of them cannot be stable.

Since M ≠ M', there exists a pair in C that is in one but not the other. Let (a, b) be the one of these pairs that has the highest similarity. WLOG, (a, b) ∈ M∖M'. We show that M' is unstable. Four cases:

1. Neither a nor b is matched in M'. This makes M' unstable by definition.
2. a is not matched in M' and b is matched to some a' ∈ A. s(a, b) > s(a', b) since (a, b) has the highest similarity of differing pairs. Hence M' is unstable.
3. a is matched to some b' ∈ B and b is not matched. By symmetry from 2.
4. a is matched to some b' ∈ B and b is matched to some a' ∈ A. s(a, b) > s(a', b) and s(a, b) > s(a, b') since (a, b) has the highest similarity of differing pairs. Hence M' is unstable. ∎

Observe that the similarity scores induce preferences between A and B. Every member of A can assign a preference to every member of B with which it shares a candidate pair. The preferences are monotonic with the similarities. Members of B can similarly preference members of A. This can be input into the Gale-Shapley algorithm to produce a matching.

Corollary: The greedy solver yields the same solution as the Gale-Shapley algorithm.
Proof: The Gale-Shapley algorithm always yields a stable matching. [1] The greedy solver also always returns a stable matching. Since there is only one stable matching for our problem, they both return it. ∎

The point being…

This lets us make progress on parallelising the greedy solver by studying some of the parallel algorithms for the Stable Marriage Problem. [2-5] are some relevant papers. I haven't read them yet.

[1] Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15. http://www.dtic.mil/dtic/tr/fulltext/u2/251958.pdf
[2] Larsen, Jesper. A parallel approach to the stable marriage problem. Datalogisk Institut, Københavns Universitet, 1997. https://di.ku.dk/forskning/Publikationer/tekniske_rapporter/1997/97-05.pdf
[3] Tseng, S. S. "The average performance of a parallel stable marriage algorithm." BIT Numerical Mathematics 29.3 (1989): 448-456. https://link.springer.com/article/10.1007/BF02219230
[4] Quinn, Michael J. "A note on two parallel algorithms to solve the stable marriage problem." BIT Numerical Mathematics 25.3 (1985): 473-476. https://link.springer.com/article/10.1007/BF01935367

Aha! Link: https://csiro.aha.io/features/ANONLINK-61