GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY

Efficient allocation of indivisible goods is an important problem in mathematical economics and operations research, where the concept of Walrasian equilibrium plays a fundamental role. As a sufficient condition for the existence of a Walrasian equilibrium, the concept of gross substitutes condition for valuation functions is introduced by Kelso and Crawford (1982). Since then, several variants of gross substitutes condition as well as a discrete concavity concept, called M ♮ -concavity, have been introduced to show the existence of an equilibrium in various models. In this paper, we survey the relationship among Kelso and Crawford's gross substitutes condition and its variants, and discuss the connection with M ♮ -concavity. We also review various characterizations and properties of these concepts.

Related papers:

title: Job Matching, Coalition Formation, and Gross Substitutes
abstract: Competitive adjustment processes in labor markets with perfect information but heterogeneous firms and workers are studied. Generalizing results of Shapley and Shubik [7], and of Crawford and Knoer , we show that equilibrium in such markets exists and is stable, in spite of workers' discrete choices among jobs, provided that all workers are gross substitutes from each firm's standpoint. We also generalize Gale and Shapley's [3] result that the equilibrium to which the adjustment process converges is biased in favor of agents on the side of the market that makes offers, beyond the class of economies to which it was extended by Crawford and Knoer . Finally, we use our techniques to establish the existence of equilibrium in a wider class of markets, and some sensible comparative statics results about the effects of adding agents to the market are obtained. THE ARROW-DEBREU THEORY of general economic equilibrium has long been recognized as a powerful and elegant tool for the analysis of resource allocation in market economies. Not all markets fit equally well into the Arrow-Debreu framework, however. Consider, for example, the labor market-or the housing market, which provides an equally good example for most of our purposes. Essential features of the labor market are pervasive uncertainty about market opportunities on the part of participants, extensive heterogeneity, in the sense that job satisfaction and productivity generally differ (and are expected to differ) interactively and significantly across workers and jobs, and large set-up costs and returns to specialization that typically limit workers to one job. All of these features can be fitted formally into the Arrow-Debreu framework. State-contingent general equilibrium theory, for example, provides a starting point for studying the effects of uncertainty. But this analysis has been made richer and its explanatory power broadened by the examination of equilibrium with incomplete markets, search theory, and market signaling theory. The purpose of this paper is to attempt some improvements in another dimension: we study the outcome of competitive sorting processes in markets where complete heterogeneity prevails (or may prevail). To do this, we take as given the implications of set-up costs and returns to specialization by assuming that, while firms can hire any number of workers, workers can take at most one job. We also return to the simplification of perfect information. In the customary view of competitive markets, agents take market prices as given and respond noncooperatively to them. In this framework equilibrium cannot exist in general unless the goods traded in each market are truly homogeneous; heterogeneity therefore generally requires a very large number of markets. And since these markets are necessarily extremely thin-in many cases containing only a single agent on each side-the traditional stories supporting the plausibility of price-taking behavior are quite strained.

title: The English Auction with Differentiated Commodities
abstract: We study economies (with indivisibilities) that satisfy the gross substitutes (GS) condition. We define an excess demand set with the property that increasing the prices of all goods in excess demand eventually leads to the smallest Walrasian prices. This procedure is a generalization of the auction studied by G. Demange, D. Gale and M. J. Sotomayor, Polit. Econ. 94 (1986), 863–872. In our auction, truthful revelation of demand is a perfect Bayesian equilibrium if the smallest Walrasian prices correspond to the Vickrey–Clarke–Groves payments. However, no dynamic auction can reveal sufficient information to implement the Vickrey mechanism if all GS preferences are allowed. Journal of Economic Literature Classification Numbers: D4, D44, D5, D51.

title: WALRASIAN EQUILIBRIUM WITH GROSS SUBSTITUTES
abstract: In this paper we study the problem of efficient production and allocation of indivisible objects among a set of consumers. We assume that the agents’ preferences depend on the bundle of objects and the quantity of money they consume. Furthermore, we assume that preferences are quasilinear in money, and that agents have a large endowment of money. With indivisibilities, it is well-known that many familiar properties of the utility functions fail to ensure existence. In their striking analysis of the matching problem, Kelso and Crawford  introduce the gross substitutes (GS) condition which ensures the non-emptiness of the core. We propose two new conditions, and show that with quasilinearity they are equivalent Article ID jeth.1999.2531, available online at http:www.idealibrary.com on

