MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

Men A,B,C,DA,B,C,D rank women W,X,Y,ZW,X,Y,Z as A ⁣: ⁣W,X,Y,ZA\!:\!W,X,Y,Z; B ⁣: ⁣W,Y,X,ZB\!:\!W,Y,X,Z; C ⁣: ⁣X,W,Z,YC\!:\!X,W,Z,Y; D ⁣: ⁣W,Z,Y,XD\!:\!W,Z,Y,X. Women rank men as W ⁣: ⁣D,A,B,CW\!:\!D,A,B,C; X ⁣: ⁣A,C,D,BX\!:\!A,C,D,B; Y ⁣: ⁣B,D,A,CY\!:\!B,D,A,C; Z ⁣: ⁣C,D,A,BZ\!:\!C,D,A,B. Running the men-proposing deferred-acceptance algorithm, find the sum of the ranks (1 = top choice) that each man assigns to the woman he ends up matched to.