{'fraction_non_alphanumeric': 0.05088834944226846, 'fraction_numerical': 0.01462462954413451, 'mean_word_length': 3.901313868613139, 'pattern_counts': {'":': 1, '<': 15, '<?xml version=': 0, '>': 95, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parameterized Supply Function Bidding: Equilibrium and Efficiency

We consider a model where a finite number of producers compete to meet an infinitely divisible but inelastic demand for a product. Each firm is characterized by a production cost that is convex in the output produced, and firms act as profit maximizers. We consider a uniform price market design that uses supply function bidding: firms declare the amount they would supply at any positive price, and a single price is chosen to clear the market. We are interested in evaluating the impact of price-anticipating behavior both on the allocative efficiency of the market and on the prices seen at equilibrium. We show that by restricting the strategy space of the firms to parameterized supply functions, we can provide upper bounds on both the inflation of aggregate cost at the Nash equilibrium relative to the socially optimal level, as well as the markup of the Nash equilibrium price above the competitive level: as long as N > 2 firms are competing, these quantities are both upper bounded by 1 + 1/(N-2). This result holds even in the presence of asymmetric cost structure across firms. We also discuss several extensions, generalizations, and related issues.


Introduction
We consider a model where a finite number of producers compete to meet an infinitely divisible, inelastic demand for a product. Each firm is characterized by a production cost that is convex in the output produced, and firms act as profit maximizers. We study a simple market design question: given a fixed, inelastic demand, how should a market mechanism be designed to yield an efficient allocation of production across suppliers-that is, an allocation which minimizes production cost?
In this paper, we focus our attention on uniform price market-clearing mechanisms for the allocation problem. These are mechanisms that set a single per unit price for the resource; firms compete by submitting supply functions that describe their desired production level as a function of price. A central clearinghouse then chooses a price that clears the market. Such mechanisms have been used to model competition in a range of industries, including energy markets, airline pricing, and contracts for management consulting services (Vives 2008). Uniform price mechanisms are interesting objects of study due to their simplicity. In particular, they are transparent and fair from the point of view of market participants: all agents are charged the same per-unit price, and asked to supply exactly what they bid via their supply functions.
We have two related goals in this market design problem. First, we desire that such a mechanism does not exhibit a large "welfare loss;" i.e., we hope that that the efficiency loss remains bounded when firms are price anticipating, regardless of the firms' cost functions. Second, we wish to ensure that the price markup when firms are price anticipating is bounded relative to the competitive price level; such a bound ensures that the exercise of market power by the firms is mitigated.
Our task is complicated by a fundamental tradeoff in mechanism design. On one hand, sufficient flexibility must be granted to the firms in declaring their supply functions to ensure that they can approximately declare their costs. On the other hand, as the strategic flexibility granted to firms increases, their temptation to misdeclare their cost increases as well. Indeed, while in principle arbitrary supply functions allow firms to declare all marginal cost information, in theory and practice we find that such strategic flexibility only encourages the exercise of market power.
Our paper sheds light on this tradeoff by studying a parameterized class of supply functions that allow firms enough flexibility to communicate information about their production cost, yet not enough flexibility to enable them to exercise market power and cripple the performance of the overall market. In other words, we partially restrict the range of possible supply functions firms can declare, and demonstrate the resulting market-clearing mechanism is nearly efficient. Our analysis lends credence to the hypothesis that restricting the strategy space granted to firms can improve allocative efficiency, as observed by several pieces of related work (see Section 2).
Before proceeding, we fix some terminology. We will assume that N firms compete to satisfy a fixed demand D > 0, where firm n has a convex, strictly increasing, and nonnegative production cost function C n (s n ). We assume that each firm n submits a supply function S n (p) to a central clearinghouse. The clearinghouse then clears the market by choosing a price p * such that n S n (p * ) = D, and firm n is asked to supply S n (p * ). For each firm, we also let P n (S) denote the inverse supply function, i.e., P n (S n (p)) = p. (These definitions are made informally, without regard to ensuring that market-clearing prices or inverse supply functions exist; we will consider these technical issues more carefully in the remainder of the paper.) We may reframe our objective as follows: are there any restrictions that can be placed on supply functions firms are allowed to submit, that ensure both efficient market performance and a bounded markup above the competitive price level?
One can start by considering simple Bertrand and Cournot structures for the supply functions.
Bertrand competition has the deficiency that equilibria may fail to exist when the marginal production cost of each firm is not linear (Shapiro 1989). On the other hand, Cournot competition is not well defined when the elasticity of demand is zero; and furthermore, if the price elasticity of demand is low, then it is straightforward to check that Cournot equilibria may have arbitrarily high welfare loss and price markup above competitive levels (Day et al. 2002).
Thus neither perfectly vertical nor perfectly horizontal supply functions yield reasonable solutions in this setting. One is then led to consider supply function equilibrium. In such a model, the strategy of each firm is not limited to one scalar (either price or quantity), but rather consists of an entire function S n (p) describing the amount of the good a firm is willing to produce at any price p.
The seminal work in the study of supply function equilibria is the paper of Klemperer and Meyer (1989); for further details, see Section 2. Unfortunately, one lesson of that line of literature is that the SFE framework is problematic from a market design standpoint; in general there may exist highly inefficient equilibria.
In the remainder of the paper, for the resource allocation environment described above, we demonstrate that we can achieve a successful mechanism design by properly restricting the class of supply functions firms are allowed to submit. We start by discussing related work in Section 2.
In Section 3, we precisely define the market mechanism we consider; in particular, we assume that each firm submits a supply function of the form S(p, w) = D − w/p, where D is the demand and w is a nonnegative scalar chosen by the firm. The parameter w can be interpreted as the amount of revenue the supplier is willing to forgo from the total payout pD that will be created when the market clears. The market manager then chooses a price so that aggregate supply is equal to demand. This is, of course, a somewhat unintuitive market design; however, our goal is to use this design as a vehicle to demonstrate the strong efficiency properties attainable when strategic flexibility is properly constrained.
We begin with a preliminary investigation of equilibria of the mechanism. For our mechanism we recover the fundamental theorem of welfare economics: when firms are price taking, there exists a competitive equilibrium, and the resulting allocation minimizes aggregate production cost. We next assume instead that firms are price anticipating, and establish existence and uniqueness of a Nash equilibrium as long as more than two firms compete.
Sections 4 and 5 present the key results of this paper: the former provides a theoretical bound on the welfare loss at the Nash equilibrium relative to the competitive outcome; and the latter provides a similar bound on the price markup at the Nash equilibrium relative to the competitive price. In Section 4 we show that as long as at least two firms are competing, the ratio of Nash equilibrium production cost to the minimal production cost is no worse than 1 + 1/(N − 2), where N is the number of firms in the market. We emphasize that this result holds regardless of the cost functions of the firms (as long as they are convex)-thus it provides a very strong competitive limit theorem, without any assumptions of symmetry between firms. In Section 5, we show that the same bound applies to the Nash equilibrium price relative to the competitive price; we also provide a bound on the Lerner index. All bounds discussed in these two sections are tight.
In Section 6, we ask a design question: to what extent are the parameterized supply functions we have chosen "optimal"? We study a class of reasonable parameterized supply function mechanisms, using the metric of worst case welfare loss at the Nash equilibrium. We note that the mechanism we have chosen is "optimal" in this sense. This result is closely related to a theorem derived by the authors in Johari and Tsitsiklis (2008), and first presented in Chapter 4 of Johari (2004).
We conclude by considering two extensions of the model, first to mitigate the possibility of negative supply by the firms (discussed in Section 7), and second to cover settings with stochastic demand (in Section B). Section 7 addresses the fact that the supply functions we have chosen allow for nonequilibrium outcomes in which a firm may be forced to buy the good, rather than supply it.
We show that this problem is generic to the design of parameterized supply function mechanisms, but also provide a simple resolution using a "maximum liability" guarantee to each firm. Section 8 concludes. Note: Due to space constraints, all proofs can be found in the e-companion.

Related Work
Our work is inspired by a recent line of literature that studies the efficiency guarantees possible in market design when the strategy spaces of market participants are restricted (Chen and Zhang 2008, Johari et al. 2005, Johari and Tsitsiklis 2006, Maheswaran 2003, Maheswaran and Basar 2004, Moulin 2007, Sanghavi and Hajek 2004, Yang and Hajek 2006, 2007, Dimakis et al. 2006, Stoenescu and Ledyard 2006, Moulin 2006. The results of Johari and Tsitsiklis (2008) are most closely related to our paper: in that work, the efficiency of scalar-parameterized mechanisms is studied for a setting where buyers bid for a capacitated resource. As we discuss in Section 3, the mechanism we consider is related to the mechanisms studied in this literature; however, the efficiency loss bounds we derive are novel. In large part this distinction is due to the fact that in our paper we consider a setting where suppliers compete to meet demand. This is part of a growing literature that quantifies efficiency losses in a variety of game theoretic environments; see Nisan et al. (2007) for a comprehensive survey.
One well-known approach to the market design problem is to use the Vickrey-Clarke-Groves (VCG) class of mechanisms (Clarke 1971, Groves 1973, Vickrey 1961. Since each firm's profit is quasilinear (i.e., the production costs are measured in monetary units), a VCG mechanism ensures that truthful reporting for each firm is a dominant strategy. However, there are several reasons why a VCG mechanism may not be desirable in practical settings. For example, there is no bound on the payment the market manager may have to make to the market participants; further, VCG mechanisms exhibit the implicit "unfairness" of providing a different price to different purveyors of the same good. See, e.g., Hobbs et al. (2000), Ausubel and Milgrom (2006), Rothkopf et al. (1990) for extensive discussion of some of the shortcomings of the VCG mechanism. In part due to these shortcomings, VCG mechanisms are rarely observed in complex multi-unit resource allocation settings, such as power and electricity markets. It is worth noting that several recent papers have studied approaches to pricing divisible resources using VCG-like mechanisms with scalar strategy spaces; see, e.g., Maheswaran and Basar (2004), Yang andHajek (2006, 2007), Johari and Tsitsiklis (2008). Similar approaches could be applied in our context to yield efficient or nearly efficient market mechanisms, though with attendant shortcomings analogous to standard VCG mechanisms.
Instead, as discussed in the Introduction, we focus on uniform price market-clearing mechanisms; this model is closely related to the analysis of supply function equilibria (SFE). Grossman (1981) and Hart (1985) provide concrete examples of SFE models. In particular, Grossman's analysis shows that in the presence of fixed startup costs to the firms, it is possible for a supply function equilibrium to achieve full efficiency; however, in general it is difficult to guarantee that the number of supply function equilibria is small, and other inefficient supply function equilibria may exist.
The seminal work in the study of supply function equilibria is the paper of Klemperer and Meyer (1989). The authors begin by showing that, in the absence of uncertainty, nearly any production allocation can be supported as a supply function equilibrium. They then show that if demand is uncertain, then the range of equilibria is dramatically reduced; and that in equilibrium, possible prices and allocations range between those achieved at Bertrand and Cournot equilibria.
The SFE framework is somewhat problematic from a market design standpoint. The original model of Klemperer and Meyer (1989) required that the different firms have identical cost functions; recent work has made progress in studying models with asymmetric firms with both affine (Baldick and Hogan 2001, Baldick et al. 2004) and nonlinear (Anderson and Hu 2008) supply functions.
This literature primarily focuses on computational approaches to finding SFE (when they exist); as a result, general bounds on efficiency and price markups are not typically available-such properties are evaluated on a case-by-case basis. In summary, therefore, the complexity of the SFE model places restrictions on the types of environments that can be successfully analyzed, and does not yield a satisfactory answer to the market design questions raised above. SFE models can be used to model a range of industries, including airline pricing and contracts for management consulting (Vives 2008); but the most prominent application of the SFE concept is to electricity markets. Many power markets actually operate in practice by having generators submit complete supply functions (see Green 1996, andGreen andNewbery 1992, for the first applications of this approach). We do not aim to provide a comprehensive survey of the electricity market literature here; the reader is referred to Day et al. (2002) for a more complete list of references, and Wilson (2002) for an elegant discussion of some of the issues involved in power market design.
We conclude by noting that electricity markets also typically exhibit inelastic demand, as assumed in our paper; see, e.g., Stoft (2002), Section 1-7.3. In light of the short run price inelasticity of demand, many short-term markets for generation today operate by setting a price for electricity so that the aggregate supply offered by generators meets the demand requirements of a given region.
As noted above, the SFE model of Klemperer and Meyer, and subsequent results on that model, treat a general model of supply function bidding where demand as stochastic. As a result, such models apply well to markets where accurate demand forecasts are not available when bids are submitted, or where demand may vary over the period where the bid is binding. For example, in some day-ahead electricity markets generators are required to submit a single bid for the entire day, over which demand varies due to time-of-day effects. By contrast, our results on efficiency are developed in a setting with deterministic demand, and thus are applicable mainly to markets where demand forecasts are accurate at the time that bids are submitted. Such a model is reasonable, for example, in electricity markets where generators are allowed to rebid a different supply function for each hour of the day, if we presume that fairly accurate hourly forecasts of demand are available in advance.

Preliminaries
We consider a model where N ≥ 2 firms compete to satisfy an inelastic demand D > 0. Note that our model assumes that the demand D is deterministically known; we believe this is a reliable assumption in short term markets (e.g., day-ahead), where prediction of demand based on historical models is likely to have very low variance. We consider a model where demand is stochastic in Section B in the e-companion.
Let s n denote the amount produced and supplied by firm n. We assume that firm n incurs a cost C n (s n ) when it produces s n units; we assume that cost is measured in monetary units, and firms are profit maximizers. We make the following assumption on the cost functions C n .
Assumption 1. For each n, the cost function C n (s n ) is continuous, with C n (s n ) = 0 if s n ≤ 0.
Over the domain s n ≥ 0, the cost function C n (s n ) is convex and strictly increasing.
Since demand is inelastic, it is clear that aggregate welfare maximization is equivalent to aggregate cost minimization, i.e., the following optimization problem: subject to n s n = D; (2) s n ≥ 0, n = 1, . . . , N.
Any solution s to (1)-(3) is referred to as efficient.
We consider the following market mechanism for production allocation. Each firm n submits a supply function to the market manager, which gives (as a function of price) the amount the firm is willing to produce. In contrast to much of the literature on supply function equilibria (e.g., Klemperer and Meyer 1989), we consider the implications of restricting the space of supply functions firms are allowed to choose from; in particular, we will assume the supply functions are chosen from a parameterized family of supply functions.
Formally, the details of our market mechanism are as follows. We assume that firm n submits a parameter w n ≥ 0 to the market manager. The parameter indicates that at a price p > 0, firm n is willing to supply S(p, w n ) units given by: We then assume that the market manager chooses the price p(w) > 0 to clear the market, i.e., so that s S(p(w), w n ) = D. Such a choice is only possible if n w n > 0, in which case: On the other hand, if n w n = 0, then S(p, w n ) = D for all n, regardless of the value of p; so we fix the following conventions: S(0, 0) = D, and p(0) = 0.
(This makes the function p continuous in w.) The parameter w n may be interpreted as the revenue that firm n is willing to forgo; this follows since pD is the total pool of revenue when the price is p, and pS(p, w n ) = pD − w n is the revenue to firm n when the price is p. It is straightforward to observe various peculiarities of this mechanism.
First, it does not make any provision for firms to submit capacity constraints; we will find that this does not affect equilibrium behavior, but of course out of equilibrium the inability to declare capacity could force a firm to deliver supply beyond its means. On the other hand, any static supply function bidding model (with deterministic demand) where firms are allowed to declare capacities will have a range of highly undesirable equilibria, where firms choose capacities that exactly total the desired demand. In such equilibria, firms choose supply functions that approach capacity as the price approaches infinity. As a result, these equilibria always have astronomical prices, and every measure of market performance can be shown to degrade in such a context. 1 We believe that extracting capacity information from firms in such settings will require a more complete dynamic model of market structure, and this remains an important research direction.
A second concern regarding the market mechanism we have designed here is that prospective suppliers may be forced to purchase the good at the outcome of the market. This can happen when w is chosen so that D − w n /p(w) < 0 for some firm n; nothing rules this out in the definition of the mechanism. Of course, such behavior cannot happen in equilibrium, but firms will be rightly nervous of agreeing to a market mechanism with such a property. We will discuss in Section 6 two responses to this issue. We will also provide a characterization of the mechanism we have chosen as the best possible mechanism available in a certain class with reasonable properties.
We begin by considering a setting where firms act as price takers: given a price µ > 0, a price taking firm n acts to maximize the following profit function over w n ≥ 0: The first term represents the revenue to firm n when the price is µ and the firm supplies S(µ, w n ) units; the second term represents the cost to the firm of producing S(µ, w n ) units. Observe that since cost is measured in monetary units, the payoff is quasilinear in money.
It is straightforward to show that under our assumptions, when firms are price takers, there exists a competitive equilibrium, and the resulting allocation is efficient (i.e., an optimal solution to (1)- (3)). In a competitive equilibrium, firms maximize their payoff, and the price is chosen according to (5) to clear the market. For details on this result, see Theorem 5 in the e-companion.
In contrast to the price taking model, we now consider an oligopoly model where the firms are price anticipating instead. Price anticipating firms will realize that µ is set according to µ = p(w) from (5), and adjust their payoff accordingly. We use the notation w −n to denote the vector of strategies of firms other than n; i.e., w −n = (w 1 , w 2 , . . . , w n−1 , w n+1 , . . . , w N ). Given w −n , each firm n chooses w n to maximize: over nonnegative w n . If we substitute for p(w) from (5) and for S(p, w n ) from (4), we have: The payoff function Q n is similar to the payoff function P n , except that the firm anticipates that the network will set the price µ according to µ = p(w) from (5). The following theorem shows that there exists a unique Nash equilibrium allocation when N > 2 firms compete, by showing that at a Nash equilibrium it is as if the firms are solving another optimization problem of the same form as the aggregate cost minimization problem (1)-(3), but with "modified" cost functions.
Theorem 1. Assume that N ≥ 2, and suppose that Assumption 1 is satisfied. If N = 2, then no Nash equilibrium exists for the game defined by (Q 1 , . . . , Q N ). On the other hand, if N > 2, then there exists a Nash equilibrium w ≥ 0 of the game defined by (Q 1 , . . . , Q N ), and it satisfies n w n > 0. For any Nash equilibrium w, the vector s defined by s n = S(p(w), w n ) is the unique optimal solution to the following optimization problem: subject to n s n = D; s n ≥ 0, n = 1, . . . , N, whereĈ We note the following corollary for later reference: at a Nash equilibrium, one firm produces the entire supply only if it was efficient to do so.
Corollary 1. Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w is a Nash equilibrium w ≥ 0 of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) = D, and S(p(w), w m ) = 0 for m = n. Then the Nash equilibrium production vector is efficient.
We note that the use of "modified" cost functions in the proof of Theorem 1 is similar to the use of potential functions to study Nash equilibria in some games (Monderer and Shapley 1996). However, the objective function (10) is not a potential function for the game defined by (Q 1 , . . . , Q N ): while each payoff function is determined by the vector w of strategic choices of other players, the objective function (10) depends only on the resulting production vector s. As a result, it is straightforward to check that (10) is neither an ordinal nor exact potential function.
The most closely related results concern the proportional allocation mechanism for allocation of a single divisible good among strategic buyers, studied by Kelly (1997), La and Anantharam (2000), Hajek and Gopalakrishnan (2002), Maheswaran and Basar (2003), Johari and Tsitsiklis (2004). Observe that the quantity w n /p(w) is the "relief" provided to firm n relative to the total demand D, since firm n is asked to supply D − w n /p(w) when the market clears. Suppose we define a virtual divisible good of (N − 1)D units that we interpret as the total relief that will be granted to firms. At the market clearing price, if w n > 0, firm n's relief is: If w n = 0, then firm n receives no relief: it must supply the entire demand D. Thus total relief is allocated to the firms in proportion to their bids. Further, we can define a utility function U n (x n ) for firm n as a function of the relief, by simply negating the cost at the supply D − x n : (Recall that C n (s n ) = 0 for s n ≤ 0.) The payoff to firms when they are price anticipating may then be written: where h n (W ) = W/(N − 1). Note that the last term in the utility does not depend on firm n's bid.
Thus the game firms play when they are price anticipating is strategically equivalent to one where firm n submits a bid w n ; receives a share w n /( m w m ) of the total relief (N − 1)D if w n > 0, and receives zero relief if w n = 0; and pays (1 − 1/(N − 1))w n . This is essentially a proportional allocation mechanism, except that the payment made is scaled by the constant 1 − 1/(N − 1).
Our proof technique for existence and uniqueness of competitive and Nash equilibria is therefore essentially equivalent to similar proofs for the proportional allocation mechanism (such as those by Hajek and Gopalakrishnan (2002) and Maheswaran and Basar (2003)). Our presentation is most closely related to Johari and Tsitsiklis (2004), where existence and uniqueness of Nash equilibria is established via the use of modified utility functions.
Despite the close connection of our supply function bidding game and the proportional allocation mechanism, efficiency loss results for the proportional allocation mechanism from Johari and Tsitsiklis (2004) cannot be directly translated to efficiency loss analysis of our supply function bidding game. Note that the utility functions defined above are negative, while positivity is essential to the efficiency loss analysis by Johari and Tsitsiklis (2004). A strategically equivalent positive However, the ratio of Nash equilibrium aggregate utility to the maximum possible aggregate utility is not directly related to the ratio of Nash equilibrium aggregate cost to the minimum possible aggregate cost. This difference accounts for differing efficiency loss ratios in our subsequent development. Further, our efficiency loss analysis relies heavily on the specific form of the modified cost functionĈ n ; this function is not equivalent to the modified utility function used in the proof of existence and uniqueness of Nash equilibria for the proportional allocation mechanism.

Welfare Loss
We let s * denote an efficient production vector, and let s denote the production vector at a Nash equilibrium. We now ask: what is the welfare loss at the Nash equilibrium? To answer this question, we must compare the cost n C n (s n ) with the cost n C n (s * n ). (We know, of course, that n C n (s n ) ≥ n C n (s * n ) by definition of s * .) The following theorem provides an explicit bound for the welfare loss.
Theorem 2. Assume that N > 2, and suppose that Assumption 1 is satisfied. If s * is any efficient production vector, and s is the production vector at a Nash equilibrium, then: Furthermore, this bound is tight: for every ε > 0 and N > 2, there exists a choice of cost functions C n , n = 1, . . . , N , such that: The preceding theorem shows that in the worst case, aggregate cost rises by no more than a factor 1 + 1/(N − 2) when firms are price anticipating. Furthermore, this bound is essentially tight.
We note that the increase in aggregate production cost, a factor of 1/(N − 2), approaches zero as the number of firms N grows large, even though the firms are price anticipating. This is a form of a competitive limit theorem (Mas-Colell et al. 1995). Competitive limit theorems have been extensively studied, especially in the context of strategic market games (Giraud 2003, Shapley and Shubik 1977, Dubey and Shubik 1978. However, such results typically use a replication approach: starting from K firms, an economy of N K firms is created by replicating each firm N times. As a result, no single firm can be dominant in the limit. By contrast, our result holds even if only a small number of firms continue to remain dominant as N → ∞; i.e., we do not require any symmetry constraints on the cost functions of the firms. In general, in an industry with one large firm and many small firms, we do not expect to achieve full efficiency; nevertheless, the mechanism described in this paper ensures this is the case. In Johari and Tsitsiklis (2004), for the proportional allocation of a divisible good among strategic buyers, it is shown that the worst case efficiency loss when buyers are price anticipating is 25% of the maximum possible aggregate utility. The worst case efficiency loss there is obtained when one buyer receives a constant fraction of the resource, and the remainder of the resource is split into vanishingly small slices among a large collection of buyers. However, in our setting, the total "relief" available to firms scales as (N − 1)D, and each firm can only obtain a relief at most equal to D (cf. the discussion in Section 3). This feature of the mechanism intuitively limits the efficiency loss one firm can create, and provides insight into the decay of efficiency loss to zero as N → ∞.

Price Bounds
In this section we prove two upper bounds on the Nash equilibrium price; since the demand is fixed and inelastic, these will also be upper bounds on the revenue to the firms at a Nash equilibrium.
We restrict attention to settings where at least two firms are active at the Nash equilibrium; by Corollary 1, this is guaranteed if any efficient allocation calls for at least two active producers.
The following theorem compares the price at a Nash equilibrium to the price at a competitive equilibrium.
Theorem 3. Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w ≥ 0 is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) > 0 and S(p(w), w m ) > 0 for at least two firms m, n, m = n. Let w * and µ * denote a competitive equilibrium. Then: The preceding theorem shows the Nash equilibrium price is no more than a factor 1 + 1/(N − 2) above the competitive price level. Note that since the total payment to the firms is p(w)D at the Nash equilibrium, and µ * D at the competitive equilibrium, the same bound holds for the total payment made to the firms.
We can use a similar approach to bound the Lerner index, which we define as follows at a strategy vector w: (We have chosen to define the Lerner index using the right directional derivative of the cost; of course, if the cost functions are differentiable, this choice is inconsequential.) The Lerner index is commonly used to measure the price markup above competitive levels in oligopolies. We bound the index in the following corollary.
Corollary 2. Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w is a Nash equilibrium w ≥ 0 of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) > 0 and S(p(w), w m ) > 0 for at least two firms m, n, m = n. Then: The bounds of this section, together with the welfare loss bounds of the previous section, strongly characterize the performance of the mechanism we have proposed. We note that as in the comment at the end of the preceding section, our bounds on prices show convergence to the competitive price level as the number of firms approaches infinity. This limit holds even in the absence of symmetry between the firms.

A Characterization Theorem
In this section, we provide a positive characterization of the market mechanism studied in this paper. Our presentation is inspired by a related result derived for a mechanism where consumers submit demand functions to a market that allocates a resource with inelastic supply, reported in Johari and Tsitsiklis (2008). In that paper, we showed that among all mechanisms satisfying certain reasonable assumptions, the bidding mechanism considered minimizes the worst case efficiency loss at a Nash equilibrium. In this paper, we present a corresponding result which demonstrates that within a reasonable class of market mechanisms that use parameterized supply functions, the one studied in this paper yields the lowest possible worst case welfare loss at Nash equilibrium. Since the argument is closely related to that in Johari and Tsitsiklis (2008), we omit the details of the proof; they can be found in Johari (2004). Nevertheless, as we describe below, this characterization result differs from the result obtained in Johari and Tsitsiklis (2008).
For the purposes of this section, we let C denote the set of all cost functions that satisfy Assumption 1; i.e., C = C : R → R + | C is continuous on R, strictly increasing, and convex on R + , and C(s) = 0 for s ≤ 0}.
We begin by defining the class of market mechanisms we will study in this section. We let p S (w) denote this solution.
2. For all C ∈ C, a firm's payoff is concave if the firm is price taking; that is, for all p > 0 the function: is concave for w ≥ 0.
3. For all C n ∈ C, a firm's payoff is concave if the firm is price anticipating; that is, for all w −n ∈ (R + ) N −1 , the function: is concave in w n > 0 if w −n = 0, and concave in w n ≥ 0 if w −n = 0.
4. The function S is uniformly less than or equal to D; i.e., for all p > 0 and w ≥ 0, S(p, w) ≤ D. Given any S ∈ S(D, N ), we interpret the resulting market mechanism as follows: each firm n chooses a parameter w n , thus specifying a supply function S(·, w n ), and the market clears according to p S (w). This determines the production, and hence the profit, of each firm-just as for the mechanism developed in Section 3.
We now briefly discuss each of the assumptions in Definition 1. The first assumption ensures that a unique market-clearing price exists; without this assumption, firms may not have a unique prediction of the market outcome given a strategic decision they make. The second and third conditions ease characterization of equilibria in terms of only first order conditions. The second condition allows us to characterize competitive equilibria in terms of only first order conditions, as in the proof of Theorem 5. The third condition allows us to characterize Nash equilibria in terms of only first order conditions, a property we exploited in the proof of Theorem 1; indeed, at least quasiconcavity is generally used to guarantee existence of pure strategy Nash equilibria in games with continuous action spaces (Fudenberg and Tirole 1991). The fourth condition forces the declared supply to be no larger than D; this is a reasonable assumption when demand is deterministically known in advance, as we have assumed. Finally, the fifth condition is a "full range" assumption: it ensures that firms always have a strategic choice available to declare any supply between [0, D], given the eventual market-clearing price p. This condition would be necessary to ensure that welfare maximization is possible; otherwise, for some choices of cost functions, no choice of w could achieve the efficient outcome.
This class of market mechanisms generalizes the supply function interpretation of the mechanism discussed in Section 3. According to (4) Our interest is in the worst-case ratio (over C 1 , . . . , C N ∈ C) of aggregate cost at any Nash equilibrium to minimal aggregate cost, defined as the solution to (1)-(3). Formally, for S ∈ S(D, N ) we define a constant ρ(D, N, S) as follows: s solves (1)-(3), and w is a Nash equilibrium Note that since any cost function satisfying Assumption 1 is strictly increasing and nonnegative, and D > 0, N n=1 C n (s n ) is strictly positive at any optimal solution s to (1)-(3). However, Nash equilibria may not exist for some cost function choices C 1 , . . . , C N ; in this case we set ρ(D, N, S) = ∞. We have the following theorem; as discussed above, the proof is related to that for Theorem 1 in Johari and Tsitsiklis (2008), and full details of the argument can be found in Johari (2004) We now briefly comment on the relationship between this result and the result obtained in Johari and Tsitsiklis (2008), where the authors consider the allocation of a divisible good among strategic buyers. It is shown that the proportional allocation mechanism (cf. Section 3) minimizes the worst case efficiency loss when users are price anticipating, among all market-clearing mechanisms satisfying a set of conditions similar (though weaker) than those in Definition 1. In some sense, that theorem obtains a slightly stronger result than our result in this paper: in particular, Johari and Tsitsiklis (2008) obtain an explicit characterization of all mechanisms in the class they study; in part, this is due to the fact that they study mechanisms which are well defined for any quantity of resource and number of users. By contrast, in our setting the mechanisms we consider explicitly depend on the amount of resource available. Further, since our efficiency loss result in Theorem 2 depends explicitly on the number of firms, we consider a class of mechanisms in Definition 1 where the number of firms is fixed. Both these features require a slightly different argument than that in Johari and Tsitsiklis (2008), though of course the results share a common heritage.
The preceding theorem establishes that, at least within the class S(D, N ), the choice S(p, w) = D − w/p that we have studied in this paper is in some sense "optimal": it minimizes the worst case welfare loss over all mechanisms in S(D, N ). Note that in the third result of the theorem, we find that all mechanisms in S(D, N ) are actually independent of N . Thus our chosen mechanism from (4) is actually worst-case optimal for any number of firms N .
This result has two major caveats. First, there are strong concavity restrictions imposed for mathematical tractability; removing these remains a direction for future research. Second, and perhaps more undesirable from a practical standpoint, is the eventual deduction that any mechanism in S(D, N ) has the possibility of "negative supply" out of equilibrium-i.e., a firm being asked to purchase the good, rather than supply it. (This follows from the characterization in part 3 of the theorem.) We address this issue in the following section.

Negative Supply
One undesirable feature of the parameterized supply functions we have chosen is that they allow for nonequilibrium outcomes in which a firm may have a negative supply. While we have shown that the supply of each firm is nonnegative at both the competitive equilibrium and at the Nash equilibrium, nonequilibrium bidding may lead to negative supply to some firms. In practical terms, this implies that firms may be asked to buy the good when the market clears, even if they have no intention or ability to do so.
A natural question, therefore, is whether a reasonable parametric class of supply functions can be designed with properties similar to those we have already proven, but where the supply functions are uniformly nonnegative. Our first result, in Section 7.1, will demonstrate this is not possible in general. However, if we enforce a finite "maximum liability" for each firm, then we can use the same mechanism as that described earlier in the paper to achieve good market performance; we discuss such an approach in Section 7.2.

Nonnegative Parameterized Supply Functions
In this section, we will consider parameterized supply functions S that are uniformly nonnegative, and for which the payoffs to market participants are concave when they are price anticipating.
These are formalized in the following definition; recall the definition of C in (16). We let p S (w) denote this solution.
3. For all C n ∈ C, a firm's payoff is concave if the firm is price anticipating; that is, for all w −n ∈ (R + ) N −1 , the function: is concave in w n > 0 if w −n = 0, and concave in w n ≥ 0 if w −n = 0.
Note that Condition 1 in the preceding definition is identical to Condition 1 in Definition 1, and Condition 2 in the preceding definition is identical to Condition 3 in Definition 1. The key difference is that in addition to these two conditions, we only have one simple constraint: the parameterized supply functions must be nonnegative. We have the following result.
Proposition 1. Fix N > 0 and D > 0. Let S ∈ S + (D, N ). Let C = (C 1 , . . . , C N ), and C = (C 1 , . . . , C N ) be two collections of cost functions such that C n , C n ∈ C for all n. If w is a Nash equilibrium when the firms have costs given by C, then w is also a Nash equilibrium when the firms have costs given by C.
The preceding result is disconcerting: clearly, any mechanism satisfying the conditions of the proposition can have arbitrarily high welfare loss, as well as an arbitrarily high markup above the competitive price, when firms are price anticipating. In the next section, we consider an alternate method by which we can address the problem of negative supply.

Maximum Liability
In this section we consider a simple modification to the basic model which protects firms from large payments due to having to buy some of the product (i.e., if they have negative supply) at a nonequilibrium outcome.
We continue to assume that S(p, w n ) and the market-clearing price p(w) are defined as before, i.e., S(p, w n ) = D − w n /p. We fix a maximum liability W > 0, such that no firm will ever have to pay more than W when the market is cleared. Thus, if p(w)S(p(w, w n ) < −W , then firm n only pays W to the market manager. Formally, the payoff of firm n now becomes: One interpretation of this game is as follows. Each firm submits a "deposit" of W to the market manager. The game is then played as before, and the market manager clears the market. At the resulting allocation, any required payment higher than W by a firm is forgiven.
We have the following proposition.
Proposition 2. Assume that N > 2, and W > 0. Suppose also that Assumption 1 is satisfied.
Then w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) if and only if w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ).
While this extension to the game is appealing from a market implementation point of view, we must be careful in interpreting the preceding result. Suppose that w is a strategy vector where p(w)S(p(w), w n ) < −W ; in particular, S(p(w), w n ) < 0. In this case we will have m =n S(p(w), w m ) > D-that is, the remaining firms will be producing excess supply. In an economy with free disposal, this does not pose any problem; but if free disposal fails, then the market mechanism is problematic. 2 Furthermore, we note that if the maximum liability rule is implemented, then the market operator effectively subsidizes the misalignment of supply and demand; the total payment received from the demand side of the market is insufficient to compensate those suppliers that deliver positive supply. In general, then, addressing the possibility of negative supply when w is out of equilibrium remains an important implementation-dependent issue.

