I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:
The article says that:
In general, we can categorize two-sided matching problem into three typical kinds of models in terms of different decision objectives: stable matching, maximum cardinality matching, and maximum weight matching. In the first model, the objective is to seek a stable matching solution, and we count a solution as stable matching only when there does not exist any alternative pairing (𝐴, 𝐵) in which 𝐴 and 𝐵 are individually better off than they would be with the element currently matched. Gale and Shapley put forward an approach, also named Gale-Shapley algorithm, to get a stable matching solution in the perspective of mathematics and game theory, which symbolizes the beginning of two-sided matching research and enlightens the subsequent scholars to pay more attention to this topic. In the second model, the objective is to seek a solution in which the number of matching pairs is maximized.
I am able to understand stable matching. I can’t understand how the number of matching pair is maximized. This may occur because we have 2 sets. One of boys and other of girls. One element in one set has more than one matching in the other set. This might occur due to preference sequence. Am I right about maximum cardinality?
What I understand preference sequence as the order of preferences of elements of one set for the other. Due to maximum cardinality, it is possible that element Of one set has same preferences for multiple elements of the other set.
Am I right about preference sequences?
Somebody please guide me.