Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-021 | 3rd March 2008 00:00

The Complexity of Rationalizing Matchings


Authors: Shankar Kalyanaraman, Chris Umans
Publication: 11th March 2008 07:15
Downloads: 3122


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.

ISSN 1433-8092 | Imprint