Monotone comparative statics under dual submodularity, with an application to aggregate deferred acceptance

arXiv:2304.12171 · econ.TH · Submitted 2023-04-24 · 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: "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".

Alfred Galichon, Yu-Wei Hsieh, Maxime Sylvestre

New York University · Amazon.com · Universite Paris-Dauphine

econ.TH

Submitted: 2023-04-24

Updated: 2026-10-28

Comments: Substantially revised version. 38 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 75/100

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…

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

Summary

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. p. 012171#pg2>. 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. p. 012171#pg4>. 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. p. 012171#pg6>.

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>. This theory is dual in a very precise sense to Topkis’ theory, and allows us to show that r(p, q¯) is weakly increasing in p and ¯q <ref:2304.12171#pg10>. The key property required for this result is that the cost function c(q) must be the convex conjugate of a submodular function, which implies but is not equivalent to, the fact that it is supermodular <ref:2304. p. 312171#pg9>.

Monotone Comparative Statics Results

The paper introduces two notions of order on functions: the Q-order and the P-order <ref:2304.12171#pg10>. The Q-order is defined such that ψ ≤Q ψ′ if for q ∈ dom(ψ), q′ ∈ dom(ψ′) and δ1 ∈ [0,(x − y)+] there is δ2 ∈ [0,(x − y)−] such that ψ (q − δ1 + δ2) + ψ' (q' + δ1 - δ2) ≤ ψ (q) + ψ' (q') <ref:2304. p. 012171#pg10>. The P-order is defined by the condition that for p ∈ dom(ϕ) and p′ ∈ dom(ϕ′), ϕ(p ∧ p′) + ϕ′(p ∨ p′) ≤ ϕ(p) + ϕ'(p') <ref:2304.12171#pg9>. Theorem 4 states that for a convex, proper, closed function c on R Z, the four assertions are equivalent <ref:2304. p. 4 p. 912171#pg10>.

Application to Aggregate Deferred Acceptance

The paper formalizes a general version of the deferred acceptance algorithm which works both in small and large markets and with deterministic and random utility <ref:2304.12171#pg6>. The algorithm involves proposal, disposal, and update phases where the mass of available offers is decreased by the mass of rejected offers <ref:2304. p. 312171#pg6>. Theorem 5 shows that if G and H are submodular welfare functions, then algorithm 1 is well defined and up to an extraction, the sequence (µP,k, τP,k, τ T,k) converges <ref:2304. p. 812171#pg21>.

Convergence in Random Utility Settings

The paper applies the procedure to the random utility setting where passenger utility is a sum of a deterministic component and a random term <ref:2304.12171#pg25>. The resulting welfare functions G (α) and H (γ) are submodular welfare functions <ref:2304. p. 012171#pg24>. As a corollary of theorem 5, it follows that a generalized equilibrium matching exists in the case of models of random utility <ref:2304. p. 012171#pg25>. The resulting demand vectors are given by an extension of relation (3.9) to a set inclusion <ref:2304. p. 012171#pg25>.

Duality and Matrons

The Q-set order is defined as B ≤Q B′ if and only if ιB ≤Q ιB′ that is, if and only if ι∗B ≤P ι∗B′ <ref:2304.12171#pg11>. This notion of matrons relates to two previous notions introduced by Murota (1998) and by Chen and Li (2022) <ref:2304. p. 812171#pg31>. The Q-order on functions can be seen as the extension of M-convexity to non polyhedral functions <ref:2304. p. 812171#pg32>. This duality between Q-order and P-order is the extension of that result to non polyhedral convex functions <ref:2304. p. 012171#pg31>. The Q-set order can also be linked to a classical notion, the notion of weak set order <ref:2304. p. 812171#pg31>.

Convergence of the Algorithm

The proof of the convergence result relies on Lemma 3, which states that (τP,k) is weakly increasing and (τT,k) is weakly decreasing <ref:2304.12171#pg35>. The final step shows that max(α − τα, γ − τγ) = 0 or equivalently min(τα, τγ) = 0. p. 4 This implies that the algorithm converges toward a generalized equilibrium matching. p. 0 p. 0 p. 0 The convergence is guaranteed because the mass of contracts that have been rejected can only increase <ref:2304. p. 9 p. 9 p. 9 p. 912171#pg21>.

Quadratic Case Interpretation

In the quadratic cost case, the fact that c∗ is submodular is equivalent to Q having nonpositive off-diagonal entries, which means Q is a Stieltjes matrix <ref:2304.12171#pg12>. This property characterizes the inverse of a Stieltjes matrix using an inequality involving supremum and infimum <ref:2304. p. 912171#pg10>. This property is exactly the exchangeability condition in the particular case of quadratic functionals <ref:2304. p. 9 p. 912171#pg10>.

Dual Version of Topkis' Theorem

