Changes
Created page with '==Preference system== A '''preference system''' is given by a graph ''G=(V,E)'' and for every node <math>v \in V</math> a linear order <math><_v</math> on the edges incident to …'
==Preference system==
A '''preference system''' is given by a graph ''G=(V,E)'' and for every node <math>v \in V</math> a linear order <math><_v</math> on the edges incident to ''v''. If ''e'' and ''f'' are edges incident to ''v'' and <math>e <_v f</math>, then we say that ''v'' '''prefers''' ''e'' to ''f'' and ''f'' is '''dominated''' by ''e''. It may be confusing at first that the nodes have preferences on the edges (and not other nodes), but this makes sense if we take into account that ''G'' may have parallel edges.
If partial orders are given at each node instead of linear orders, we speak of a '''preference system with ties'''. If ''G'' is bipartite, then we have a '''bipartite preference system'''.
==Stable matching==
Let ''(G,<)'' be a preference system. A matching ''M'' of ''G'' is '''stable''' if every edge not in ''M'' is dominated by at least one edge in ''M''. The problem of finding a stable matching is traditionally called the ''stable marriage problem'' if ''G'' is bipartite and the ''stable roommates problem'' if ''G'' is non-bipartite.
By the classic result of Gale and Shapley <ref>D. Gale, L.S. Shapley, ''College admissions and stability of marriage'', Amer. Math. Monthly (1962) 69(1), 9-15. [http://www.jstor.org/stable/2312726 JSTOR link].</ref>, every bipartite preference system has a stable matching and one can be found by the deferred acceptance algorithm. A non-bipartite preference system may not have a stable matching, but Irving <ref>R. W. Irwing, ''An efficient algorithm for the stable roommates problem'', J. Algorithms 6 (1985), 577-595. [http://dx.doi.org/10.1016/0196-6774(85)90033-1 DOI link]</ref> gave a polynomial algorithm to decide if it exists and find one.
==Popular matching==
Let ''(G,<)'' be a preference system. Given two matchings ''M'' and ''N'', we say that a node ''v'' prefers ''M'' to ''N'' if either ''v'' is matched in ''M'' but not in ''N'', or ''v'' is matched in both and it prefers the edge incident to it in ''M'' to the edge incident to it in ''N''.
A matching ''M'' is '''popular''' if for every other matching ''N'' the number of nodes who prefer ''M'' to ''N'' is at least the number of nodes who prefer ''N'' to ''M''. Not every preference system has a popular matching, not even in the bipartite case, and not every popular matching has the same size.
==References==
<references/>
[[Category: Definitions]]
A '''preference system''' is given by a graph ''G=(V,E)'' and for every node <math>v \in V</math> a linear order <math><_v</math> on the edges incident to ''v''. If ''e'' and ''f'' are edges incident to ''v'' and <math>e <_v f</math>, then we say that ''v'' '''prefers''' ''e'' to ''f'' and ''f'' is '''dominated''' by ''e''. It may be confusing at first that the nodes have preferences on the edges (and not other nodes), but this makes sense if we take into account that ''G'' may have parallel edges.
If partial orders are given at each node instead of linear orders, we speak of a '''preference system with ties'''. If ''G'' is bipartite, then we have a '''bipartite preference system'''.
==Stable matching==
Let ''(G,<)'' be a preference system. A matching ''M'' of ''G'' is '''stable''' if every edge not in ''M'' is dominated by at least one edge in ''M''. The problem of finding a stable matching is traditionally called the ''stable marriage problem'' if ''G'' is bipartite and the ''stable roommates problem'' if ''G'' is non-bipartite.
By the classic result of Gale and Shapley <ref>D. Gale, L.S. Shapley, ''College admissions and stability of marriage'', Amer. Math. Monthly (1962) 69(1), 9-15. [http://www.jstor.org/stable/2312726 JSTOR link].</ref>, every bipartite preference system has a stable matching and one can be found by the deferred acceptance algorithm. A non-bipartite preference system may not have a stable matching, but Irving <ref>R. W. Irwing, ''An efficient algorithm for the stable roommates problem'', J. Algorithms 6 (1985), 577-595. [http://dx.doi.org/10.1016/0196-6774(85)90033-1 DOI link]</ref> gave a polynomial algorithm to decide if it exists and find one.
==Popular matching==
Let ''(G,<)'' be a preference system. Given two matchings ''M'' and ''N'', we say that a node ''v'' prefers ''M'' to ''N'' if either ''v'' is matched in ''M'' but not in ''N'', or ''v'' is matched in both and it prefers the edge incident to it in ''M'' to the edge incident to it in ''N''.
A matching ''M'' is '''popular''' if for every other matching ''N'' the number of nodes who prefer ''M'' to ''N'' is at least the number of nodes who prefer ''N'' to ''M''. Not every preference system has a popular matching, not even in the bipartite case, and not every popular matching has the same size.
==References==
<references/>
[[Category: Definitions]]