Conclusion
We have considered a resource allocation problem where multiple suppliers compete to meet an inelastic demand. We present a novel investigation of a fundamental issue in mechanism design: how much strategic flexibility should players be given to ensure successful market performance?
In our model, we restrict attention to uniform price market-clearing mechanisms. We demonstrate in this paper that by using a properly chosen class of supply functions parameterized by a single scalar, both high efficiency and low price markups can be guaranteed.
In addition to the analysis carried out here, we have extended the model and market mechanism to include the possibility that demand may be stochastic. Due to space constraints, we have deferred discussion of this extension to Section B in the e-companion. We demonstrate there that the welfare loss result of Section 4 carries over even to a setting where demand is inelastic but stochastically determined, by showing that in such an instance it is as if firms play a game with deterministic demand but different cost functions.

A.1. Competitive Equilibrium
In this subsection, we consider firms that act as price takers; we will verify a straightforward result, that the second fundamental welfare theorem holds for the mechanism we are considering. While this is a standard result, its proof will guide our study of existence and uniqueness of a Nash equilibrium in Theorem 1.
A pair (w, µ) where w ≥ 0 and µ > 0 is a competitive equilibrium if firms maximize their payoff as defined in (7), and the market is cleared by setting the price µ according to (5): P n (w n ; µ) ≥ P n (w n ; µ) for w n ≥ 0, n = 1, . . . , N ; When firms are price takers, there exists a competitive equilibrium, and the resulting allocation is efficient (i.e., an optimal solution to (1)- (3)). This is formalized in the following theorem.
Proof. We use a standard approach for quasilinear environments: the key idea in the proof is to use Lagrangian techniques to establish that the equilibrium conditions (18)-(19) are identical to the optimality conditions for (1)- (3), under the identification s n = S(µ, w n ) for each n.
Step 1: Given µ > 0, w satisfies (18) if and only if w n ∈ [0, µD] for all n, and: To see that these conditions are necessary and sufficient, first note that firm n would never bid more than µD when the price is µ. If w n > µD, then S(µ, w n ) < 0, so the payoff P n (w n ; µ) becomes negative; on the other hand, P n (µD; µ) = 0. Thus if w n satisfies (18) for firm n, then w n ∈ [0, µD].
To complete the proof, we note only that convexity of C n implies concavity of P n ; and thus w n satisfies (18) if and only if w n ∈ [0, µD], and w n satisfies the optimality conditions (20)-(21).
Step 2: There exists a vector s ≥ 0 and a scalar µ > 0 such that: The vector s is then an optimal solution to (1)-(3). At least one optimal solution to (1)- (3) exists since the feasible region is compact and the objective function is continuous. We form the Lagrangian: Here the second term is a penalty for the demand constraint. A standard constraint qualification (Bertsekas 1999, Section 5.2) holds for (1) there exists at least one pair (s, µ) satisfying (22)-(24). We see that µ > 0 from (22), since s n > 0 for at least one firm n.
Step 5: Completing the proof. By Steps 2 and 3, there exists a vector w and a scalar µ > 0 satisfying (18)-(19); by Steps 2 and 4, the vector s defined by s n = S(µ, w n ) is efficient.
Proof. The proof proceeds in a number of steps. We first show that at a Nash equilibrium, at least two components of w must be positive. This suffices to show that the payoff function Q n is concave and continuous for each firm n. We use these properties to show no Nash equilibrium exists if N = 2, and then restrict attention to the case N > 2. We then establish necessary and sufficient conditions for w to be a Nash equilibrium; these conditions look similar to the optimality conditions (20)-(21) in the proof of Theorem 5, but for "modified" cost functions defined according to (13). Mirroring the proof of Theorem 5, we then show the correspondence between these conditions and the optimality conditions for the problem (10)-(12). This correspondence establishes existence of a Nash equilibrium, and uniqueness of the resulting allocation.
Step 1: If w is a Nash equilibrium, then at least two coordinates of w are positive. Fix a firm n, and suppose w m = 0 for every m = n. The payoff to firm n is then: The first expression follows by noting that when w n = 0 (so that w = 0), we have p(w) = 0, while S(p(w), w n ) = D for firm n. (Recall the convention (6) that S(0, 0) = D.) For the second expression, note that when w n > 0, we have the inequality S(p(w), w n ) = D − (N − 1)D ≤ 0, so C(S(p(w), w n )) = 0. We now see that when w n = 0, firm n can profitably deviate by increasing w n infinitesimally (since C n (D) > 0); on the other hand, when w n > 0, firm n can profitably deviate by infinitesimally decreasing w n . Thus no Nash equilibrium exists with m =n w m = 0. Since this holds for every firm n, we conclude that at least two coordinates of w must be positive.
Step 2: If the vector w ≥ 0 has at least two positive components, then the function Q n (w n ; w −n ) is concave and continuous in w n , for w n ≥ 0. When m =n w m > 0, from (9) we have: Indeed, when m =n w m > 0, the function w n /(w n + s =r w s ) is a strictly concave function of w n (for w n ≥ 0). Since C n was assumed to be convex and nondecreasing (and hence continuous), it follows that Q n (w n ; w −n ) is concave and continuous in w n for w n ≥ 0.
Step 3: If N = 2, then no Nash equilibrium exists. Suppose that (w 1 , w 2 ) is a Nash equilibrium.
Then by Step 1, w 1 > 0 and w 2 > 0; and by Step 2, in this case the payoff to firm 1 as a function of w 1 ≥ 0 is: The preceding expression is strictly increasing in w 1 , so (w 1 , w 2 ) could not have been a Nash equilibrium. Thus no Nash equilibrium exists if N = 2.
Based on the preceding step, for the remainder of the proof, we will assume that N > 2.
Step 4: The vector w is a Nash equilibrium if and only if at least two components of w are positive, and for each n, w n ∈ [0, ( m =n w m )/(N − 2)] and the following conditions hold: Let w be a Nash equilibrium. By Steps 1 and 2, w has at least two positive components and Q n (w n ; w −n ) is concave and continuous for w n ≥ 0. We first observe that we must have w n ≤ ( m =n w m )/(N − 2); if not, then S(p(w), w n ) < 0, and by arguing as in Step 1 of the proof of Theorem 5 we can show that firm n can profitably deviate by choosing w n = ( m =n w m )/(N − 2).
Thus w n must maximize Q n (w n ; w −n ) over 0 ≤ w n ≤ ( m =n w m )/(N − 2), and satisfy the following first order optimality conditions: Recalling the expression for p(w) given in (5), after multiplying through by p(w) the preceding optimality conditions become: We now note that by definition, we have: Substituting into (27)-(28) and simplifying yields (25)-(26).
Conversely, suppose that w has at least two strictly positive components, that 0 ≤ w n ≤ ( m =n w m )/(N − 2), and that w satisfies (25)-(26). Then we may simply reverse the argument: by Step 2, Q n (w n ; w −n ) is concave and continuous in w n ≥ 0, and in this case the conditions (25)- (26) imply that w n maximizes Q n (w n ; w −n ) over 0 ≤ w n ≤ ( m =n w m )/(N − 2). Since we have already shown that choosing w n > ( m =n w m )/(N − 2) is never optimal for firm n, we conclude w is a Nash equilibrium.
If we let µ = p(w), note that the conditions (25)-(26) have the same form as the optimality conditions (20)- (21), but for a different cost function given byĈ n . We now use this relationship to complete the proof in a manner similar to the proof of Theorem 5.
Step 5: The functionĈ n (s n ) defined in (13) is continuous, and strictly convex and strictly increasing over s n ≥ 0, withĈ n (s n ) = 0 for s n ≤ 0. Since C n (s n ) = 0 for s n ≤ 0, it follows thatĈ n (s n ) = 0 for s n ≤ 0. For s n ≥ 0, we simply compute the directional derivatives ofĈ n : ∂ +Ĉ n (s n ) ∂s n = 1 + s n (N − 2)D ∂ + C n (s n ) ∂s n ; Since C n is strictly increasing and convex, for 0 ≤ s n < s n we will have: This guarantees thatĈ n is strictly increasing and strictly convex over s n ≥ 0.
Step 6: There exists a unique vector s ≥ 0 and at least one scalar ρ > 0 such that: 1 + s n (N − 2)D The vector s is then the unique optimal solution to (10)-(12). By Step 5, sinceĈ n is continuous and strictly convex over the convex, compact feasible region for each n, we know that (10)- (12) have a unique optimal solution s. As in the proof of Theorem 5, there exists a Lagrange multiplier ρ such that (s, ρ) satisfy the stationarity conditions (29)-(30), together with the constraint (31).
The fact that ρ > 0 follows from (29), since at least one s n is positive.
Step 7: If s ≥ 0 and ρ > 0 satisfy (29)-(31), then the vector w defined by w n = (D − s n )ρ is a Nash equilibrium. First observe that with this definition, together with (31) and the fact that s n ≥ 0, we have w n ≥ 0 for all n. Furthermore, since s n ≥ 0, of course we have (1 + 1/(N − 2))s n ≥ 0; it is thus straightforward to check that we have: Finally, at least two components of w are strictly positive, since otherwise we have s n 1 = s n 2 = D for some n 1 = n 2 , in which case n s n > D, which contradicts (31).

