Contractual Structure and Obvious Manipulation in Many-to-Many Matching

arXiv:2611.17029 · econ.TH · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Contractual Structure and Obvious Manipulation in Many-to-Many Matching".

Warren: Here's the gist of the paper. We study how contractual structure affects worst-case and best-case obvious manipulation in many-to-many matching with substitutable preferences Efficient individually rational mechanisms rule out best-case obvious manipulations on both the full substitutable domain and the unitary domain Under simple and economically natural conditions on hospitals’ choices, every stable mechanism on the full domain admits obvious manipulations in both cases; hospital-proposing deferred acceptance can admit both types even under unitary doctors’ preferences A further sufficient condition makes efficient stable-dominating mechanisms obviously manipulable in the worst case On the unitary domain, doctor-proposing deferred acceptance is not obviously manipulable If each doctor–hospital pair has at most one feasible contract, this positive conclusion extends to every stable-dominating mechanism The Core Inquiry The paper addresses how contractual structure influences the scope for obvious manipulation in many-to-many matching markets with substitutable preferences The central question is how features like multiple contracts or contract specification affect the scope for obvious manipulation of stable mechanisms and efficient mechanisms that improve upon stable outcomes The incentive criterion used is non-obvious manipulability (NOM), which compares the extrema of option sets available under two declarations using the agent’s true preference The analysis distinguishes between stability and efficiency, showing that contractual alternatives can affect these two comparisons differently Efficiency and Best-Case Bounds Efficiency places a restriction on the best-case comparison that does not depend on stable domination or on the hospital conditions introduced below Theorem 1 establishes that in the many-to-many matching model, no efficient individually rational mechanism admits obvious manipulations in the best case, holding on both preference domains This result is proven by showing that efficiency forces the doctor to receive a set of contracts that is weakly worse than the best possible outcome under any deviation Contractual Competition and Manipulation The paper identifies specific configurations of hospital choices that generate obvious manipulations in a fixed admissible market The first configuration involves alternative agreements with the same doctor that are acceptable separately but compete when offered together If a market admits protected competing contracts, every stable mechanism is OM in both the best and worst cases, and a single declaration improves both extrema The second configuration involves contractual replacement with competition, where a doctor's preferred contract can be displaced by others while another contract is accepted despite competition Theorem 4 shows that if the market admits contractual replacement with competition, any efficient stable-dominating mechanism is OM in the worst case on both domains Unitary Preferences and NOM Results The analysis under unitary preferences reveals that doctor-proposing deferred acceptance (DDAM) is NOM in every admissible market This is proven by constructing an auxiliary market where doctors have unit-demand preferences, and showing that the resulting outcome under DDAM is weakly preferred to any alternative report Furthermore, when each doctor–hospital pair has at most one feasible contract, every stable-dominating mechanism is NOM The results demonstrate that neither stable mechanisms on the full domain nor HDAM on the unitary domain, nor efficient stable-dominating mechanisms on either domain can be NOM in all admissible markets The comparison highlights that contractual structure and unitary preference restrictions affect which stable mechanisms remain NOM Efficiency specifically prevents best-case obvious manipulation but need not prevent a worst-case improvement The study leaves open the behavior of stable-dominating mechanisms that are neither stable nor efficient in markets with alternative contracts References ALVA, S., AND V.

Ruth: MANJUNATH (2019a): “Stable-dominating rules,” Working paper, September 4.

Warren: ARCHBOLD, T., B.

Ruth: DE KEIJZER, AND C.

Paper summary: Ruth: So to wrap up the paper "Contractual Structure and Obvious Manipulation in Many-to-Many Matching," the authors show that we can’t rely on a single type of mechanism to rule out manipulation across all scenarios.

Warren: The implication is that if you're designing these matching markets, the contract structure is just as important as the stability rules you apply to keep things from going haywire >

Iris: They establish that efficiency rules out best-case manipulation, which is a solid piece of evidence, but they show that worst-case manipulation can still happen depending on how contracts are set up >

Ruth: The main point for the world is that these results show how agent preferences and contract terms interact to create opportunities for manipulation in complex matching systems >

Warren: If you're running a system where doctors choose from multiple hospitals, understanding these structural effects helps you predict where the incentive problems will pop up >

Conclusion: Ruth: So we've been talking about how contract structure messes with manipulation in these many-to-many matching markets, and now we're looking at where this specific paper lands—"Contractual Structure and Obvious Manipulation in Many-to-Many Matching."

