Interfaces with Other Disciplines
Efficient market-clearing prices in markets with nonconvexities

https://doi.org/10.1016/j.ejor.2003.12.011Get rights and content

Abstract

This paper addresses the existence of market clearing prices and the economic interpretation of strong duality for integer programs in the economic analysis of markets with nonconvexities (indivisibilities). Electric power markets in which nonconvexities arise from the operating characteristics of generators motivate our analysis; however, the results presented here are general and can be applied to other markets in which nonconvexities are important. We show that the optimal solution to a linear program that solves the mixed integer program has dual variables that: (1) have the traditional economic interpretation as prices; (2) explicitly price integral activities; and (3) clear the market in the presence of nonconvexities. We then show how this methodology can be used to interpret the solutions to nonconvex problems such as the problem discussed by Scarf [Journal of Economic Perspectives 8(4) (1994) 111].

Introduction

Scarf, 1990, Scarf, 1994 describes most markets in today's advanced economies as having considerable indivisibilities (nonconvexities). For example, firms must make discrete decisions on whether to invest in a new project or when to start-up a production process. It has been widely believed that in the presence of nonconvexities in the cost function, it is not possible to guarantee the existence of linear prices that will allow the market to clear, unless the solution to the relaxed convex problem just happens to produce an integral solution (e.g. assignment problems).

Unfortunately, the modeling of nonconvexities such as discrete choices and economies of scale have largely been avoided due to the intractability of such problems. Standard graduate texts in microeconomics such as Kreps (1990) and Varian (1992) note that assuming away nonconvexities is unrealistic, but they proceed with the standard assumptions without addressing the issue further. Mathematical references used by economists such as Chiang (1984) and Takayama (1985) do not mention integer programming for solving optimization problems with nonconvexities. In the face of nonconvexities, linear commodity prices in general will result in either a situation of excess supply or excess demand, and the market will not clear. As a simple example in which nonconvexities prevent a market from clearing, consider a market in which all firms have the same cost and entry is free. Each firm must incur a fixed cost of one to produce any positive amount of a good in the range (0,1]; in that range, marginal cost is zero. If the market demand curve is P=2−0.6Q, then there is no market equilibrium. For any price less than 1, no firm will produce and there will be a shortage. For any price strictly greater than 1, quantity supplied is infinite, and there is a surplus. Finally, for P=1, quantity demanded is 1.67, but the quantity supplied will be no more than 1, because if a second firm enters, it will not earn enough revenue to cover its fixed cost.

Because of such problems, it has been more convenient and tractable to employ linear or convex nonlinear optimization models to represent profit maximization problems for producers and utility maximization problems for consumers. Such optimization problems assume desirable properties such as the continuity and concavity of the objective function to be maximized, and the convexity of the feasible region defined by the constraint set. As a justification for the assumption of convexity, Arrow and Hahn (1971), Mas-Colell et al. (1995), Takayama (1985), and Varian (1992) argue that if agents in an economy were replicated many times, then linear prices will support a competitive equilibrium. Arrow and Hahn use the convex hull of the nonconvex set of constraints to show an “approximate” equilibrium. An equilibrium in such a market yields a linear commodity price (or vector of linear prices) and quantity (or vector of quantities) such that all economic agents maximize their objectives and the market clears (the quantity supplied equals the quantity demanded for each commodity priced). Conceptually, a linear price vector arises out of the application of the Separating Hyperplane Theorem. (For example, see Takayama, 1985, pp. 39–49, 103.) Such simplifying assumptions about the objective function and constraint sets allow economists to prove the existence of market clearing prices using fixed-point arguments. Computationally, if the market equilibrium problem is solved by Samuelson's (1952) principle, the equilibrium prices for such markets are simply the dual variables (shadow prices or LaGrange multipliers) for the market clearing constraints of the goods.