By
Step 4, to check that w is a Nash equilibrium, we must only check the stationarity conditions (25)-(26). We simply note that under the identification w n = (D − s n )ρ, using (31) we have that: ρ = n w n (N − 1)D = p(w); and s n = D − w n ρ = S(ρ, w n ).
Step 8: If w is a Nash equilibrium, then there exists a scalar ρ > 0 such that the vector s defined by s n = S(p(w), w n ) satisfies (29)-(31). We simply reverse the argument of Step 7. Since w is a Nash equilibrium, by Step 1 n w n > 0, so p(w) > 0; thus n s n = D, i.e., (31) is satisfied. By Step 4, w satisfies (25)-(26). We now consider two possibilities. First suppose that 0 ≤ s n < D for all n; then let ρ = p(w). In this case ρ > 0 and 0 < w n ≤ ( m =n w m )/(N − 2) for all n, so (25)- (26) become equivalent to (29)-(30). On the other hand, suppose that s n = D for some n; then s m = 0 for all m = n. We define ρ by: ∂s n .
Note that again, we have ρ > 0. We now argue as in Step 4 of the proof of Theorem 5. By combining (26) with the definition of ρ, we see that (30) is satisfied. Finally, since s m > 0 only for m = n, we combine (25) with the fact that ∂ − C n (s n ) ≤ ∂ + C n (s n ) (by convexity) to see that (29) holds, as required.
Step 9: There exists a Nash equilibrium w, and for any Nash equilibrium w the vector s defined by s n = S(p(w), w n ) is the unique optimal solution of (10)-(12). This conclusion is now straightforward. Existence follows by Steps 6 and 7. Uniqueness of the resulting production vector s, and the fact that s is an optimal solution to (10)-(12), follows by Steps 6 and 8. 2

