Complexity of marriage matching problem?
I may have misunderstood the question, because my answer conflicts with Serge's. To my understanding, you're asking about the Linear Bottleneck Assignment Problem. This is known to be solved in O(n^2.5).

The most complete source of information is [1], although I really don't like the book's style. There's also a website: http://www.assignmentproblems.com/linearBNAP.htm

EDIT: To clarify, the we want an assignment such that the edge with maximal cost is minimized. The cost will be the maximal number of unassigned attributes for either the man or the woman that are matched.

EDIT2: I can only offer references from the book I cited. Three of them are:


G. Carpaneto and P. Toth Algorithm for the solution of the bottleneck assignment problem. Computing, 27:179-187m 1981
U. Derigs. Alternate strategies for solving bottleneck assignment problems - analysis and computational results. Computing, 33:95-106, 1984
U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285-295, 1978


You should try to get hold of the book, since lists some of the available algorithms.

[1] Assignment Problems by Rainer Burkard, Mauro Dell'Amico, Silvano Martello