Warren: Yeah, the main thing is that it shows you can’t just pick one set of rules for stability or efficiency and expect it to stop every kind of manipulation.

Iris: Exactly. It lays out how different contract setups—like when hospitals can make multiple deals with the same doctor—create these specific loopholes for obvious manipulation in both the best and worst cases.

Ruth: It really highlights that efficiency rules out one type of manipulation, but those alternative contracts open doors for others, depending on whether you're looking at the full set of choices or just a single doctor’s options.

Warren: The authors show that under certain conditions, like when doctors only have unit-demand preferences, then a specific mechanism called doctor-proposing deferred acceptance isn't actually manipulable in the worst case.

Iris: That’s a strong result because it pinpoints exactly which contractual constraints actually protect people from getting exploited by these obvious manipulation tactics.

Ruth: So what does this mean practically for someone running a matching system? It means you can’t just focus on one stability criterion; you have to look at the specific contracts being offered and how those interact with the preferences.

Warren: It suggests that designing the contract itself is a critical first step before you even worry about choosing between stable or efficient mechanisms.

Iris: And this opens up questions about what happens when we add more complexity, like when a market admits contractual replacement with competition, which introduces another layer of instability to check.

Ruth: That leads us right into the next part where we look at how these structural issues play out when we move from simple stability to things that are just efficient but maybe not stable.

R. Pablo Arribillaga, Beatriz Millan, Eliana Pepa Risma

Instituto de Matemática Aplicada San Luis (CONICET–UNSL) · RedNIE

econ.TH

Submitted: 2026-11-12

Updated: 2026-11-12

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: We study how contractual structure affects worst-case and best-case obvious manipulation in many-to-many matching with substitutable preferences Efficient individually rational mechanisms rule out…

Key concepts

Non-Obvious Manipulability (NOM)
This criterion compares the best and worst possible outcomes available to an agent under two different declarations using their true preferences. If an outcome is NOM, it means the agent cannot be tricked into choosing a worse option when comparing these two scenarios.
Efficient Mechanisms
These are mechanisms that achieve the highest possible welfare while remaining individually rational. The paper shows that efficiency imposes strong constraints, specifically ruling out obvious manipulations in the best-case scenario for these mechanisms in many-to-many matching.
Unitary Preferences
This condition restricts agents (like doctors) to having only one preferred contract or option among their choices. Analyzing results under this restriction simplifies the findings, showing that doctor-proposing deferred acceptance becomes non-manipulable in specific scenarios.
Contractual Structure
This refers to the rules governing how contracts are formed and offered in a matching market. The paper investigates how features like having multiple competing contracts or replacement options influence whether stable mechanisms can be manipulated.

Terminology

Summary

We study how contractual structure affects worst-case and best-case obvious manipulation in many-to-many matching with substitutable preferences Efficient individually rational mechanisms rule out best-case obvious manipulations on both the full substitutable domain and the unitary domain Under simple and economically natural conditions on hospitals’ choices, every stable mechanism on the full domain admits obvious manipulations in both cases; hospital-proposing deferred acceptance can admit both types even under unitary doctors’ preferences A further sufficient condition makes efficient stable-dominating mechanisms obviously manipulable in the worst case On the unitary domain, doctor-proposing deferred acceptance is not obviously manipulable If each doctor–hospital pair has at most one feasible contract, this positive conclusion extends to every stable-dominating mechanism

The Core Inquiry

The paper addresses how contractual structure influences the scope for obvious manipulation in many-to-many matching markets with substitutable preferences The central question is how features like multiple contracts or contract specification affect the scope for obvious manipulation of stable mechanisms and efficient mechanisms that improve upon stable outcomes The incentive criterion used is non-obvious manipulability (NOM), which compares the extrema of option sets available under two declarations using the agent’s true preference The analysis distinguishes between stability and efficiency, showing that contractual alternatives can affect these two comparisons differently

Efficiency and Best-Case Bounds

Efficiency places a restriction on the best-case comparison that does not depend on stable domination or on the hospital conditions introduced below Theorem 1 establishes that in the many-to-many matching model, no efficient individually rational mechanism admits obvious manipulations in the best case, holding on both preference domains This result is proven by showing that efficiency forces the doctor to receive a set of contracts that is weakly worse than the best possible outcome under any deviation

