REVIEW 3 major objections 3 minor 35 references
Revealed Preferences for Matching with Contracts
T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves that stable agreements always exist in many-to-many matching with contracts when both sides are represented by coherent choice functions, and that a simple iterative algorithm produces the stable agreement that side 1…
desk verdict Solid core result on stable agreements under coherent choice functions, with a scope warning about Substitutes and an unformalized competitive-equilibrium comparison. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Coherent choice functions: a function $f:2^X\to 2^X$ with $f(A)\subseteq A$ (Contraction), with $f(A-\{x\})\subseteq f(A)$ whenever $x$ is rejected from $A$ (Irrelevance of Rejected Contracts), and with $x\in f(A)$ implying $x\in f(B)$ for $B\subseteq A$ (Substitutes). The path-independence lemma shows these three conditions are equivalent to $f(A\cup B)=f(f(A)\cup f(B))$, and that identity is the engine of the proofs. The induced revealed-preference preorder, $B\leq_f A$ iff $f(A\cup B)=f(A)$, turns stable agreements into a partially ordered set and makes the algorithm's iterations monotone: side 2 sees successively better offers, while contracts rejected once can never become acceptable again. The iterative equation $Z_{j+1}=(Z_j-f_1(Z_j))\cup f_2(f_1(Z_j))$ is the computational core: side 1 proposes $f_1(Z_j)$, side 2 accepts $f_2(f_1(Z_j))$, and rejected contracts stay on the table. For the lattice part, the operator $I_f(A)=A\cup\{x\notin A: x\notin f(\{x\}\cup A)\}$ translates the revealed preference order into set containment and builds the meet of two stable agreements.
What would settle it
Exhibit one finite contract set $X$ and two choice functions $f_1, f_2$ that each satisfy all three coherence conditions of Definition 1 but for which no set $A$ satisfies $f_1(A)=f_2(A)=A$ and blocks every singleton addition accepted by both sides; Appendix C offers a near-miss example, but one of its functions fails coherence, so a genuine such pair would refute Theorem 3. Separately, build an m-economy satisfying no-shortage and Definition 10 with a stable agreement containing two same-template contracts whose prices have a third price level strictly between them, which Theorem 5 says cannot happen.
Extended reading notes
Core claim
At the center is an agreement problem: two sides, each with a coherent choice function $f_1, f_2$ over a finite contract set $X$. Agreements are sets $A$ with $f_1(A)=f_2(A)=A$; stable agreements additionally block every single-contract addition that both sides would accept. The main theorem says stable agreements always exist. Starting at $Z_0=X$ and repeatedly applying $Z_{j+1}=(Z_j-f_1(Z_j))\cup f_2(f_1(Z_j))$, the process stabilizes in at most $|X|$ steps, and $S=f_1(Z_f)$ is a stable agreement. Moreover every stable agreement $A$ satisfies $A\leq_1 S$ and $S\leq_2 A$, so $S$ is side 1's best and side 2's worst stable agreement. Running the same process on the intersection $W=I_1(B)\cap I_1(C)$ yields the greatest lower bound of any two stable agreements $B$ and $C$, and the order-dual construction yields a least upper bound, so the stable agreements form a lattice. This framework subsumes classical deferred-acceptance matching and earlier one-to-many contract matching when preferences are expressed as coherent choice functions. In m-economies that satisfy no-shortage and money-monotonicity conditions, every stable agreement obeys the law of two prices: two contracts with the same template cannot have a third price level strictly between their prices.
Load-bearing premise
The load-bearing premise is that both sides' preference rules satisfy the Substitutes condition—a contract chosen from a large menu remains chosen from every smaller menu—so no contract can make another more attractive; the paper itself notes that producers with complementary outputs or economies of scale violate this, and then the existence, optimality, and lattice theorems no longer apply.
Editorial extensions
If this is right
- Stable agreements exist for every many-to-many matching market in which both sides' collective preferences are coherent, without special assumptions restricting the number of contracts per agent.
- The side-1-optimal stable agreement is computed in at most $|X|$ rounds, each round requiring only the two choice functions' answers, so the algorithm is polynomial in the number of contracts.
- The set of stable agreements carries two inverse partial orders, $\leq_1$ and $\leq_2$, and forms a lattice; the meet of two stable agreements is found by running the same algorithm on $I_1(B)\cap I_1(C)$.
- In money economies satisfying no-shortage and price-monotonicity, every stable agreement assigns nearly uniform prices: two contracts with the same template cannot have a price level strictly between their prices.
- Any competitive equilibrium is a stable agreement, but stable agreements can exist in markets that have no competitive equilibrium, so stable agreements form a broader solution concept.
Reading between the lines
- If the lattice result transfers to mechanism design, one could define compromise stable agreements by taking lattice medians between the side-1-best and side-2-best outcomes; the paper does not discuss such a construction.
- The law of two prices offers a market diagnostic: observing the same template traded at three distinct price levels in a market without shortages would indicate that one of the coherence or money-monotonicity assumptions fails in the field.
- Because the algorithm only needs choice queries, it could in principle run on preferences learned from behavior rather than from utility functions; the paper frames the conceptual possibility but does not test implementations.
- For markets with complementarities, such as couples applying to residency programs, the failure mode is not a slower algorithm but potential nonexistence of stable agreements, which sharpens the reason substitutes assumptions underpin many market-design platforms.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a revealed-preference framework for many-to-many matching with contracts. Preferences are represented by coherent choice functions satisfying Contraction, Irrelevance of Rejected Contracts, and Substitutes. After aggregating individual preferences on each side into a collective choice function, the two-sided matching problem becomes an agreement problem between two choice functions f1 and f2. The paper defines agreements, stable sets, and stable agreements, and studies the iterative algorithm Z_{j+1} = (Z_j - f1(Z_j)) ∪ f2(f1(Z_j)). The main results are that the terminal set S = f1(Z_f) is a stable agreement, that S is the best stable agreement for side 1 and worst for side 2, that stable agreements form a lattice under the induced partial orders, and that the algorithm runs in at most |X| iterations. A final section introduces money, templates, and prices, and proves a 'law of two prices' under a no-shortage assumption. The abstract claims that stable agreements generalize competitive equilibria and exist in many situations where competitive equilibria do not.
Significance. If the advertised scope were fully supported, the paper would provide a clean unification of Gale-Shapley, Kelso-Crawford, Hatfield-Milgrom, and related results in a purely choice-theoretic setting. The proof of Theorems 3 and 4 is detailed and I did not find an internal contradiction in the central derivation; the algorithm's linear termination bound is genuine, and the lattice proof is a substantive contribution. The main strike against the paper is that the existence and lattice theorems are conditional on the Substitutes clause of coherence, and the paper itself identifies important economic environments, such as couples seeking complementary positions and producers with complementary outputs or economies of scale, where that clause fails. Appendix C shows the existence theorem is false without it. The advertised claims about general two-sided markets and about competitive equilibria therefore outrun the theorems as written. This is a scope problem rather than a flaw in the conditional mathematics, so it is fixable by a careful revision of the claims, but it currently affects the central message.
major comments (3)
- [Section 9.1 and Appendix C] The existence theorem's domain is narrower than the paper's advertised scope. Theorem 3 relies on coherence of both choice functions, and the Substitutes clause is used in nearly every lemma of Section 8 (e.g., Lemmas 3, 5, 7, 12, and 17-21). Appendix C gives two choice functions, one failing only Substitutes, for which no stable agreement exists. Section 9.1 explicitly says that producers with complementary outputs or economies of scale have non-coherent choice functions, and Section 5.2 says a couple's collective choice function does not satisfy Substitutes. Therefore the abstract's claim that stable agreements exist 'in many situations' and the framing of the framework as covering general two-sided markets are not supported by the theorems; the claims should be restricted to coherent preferences, with the known failures stated up front.
- [Sections 9.2 and 11] The claim that stable agreements are 'more general than competitive equilibria' is not evaluable as written. Competitive equilibrium is never defined in the revealed-preference framework; Section 9.2 states that classical solution concepts such as competitive equilibrium 'cannot be defined in a straightforward manner' in this setting. The conclusion's assertion that 'if there are competitive equilibria they are in this set' is stated without a theorem or proof. Please either provide a formal definition of the comparison concept and prove the inclusion, or remove or carefully caveat the competitive-equilibrium claims from the abstract and conclusion.
- [Definition 9(2) and Theorem 5] The law of two prices depends crucially on the no-shortage assumption, which is not satisfied by the natural finite encoding X = I × J × T × P. Definition 9(2) requires that for every contract x in a stable agreement A there is a distinct contract y outside A with the same i, j, t, and p. In the standard contract set with one contract per quadruple, no such y exists once the unique contract is realized. The theorem therefore applies only to economies with duplicate contracts, and the 'almost one price law' is not a consequence of the matching model developed in Sections 5-8. This restriction should be stated as an explicit hypothesis of the market interpretation, and the conclusion should not present the law as a general property of stable agreements.
minor comments (3)
- [Section 5.2] In the proof that the marriage choice function satisfies Substitutes, the expression 'A ⊆ B ⊆ Mi' uses the undefined symbol Mi; it should presumably be Xi.
- [Appendix C] The example says that f2 satisfies 'path equivalence,' but Section 8.1.1 defines 'Path Independence'; please use consistent terminology.
- [Theorem 2] In the proof of Theorem 2, the line 'fi(A ∪ B) = f(B) = B' should use fi(B) rather than f(B), and it would help to derive the equality explicitly from the two assumed inequalities.
Circularity Check
No significant circularity: the existence and lattice theorems are proved constructively from the coherence assumptions, and self-citations are only background.
full rationale
The derivation chain is self-contained. The algorithm of Equation (2) is defined directly from the two choice functions f1 and f2, with Z0 = X, and Lemma 1 proves termination from finiteness. The set S = f1(Zf) is then shown to be an agreement in Lemma 14 and a stable set in Lemma 18 using only the coherence axioms, Lemmas 15-17, and the concrete iterative construction. The extremal claim A <=1 S and S <=2 A in Theorem 3 is derived from Lemma 21, which is proved by induction on Zi using Lemma 20, not by assuming that a stable agreement exists or by fitting S to any target. The lattice result in Theorem 4 constructs SW from WB^C = I1(B) ∩ I1(C) by running the same iteration on that set and proves stability of SW without importing the target conclusion. The self-citations, e.g., to [19], [20], [21], and [22], supply background equivalences and related frameworks but are not used as the proof of any central theorem; the relevant lemmas cite classical results such as Plott's Path Independence and give proofs. No fitted parameter is renamed as a prediction, and no definition of the solution concept assumes the existence or optimality of the output. The paper's later conditions, such as no-shortage and the money-economy assumptions, are additional hypotheses for the price result and are not smuggled versions of the conclusion. Therefore no circular step is present.
Assumptions & free parameters
assumptions (5)
- domain assumption Both parties have preferences representable by coherent choice functions satisfying Contraction, IRC, and Substitutes (Definition 1).
- domain assumption Collective side preference is the union of individual choices over the contracts of that side's agents (Equation 1), a no-externality assumption.
- domain assumption The contract set X is finite.
- domain assumption For money economies, no-shortage of contracts (Definition 9) and monotone price preferences (Definition 10) hold.
- standard math Plott's Path Independence theorem (Lemma 7) and the IRC/Local Monotonicity equivalence (Lemma 2) are accepted as proven background.
Cite this review
Pith. "Pith review of Revealed Preferences for Matching with Contracts." pith.science (2026). https://pith.science/paper/SDIW2OXJ
@misc{pith2026190808823,
author = {Pith},
title = {Pith review of: Revealed Preferences for Matching with Contracts},
year = {2026},
howpublished = {\url{https://pith.science/paper/SDIW2OXJ}},
note = {Machine review of arXiv:1908.08823}
}
read the original abstract
Many-to-many matching with contracts is studied in the framework of revealed preferences. All preferences are described by choice functions that satisfy natural conditions. Under a no-externality assumption individual preferences can be aggregated into a single choice function expressing a collective preference. In this framework, a two-sided matching problem may be described as an agreement problem between two parties: the two parties must find a stable agreement, i.e., a set of contracts from which no party will want to take away any contract and to which the two parties cannot agree to add any contract. On such stable agreements each party's preference relation is a partial order and the two parties have inverse preferences. An algorithm is presented that generalizes algorithms previously proposed in less general situations. This algorithm provides a stable agreement that is preferred to all stable agreements by one of the parties and therefore less preferred than all stable agreements by the other party. The number of steps of the algorithm is linear in the size of the set of contracts, i.e., polynomial in the size of the problem. The algorithm provides a proof that stable agreements form a lattice under the two inverse preference relations. Under additional assumptions on the role of money in preferences, agreement problems can describe general two-sided markets in which goods are exchanged for money. Stable agreements provide a solution concept, including prices, that is more general than competitive equilibria. They satisfy an almost one price law for identical items.
Reference graph
Works this paper leans on
-
[9]
Christopher P. Chambers and M. Bumin Yenmez. Choice and match ing. American Economic Journal: Microeconomics , 9(3):126–147, August 2017
work page 2017
-
[1]
M. A. Aizerman. New problems in the general choice theory: Revie w of a research trend. Social Choice and Welfare , 2:235–282, 1985
work page 1985
-
[2]
M. A. Aizerman and A. V. Malishevski. General theory of best var iants choice: Some aspects. IEEE Transactions on Automatic Control , AC- 26:1030–1040, 1981
work page 1981
-
[3]
Stable schedule matching under revea led preference
Ahmet Alkan and David Gale. Stable schedule matching under revea led preference. Journal of Economic Theory , 112(2):289–306, October 2003
work page 2003
-
[4]
Kenneth J. Arrow. Rational choice functions and orderings. Economica, 26:121–127, 1959
work page 1959
-
[5]
Matching with contracts: T he critical role of irrelevance of rejected contracts
Orhan Ayg¨ un and Tayfun S¨ onmez. Matching with contracts: T he critical role of irrelevance of rejected contracts. Boston College Working Papers in Economics 804, Boston College Department of Economics, May 2012
work page 2012
-
[6]
Understanding preferenc es: ”de- mand types”, and the existence of equilibrium with indivisibilities
Elizabeth Baldwin and Paul Klemperer. Understanding preferenc es: ”de- mand types”, and the existence of equilibrium with indivisibilities. Econo- metrica, 87(3):867–932, May 2019
work page 2019
-
[7]
C. Blair. The lattice structure of the set of stable matchings with multiple partners. Mathematics of Operations Research , 13:619–628, 1988. 29
work page 1988
Show all 35 references
-
[8]
R e- designing the israeli medical internship match
Slava Bronfman, Noga Alon, Avinatan Hassidim, and Assaf Romm. R e- designing the israeli medical internship match. In EC ’15: Proceed- ings of the Sixteenth ACM Conference on Economics and Comput a- tion, pages 753–754. ACM, June 2015. Electronic copy available at: http://ssrn...
2015
-
[10]
Rational selection of decision functions
Herman Chernoff. Rational selection of decision functions. Econometrica, 26:121–127, 1954
1954
-
[11]
A theory of stability in man y-to- many matching markets
Federico Echenique and Jorge Oviedo. A theory of stability in man y-to- many matching markets. Theoretical Economics, 1:233–273, 2006
2006
-
[12]
College admissions and the stability of marriage
David Gale and Lloyd Shapley. College admissions and the stability of marriage. American Mathematical Monthly , 69:9–15, 1962
1962
-
[13]
Matching in network s with bilateral contracts
John William Hatfield and Scott Duke Kominers. Matching in network s with bilateral contracts. American Economic Journal: Microeconomics , 4(1):176–208, 2012
2012
-
[14]
Contract design an d sta- bility in many-to-many matching
John William Hatfield and Scott Duke Kominers. Contract design an d sta- bility in many-to-many matching. Games and Economic Behavior , 101:78– 97, 2017
2017
-
[15]
Full substitutability
John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Mic hael Ostrovsky, and Alexander Westkamp. Full substitutability. Theoretical Economics. to appear
-
[16]
John William Hatfield and Paul R. Milgrom. Matching with contracts. The American Economic Review , 95(4):913–935, September 2005
2005
-
[17]
Kelso Jr
Alexander S. Kelso Jr. and Vincent P. Crawford. Job matching, coalition formation and gross substitutes. Econometrica, 50:1483–1504, 1982
1982
-
[18]
Donald E. Knuth. Mariages Stables et leurs relations avec d’autres problmes combinatoires. Les Presses de l’Universit de Montral, 1976
1976
-
[19]
Nonmono tonic reasoning, preferential models and cumulative logics
Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmono tonic reasoning, preferential models and cumulative logics. Artificial Intelligence , 44(1–2):167–207, July 1990. CoRR: cs.AI/0202021
1990
-
[20]
Combinatoria l auc- tions with decreasing marginal utilities
Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatoria l auc- tions with decreasing marginal utilities. Games and Economic Behav- ior, 55(2):270–296, 2006. A preliminary version appeared in ACM EC’01, Tampa, Oct. 2001
2006
-
[21]
Nonmonotonic logics and semantics
Daniel Lehmann. Nonmonotonic logics and semantics. Journal of Logic and Computation , 11(2):229–256, 2001. CoRR: cs.AI/0202018. 30
2001
- [22]
-
[23]
Gross substitutability: An algorithmic surve y
Renato Paes Leme. Gross substitutability: An algorithmic surve y. Games and Economic Behavior , 106(C):294–316, 2017
2017
-
[24]
The communication requirements of effi cient al- locations and supporting prices
Noam Nisan and Ilya Segal. The communication requirements of effi cient al- locations and supporting prices. Journal of Economic Theory , 129(1):192– 224, 2006. https://doi.org/10.1016/j.jet.2004.10.007
2006 doi
-
[25]
Charles R. Plott. Path independence, rationality and social cho ice. Econo- metrica, 41(6):1075–1091, 1973
1973
-
[26]
Alvin E. Roth. The evolution of the labor market for medical inter ns and residents: A case study in game theory. Journal of Political Economy , 92(6):991–1016, December 1984
1984
-
[27]
Alvin E. Roth. Stability and polarization of interests in job matchin g. Econometrica, 52:47–57, 1984
1984
-
[28]
Alvin E. Roth. The college admissions problem is not equivalent to th e marriage problem. Journal of Economic Theory , 36:277–288, 1985
1985
-
[29]
Alvin E. Roth. Conflict and coincidence of interest in job matching : Some new results and open questions. Mathematics of Operation Research , 10(3):379–389, August 1985
1985
-
[30]
Roth and Elliott Peranson
Alvin E. Roth and Elliott Peranson. The redesign of the matching m ar- ket for american physicians: Some engineering aspects of economic design. American Economic Review , 89:748–780, 1999
1999
-
[31]
Samuelson
Paul A. Samuelson. A note on the pure theory of consumers’ b ehaviour. Economica. New Series , 17(5):61–71, February 1938
1938
-
[32]
Samuelson
Paul A. Samuelson. Consumption theory in terms of revealed pr eference. Economica. New Series , 60(15):243–253, November 1948
1948
-
[33]
Schervish, and Joseph B
Teddy Seidenfeld, Mark J. Schervish, and Joseph B. Kadane. C oherent choice functions under uncertainty. Synthese, 172(1):157–176, January 2010
2010
-
[34]
Amartya K. Sen. Collective Choice and Social Welfare . Holden-Day, San Francisco, CA, 1970
1970
-
[35]
Amartya K. Sen. Choice functions and revealed preference. The Review of Economic Studies , 38(3):307–317, July 1971. 31 A V-substitutes valuations and coherent func- tions We shall show that any valuation that is v-substitutes yields a coher ent choice function. We consider th...
1971
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.