Fractional Matchings under Preferences: Stability and Optimality

We study on the so-called ordinal stability and cardinal stability, and investigate the computational complexity of finding an ordinally stable or cardinally stable fractional matching which either maximizes the social welfare (i.e., the overall utilities of the agents) or the number of fully matched agents (i.e., agents whose matching values sum up to one). We complete the complexity classification of both optimization problems for both ordinal stability and cardinal stability, distinguishing between the marriage (bipartite) and roommates (non-bipartite) cases and the presence or absence of ties in the preferences. In this talk we will focus on the definitions and discuss an algorithm for maximizing the number of fully matched agents in ordinally stable roommates without ties.

This is a joint work with Jiehua Chen and Manuel Sorge, appeared in IJCAI ‘21.

Recording