Open versus closed loop capacity equilibria in electricity markets under perfect and oligopolistic competition

We consider two game-theoretic models of the generation capacity expansion problem in liberalized electricity markets. The first is an open loop equilibrium model, where generation companies simultaneously choose capacities and quantities to maximize their individual profit. The second is a closed loop model, in which companies first choose capacities maximizing their profit anticipating the market equilibrium outcomes in the second stage. The latter problem is an equilibrium problem with equilibrium constraints. In both models, the intensity of competition among producers in the energy market is frequently represented using conjectural variations. Considering one load period, we show that for any choice of conjectural variations ranging from perfect competition to Cournot, the closed loop equilibrium coincides with the Cournot open loop equilibrium, thereby obtaining a ‘Kreps and Scheinkman’-like result and extending it to arbitrary strategic behavior. When expanding the model framework to multiple load periods, the closed loop equilibria for different conjectural variations can diverge from each other and from open loop equilibria. We also present and analyze alternative conjectured price response models with switching conjectures. Surprisingly, the rank ordering of the closed loop equilibria in terms of consumer surplus and market efficiency (as measured by total social welfare) is ambiguous. Thus, regulatory approaches that force marginal cost-based bidding in spot markets may diminish market efficiency and consumer welfare by dampening incentives for investment. We also show that the closed loop capacity yielded by a conjectured price response second stage competition can be less or equal to the closed loop Cournot capacity, and that the former capacity cannot exceed the latter when there are symmetric agents and two load periods.     

Optimal design of a manpower system

An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619.     

Average shadow price and equilibrium price: A case study of tradable pollution permit markets

Shadow prices indicate implicit values of limited resources at the margin and provide important information in decision making for resource management. In continuous economic models, shadow prices associated with demand-supply balance constraints represent consumers’ willingness to pay and producers’ marginal cost, hence they correspond to market equilibrium prices. As well known, however, marginal analysis fails in the case of discrete optimization, such as mixed integer programming. An alternative concept has been introduced in the literature to measure the value of an extra unit of a limited resource in such cases. This concept is based on average rather than marginal values, thus called the average shadow price, and interpreted in the same way as conventional shadow prices. Whether average shadow prices in a discrete economic model can serve as market equilibrium prices has not been addressed in the related literature. The present paper addresses this issue in an empirical setting. Using a tradable pollution permit market as an example, where firms’ YES/NO type technology adoption decisions are represented by binary variables, we show that the average shadow price of tradable permits can be interpreted as the equilibrium price only when certain conditions related to the cost structure and emission levels hold. On the other hand, we show that an iterative procedure based on individual firms’ cost minimizing behavior presents a better approach for finding a price that can eliminate or reduce the gap between demand and supply of permits in the market.     

Consumption–investment strategies with non-exponential discounting and logarithmic utility

In this paper, we revisit the consumption–investment problem with a general discount function and a logarithmic utility function in a non-Markovian framework. The coefficients in our model, including the interest rate, appreciation rate and volatility of the stock, are assumed to be adapted stochastic processes. Following Yong (2012a,b)’s method, we study an N-person differential game. We adopt a martingale method to solve an optimization problem of each player and characterize their optimal strategies and value functions in terms of the unique solutions of BSDEs. Then by taking limit, we show that a time-consistent equilibrium consumption–investment strategy of the original problem consists of a deterministic function and the ratio of the market price of risk to the volatility, and the corresponding equilibrium value function can be characterized by the unique solution of a family of BSDEs parameterized by a time variable.     

基于改进的粒子群算法求解供应链网络均衡问题

传统的供应链求解方法为投影法,针对其要对投影进行计算,十分复杂的缺点,提出用改进的粒子群算法求解供应链均衡问题,利用动态异步调整学习因子来有效的提高了算法搜索能力与精度。本文介绍了供应链网络均衡问题转变为无约束优化问题的方法,然后用改进的粒子群优化算法进行求解。通过四个数值算例,将实验结果与标准粒子群算法、蜂群算法、学习因子同步变化的粒子群算法进行比较,验证了改进的粒子群优化算法在解决供应链网络均衡问题中的有效性与优越性,为供应链网络求解提供了一种新的方法。     

A stability conjecture on bandwidth sharing networks

We consider a queueing model where documents are simultaneously transferred over a communication network. The bandwidth allocated to each document transfer is assumed to be the solution of a utility optimization problem. Under a natural stability condition and under the assumption that document arrivals are Poisson and that document sizes are independent exponential distributions, such queueing models have been proven to be positive recurrent. It has been conjectured for a decade that the assumption of exponentially distributed documents can be removed. There exist numerous generalizations without this exponential assumption, but a general proof remains elusive.     