title: Discrete convexity and equilibria in economies with indivisible goods and money
abstract: We consider a production economy with many indivisible goods and one perfectly divisible good. The aim of the paper is to provide some light on the reasons for which equilibrium exists for such an economy. It turns out, that a main reason for the existence is that supplies and demands of indivisible goods should be sets of a class of discrete convexity. The class of generalized polymatroids provides one of the most interesting classes of discrete convexity.

title: Convexity and Steinitz's Exchange Property
abstract: “Convex analysis” is developed for functions defined on integer lattice points. We investigate the class of functions which enjoy a variant of Steinitz's exchange property. This includes linear functions on matroids, valuations on matroids (in the sense of Dress and Wenzel), and separable concave functions on the integral base polytope of submodular systems. It is shown that a function ω has the Steinitz exchange property if and only if it can be extended to a concave function ω such that the maximizers of ( ω +any linear function) form an integral base polytope. A Frenchel-type min–max theorem and discrete separation theorems are established which imply, as immediate consequences, Frank's discrete separation theorem for submodular functions, Edmonds' intersection theorem, Fujishige's Fenchel-type min–max theorem for submodular functions, and also Frank's weight splitting theorem for weighted matroid intersection.

title: Discrete convex analysis
abstract: A theory of “discrete convex analysis” is developed for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, subgradients, the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. Sections 1–4 extend the conjugacy relationship between submodularity and exchange ability, deepening our understanding of the relationship between convexity and submodularity investigated in the eighties by A. Frank, S. Fujishige, L. Lovász and others. Sections 5 and 6 establish duality theorems for M- and L-convex functions, namely, the Fenchel min-max duality and separation theorems. These are the generalizations of the discrete separation theorem for submodular functions due to A. Frank and the optimality criteria for the submodular flow problem due to M. Iri-N. Tomizawa, S. Fujishige, and A. Frank. A novel Lagrange duality framework is also developed in integer programming. We follow Rockafellar’s conjugate duality approach to convex/nonconvex programs in nonlinear optimization, while technically relying on the fundamental theorems of matroid-theoretic nature.

title: Recent Developments in Discrete Convex Analysis
abstract: This paper describes recent developments in discrete convex analysis. Particular emphasis is laid on natural introduction of the classes of L-convex and M-convex functions in discrete and continuous variables. Expansion of the application areas is demonstrated by recent connections to submodular function maximization, finite metric space, eigenvalues of Hermitian matrices, discrete fixed point theorem, and matching games.

title: A Note on Kelso and Crawford's Gross Substitutes Condition
abstract: In their 1982 article, Kelso and Crawford proposed a gross substitutes condition for the existence of core (and equilibrium) in a two-sided matching model. Since then, this condition has often been used in the literature on matching models and equilibrium models in the presence of indivisibilities. In this paper we prove that a reservation value (or utility) function satisfies the gross substitutes condition if and only if it is anM?-concave function defined on the unit-hypercube, which is a discrete concave function recently introduced by Murota and Shioura (1999).

title: New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities
abstract: The concept of M-convex functions plays a central role in "discrete convex analysis", a unified framework of discrete optimization recently developed by Murota and others. This paper gives two new characterizations of M- and M'-convex functions generalizing Gul and Stacchetti's results on the equivalence among the single improvement condition, the gross substitutes condition and the no complementarities condition for set functions (utility functions on {0,1} vectors) as well as Fujishige and Yang's observation on the connection to M-convexity. We also discuss implications of our results in an exchange economy with indivisible goods.

