CaltechAUTHORS
  A Caltech Library Service

The Complexity of Rationalizing Matchings

Kalyanaraman, Shankar and Umans, Christopher (2008) The Complexity of Rationalizing Matchings. In: Algorithms and Computation. Lecture Notes in Computer Science. No.5369. Springer , Berlin, pp. 171-182. ISBN 978-3-540-92181-3. https://resolver.caltech.edu/CaltechAUTHORS:20191126-155702845

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191126-155702845

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 rationalization or 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 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-540-92182-0_18DOIArticle
https://rdcu.be/b3YkBPublisherFree ReadCube access
Additional Information:© 2008 Springer-Verlag Berlin Heidelberg. Supported by NSF CCF-0346991, NSF CCF-0830787, BSF 2004329 and a Graduate Research Fellowship from the Social and Information Sciences Laboratory (SISL) at Caltech. Supported by NSF CCF-0346991, NSF CCF-0830787, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant. We are indebted to Federico Echenique for numerous invaluable discussions and for getting us started on this work.
Funders:
Funding AgencyGrant Number
NSFCCF-0346991
NSFCCF-0830787
Binational Science Foundation (USA-Israel)2004329
Caltech Social and Information Sciences LaboratoryUNSPECIFIED
NSF Graduate Research FellowshipUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:5369
DOI:10.1007/978-3-540-92182-0_18
Record Number:CaltechAUTHORS:20191126-155702845
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191126-155702845
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100080
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Nov 2019 00:05
Last Modified:16 Nov 2021 17:51

Repository Staff Only: item control page