Contractual Competition and Manipulation

The paper identifies specific configurations of hospital choices that generate obvious manipulations in a fixed admissible market The first configuration involves alternative agreements with the same doctor that are acceptable separately but compete when offered together If a market admits protected competing contracts, every stable mechanism is OM in both the best and worst cases, and a single declaration improves both extrema The second configuration involves contractual replacement with competition, where a doctor's preferred contract can be displaced by others while another contract is accepted despite competition Theorem 4 shows that if the market admits contractual replacement with competition, any efficient stable-dominating mechanism is OM in the worst case on both domains

Unitary Preferences and NOM Results

The analysis under unitary preferences reveals that doctor-proposing deferred acceptance (DDAM) is NOM in every admissible market This is proven by constructing an auxiliary market where doctors have unit-demand preferences, and showing that the resulting outcome under DDAM is weakly preferred to any alternative report Furthermore, when each doctor–hospital pair has at most one feasible contract, every stable-dominating mechanism is NOM

Conclusion and Implications

The results demonstrate that neither stable mechanisms on the full domain nor HDAM on the unitary domain, nor efficient stable-dominating mechanisms on either domain can be NOM in all admissible markets The comparison highlights that contractual structure and unitary preference restrictions affect which stable mechanisms remain NOM Efficiency specifically prevents best-case obvious manipulation but need not prevent a worst-case improvement The study leaves open the behavior of stable-dominating mechanisms that are neither stable nor efficient in markets with alternative contracts

References

ALVA, S., AND V. MANJUNATH (2019a): “Stable-dominating rules,” Working paper, September 4. p. 4

Where the paper says it

The stable-domination criterion is studied by Alva and Manjunath (2019a), and the search for welfare improvements over deferred acceptance is central to Kesten (2010) and Do˘gan and Ehlers (2021). Alva and Manjunath (2019b) analyze restrictions on strategyproof Pareto improvements, while Chen and Möller (2024) study regret-free truth-telling for efficient stable-dominating rules in school choice.

ARCHBOLD, T. p. 5

Where the paper says it

for tops-only voting rules. With monetary transfers, Archbold et al.

, B. DE KEIJZER, AND C. p. 5
Where the paper says it

With monetary transfers, Archbold et al. (2025) show that the two requirements have different implications for subsidies in bilateral trade, and de Keijzer et al.

VENTRE (2025): “Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade,” ACM Transactions on Economics and Computation, 13, 16:1–16:26. p. 5
Where the paper says it

With monetary transfers, Archbold et al. (2025) show that the two requirements have different implications for subsidies in bilateral trade, and de Keijzer et al.

ARRIBILLAGA, R. p. 0

Where the paper says it

Contractual Structure and Obvious Manipulation in Many-to-Many Matching* R. Pablo Arribillaga† Beatriz Millan‡ Eliana Pepa Risma§ October 6, 2026 Abstract We study how contractual structure affects worst-case and best-case obvious manipulation in many-to-many matching with substitutable preferences.

P., AND A. G. BONIFACIO (2024): “Obvious manipulations of tops-only voting rules,” Games and Economic Behavior, 143, 12–24. p. 4
Where the paper says it

In voting, Aziz and Lam (2021) distinguish best-case and worst-case obvious manipulation and show that, for positional scoring rules with at least three voters and alternatives, the existence of a best-case obvious manipulation entails the existence of a worstcase obvious manipulation. Arribillaga and Bonifacio (2024) obtain a related implication 5

CHEN, P., M. EGESDAL, M. PYCIA, AND M. B. YENMEZ (2016): “Manipulability of stable mechanisms,” American Economic Journal: Microeconomics, 8, 202–214. p. 4

Where the paper says it

Chen et al. (2016) relate comparisons of stable mechanisms by manipulability to agents’ welfare comparisons.

CHEN, S.: “Information Disclosure and Incentive Collapse in Division Problems,” Mimeo. p. 5

Where the paper says it

(2026) characterize them separately in budget-feasible procurement. In division problems with single-peaked preferences, Arribillaga and Bonifacio (2025a) characterize a broad class of efficient, own-peak-only NOM rules satisfying the equal division guarantee, while Arribillaga and Bonifacio (2025b) show that adding consistency singles out the uniform rule.

DE KEIJZER, B. p. 5

Where the paper says it

