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