Pith. sign in

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 →

arxiv 1908.08823 v2 pith:SDIW2OXJ submitted 2019-08-23 cs.GT econ.TH

classification cs.GTecon.TH MSC 91B6891B2691B08
keywords matchingwithcontractschoicefunctionssubstitutesstableagreementsrevealedpreferenceslatticeofmatchingslawonepricemany-to-many
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a unified revealed-preference theory of many-to-many matching with contracts. It claims that if each side's preferences are encoded by a coherent choice function—a rule that picks a preferred subset from any menu and satisfies contraction, irrelevance of rejected contracts, and substitutes—then a stable agreement always exists. A simple iteration starting from all contracts computes the stable agreement that side 1 likes at least as much as any other stable agreement, and side 2 likes least; the same iteration proves that stable agreements form a lattice under the two preference orders. Because the contract set shrinks at every round, the algorithm terminates in at most as many steps as there are contracts. For markets with money, the paper derives a law of two prices: identical goods in any stable agreement can differ in price only by adjacent price levels.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [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.
  2. [Appendix C] The example says that f2 satisfies 'path equivalence,' but Section 8.1.1 defines 'Path Independence'; please use consistent terminology.
  3. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

The central results depend on three modeling assumptions rather than fitted parameters: coherent choice functions, no-externality aggregation, and finiteness. The money-economy section adds no-shortage and money-monotonicity. No free parameters or invented entities appear; this is a pure theorem paper.

assumptions (5)
  • domain assumption Both parties have preferences representable by coherent choice functions satisfying Contraction, IRC, and Substitutes (Definition 1).
    This is the main modeling premise. Theorems 1, 3 and 4 all invoke coherence; Appendix C shows a stable agreement can fail when a choice function violates Substitutes.
  • 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.
    Section 5.1 assumes each agent only cares about contracts in which they appear. Without this, a many-to-many market cannot be collapsed into one choice function per side.
  • domain assumption The contract set X is finite.
    Section 4.1 fixes a finite X; finiteness is used for termination of the iterative algorithm in Lemma 1 and for the lattice arguments.
  • domain assumption For money economies, no-shortage of contracts (Definition 9) and monotone price preferences (Definition 10) hold.
    These assumptions appear only in Section 9 but are essential to the law of two prices: no-shortage manufactures contracts at intermediate prices, and money-monotonicity makes both sides accept them.
  • standard math Plott's Path Independence theorem (Lemma 7) and the IRC/Local Monotonicity equivalence (Lemma 2) are accepted as proven background.
    The paper supplies proofs of both, so they are standard imports rather than ad hoc assumptions; they are used throughout Section 8.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 33 canonical work pages

  1. [9]

    Chambers and M

    Christopher P. Chambers and M. Bumin Yenmez. Choice and match ing. American Economic Journal: Microeconomics , 9(3):126–147, August 2017

  2. [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

  3. [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

  4. [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

  5. [4]

    Kenneth J. Arrow. Rational choice functions and orderings. Economica, 26:121–127, 1959

  6. [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

  7. [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

  8. [7]

    C. Blair. The lattice structure of the set of stable matchings with multiple partners. Mathematics of Operations Research , 13:619–628, 1988. 29

Show all 35 references
  1. [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...

  2. [10]

    Rational selection of decision functions

    Herman Chernoff. Rational selection of decision functions. Econometrica, 26:121–127, 1954

  3. [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

  4. [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

  5. [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

  6. [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

  7. [15]

    Full substitutability

    John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Mic hael Ostrovsky, and Alexander Westkamp. Full substitutability. Theoretical Economics. to appear

  8. [16]

    John William Hatfield and Paul R. Milgrom. Matching with contracts. The American Economic Review , 95(4):913–935, September 2005

  9. [17]

    Kelso Jr

    Alexander S. Kelso Jr. and Vincent P. Crawford. Job matching, coalition formation and gross substitutes. Econometrica, 50:1483–1504, 1982

  10. [18]

    Donald E. Knuth. Mariages Stables et leurs relations avec d’autres problmes combinatoires. Les Presses de l’Universit de Montral, 1976

  11. [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

  12. [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

  13. [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

  14. [22]

    Ultra valuations

    Daniel Lehmann. Ultra valuations. arXiv:1712.04236, Septembe r 2018

  15. [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

  16. [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

  17. [25]

    Charles R. Plott. Path independence, rationality and social cho ice. Econo- metrica, 41(6):1075–1091, 1973

  18. [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

  19. [27]

    Alvin E. Roth. Stability and polarization of interests in job matchin g. Econometrica, 52:47–57, 1984

  20. [28]

    Alvin E. Roth. The college admissions problem is not equivalent to th e marriage problem. Journal of Economic Theory , 36:277–288, 1985

  21. [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

  22. [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

  23. [31]

    Samuelson

    Paul A. Samuelson. A note on the pure theory of consumers’ b ehaviour. Economica. New Series , 17(5):61–71, February 1938

  24. [32]

    Samuelson

    Paul A. Samuelson. Consumption theory in terms of revealed pr eference. Economica. New Series , 60(15):243–253, November 1948

  25. [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

  26. [34]

    Amartya K. Sen. Collective Choice and Social Welfare . Holden-Day, San Francisco, CA, 1970

  27. [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...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.