ECCC-Report TR08-021https://eccc.weizmann.ac.il/report/2008/021Comments and Revisions published for TR08-021en-usTue, 11 Mar 2008 07:15:47 +0200
Paper TR08-021
| The Complexity of Rationalizing Matchings |
Shankar Kalyanaraman,
Chris Umans
https://eccc.weizmann.ac.il/report/2008/021Given 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.
Tue, 11 Mar 2008 07:15:47 +0200https://eccc.weizmann.ac.il/report/2008/021