Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • Article
  • Games and Economic Behavior

Testing Substitutability

By: John William Hatfield, Nicole Immorlica and Scott Duke Kominers
  • Format:Print
ShareBar

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.
  • Find it at Harvard
  • Purchase

About The Author

Scott Duke Kominers

Entrepreneurial Management
→More Publications

More from the Authors

    • June 2025
    • Journal of Finance

    Collusion in Brokered Markets

    By: John William Hatfield, Scott Duke Kominers and Richard Lowery
    • Faculty Research

    Shifting Work Patterns with Generative AI

    By: Eleanor W. Dillon, Sonia Jaffe, Nicole Immorlica and Christopher T. Stanton
    • March 14, 2025
    • Harvard Crimson

    Harvard Students Should Ignore Calls to Boycott Israel Trek

    By: Jesse M. Fried, Paul A. Gompers, Scott Kominers and Mark C. Poznansky
More from the Authors
  • Collusion in Brokered Markets By: John William Hatfield, Scott Duke Kominers and Richard Lowery
  • Shifting Work Patterns with Generative AI By: Eleanor W. Dillon, Sonia Jaffe, Nicole Immorlica and Christopher T. Stanton
  • Harvard Students Should Ignore Calls to Boycott Israel Trek By: Jesse M. Fried, Paul A. Gompers, Scott Kominers and Mark C. Poznansky
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College.