A.3. Corollary 1
Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w is a Nash equilibrium w ≥ 0 of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) = D, and S(p(w), w m ) = 0 for m = n. Then the Nash equilibrium production vector is efficient.
Proof. If w is a Nash equilibrium at which only firm n produces, then from (25)-(26), we have: But now define µ as: Then the vector s defined by s n = S(p(w), w n ) and the multiplier µ satisfy (22)-(24), and by Step 2 of the proof of Theorem 5, s is an efficient allocation. 2

A.4. Theorem 2
Assume that N > 2, and suppose that Assumption 1 is satisfied. If s * is any efficient production vector, and s is the production vector at a Nash equilibrium, then: Furthermore, this bound is tight: for every ε > 0 and N > 2, there exists a choice of cost functions C n , n = 1, . . . , N , such that: Proof. We exploit the structure of the modified cost functionsĈ n to prove the result. Let G n (s n ) = sn 0 C n (z) dz. Then by our assumptions on C n , G n is a convex, continuous, nondecreasing function for s n ≥ 0, with G n (0) = 0. Convexity of G n implies that for s n ≥ 0, we have: Since G n (0) = 0, we conclude that for s n ≥ 0 we have s n C n (s n ) − G n (s n ) ≥ 0; from the definition of C n in (13), we conclude thatĈ n (s n ) ≥ C n (s n ) for s n ≥ 0. This yields: On the other hand, notice that for s n ≥ 0, we have G n (s n ) ≥ 0. Thus for 0 ≤ s n ≤ D, we have: This yields: Since s is an optimal solution to (10)-(12), we know that nĈ n (s n ) ≤ nĈ n (s * n ). Combining this inequality with (34) and (35) yields the bound (14).
It remains to show that the bound is tight, i.e., that (15) holds; we prove this via an example.
We fix D > 0, and assume we are given N > 2. Choose t such that D/N < t < D, and choose δ such that 0 < δ < 1. Consider the following cost functions: C n (s n ) = αs n , n = 2, . . . , N, Thus C 1 is piecewise linear, and C n is linear for n = 2, . . . , N . It is straightforward to check that t > D/N implies α > 1; thus, the unique optimal solution to (1)-(3) is given by s * 1 = D, s * n = 0 for n = 2, . . . , N , and we have n C n (s * n ) = D − t + δt.

