Supermodularity and complementarity in economics: an elementary survey.

• Author: Amir, Rabah

1. Introduction

   This survey provides an overview of the theory of supermodular optimization and games, with a marked emphasis on accessibility, for as broad an audience as possible. Supermodular optimization is a new methodology for conducting comparative statics or sensitivity analysis, that is, it determines how changes in exogenous parameters affect endogenous variables in optimizing models. (1) As such, the use of this methodology is pervasive in economics, and the conclusions thereby derived are often one of the main motivations behind the construction of a model. The main characteristic of this methodology is that it relies essentially oil critical assumptions for the desired monotonicity conclusions and dispenses with superfluous assumptions that are often imposed only by the use of the classical method, which is based oil the Implicit Function Theorem and includes smoothness, interiority, and concavity. The main insight is indeed quite simple. If, in a maximization problem, the objective reflects a complementarity between an endogenous variable and an exogenous parameter, in the sense that having more of one increases the marginal return to having more of the other, then the optimal value of the former will be increasing in the latter. In the case of multiple endogenous variables, then all of them must also be complements in order to guarantee that their increases are mutually reinforcing. This conclusion follows directly from the underlying complementarity relationship and is thus independent of the aforementioned superfluous assumptions. It thus holds even if there are multiple optimal values of the endogenous variable(s).

   Is a new look at complementarity needed? Topkis (1998, p. 3) quotes Samuelson (1947) as asserting the following: "In my opinion the problem of complementarity has received more attention than is merited by its intrinsic importance," only for Samuelson to correct himself later in Samuelson (1974) by adding "The time is ripe for a fresh modern look at the concept of complementarity. The last word has not yet been said on this ancient preoccupation of literary and mathematical economists. The simplest things are often the most complicated to understand fully." It is hoped that this survey will convince the reader of the correctness of Samuelson's latter view.

   Another major methodological breakthrough due to this framework of analysis is the theory of supermodular games, better known in economics as games with strategic complementarities. The main characteristic of these games is that they have monotonic reaction curves, reflecting a complementarity relationship between own actions and rivals' actions. As a consequence of Tarski's fixed-point theorem, the latter property guarantees the existence of pure-strategy Nash equilibrium points. Because the latter type of equilibrium is most often the desired concept in economic models, the scope of game-theoretic modeling in economics is thereby substantially enlarged. Another key observation in this respect is that supermodularity is often the relevant notion in the comparative statics of Nash equilibrium points. Furthermore, it will be argued that supermodular games are more conducive to predictable comparative statics properties than games with continuous best-responses, the latter being the other class of games with pure-strategy Nash equilibrium points.

   While maintaining rigor in the presentation of the concepts and proofs, some informal aspects in the exposition are adopted, whenever they result in substantial simplification. The major step in achieving such an accessible exposition lies in the restriction of the theory to the case of real action and parameter spaces. While this reduces the scope of the theory and masks its striking elegance, it does, nevertheless, cover most economic applications of broad interest. The main results from the theory of supermodular games are also, thereby, simplified and more accessible. The multidimensional Euclidean framework is presented in summary form at the end of the survey. General comparative comments are given at various points to provide some sense of the scope, usefulness, and limitations of this theory from an applications-oriented perspective. A number of well-known economic applications are covered, including monopoly theory, Cournot and Bertrand competition, a two-stage R&D model, search, matching, and growth theory. Some of these are covered both with the cardinal and the ordinal notions of complementarity in order to provide some comparative perspective. Various practical tricks in fully exploiting the benefits of this theory are also illustrated via some of the applications presented.

   This survey is organized as follows. The next section presents the simplified version of Topkis's Monotonicity Theorem with real decision and parameter spaces and compares this result with the standard method. Section 3 introduces games with strategic complementarities and their key properties, including the comparative statics of their equilibria. Section 4 presents the ordinal complementarity conditions and Milgrom-Shannon's Theorem. The (Euclidean) multidimensional case forms Section 5. Concluding remarks and other aspects of the theory, not covered in this survey, are summarized in Section 6. Last but not least, several illustrative applications and comparative comments are presented throughout to bring out the added value of this new approach in an accessible manner.