With monetary transfers, Archbold et al. (2025) show that the two requirements have different implications for subsidies in bilateral trade, and de Keijzer et al.

, G. SCHÄFER, A. TSIKIRIDIS, AND C. VENTRE (2026): “Breaking Barriers, Finding Boundaries: Not Obviously Manipulable Budget-Feasible Mechanism Design,” Proceedings of the AAAI Conference on Artificial Intelligence, 40, 16803–16811. p. 0
Where the paper says it

On the unitary domain, doctor-proposing deferred acceptance is not obviously manipulable. If each doctor–hospital pair has at most one feasible contract, this positive conclusion extends to every stable-dominating mechanism.

DOGAN ˘, B., AND L. EHLERS (2021): “Minimally unstable Pareto improvements over deferred acceptance,” Theoretical Economics, 16, 1249–1279. p. 4

Where the paper says it

The stable-domination criterion is studied by Alva and Manjunath (2019a), and the search for welfare improvements over deferred acceptance is central to Kesten (2010) and Do˘gan and Ehlers (2021). Alva and Manjunath (2019b) analyze restrictions on strategyproof Pareto improvements, while Chen and Möller (2024) study regret-free truth-telling for efficient stable-dominating rules in school choice.

ECHENIQUE, F. p. 4

Where the paper says it

The unit-demand examples isolate the role of contractual alternatives, while the full-domain result for stable mechanisms also uses the willingness to accept several contracts with the same partner. More broadly, Blair (1988), Echenique and Oviedo (2006), and Klaus and Walzl (2009) develop the structure and stability theory of many-to-many matching.

, AND J. OVIEDO (2006): “A theory of stability in many-to-many matching markets,” Theoretical Economics, 1, 233–273. p. 4
Where the paper says it

The unit-demand examples isolate the role of contractual alternatives, while the full-domain result for stable mechanisms also uses the willingness to accept several contracts with the same partner. More broadly, Blair (1988), Echenique and Oviedo (2006), and Klaus and Walzl (2009) develop the structure and stability theory of many-to-many matching.

HATFIELD, J. p. 1

Where the paper says it

Some activities can be agreed separately with the same partner, while other contracts specify mutually exclusive terms. For example, Hatfield and Kominers (2017) discuss medical internship arrangements in which surgical and medical placements can be assigned through separate contracts, including placements at the same hospital.

p. 1
Where the paper says it

Some activities can be agreed separately with the same partner, while other contracts specify mutually exclusive terms. For example, Hatfield and Kominers (2017) discuss medical internship arrangements in which surgical and medical placements can be assigned through separate contracts, including placements at the same hospital.

W., F. KOJIMA, AND Y. NARITA (2014): “Many-to-many matching with max–min preferences,” Discrete Applied Mathematics, 179, 235–240. p. 4
Where the paper says it

On incentives, Hatfield et al. (2014) show that even a stringent max–min preference restriction does not guarantee a stable and strategy-proof mechanism.

HATFIELD, J. W., AND S. D. KOMINERS (2017): “Contract design and stability in many-tomany matching,” Games and Economic Behavior, 101, 78–97. p. 0

Where the paper says it

Keywords: obvious manipulations, worst case, best case, stability, efficiency, many-tomany matching, contracts. *We acknowledge the financial support from UNSL through grants 032016 and 030120, from Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET) through grant PIP 112-200801-00655, and from Agencia Nacional de Promoción Científica y Tecnológica through grant PICT 2017-2355.

KESTEN, O.: “School choice with consent,” The Quarterly Journal of Economics, 125, 1297–1348. p. 4

Where the paper says it

The stable-domination criterion is studied by Alva and Manjunath (2019a), and the search for welfare improvements over deferred acceptance is central to Kesten (2010) and Do˘gan and Ehlers (2021). Alva and Manjunath (2019b) analyze restrictions on strategyproof Pareto improvements, while Chen and Möller (2024) study regret-free truth-telling for efficient stable-dominating rules in school choice.

KLAUS, B., AND M. WALZL (2009): “Stable many-to-many matchings with contracts,” Journal of Mathematical Economics, 45, 422–434. p. 4

Where the paper says it

The unit-demand examples isolate the role of contractual alternatives, while the full-domain result for stable mechanisms also uses the willingness to accept several contracts with the same partner. More broadly, Blair (1988), Echenique and Oviedo (2006), and Klaus and Walzl (2009) develop the structure and stability theory of many-to-many matching.

