The Complexity of Rationalizing Matchings.

Abstract

Given a set of observed economic choices, can one infer preferences and/or utility functions for the
\nplayers that are consistent with the data? Questions of this type are called rationalization or revealed
\npreference problems in the economic literature, and are the subject of a rich body of work.
\nFrom the computer science perspective, it is natural to study the complexity of rationalization in various
\nscenarios. We consider a class of rationalization problems in which the economic data is expressed
\nby a collection of matchings, and the question is whether there exist preference orderings for the nodes
\nunder which all the matchings are stable.
\nWe show that the rationalization problem for one-one matchings is NP-complete. We propose two
\nnatural notions of approximation, and show that the problem is hard to approximate to within a constant
\nfactor, under both. On the positive side, we describe a simple algorithm that achieves a 3/4 approximation
\nratio for one of these approximation notions. We also prove similar results for a version of many-one matching.