TL;DR
This paper introduces an efficient algorithm to test if an agent's preferences are "substitutable," a crucial property for stable matching mechanisms. While direct preference testing is polynomial, testing with only access to an agent's choices or valuations is shown to be computationally hard, requiring exponential time in the worst case.
What Problem Does This Paper Address?
Many real-world matching markets, like those for medical residents or job candidates, rely on stable matching algorithms. A key assumption for guaranteeing stable outcomes in these markets is that agents' preferences are "substitutable." This means that if an agent rejects a contract, they won't change their mind and accept it later just because more options become available.
The challenge arises when market designers need to verify this substitutability property. If agents submit their full preference lists, testing can be done efficiently. However, in many scenarios, designers might only have indirect access to preferences, such as through an agent's "choice function" (what they pick from a given set of options) or their "valuation function" (a numerical representation of their preferences). The paper investigates how computationally difficult it is to test substitutability in these indirect access scenarios.
Methods
The paper presents two main contributions:
- Efficient Testing with Preference Relations: The authors develop a deterministic algorithm that can test substitutability for an agent's explicit preference relation in polynomial time. Specifically, the algorithm runs in $O(|X|^3 \cdot N^3)$ time, where $|X|$ is the number of available contracts and $N$ is the length of the preference list. This is a significant improvement over a naive approach that would require exponential time. The algorithm works by systematically checking for "substitutability violations" – specific combinations of contracts and available sets that break the substitutability property.
- Hardness Results for Indirect Access: Using techniques like Yao's minimax principle, the paper proves that if a market designer only has oracle access to an agent's choice function or valuation function, testing substitutability becomes computationally intractable. No algorithm, even a randomized one, can do this in subexponential time in the worst case. This implies that for these indirect access scenarios, the problem requires an exponential number of queries to the agent's choices or valuations.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithms and complexity analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Preference Lists are Key: The paper highlights that having direct access to an agent's preference list is crucial for efficient substitutability testing. This suggests that designing market interfaces that encourage detailed preference submissions can greatly simplify verification.
- The "Curse of Indirectness": The most striking finding is the dramatic increase in computational difficulty when moving from direct preference lists to indirect access (choice functions or valuations). This suggests a fundamental trade-off between the ease of preference elicitation and the difficulty of verifying properties like substitutability.
- Substitutability is "Local" for Preferences, but "Global" for Choices: While substitutability violations can be identified by examining relatively small subsets of preferences, the paper shows that to detect violations using only choice functions, one might need to probe a vast number of possibilities, leading to exponential complexity.
- Quasilinear Preferences Don't Save the Day: Even when agents have quasilinear utility functions (a common simplification in economics), testing substitutability via valuation functions remains computationally hard.
Key Results
- An algorithm is provided to test substitutability of preference relations in $O(|X|^3 \cdot N^3)$ time.
- It is proven that testing substitutability with only oracle access to an agent's choice function requires an expected exponential number of queries in the worst case.
- Similarly, testing substitutability with only oracle access to an agent's valuation function also requires an expected exponential number of queries in the worst case.
- These hardness results hold even for randomized algorithms and with only a small probability of error.
Limitations and Future Work
- Preference Encoding Length: The paper notes that the choice functions used in the hardness proofs do not necessarily correspond to preference relations with polynomial-length encodings. This leaves open the question of whether there exist specific preference structures that are testable in polynomial time via the preference relation but require exponential time via choice function access.
- Demand Correspondences: The hardness result for valuation functions is not an exact analogue of the result for choice functions, as it involves queries to valuation functions rather than demand correspondences. The complexity of testing gross substitutability given oracle access to demand correspondences remains an open question.
- Alternative Languages: The authors suggest that market designers might need to develop alternative ways for agents to express substitutable preferences, beyond standard preference lists, to facilitate efficient testing and market operation. The generality and effectiveness of such languages are areas for future research.
Summary updated