KOMINERS, S. p. 1

Where the paper says it

Some activities can be agreed separately with the same partner, while other contracts specify mutually exclusive terms. For example, Hatfield and Kominers (2017) discuss medical internship arrangements in which surgical and medical placements can be assigned through separate contracts, including placements at the same hospital.

D.: “On the correspondence of contracts to salaries in (many-tomany) matching,” Games and Economic Behavior, 75, 984–989. p. 0
Where the paper says it

JEL classification: D71, D72. Keywords: obvious manipulations, worst case, best case, stability, efficiency, many-tomany matching, contracts.

MA, J., AND S. D. KOMINERS (2018): “Bundling Incentives in (Many-to-Many) Matching with Contracts,” Working Paper 19-011, Harvard Business School. p. 3

Where the paper says it

Kominers (2012) identifies unitarity as a key condition for embedding matching with contracts into matching with salaries. Ma and Kominers (2018) study incentives to alter the contract language through unilateral bundling.

ORTEGA, J., AND E. SEGAL-HALEVI (2022): “Obvious manipulations in cake-cutting,” Social Choice and Welfare, 1–20. p. 4

Where the paper says it

Alva and Manjunath (2019b) analyze restrictions on strategyproof Pareto improvements, while Chen and Möller (2024) study regret-free truth-telling for efficient stable-dominating rules in school choice. A related connection between efficiency and the best-case requirement appears in cake-cutting: Ortega and Segal-Halevi (2022, Lemma 4) show that Pareto-optimal direct-revelation mechanisms satisfy that requirement.

PSOMAS, A., AND P. VERMA (2022): “Fair and efficient allocations without obvious manipulations,” arXiv preprint arXiv:2206. p. 4

Where the paper says it

A related connection between efficiency and the best-case requirement appears in cake-cutting: Ortega and Segal-Halevi (2022, Lemma 4) show that Pareto-optimal direct-revelation mechanisms satisfy that requirement. Psomas and Verma (2022) also analyze the two comparisons separately in fair allocation of indivisible goods.

11143.

TROYAN, P., AND T. MORRILL (2020): “Obvious manipulations,” Journal of Economic Theory, 185, 104970. p. 1

Where the paper says it

We examine stable mechanisms and efficient stable-dominating mechanisms, evaluating welfare for doctors while retaining individual rationality for both doctors and hospitals. Our incentive criterion is non-obvious manipulability (NOM), introduced by Troyan and Morrill (2020).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Incorporate non-obvious manipulation (NOM) criteria into mechanism design to analyze incentive compatibility when agents are not perfectly rational about other agents' preferences, specifically by examining how contractual structure affects whether a misreport improves the worst possible outcome or the best possible outcome relative to truthful reporting.

  2. Develop AI systems capable of designing hospital-proposing deferred acceptance mechanisms that are non-obvious manipulable in both the worst and best cases when markets admit protected competing contracts, allowing for strategic manipulation under specific contractual conditions.

  3. Design efficient stable-dominating mechanisms within many-to-many matching settings that are non-obvious manipulable only in the worst case, leveraging conditions like contractual replacement with competition to secure a worst-case improvement while maintaining efficiency.

  4. Create algorithms that identify and exploit markets admitting competing contracts or contractual replacement with competition to achieve specific manipulative outcomes, such as improving both the worst and best possible results simultaneously through a single declaration.

  5. Implement models that rigorously test the distinction between stability and efficiency in allocation mechanisms, allowing the AI to determine when an efficient mechanism rules out best-case obvious manipulations while stability alone does not rule out worst-case improvements.

Abstract

We study how contractual structure affects worst-case and best-case obvious manipulation in many-to-many matching with substitutable preferences. Efficient individually rational mechanisms rule out best-case obvious manipulations on both the full substitutable domain and the unitary domain. Under simple and economically natural conditions on hospitals' choices, every stable mechanism on the full domain admits obvious manipulations in both cases; hospital-proposing deferred acceptance can admit both types even under unitary doctors' preferences. A further sufficient condition makes efficient stable-dominating mechanisms obviously manipulable in the worst case. On the unitary domain, doctor-proposing deferred acceptance is not obviously manipulable. If each doctor--hospital pair has at most one feasible contract, this positive conclusion extends to every stable-dominating mechanism.

Sources

Related papers