Donald M. Topkis is a Professor at the University of California at Davis.

Supermodularity and Complementarity

By DONALD M. TOPKIS

PRINCETON UNIVERSITY PRESS

Copyright © 1998 Princeton University Press
All right reserved.
ISBN: 978-0-691-03244-3

Contents

Preface…………………………………………………………………………xiChapter 1 – Introduction…………………………………………………….3Chapter 2 – Lattices, Supermodular Functions, and Related Topics…………………7Chapter 3 – Optimal Decision Models…………………………………………..94Chapter 4 – Noncooperative Games……………………………………………..175Chapter 5 – Cooperative Games………………………………………………..207Bibliography…………………………………………………………………….263Index…………………………………………………………………………..269

Chapter One

Introduction

One may sometimes conclude too readily that an old, familiar, and simple concept, exemplified in myriad common situations, has little new to offer. In particular, how much novelty could be expected from the descriptive notion of complementarity, whereby two products are considered complements if having more of one product increases the marginal value derived from having more of the other product? Indeed, a half century ago, Samuelson [1947] declared:

In my opinion the problem of complementarity has received more attention than is merited by its intrinsic importance.

Yet, a quarter century later, Samuelson [1974] came to assert:

The time is ripe for a fresh, modern look at the concept of complementarity. … [T]he 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.

The latter quotation also expresses the motivation for this monograph, which links complementarity to powerful tools involving supermodular functions on lattices and focuses on analyses and issues related to monotone comparative statics.

Comparative statics examines how optimal decisions or equilibria in a parameterized collection of problems vary with respect to the parameter. In a decision problem, the parameter may affect the objective function and the feasible region. In a noncooperative game, the parameter may affect the payoff functions of the various players, the collection of feasible strategies for the players, and the set of players participating in the game. In a cooperative game, the parameter may affect the characteristic function and the set of players in the game. Monotone comparative statics is particularly concerned with scenarios where optimal decisions or equilibria vary monotonically with the parameter. Several alternate notions of complementarity may be stated in terms of monotone comparative statics. One notion would consider a system of products to be complements if, treating the levels of any subset of the products as a parameter, optimal levels for the other products increase with the parametric levels of the former subset of products. Another notion would consider a system of products to be complements if the acquisition prices for the products are treated as a parameter and the optimal levels of all products increase as the prices of the products decrease. These two alternate notions of complementarity turn out to be very closely related to that notion given in the second sentence of the preceding paragraph. The key to these relationships is found in properties of supermodular functions, which are intimately related to complementarity.

The economics literature is replete with examples of monotone comparative statics. Most of these examples are manifestations of complementarity, with a common explicit or implicit theoretical basis in properties of a supermodular function on a lattice. Supermodular functions on a lattice yield a characterization for complementarity and extend the notion of complementarity to a general and abstract setting, which is a natural mathematical context for studying complementarity and monotone comparative statics. Within this context, handy analytical tools are available and may be further developed. Supermodularity is a basis of a unifying theory for analyzing structural properties of a collection of parameterized optimization problems. Fundamental results give sufficient and necessary conditions under which optimal solutions for a collection of parameterized optimization problems vary monotonically with the parameter. Concepts and results related to supermodular functions on a lattice constitute a formal step in a long line of economics literature on complementarity. While informal statements of properties related to complementarity are intuitively appealing, this monograph cites several anomalies where examples with some flavor of complementarity fail to possess properties that intuition might expect.

This monograph develops a comprehensive theory relating to supermodular functions on a lattice, with a focus on the connection between supermodular functions and complementarity as well as on the role of supermodularity and complementarity for monotone comparative statics. Furthermore, this monograph exhibits the use of that theory in the analysis of many diverse models. The emphasis is on methodology. The theoretical material is a systematic and integrated view that summarizes and refines previously published research, fills in gaps, makes new connections, and introduces new results. The present framework makes available tools with which one can construct concise proofs having to do with supermodularity, complementarity, and monotone comparative statics, rather than deriving ad hoc proofs for different models. It facilitates identifying the most general scenarios and assumptions for models to exhibit monotone comparative statics and other properties related to complementarity, as well as delimiting classes of models and structural hypotheses for which such properties might hold. And it serves to elucidate a common theoretical basis whereby apparently disparate models share essential features and to enable the recognition of essential distinctions between models. The choice of theoretical material for inclusion here is based on potential relevance and utility and on providing a relatively complete perspective of salient issues. The inclusion of examples and applications, some previously published and some new, is far more selective than the theoretical material. Besides their intrinsic importance, the particular selection of examples and applications is based on how well they illustrate uses of the present methodology, where this methodology constitutes the primary technical issue and is not clouded by substantial extraneous technical issues. The exposition of the theory and the applications is, for the most part, self-contained.

The heart of this monograph is Chapter 2, which presents concepts and theory relating to lattices, supermodularity, complementarity, and monotone comparative statics. It develops tools to facilitate the analysis of supermodularity, complementarity, and monotone comparative statics, and it clarifies the role of lattices, supermodularity, and complementarity for monotone comparative statics. Topics in Chapter 2 include partially ordered sets and lattices; completeness and related topological properties; an ordering relation used to compare sets of feasible solutions or sets of optimal solutions; fixed points; supermodular functions and increasing differences; maximization of supermodular functions; sufficient and necessary conditions for monotone comparative statics; and equivalences and implications among various notions related to complementarity. The theory does without traditional assumptions of differentiability, concavity, and divisibility that are required by classical methods for comparative statics. Some brief illustrative examples are included.

Chapter 3, Chapter 4, and Chapter 5 apply theory from Chapter 2 to decision problems, noncooperative games, and cooperative games, respectively. These three applications chapters are largely independent of one another. Chapter 3 studies matching workers to firms; a detailed model of a firm engaged in manufacturing and marketing operations; production planning; transportation and transshipment problems; other network models (the shortest path problem in an acyclic network, the minimum cut problem, the maximum closure problem) with applications to dynamic economic lot size production models, the selection of activities, and equivalences among certain combinatorial structures; the optimality of myopic decisions; Markov decision processes; stochastic inventory problems; and stochastic transformations related to the latter two classes of decision problems. Chapter 4 examines the existence of an equilibrium point in a noncooperative game; parametric properties of equilibrium points; algorithms for approximating an equilibrium point; and examples. Chapter 5 looks at the core of a cooperative game with side payments; the greedy algorithm; cooperative games depending on a parameter; a class of activity optimization games; and examples.

(Continues…)

Excerpted from Supermodularity and Complementarityby DONALD M. TOPKIS Copyright © 1998 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.