title: Gross substitution, discrete convexity, and submodularity
abstract: We consider a class of functions satisfying the gross-substitutes property (GS-functions). We show that GS-functions are concave functions, whose parquets are constituted by quasi-polymatroids. The class of conjugate functions to GS-functions turns out to be the class of polyhedral supermodular functions. The class of polyhedral GS-functions is a proper subclass of the class of polyhedral submodular functions. PM-functions, concave functions whose parquets are constituted by g-polymatroids, form a proper subclass of the class of GS-functions. We provide an additional characterization of PM-functions.

title: Presentation and structure of substitutes valuations
abstract: We propose two different methods for presenting substitutes (a.k.a. gross-substitutes) valuations. Each provides short descriptions for a family of substitutes valuations. We also show that substitutes valuation are closed under k-satiation.

title: Combinatorial Auctions with Decreasing Marginal Utilities
abstract: In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.

title: Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions
abstract: The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.

title: Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items
abstract: We address the problem of computing a Walrasian equilibrium price in an ascending auction with gross substitutes valuations. In particular, an auction market is considered where there are multiple differentiated goods and each good may have multiple units. Although the ascending auction is known to i¬ nd an equilibrium price vector in i¬ nite time, little is known about its time complexity. The main aim of this paper is to analyze the time complexity of the ascending auction globally and locally, by utilizing the theory of discrete convex analysis. An exact bound on the number of iterations is given in terms of the L infinity distance between the initial price vector and an equilibrium, and an efficient algorithm to update a price vector is designed based on a min-max theorem for submodular function minimization.

title: Matching with Contracts
abstract: We develop a model of matching with contracts which incorporates, as special cases, the college admissions problem, the Kelso-Crawford labor market matching model, and ascending package auctions. We introduce a new "law of aggregate demand" for the case of discrete heterogeneous workers and show that, when workers are substitutes, this law is satisfied by profit-maximizing firms. When workers are substitutes and the law is satisfied, truthful reporting is a dominant strategy for workers in a worker-offering auction/matching algorithm. We also parameterize a large class of preferences satisfying the two conditions.

title: Ascending Auctions with Package Bidding
abstract: A family of ascending package auction models is introduced in which bidders may determine their own packages on which to bid. In the proxy auction (revelation game) versions, the outcome is a point in the core of the exchange economy for the reported preferences. When payoffs are linear in money and goods are substitutes, sincere reporting constitutes a Nash equilibrium and the outcome coincides with the Vickrey auction outcome. Even when goods are not substitutes, ascending proxy auction equilibria lie in the core with respect to the true preferences. Compared to the Vickrey auction, the proxy auctions generate higher equilibrium revenues, are less vulnerable to shill bidding and collusion, can handle budget constraints much more robustly, and may provide better ex ante investment incentives.

title: Application of M-Convex submodular flow problem to mathematical economics
abstract: This paper considers an economic model in which producers and consumers trade various indivisible commodities through a perfectly divisible commodity, money. On the basis of the recent developments in discrete mathematics (combinatorial optimization), we give an efficient algorithm to decide whether a competitive equilibrium exists or not, when cost functions of the producers are M♮-convex and utility functions of the consumers are M♮-concave and quasilinear in money, where M♮-convexity is closely related to the gross substitutes condition.

title: Distributive lattices, polyhedra, and generalized flows
abstract: A D-polyhedron is a polyhedron P such that if x,y are in P then so are their componentwise maximums and minimums. In other words, the point set of a D-polyhedron forms a distributive lattice with the dominance order. We provide a full characterization of the bounding hyperplanes of D-polyhedra. Aside from being a nice combination of geometric and order theoretic concepts, D-polyhedra are a unifying generalization of several distributive lattices which arise from graphs. In fact with a D-polyhedron we associate a directed graph with arc-parameters, such that points in the polyhedron correspond to vertex potentials on the graph. Alternatively, an edge-based description of the points of a D-polyhedron can be given. In this model the points correspond to the duals of generalized flows, i.e., duals of flows with gains and losses. These models can be specialized to yield distributive lattices that have been previously studied. Particular specializations are: flows of planar digraphs (Khuller, Naor and Klein), @a-orientations of planar graphs (Felsner), c-orientations (Propp) and @D-bonds of digraphs (Felsner and Knauer). As an additional application we identify a distributive lattice structure on generalized flow of breakeven planar digraphs.