TR08-021 Authors: Shankar Kalyanaraman, Chris Umans

Publication: 11th March 2008 07:15

Downloads: 2865

Keywords:

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.