The Complexity of Rationalizing Matchings
The Complexity of Rationalizing Matchings
复制标题
合理化匹配的复杂性
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
C. Umans
中科院分区：
文献类型：
--
作者：
Shankar Kalyanaraman;C. Umans
给出一组观察到的经济选择，人们能否推断出与数据一致的玩家的偏好和/或效用函数？这类问题在经济学文献中被称为合理化问题或显性偏好问题，是大量著作的主题。
从计算机科学的角度来看，研究各种情况下合理化的复杂性是很自然的。我们考虑了一类合理化问题，其中经济数据由一组匹配来表示，问题是所有匹配都是稳定的节点是否存在偏好排序。
我们证明了一对一匹配的合理化问题是NP-完全的。我们提出了两种自然的逼近概念，并证明了在这两种情况下，问题很难在一个恒定因子内逼近。在积极的一面，我们描述了一个简单的算法，它实现了这些近似概念之一的3/4的近似比。我们还证明了多对一匹配的一个版本的类似结果。
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.