Linking energy system and macroeconomic growth models

We compare two alternative approaches for coupling macroeconomic growth models (MGM) and energy system models (ESM). The hard-link approach integrates the techno-economics of the ESM completely into the MGM and solves one highly complex optimisation problem. The soft-link leaves the two models separate and energy supply functions are integrated into the MGM that are derived from the optimal solution of the ESM. The energy supply functions relate the price of energy computed with the ESM to the quantity of energy computed with the MGM. An iterative process exchanges price-quantity information between the models. Hence, the soft-link leads to an energy market equilibrium. But energy supply functions do not consider variable interest rates that influence the energy supply functions. This is due to the fact that ESMs are partial models that assume an exogenous interest rate; however the interest rate is computed endogenously in MGMs. This missing interaction leads to a capital market dis-equilibrium in the soft-link compared to the hard-link approach inducing a mis-allocation of investments. Extending the soft-link approach by also considering the time variable interest rate of the MGM does not improve the results. Though the computational complexity is greater the hard-link approach assures simultaneous energy and capital market equilibrium. We would like to thank Leonardo Barreto, Christoph Boehringer, Valentina Bosetti, Elmar Kriegler, Marian Leimbach, Kai Lessmann, Emanuele Massetti, Massimo Tavoni, Hal Turton and Alexander Wokaun for discussions of an earlier draft. Christian Flachsland found many typos and better formulations. All remaining errors are ours.     

Optimal supplier choice with discounting

This paper investigates a model for pricing the demand for a set of goods when suppliers operate discount schedules based on total business value. We formulate the buyers's decision problem as a mixed binary integer program, which is a generalization of the capacitated facility location problem (CFLP). A branch and bound (BnB) procedure using Lagrangean relaxation and subgradient optimization is developed for solving large-scale problems that can arise when suppliers’ discount schedules contain multiple price breaks. Results of computer trials on specially adapted large benchmark instances of the CFLP confirm that a sub-gradient optimization procedure based on Shor and Zhurbenko's r-algorithm, which employs a space dilation in the direction of the difference between two successive subgradients, can be used efficiently for solving the dual problem at any node of the BnB tree.     

Two-level periodic marketing networks without market news

A model is constructed for a two-level periodic marketing network wherein traders buy goods from farmers in a number of spatially separated markets and transport them to urban centers for sale to consumers. It is assumed that there is no market news dissemination. As a result, market disturbances are transmitted throughout the network at a rate limited by the trading activity. Moreover, distant markets may even be isolated from local disturbances. This model possesses one and only one equilibrium state. That equilibrium state is asymptotically stable if the slopes of the various supply and demand functions are sufficiently restricted in the vicinity of the equilibrium state.     

Estimation of Transit Origin–Destination Matrices from Passenger Counts Using a Frequency-Based Approach

This paper investigates the transit passenger origin–destination (O–D) estimation problem in congested transit networks where updated passenger counts and outdated O–D matrices are available. The bi-level programming approach is used for the transit passenger O–D estimation problem. The upper level minimizes the sum of error measurements in passenger counts and O–D matrices, and the lower level is a new frequency-based stochastic user equilibrium (SUE) assignment model that can determine simultaneously the passenger overload delays and passenger route choices in congested transit network together with the resultant transit line frequencies. The lower-level problem can be formulated as either a logit-type or probit-type SUE transit assignment problem. A heuristic solution algorithm is developed for solving the proposed bi-level programming model which is applicable to congested transit networks. Finally, a case study on a simplified transit network connecting Kowloon urban area and the Hong Kong International Airport is provided to illustrate the applications of the proposed bi-level programming model and solution algorithm. This revised version was published online in July 2006 with corrections to the Cover Date.     

基于特殊路径的局内车辆路径问题混合策略研究

针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析。     

Gap functions and penalization for solving equilibrium problems with nonlinear constraints

The paper deals with equilibrium problems (EPs) with nonlinear convex constraints. First, EP is reformulated as a global optimization problem introducing a class of gap functions, in which the feasible set of EP is replaced by a polyhedral approximation. Then, an algorithm is given for solving EP through a descent type procedure, which exploits also exact penalty functions, and its global convergence is proved. Finally, the algorithm is tested on a network oligopoly problem with nonlinear congestion constraints.     

ENERGY‐USE CHOICES AND ALLOWANCE TRADING UNDER THE PERSONAL CARBON TRADING SCHEME

