Ludde127
2023-06-05

L

Given two sets X and Y a matching M is a set of pairs (xi, yi) so that each x and y occurs in exactly one matching.

A bipartite graph consists of two distinct sets of nodes U and V with only edges (u, v) where u is from U and v from V.

Thus the matchings created from the stable matching problem are a bipartite graph. Assume each node in U has a ranking of its prefered nodes in V and each node in V has a ranking of the nodes in U. Then we can create a stable matching by; starting with a node u in U pair u with its most preffered node in v, this makes a temporary matching (u, v). If later in the algorithm another node u which is better ranked in v's list matches the old match is broken and the new one is created.

A matching is unstable if it has to pairs (u_a, v_a), (u_b, v_b) and

- u_a prefers v_b and v_b prefers u_a or if,
- v_a prefers u_b and u_b prefers v_a.

A stable matching is a perfect matching which contains no unstable pairs.

An algorithm for solving this problem is the **Gale-shapley algorithm**.

Proving the Gale-Shapley algorithm can be done by reasoning.

Card: 1/42
Score:
0.0

Press to start

Card: 1/7
Score:
0.0

Press to start

Card: 1/31
Score:
0.0

Press to start