Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance
summary
The gist
We propose monotone comparative statics results for maximizers of submodular functions, as opposed to maximizers of supermodular functions as in the classical theory put forth by Veinott…
In short
The paper develops monotone comparative statics results for maximizers of submodular functions, contrasting with classical supermodular theory. It introduces dual notions of order (Q-order and P-order) based on matrons, which are related to set orders. These results are applied to a deferred acceptance algorithm for divisible goods, proving its convergence properties in both deterministic and random utility settings.
Key concepts
- Submodular Functions
- These functions exhibit diminishing returns; adding an item provides less marginal benefit than adding a previous one. The paper focuses on functions whose convex conjugate is submodular, which is key to the monotone comparative statics results.
- Q-order and P-order
- These are two specific mathematical orders defined on functions. The Q-order relates to a specific inequality involving small changes in inputs, while the P-order involves a condition on the sum of values at joins and meets of sets. They are shown to be equivalent for certain functions.
- Matrons
- Matrons are introduced as continuous generalized polymatroids that represent the relationship between two functions. They provide a way to characterize exchangeability and link the Q-order and P-order, extending classical notions like Murota's and Chen and Li's work.
- Deferred Acceptance Algorithm
- This is an algorithm used in market matching problems, where participants propose, dispose of offers, and update their preferences. The paper formalizes a general version of this algorithm that converges to a generalized equilibrium matching under submodular welfare functions.
Terminology used across episodes
This episode discusses
- Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance · Paper Radio
- Monotone Comparative Statics without Lattices
- Monotone Comparative Statics for Equilibrium Problems
The paper
Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance · Read on arXiv
Alfred Galichon, Yu-Wei Hsieh, Maxime Sylvestre
New York University · Amazon.com · Universite Paris-Dauphine
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: "Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance".
Warren: Here's the gist of the paper. We propose monotone comparative statics results for maximizers of submodular functions, as opposed to maximizers of supermodular functions as in the classical theory put forth by Veinott, Topkis, Milgrom, and Shannon among others <ref:2304.12171#pg2>.
Ruth: This paper introduces a monotone comparative statics result based on a natural order on matrons, which is dual in some sense to Veinott’s strong set order on sublattices <ref:2304.12171#pg4>.
Warren: As an application, we propose a deferred acceptance algorithm that operates in the case of divisible goods, and we study its convergence properties <ref:2304.12171#pg6>.
Ruth: Theoretical Framework for Submodularity The paper establishes a theory for exchangeable functions, which are defined as the convex conjugates of submodular functions, and provides a monotone comparative statics theory for them <ref:2304.12171#pg5>.
Title and authors: Ruth: So this paper is called "Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance". It sounds really technical for a title. Warren Yeah, it's definitely deep stuff. It basically tackles how you can get monotone comparative statics results for maximizers of submodular functions instead of the supermodular ones that Veinott and others worked on before <ref:2304.12171#pg2>. Iris It’s interesting because it's setting up a dual structure, something that relates to Veinott’s strong set order on sublattices <ref:2304.12171#pg4>. Ruth Exactly. They introduce a new structure they call matrons, which is described as being dual to those sublattices, and this order on matrons is what they use for their comparative statics results <ref:2304.12171#pg5>.
Warren: And then they use that order on matrons to propose a deferred acceptance algorithm, specifically one that works with divisible goods, and they study how well it converges <ref:2304.12171#pg6>. Ruth That application part is what makes it practical for real-world problems in markets. It takes this abstract comparison between functions and applies it to a concrete matching problem.
Iris: From my econometric side, I’m interested in how they define that dual relationship because the theory of exchangeable functions, which are defined as the convex conjugates of submodular functions, allows them to show that r(p,) is weakly increasing in both p and <ref:2304.12171#pg10>. Warren That monotonicity is key because it’s what drives the convergence of their algorithm later on.
Ruth: Right. So, to summarize this first part, they’re moving away from supermodular maximizers to submodular ones, using a new dual order on matrons, and applying that structure to an algorithm for divisible goods <ref:2304.12171#pg1>. It sets up the foundation for their main result.
Warren: And it immediately links this structure back to how demand or supply changes when alternatives become more or less available, which is the core idea of substitutability <ref:2304.12171#pg3>. That’s where things get interesting for us.
The paper's summary: Ruth: Moving into the summary of this paper, it lays out a theory for exchangeable functions, which are defined as the convex conjugates of submodular functions <ref:2304.12171#pg5>. Iris And this theory is stated to be dual in a very precise sense to Topkis’ theory <ref:2304.12171#pg9>. Ruth That duality allows them to show that r(p,) is weakly increasing in p and <ref:2304.12171#pg10>. Warren So, if we take the cost function c(q) to be the convex conjugate of a submodular function, that implies it’s supermodular in some sense <ref:2304.12171#pg9>. Iris That's a big distinction because it’s not strictly equivalent, but it shows a necessary condition for their results.
Ruth: The paper introduces two notions of order on functions, the Q-order and the P-order <ref:2304.12171#pg10>. Warren I remember the Q-order being defined by this specific inequality involving delta one and delta two which looks like it describes how changes in one function relate to changes in the other <ref:2304.12171#pg10>.
Iris: And then they have the P-order, which is defined by phi(p p') + phi'(p p') at most phi(p) + phi'(p') <ref:two thousand three hundred four point one two one seven one#pg9. Ruth Theorem four actually says that for a convex, proper, closed function c on R Z, these four assertions—the Q-order and the P-order—are equivalent <ref:2304.12171#pg10>.
Warren: So they’re essentially saying that you can use either of these orders, because they are equivalent for this type of cost function <ref:2304.12171#pg9>. Ruth That equivalence is powerful because it means the Q-order and P-order are just different ways of looking at the same underlying structure.
Iris: It suggests that the Q-order is essentially an extension of M♮-convexity to non polyhedral functions <ref:2304.12171#pg32>. Warren That’s what I thought. So they are extending known concepts into less structured mathematical spaces.
Ruth: And this is where the structure becomes really interesting because it connects back to previous notions like Murota’s and Chen and Li’s work on matrons <ref:2304.12171#pg31>. Iris It seems like they are building on a long line of ideas about these structures in combinatorial optimization.
Warren: It makes the connection between the Q-order and P-order explicit, showing that they are dual concepts <ref:2304.12171#pg31>. So it’s not just two separate definitions, but a true duality in action.
The paper's improvements: Ruth: Now let’s talk about the improvements suggested by this paper itself. The main improvement is formalizing the notion of matrons as continuous generalized polymatroids <ref:2304.12171#pg33>. Iris That representation is always possible, and it requires a compatibility condition called paramodularity introduced by Frank in one thousand nine hundred eighty-four <ref:2304.12171#pg33>. Ruth So, if you have two functions g and h, they can be associated with a matron if they satisfy that compatibility condition <ref:two thousand three hundred four point one two one seven one#pg33. Warren That’s the engineering part—the idea that you can always find this representation, provided you have those functions in mind.
Iris: But it also connects to exchangeability itself because Proposition one states that if f is an exchangeable l <ref:2304.12171#pg2>.s.c function, then f must be convex <ref:two thousand three hundred four point one two one seven one#pg31. Ruth So, this means a lot for classifying functions—if you know the function is exchangeable, you automatically know it’s convex <ref:two thousand three hundred four point one two one seven one#pg31.
Warren: And then they link the Q-order to a classical notion called weak set order <ref:two thousand three hundred four point one two one seven one#pg31. Iris But they clarify that the P-order, which is also called the strong set order, is stronger than the weak order <ref:two thousand three hundred four point one two one seven one#pg31. Ruth So this hierarchy of orders helps us understand exactly how much structure we have to work with.
Warren: And it ties back to the quadratic case interpretation where submodularity means Q having nonpositive off-diagonal entries, which means Q is a Stieltjes matrix <ref:2304.12171#pg12>. Iris That property exactly characterizes the inverse of a Stieltjes matrix using an inequality involving supremum and infimum <ref:two thousand three hundred four point one two one seven one#pg34.
Conclusion: Ruth: So, wrapping up on this paper "Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance", the main result is that they established monotone comparative statics results for maximizers of submodular functions <ref:2304.12171#pg5>. Iris And their application to aggregate deferred acceptance shows that if G and H are submodular welfare functions, then algorithm one is well defined and up to an extraction, the sequence (mu P,k, tau P,k, tau T,k) converges <ref:2304.12171#pg21>. Warren That convergence means the process settles down toward a generalized equilibrium matching <ref:two thousand three hundred four point one two one seven one#pg6.
Ruth: It implies that for divisible goods, you can use this algorithm to find stable outcomes even when dealing with random utility <ref:two thousand three hundred four point one two one seven one#pg6. Iris And in the random utility setting, the resulting welfare functions G(alpha) and H(gamma) are submodular welfare functions <ref:2304.12171#pg24>. Warren So, as a corollary of theorem five this means that a generalized equilibrium matching exists in models involving random utility <ref:two thousand three hundred four point one two one seven one#pg25.
Ruth: The demand vectors are given by an extension of relation (three point nine) to a set inclusion <ref:2304.12171#pg25>. Iris That’s the final output, which is how we determine what happens next in the system.
Warren: To wrap up, this paper "Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance", it gives us a method for finding generalized equilibrium matchings <ref:2304.12171#pg6>. Ruth It’s a method that relies on the properties of submodular functions, and it shows how these properties translate into guaranteed convergence in the algorithm.
Iris: I just want to say that if you think about it, the whole point is showing how exchangeability translates into convexity <ref:two thousand three hundred four point one two one seven one#pg31.
Warren: It’s a solid piece of work that links structural properties of functions to algorithmic convergence in matching problems, and we get a method for finding generalized equilibrium matchings via the paper "Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance".
More episodes
- Daily Summary for 2026-11-19
- 2608.21274-Recommendation Quality and the Concentration of Consumption: Experimental Evidence from Netflix
- 2408.02757-A nonparametric test for diurnal variation in spot correlation processes
- 2306.16393-High-Dimensional Canonical Correlation Analysis
- 2605.17299-Geometric Brownian motion with intermittent entries and exits
- 2607.04753-Fooling Yourself: how narratives shape beliefs
- 2408.14671-Inference on Treatment Effects with Repeatedly Mismeasured High-Dimensional Controls
- 2201.06898-Difference-in-Differences Estimators for Treatments Continuously Distributed at Every Period
- 2501.15307-Influence Functions: A Unified Differentiation-Based Framework
- The day in conversation for 2026-11-19