We provide an algorithm for testing the substitutability of a length-N preference relation over a set of contracts X in time O(vertical bar X vertical bar N-3 center dot(3)). 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 vertical bar X vertical bar. 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.