Carbon emissions caused by the household sector have become a major contributor to total emissions. Personal carbon trading (PCT), although untested in practice, could potentially be a powerful tool to induce change in consumer behavior. In this paper, we present an optimization model to determine the energy use choices and allowance trading, and a market equilibrium model to obtain the total supply and demand functions of allowances and then to derive the equilibrium allowance price. It is shown that the level of allocated allowance, energy price, emission rate, and transaction costs could influence the equilibrium allowance price and traded volume. Furthermore, the allowance price is affected negatively and slightly by changes in energy prices, so the total energy price variations will be lessened relatively in the PCT scheme. To further demonstrate these relationships, numerical simulations are conducted. On the basis of the simulation results, the implications of this study are discussed and suggestions for future study are provided.     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

信用期下时滞变质品供应链库存和定价的Stackelberg均衡策略

在允许缺货和考虑资金机会成本情况下,根据时滞变质品的基本库存模型,分别构建了信用期下供应商为领导者(SL)和零售商为领导者(RL)的Stackelberg博弈模型。通过分析SL和RL下的Stackelberg博弈模型唯一均衡解,得到两个模型中均衡解的解析表达式。最后,根据数值算例分析得出:(1)在SL供应链中信用期并不总使整个供应链协调,然而在RL供应链中信用期的协调效果较好;(2)延长信用期或增加零售价格均能刺激零售商多订货;(3)在两个模型中,零售价格均随变质时刻递增,且整条供应链达到Pareto改进;(4)SL中供应商变动信用期与RL中零售商变动价格相比,SL供应链收益更高;而当信用期和价格固定,其他参数变动时,RL供应链收益更大。     

Competitive facility location on decentralized supply chains

This paper addresses a novel competitive facility location problem about a firm that intends to enter an existing decentralized supply chain comprised of three tiers of players with competition: manufacturers, retailers and consumers. It first proposes a variational inequality for the supply chain network equilibrium model with production capacity constraints, and then employs the logarithmic-quadratic proximal prediction–correction method as a solution algorithm. Based on this model, this paper develops a generic mathematical program with equilibrium constraints for the competitive facility location problem, which can simultaneously determine facility locations of the entering firm and the production levels of these facilities so as to optimize an objective. Subsequently, a hybrid genetic algorithm that incorporates with the logarithmic-quadratic proximal prediction–correction method is developed for solving the proposed mathematical program with an equilibrium constraint. Finally, this paper carries out some numerical examples to evaluate proposed models and solution algorithms.     

A column generation algorithm for the estimation of origin–destination matrices in congested traffic networks

The general problem of estimating origin–destination (O–D) matrices in congested traffic networks is formulated as a mathematical programme with equilibrium constraints, referred to as the demand adjustment problem (DAP). This approach integrates the O–D matrix estimation and the network equilibrium assignment into one process. In this paper, a column generation algorithm for the DAP is presented. This algorithm iteratively solves a deterministic user equilibrium model for a given O–D matrix and a DAP restricted to the previously generated paths, whose solution generates a new O–D trip matrix estimation. The restricted DAP is formulated via a single level optimization problem. The convergence on local minimum of the proposed algorithm requires only the continuity of the link travel cost functions and the gauges used in the definition of the DAP.     

Sequential Discrete p-Facility Models for Competitive Location Planning

Two new models for duopolistic competitive discrete location planning with sequential acting and variable delivered prices are introduced. If locations and prices are assumed to be set once and for all by the players, the resulting bilevel program is nonlinear. Under the assumption that further price adjustments are possible, i.e., that a Nash equilibrium in prices is reached, the model can be simplified to a linear discrete bilevel formulation. It is shown that in either situation players should not share any locations or markets if they strive for profit-maximization.For the situation with price adjustments, a heuristic solution procedure is suggested. In addition, the bilevel models are shown to serve as a basis from which different well-known location models – as, for example, the p-median problem, the preemptive location problem and the maximum covering problem – can be derived as special cases.     

Heuristic algorithms for delivered price spatially competitive network facility location problems

We review previous formulations of models for locating a firm's production facilities while simultaneously determining production levels at those facilities so as to maximize the firm's profit. We enhance these formulations by adding explicit variables to represent the firm's shipping activities and discuss the implications of this revised approach. In these formulations, existing firms, as well as new entrants, are assumed to act in accordance with an appropriate model of spatial equilibrium. The firm locating new production facilities is assumed to be a large manufacturer entering an industry composed of a large number of small firms. Our previously reported proof of existence of a solution to the combined location-equilibrium problem is briefly reviewed. A heuristic algorithm based on sensitivity analysis methods which presume the existence of a solution and which locally approximate price changes as linear functions of production perturbations resulting from newly established facilities is presented. We provide several numerical tests to illustrate the contrasting locational solutions which this paper's revised delivered price formulation generates relative to those of previous formulations. An exact, although computationally burdensome, method is also presented and employed to check the reliability of the heuristic algorithm.     

Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.