2. Monotone Comparative Statics

   This section provides a simplified exposition of Topkis's (1978) framework in the special case where both the parameter and the decision sets are subsets of the reals. A number of economic applications are then presented to illustrate, in very familiar settings, the relevance and the scope of application of this simplified version of the general theory.

   Topkis's Monotonicity Theorem: The Scalar Case

   Topkis considered the following parameterized family of constrained optimization problems, where [A.sub.s] [subset] A, with the intent of deriving sufficient conditions on the objective and constraint set that yield monotone optimal solutions:

   (1) [a.sub.*](s) = arg max{F(s,a) :a [member of] A,}. (1) We take the parameter and action sets, S and A, to be subsets of R, and A, a correspondence from S to A, with [A.sub.s] being the set of feasible actions when the parameter is s.

   A function F:S X A [right arrow] R has (strictly) increasing differences in (s, a) if

   (2) F(s',a') F(s',a)(>) [greater than or equal to] F(s, a')- F(s, a). [for all] a' > a.s' > s,

   or, in other words, if the difference F(., a')--F(*, a) is an increasing function. (2) This property does not discriminate between the two variables in that Equation 2 is clearly equivalent to

   (3) F(s',a')--F(s,a')(>) [greater than or equal to] F(s',a)--F(s',a), [for all] a' > a, s' > s.

   For functions on [R.sup.2], increasing differences is equivalent to supermodularity, so the two terms will be used interchangeably. (3)

   For smooth functions, supermodularity/increasing differences admit a convenient test. (4)

   LEMMA 1. If F is twice continuously differentiable, increasing differences is equivalent to [[partial derivative].sup.2]F(s, a)/[partial derivative]a[partial derivative]s [greater than or equal to] 0, for all a and s.

   PROOF. Increasing differences is equivalent to F(x, a')--F(x, a) being an increasing function (when a' > a), which is equivalent to [partial derivative][F(s, a')--F(s, a)]/[partial derivative]s [greater than or equal to] 0, or [partial derivative]F(s, a')/[partial derivative]F(s,a)]/[partial derivative]s, that is, [partial derivative]F(s, a)/[partial derivative]s is increasing in a or [[partial derivative].sup.2]F(s. a)/[partial derivative]a[partial derivative]s [greater than or equal to] 0. QED.

   Increasing differences is interpreted as formalizing the notion of (Edgeworth) complementarity: Having more of one variable increases the marginal returns to having more of the other variable. It turns out that some form of complementarity between endogenous and exogenous variables lies at the heart of any monotone comparative statics conclusion.

   A simplified version of Topkis's Monotonicity Theorem is now given. Though a special case of the original result, it is adequate for most applications. It is assumed throughout that F is continuous (or even just upper semi continuous) in a for each s. so that the max in Equation 1 is always attained. Furthermore, the correspondence [a.sub.*](s) then always admits maximal and minimal (single-valued) selections, denoted [bar.a](s) and [a.bar](s), respectively.

   THEOREM 1. Consider Problem i with S, A [subset] R and assume that

   (i) F has increasing differences in (s, a), and

   (ii) [A.sub.s] = [g(s), h(s)], where h, ,g.S [right arrow] R are increasing functions with g [less than or equal to] h.

   Then the maximal and minimal selections of [a.sup.*](s), [bar.a](s), and [a.bar](s), are increasing functions. Furthermore, if (i) is strict, then every selection of [a.sup.*](s) is increasing.

   PROOF. By way of contradiction, assume that [bar.a](s) is not increasing, so that, for some s' > s, [bar.a](s')

   (4) 0 [greater than or equal to] F[s',[bar.a](s)]--F[s',[bar.a](s')] [greater than or equal to] F[s, [bar.a](s)] F[s,[bar.a](s')] > 0,

   so equality holds throughout. Hence, [bar.a](s) [member of] [a.sup.*](s'), a contradiction to the fact that [bar.a](s') = max{[a.sup.*](s')}, in view of the fact that [bar.a](s')

   If Assumption (i) is strict, the same contradiction argument for any selection [bar.a](s) of [a.sup.*](.) shows that Equation 4 holds with a strict middle inequality, a contradiction (as 0 > 0). So [bar.a](x) is increasing. QED.

   In this proof, the contradiction hypothesis, that is, [bar.a](s') [bar.a](s), from feasibility alone.

   To rephrase the result, in the one-dimensional case with smoothness, it is sufficient for monotone comparative statics that the objective satisfy [[partial derivative].sup.2]...