A.5. Theorem 3
Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w ≥ 0 is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) > 0 and S(p(w), w m ) > 0 for at least two firms m, n, m = n. Let w * and µ * denote a competitive equilibrium. Then: Proof. Since w ≥ 0 and at least two firms m, n have positive supply at the equilibrium, any firm r with S(p(w), w r ) > 0 must satisfy S(p(w), w r ) < D, and thus w r > 0. By (26), for any firm r that has w r > 0, we have: Since S(p(w), w r ) ≤ D, we conclude that for all r: We now claim there must exist at least one firm k such that S(µ * , w * k ) > 0 and S(µ * , w * k ) ≥ S(p(w), w k ). If not, then: a contradiction. Since S(µ * , w * k ) > 0, we know w * k < µ * D; thus, by (20), we have: Finally, since S(µ * , w * k ) ≥ S(p(w), w k ), by Assumption 1 we have: If we combine (36) (with r = k), (37), and (38), then we find: A.6. Corollary 2 Assume that N > 2, and suppose that Assumption 1 is satisfied. Suppose that w is a Nash equilibrium w ≥ 0 of the game defined by (Q 1 , . . . , Q N ) such that S(p(w), w n ) > 0 and S(p(w), w m ) > 0 for at least two firms m, n, m = n. Then: Proof. Under the assumptions of the corollary, we showed (36) holds for all firms r in the proof of Theorem 3. Rearranging terms yields the bound in the corollary. 2 A.7. Proposition 1 Fix N > 0 and D > 0. Let S ∈ S + (D, N ). Let C = (C 1 , . . . , C N ), and C = (C 1 , . . . , C N ) be two collections of cost functions such that C n , C n ∈ C for all n. If w is a Nash equilibrium when the firms have costs given by C, then w is also a Nash equilibrium when the firms have costs given by C.
Proof. Our proof proceeds by showing that for any such mechanism, the revenue to a firm is nondecreasing, and the production cost of the firm is nonincreasing, as w n increases. First fix any vector w −n . By choosing C n (s n ) = α n s n , and considering limits where α n → 0 and α n → ∞ respectively, we conclude from Condition 2 in Definition 2 that: (1) the revenue p S (w)S(p S (w), w n ) to firm n must be concave in w n ; and (2) the production S(p S (w), w n ) of firm n must be convex in w n . By Condition 3 in Definition 2, both p S (w)S(p S (w), w n ) and S(p S (w), w n ) are nonnegative.
Any concave nonnegative function must be nondecreasing, and thus the revenue p S (w)S(p S (w), w n ) is nondecreasing in w n . On the other hand, since p S (w) is the market-clearing price, by definition S(p S (w), w n ) is uniformly bounded above by D as w n varies. Any convex nonnegative function which is uniformly bounded above must be nonincreasing, and thus the production S(p S (w), w n ) is nonincreasing in w n ; hence the production cost is nonincreasing in w n as well.
Recall that the profit of a firm is revenue minus production cost; we have shown that the revenue is nondecreasing in w n , and the production cost is nonincreasing in w n . It follows that a vector w is a Nash equilibrium if and only if for each n, w n has been chosen such that the revenue to the firm has been maximized and the production cost to the firm has been minimized. In other words, w is a Nash equilibrium if and only if for all n and all w n ≥ w n , there holds: p S (w)S(p S (w), w n ) = p S (w n , w −n )S(p S (w n , w −n ), w n ) and S(p S (w), w n ) = S(p S (w n , w −n ), w n ).
Since these conditions do not involve the costs C n , the result follows. 2

