0
$\begingroup$

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:

A Two-Sided Matching Decision Model Based on Uncertain Preference Sequences

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.

Zulfi.

Improve this question
$\endgroup$
1
  • $\begingroup$ What do you mean by "the maximum cardinality problem"? What exactly is your question? $\endgroup$
    – D.W. ♦
    Commented Feb 2, 2020 at 3:51

1 Answer 1

Reset to default
1
$\begingroup$

The standard definition of the stable marriage problem is, given $n$ men and $n$ women, find a stable matching that marries all of the men and women. Consequently, by definition, everyone will be matched and the number of matches will be exactly $n$ in any solution. So, no, what you mention cannot happen, if you use that as the definition of the stable marriage problem.

I'm not 100% sure what your text is referring to when it talks about maximum cardinality matching, but I suspect it's referring to find a maximum matching in a bipartite graph, which is completely separate problem. In this problem, the matching is not required to be a stable matching and it has nothing to do with the stable marriage problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your message. You have finally got my question. Why we can't apply stable matching algorithm (by Gale Shapley) to solve bipartite graph? How its completely separate problem? Somebody please explain me why we have uncertainities due to maximum cardinality problem? $\endgroup$
    – user2994783
    Commented Feb 2, 2020 at 4:50
  • $\begingroup$ @user2994783, There's lots of material written about both problems -- I suggest reading on your own about them. This site format is not designed for back-and-forths or follow-up questions or interactive discussions. $\endgroup$
    – D.W. ♦
    Commented Feb 2, 2020 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.