Such modeling assumptions have allowed economists to construct useful models of economic behavior and to conduct insightful simulation experiments with these increasingly complex models. But since the work of Gomory and Baumol (1960), analogous dual variable interpretations for mixed-integer programs have eluded economists and mathematicians. As an example, Geoffrion and Nauss (1977) state “(integer programming) models have no shadow prices or dual variables with an interpretation comparable to that in linear programming.” The economic literature continues to reflect this belief. Current market models are largely unable to deal with the significant nonconvexities that actually exist. For example, whether or not to invest in a new capital project or whether or not to start-up a production operation are discrete decisions. Many production processes have economies of scale, a property contrary to the linearity/convexity assumption. The nonexistence of market clearing prices can be a real problem, and some degree of centralized coordination may be required in some markets to reach the welfare maximizing solution.

An important market where nonconvexities are significant and are a concern in constructing prices is the short-term (day- to week-ahead) electric power market. Nonconvexities include start-up and shut-down costs along with minimum output requirements (which state that if a plant is running, it must produce at least a certain amount). The lumpiness of the costs in these markets can have a large influence on operating schedules and ultimately investment. It is widely noted that the presence of nonconvexities implies that there will be no linear commodity prices that will support an equilibrium (e.g., Johnson et al., 1997; Madrigal and Quintana, 2000; Hobbs et al., 2001). This lack of prices leads to a potential mismatch of supply and demand that is of concern to the engineers responsible for maintaining system balance and stability, to the economists and market designers who are interested in promoting market efficiency, and to the market participants themselves who are worried about how steps taken to balance supply and demand might affect their outputs and revenues.

In this paper, we present a method for constructing a set of linear prices that will support a Walrasian competitive equilibrium in markets with nonconvexities that is based on mixed integer programming (MIP). Prices are derived from solving a MIP and an associated linear program and have a corresponding analogy to nonlinear (multi-part) prices. These prices will support equilibrium allocations in a decentralized auction-based market. That is, if a Walrasian auctioneer announced to market participants the prices we derive, from within the set of the maximizing allocations chosen by agents is a set that would clear the market. (For any ties that might occur, the auctioneer would randomly select winners.)

The role of nonlinear pricing in markets with nonconvexities has been recognized and well researched (see Wilson, 1993). However, the market environments in which nonlinear prices have been examined have not been considered perfectly competitive. For example, monopoly utility services often are subject to nonlinear pricing in the form of a demand or access charge plus a variable linear charge for the service. Additionally, nonlinear prices can be employed to enable firms to capture rents through price discrimination or to compete strategically for certain segments of the market. In contrast, the prices we propose, while being analogous to nonlinear prices, can be employed in a competitive environment where market agents are price takers and therefore do not have any market power and do not compete strategically.

Our method for calculating equilibrium prices is straightforward. First, we solve a MIP to find the optimal allocation. Next, we remove the integrality constraints and insert equality constraints (cuts) that force the integer variables to assume their optimal values in the resulting linear program (LP). We then solve the LP to find the associated dual prices on the market clearing conditions and added equality constraints. These dual (or shadow) prices then can be used as prices to support a competitive equilibrium.

The paper proceeds as follows. Section 2 reviews the relevant literature. Then in Section 3, we define a linear program that solves mixed-integer programs and discuss why linear prices on the output commodity are not sufficient for a competitive equilibrium in the face of nonconvexities. In Section 4, we discuss the example used by Scarf (1994), and we show how the market clearing prices can be computed for his model. In Section 5, we provide a general formulation of the market clearing model and a general proof that demonstrates that we can always find prices that will clear a market with indivisibilities, so long as we can find the optimal solution to the MIP that describes the market. Section 6 concludes and discusses some applications and extensions.

Section snippets

Related literature

The economics and management science literature has occasionally addressed the problem of finding dual price interpretations to integer programs and MIPs. The classic work in this area is Gomory and Baumol (1960). In order to find the solution to the MIP, Gomory and Baumol add additional constraints or cutting planes (to the LP relaxation of the MIP), which in their case they define as linear combinations of existing constraints, until the solution to the augmented LP results in an integer

Prices in the LP that solve the MIP

