Publications
Publications
- Games and Economic Behavior
Testing Substitutability
By: John William Hatfield, Nicole Immorlica and Scott Duke Kominers
Abstract
We provide an algorithm for testing the substitutability of a length-N preference relation over a set of contracts X in time O(|X|3⋅N3). Access to the preference relation is essential for this result: We show that a substitutability-testing algorithm with access only to an agentʼs choice function must make an expected number of queries exponential in |X|. An analogous result obtains when the agentʼs preferences are quasilinear in a numeraire and the algorithm only has access to the agentʼs underlying valuation function.
Keywords
Substitutability; Matching; Communication Complexity; Preference Elicitation; Marketplace Matching; Communication; Mathematical Methods; Economics
Citation
Hatfield, John William, Nicole Immorlica, and Scott Duke Kominers. "Testing Substitutability." Games and Economic Behavior 75, no. 2 (July 2012): 639–645.
About The Author