A.8. Proposition 2
Assume that N > 2, and W > 0. Suppose also that Assumption 1 is satisfied. Then w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) if and only if w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ).
Proof. The proof technique uses the fact that any firm n can always guarantee itself Q n (w n ; w −n ) > −W , given the value of w −n . To see this, first suppose that m =n w m > 0. Then if w n = ( m =n w m )/(N − 2), we will have Q n (w n ; w −n ) = 0 (as shown in Step 1 of the proof of Theorem 1). On the other hand, if m =n w m = 0, then for sufficiently small w n > 0, we will have Q n (w n ; w −n ) > −W ; this also follows by Step 1 of the proof of Theorem 1.
Thus, suppose that w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ); then we have Q n (w n ; w −n ) > −W . If w is not a Nash equilibrium for the game defined by (Q 1 , . . . , Q N ), then there exists a firm n and w n ≥ 0 such that Q n (w n ; w −n ) > Q n (w n ; w −n ). It follows that Q n (w n ; w −n ) > −W , so that w n is a profitable deviation for firm n in the game defined by (Q 1 , . . . , Q N )-a contradiction. Thus w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ).
Conversely, suppose that the vector w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ).
Then we must have Q n (w n ; w −n ) > −W for all n, so that Q n (w n ; w −n ) = Q n (w n ; w −n ). An argument similar to the preceding paragraph then shows that w is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ). 2