A mixed integer problem with m continuous variables and n integer variables (Rm×Zn) that has a feasible and bounded optimal solution can be converted to a linear program with at most m+n continuous variables (Rm+n) and at most n additional linear constraints (Gomory and Baumol, 1960). These statements can be proved by observing that an additional constraint can be defined for each integer variable setting the variable equal to its optimal value, which produces an LP that solves the MIP. (It is

Scarf's example

As an example of a market with nonconvexities that lacks a market-clearing price for the commodity, consider the problem put forth by Scarf (1994). He postulates two types of plants, each with significant fixed costs and relatively small marginal costs (Table 1). The objective of the problem (auctioneer) is to minimize the total cost of satisfying a fixed level of demand. The corresponding decentralized market problem would be for each plant of each type to maximize profits subject to internal

General formulation and proofs

In this section, we present a result concerning the equivalence of a MIP and an LP augmented with certain defined cutting planes. We then define a contract that an auctioneer might offer that is efficient and has prices that support a market clearing equilibrium. Although these results are phrased as if they apply only to formal auction markets, they also apply to other markets.

Consider an auction market that can be represented by a Primal Mixed Integer Program (PIP). The formulation below

Conclusions, applications, and extensions

This paper has addressed a problem that has troubled the economic analysis of markets with nonconvexities: the existence of market clearing prices. Given the presence of nonconvexities in emerging electricity auctions, this problem is of practical as well as theoretical interest. The contracts defined by T provide an answer to Scarf's (1994) search for a set of prices in the presence of nonconvexities that yield zero profits for all activities in the optimal solution. These results hold for any

Acknowledgements

This research was supported by the Federal Energy Regulatory Commission. Partial support for the third author was provided by NSF Grant ECS 0080577. The authors would also like to acknowledge the helpful comments and suggestions of Karla Hoffman, Herbert Scarf, and Bill Hogan. Any errors and opinions are solely the responsibility of authors.

References (33)

  • S. Bikhchandani et al.

    Competitive equilibrium in an exchange economy with indivisibilities

    Journal of Economic Theory

    (1997)
  • A. Crema

    Average shadow price in a mixed integer linear programming problem

    European Journal of Operational Research

    (1995)
  • K.J. Arrow et al.

    General Competitive Analysis

    (1971)
  • Bikhchandani, S., Ostroy, J., 2001a. Ascending price Vickrey auctions. Working...
  • Bikhchandani, S., Ostroy, J., 2001b. The package assignment model. Working...
  • S. Borenstein et al.

    An empirical analysis of the potential for market power in California's electricity industry

    Journal of Industrial Economics

    (1999)
  • S.J. Brown et al.

    The Theory of Public Utility Pricing

    (1986)
  • Ceria, S., 2001. Solving Hard Mixed Integer Programs for Electricity Generation. In: Hobbs and Rothkopf et al. (2001),...
  • A.C. Chiang

    Fundamental Methods of Mathematical Economics

    (1984)
  • A.M. Geoffrion et al.

    Parametric and postoptimality analysis in integer linear programming

    Management Science

    (1977)
  • R.E. Gomory et al.

    Integer programming and pricing

    Econometrica

    (1960)
  • F.J. Gould

    Extensions of lagrange multipliers in nonlinear programming

    SIAM

    (1971)
  • B.F. Hobbs et al.

    Evaluation of a truthful revelation auction for energy markets with nonconcave benefits

    Journal of Regulatory Economics

    (2000)
  • Hobbs, B.F., Stewart, Jr., W.R., Bixby, R.E., Rothkopf, M.H., O'Neill, R.P., Chao, H.-P., 2001. Why This Book? New...
  • R.B. Johnson et al.

    Equity and efficiency of unit commitment in competitive electricity markets

    Utilities Policy

    (1997)
  • Cited by (328)

    • Moving from linear to conic markets for electricity

      2023, European Journal of Operational Research
    • Market dynamics and investment in the electricity sector

      2023, International Journal of Industrial Organization
    • Long-run optimal pricing in electricity markets with non-convex costs

      2023, European Journal of Operational Research
    View all citing articles on Scopus
    View full text