Theorem 3 states that for two functions ψ and ψ′, the following two notions are equivalent: (1) ψ ≤Q ψ′ (2) For all q ∈ Q, q′ ∈ Q′ and δ1 ∈ [0,(q − q′)+] there is δ2 ∈ [0,(q − q′)−] such that q − (δ1 - δ2) ∈ Q, q' + (δ1 - δ2) ∈ Q' and ψ(q − (δ1 - δ2)) + ψ'(q' + (δ1 - δ2)) ≤ ψ(q) + ψ'(q') <ref:2304.12171#pg10>. This theorem provides a dual notion to Topkis’ theorem <ref:2304. p. 812171#pg9>. The Q-set order is defined by B ≤Q B′ if and only if ιB ≤Q ιB′ that is, if and only if ι∗B ≤P ι∗B′ <ref:2304. p. 712171#pg10>.

Matrons as Generalized Polymatroids

The paper introduces the concept of matrons as continuous generalized polymatroids <ref:2304.12171#pg33>. This representation of matrons is always possible, and given two functions g, h there is a matron associated with them if they satisfy a compatibility condition which is the paramodularity introduced by Frank (1984) <ref:2304.12171#pg33>.

The Role of Exchangeability

Proposition 1 states that if f: R Z → R is an exchangeable l.s.c. function then f is convex <ref:2304. p. 012171#pg31>. This result in particular implies that a closed exchangeable set is convex <ref:2304. p. 812171#pg31>. The Q-order can also be linked to a classical notion, the notion of weak set order <ref:2304. p. 812171#pg31>.

The Role of Submodularity

The paper shows that for any p ≤ p′ we have (c∗)′(p,.) ≤P(c∗)'(p′,.) <ref:2304.12171#pg29>. The proof of (3) =⇒ (2) relies on the fact that c∗ is submodular <ref:2304. p. 012171#pg10>.

Convergence Proof Details

The convergence proof uses the property that µ¯ −MG(α, µ¯) is increasing in the Q-order <ref:2304.12171#pg34>. The final convergence result is obtained by showing that min(τα, τγ) = 0. p. 6 This implies that the algorithm converges toward a generalized equilibrium matching. The convergence is guaranteed because the mass of contracts that have been rejected can only increase <ref:2304.12171#pg21>.

Dual Order Equivalence

The Q-order can also be linked to a classical notion, the notion of weak set order <ref:2304.12171#pg31>. The P-order, a. p. 0k.a. strong set order, is stronger than the weak order <ref:2304. p. 012171#pg31>. The Q-order is also stronger than the weak set order <ref:2304. p. 712171#pg31>.

Final Equivalence

Theorem 4 asserts that for a l.s.c. convex, proper, closed function c on R Z, the four assertions are equivalent <ref:2304.12171#pg10>. This includes the result that for all (p, q¯) ≤ (p′, q¯′) we have Π(r(p, q¯)) ≤Q Π(r(p', q¯')) <ref:2304.12171#pg29>.

Example of Quadratic Utility

In the quadratic utility example, c is exchangeable if and only if c∗ is submodular, which means S = A−1 is a Stieltjes matrix <ref:2304.12171#pg10>. The resulting demand vectors are determined by a linear complementarity problem <ref:2304.12171#pg10>. This property is exactly the exchangeability condition in the particular case of quadratic functionals <ref:2304.12171#pg10>.

General Application

The paper concludes by showing that a generalized equilibrium matching exists in the case of models of random utility <ref:2304.12171#pg25>. The resulting demand vectors are determined by a system of equations involving minimums <ref:2304.12171#pg25>. This system is equivalent to (3. p. 31).

Algorithm Convergence

The deferred acceptance algorithm that we have presented here can be seen as a continuous extension of the original deferred acceptance algorithm of Gale and Shapley (1962) <ref:2304.12171#pg21>. The convergence is guaranteed because the mass of contracts that have been rejected can only increase <ref:2304.12171#pg6>. The algorithm converges toward a generalized equilibrium matching. p. 0 This implies that the algorithm converges toward a generalized equilibrium matching. The convergence is guaranteed because the mass of contracts that have been rejected can only increase <ref:2304.12171#pg6>.

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. Submodular welfare function optimization: AI systems can solve complex resource allocation problems by using generalized equilibrium matchings with submodular welfare functions, as shown in Algorithm 1 and Theorem 5. This allows for finding stable outcomes in large markets with divisible goods, extending Gale and Shapley's algorithm to continuous quantities.

  2. Monotone comparative statics for demand: AI can predict how demand vectors change based on price increases or market availability using the monotone comparative statics result (Theorem 4). Specifically, the paper shows that if a function is exchangeable (c is exchangeable), then for all (p, q¯) ≤ (p′, q¯′) we have Π(p=p′)(r(p, q¯)) ≤Q Π(p=p′)r(p′, q¯').

  3. Convergence analysis for matching algorithms: AI can guarantee the convergence of continuous deferred acceptance algorithms in market design problems by utilizing the properties of submodular welfare functions. This ensures that the sequence of available offers decreases monotonically, leading to a generalized equilibrium matching (Algorithm 1).

  4. Handling random utility in decision-making: AI systems can model passenger and driver choices under random utility using discrete choice frameworks. The resulting demand vectors are given by an extension of relation (3.9), allowing the system to handle potential ties arising from uncertain preferences.

  5. Characterization of exchangeability: AI can classify cost or welfare functions as exchangeable by checking if their convex conjugate is submodular (c star is submodular). This provides a mathematical shortcut for determining if a function possesses the necessary properties for monotone comparative statics results.

Sources

Related papers