Appendix B: Stochastic Demand
In this section we extend our basic model to include the possibility that demand is stochastic. If demand is stochastic, but known before bids are submitted, then the bidding game is identical to the one studied in the main paper; as discussed in Section 2, such a model might arise if firms have access to accurate demand forecasts, and if they are able to submit a distinct bid per future period. By contrast, in this section we consider a generalization of the model in the main paper, where demand is unknown at the time that the firms submit their parameters w n . The model we consider Suppose that N firms compete for demand D, where 0 ≤ D ≤ D max , with distribution P We define an allocation in terms of the fractions allocated to each firm, rather than the absolute amount of resource allocated. Thus our welfare benchmark is now a second-best benchmark, where the social planner is forced to choose the fractional allocation of demand prior to the realization of demand. Formally, we will compare the expected cost at a Nash equilibrium to the minimum expected cost in the following problem: minimize n E[C n (π n D)] subject to n π n = 1; (40) π n ≥ 0, n = 1, . . . , N.
Notice that this problem chooses the fractions π n allocated to each resource optimally ex ante; that is, before the true demand has been realized.
Our key insight in analyzing this model is that stochastic demand is equivalent to a model with deterministic demand D = 1, for an appropriate choice of cost functions. Formally, for each firm n, define C n as follows: C n (π n ) = E[C n (π n D)].
We have the following proposition.
Proposition 3. Suppose that Assumption 1 is satisfied by the cost functions C 1 , . . . , C N . Then Assumption 1 is also satisfied by the cost functions C 1 , . . . , C N .
Proof. Observe that C n (π n ) = 0 for π n ≤ 0, since C n satisfies Assumption 1. We next show that C n is continuous. Suppose that π k n → π n as k → ∞. Then C n (π k n D) → C n (π n D) as k → ∞ for 0 ≤ D ≤ D max . Since C n (s n ) is nonnegative and nondecreasing, there exists ε > 0 such that for sufficiently large k we have 0 ≤ C n (π k n D) ≤ C n (π n D max + ε). Thus we can apply the bounded convergence theorem to conclude that as k → ∞, E[C n (π k n D)] → E[C n (π n D)]. Thus C n is continuous.
Since C n is strictly increasing, for D > 0 we have C n (π 1 n D) > C n (π 2 n D). Taking expectations shows that C n (π n ) is strictly increasing for π n ≥ 0 (since E[D] > 0). 2 The preceding proposition allows us to extend the main results of Sections 3 and 4 to the setting of stochastic demand. For example, it is straightforward to show that there exists an optimal solution to (39)-(41), and that all such solutions are identified by solutions to (1)-(3) with cost functions C 1 , . . . , C N and demand D = 1.
We use an analogue of the pricing mechanism developed in Section 3. First, each firm n chooses a parameter w n . Next, the demand D is realized. The market manager then takes as input the supply function S(p, w n ) = D − w n /p for each firm n, and clears the market by choosing p(w) according to (5). Note that when a firm n chooses a parameter w n , it is still as if the firm has chosen the supply function D − w n /p; but now the supply function depends on the eventual realization of the demand D. The payoff to each firm is then the expected profit. Since we focus on price anticipating firms in this section, we redefine their payoff explicitly in terms of the strategy vector w. Formally, by substituting using (4) and (5), the payoff to firm n is given by: If we substitute C n (π n ) = E[C n (π n D)] (cf. (42)), then we have: Now observe that Q n (w n ; w −n ) is identical to the payoff Q n (w n ; w −n ) if we substitute the cost function C n and demand D = 1 in the definition (9). From this observation, it follows that there exists a Nash equilibrium for the game defined by (Q 1 , . . . , Q N ), and further, that w is a Nash equilibrium of this game if and only if it is a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) when the cost function of each firm n is C n and the demand is D = 1. This correspondence and Theorem 2 imply a bound on efficiency loss for the game with stochastic demand: in particular, the aggregate cost at a Nash equilibrium of the game defined by (Q 1 , . . . , Q N ) is no worse than a factor 1 + 1/(N − 2) larger than the aggregate cost at an optimal solution to (39)-(41).
Note that we require the demand D to be a random variable with compact support [0, D max ]. In fact, it is clear from the proof of Proposition 3 that the key requirement is that C n (π n D) must be integrable for π n ≥ 0. But this is only possible if D has bounded support; otherwise, by choosing a cost function C n which approaches infinity rapidly enough, we can guarantee that E[C n (π n D)] = ∞.
Thus if we want to ensure that C n (π n ) is finite whenever C n satisfies Assumption 1, the random variable D must have bounded support.