Georgia Institute of Technology College of Sciences

We propose a term structure power price model that, in contrast to widely accepted no-arbitrage based approaches, accounts for the non-storable nature of power. It belongs to a class of equilibrium game theoretic models with players divided into producers and consumers. The consumers' goal is to maximize a mean-variance utility function subject to satisfying an inelastic demand of their own clients (e.g households, businesses etc.) to whom they sell the power. The producers, who own a portfolio of power plants each defined by a running fuel (e.g. gas, coal, oil...) and physical characteristics (e.g. efficiency, capacity, ramp up/down times...), similarly, seek to maximize a mean-variance utility function consisting of power, fuel, and emission prices subject to production constraints. Our goal is to determine the term structure of the power price at which production matches consumption. We show that in such a setting the equilibrium price exists and discuss the conditions for its uniqueness. The model is then extended to account for transaction costs and liquidity considerations in actual trading. Our numerical simulations examine the properties of the term structure and its dependence on various model parameters. We then further extend the model to account for the startup costs of power plants. In contrast to other approaches presented in the literature, we incorporate the startup costs in a mathematically rigorous manner without relying on ad hoc heuristics. Through numerical simulations applied to the entire UK power grid, we demonstrate that the inclusion of startup costs is necessary for the modeling of electricity prices in realistic power systems. Numerical results show that startup costs make electricity prices very spiky. In a final refinement of the model, we include a grid operator responsible for managing the grid. Numerical simulations demonstrate that robust decision making of the grid operator can significantly decrease the number and severity of spikes in the electricity price and improve the reliability of the power grid.

Friday October 23 through Sunday October 25 Emory will host the Georgia Algebraic Geometry symposium featuring the following invited speakers: Valery Alexeev (University of Georgia); Brian Conrad (Stanford University); Brian Lehman (Boston College); Max Lieblich (University of Washington); Alexander Merkurjev (UCLA); Alena Pirutka (Ecole Polytechnique); Aaron Pixton (Harvard University); Tony Varilly-Alvarado (Rice University); Olivier Wittenberg (CNRS - Ecole Normale Superieure).

We resolve an open question from (Christiano, 2014b) posed in COLT'14 regarding the optimal dependency of the regret achievable for online local learning on the size of the label set. In this framework the algorithm is shown a pair of items at each step, chosen from a set of n items. The learner then predicts a label for each item, from a label set of size L and receives a real valued payoff. This is a natural framework which captures many interesting scenarios such as collaborative filtering, online gambling, and online max cut among others. (Christiano, 2014a) designed an efficient online learning algorithm for this problem achieving a regret of O((nL^3T)^(1/2)), where T is the number of rounds. Information theoretically, one can achieve a regret of O((n log LT)^(1/2)). One of the main open questions left in this framework concerns closing the above gap. In this work, we provide a complete answer to the question above via two main results. We show, via a tighter analysis, that the semi-definite programming based algorithm of (Christiano, 2014a), in fact achieves a regret of O((nLT)^(1/2)). Second, we show a matching computational lower bound. Namely, we show that a polynomial time algorithm for online local learning with lower regret would imply a polynomial time algorithm for the planted clique problem which is widely believed to be hard. We prove a similar hardness result under a related conjecture concerning planted dense subgraphs that we put forth. Unlike planted clique, the planted dense subgraph problem does not have any known quasi-polynomial time algorithms. Computational lower bounds for online learning are relatively rare, and we hope that the ideas developed in this work will lead to lower bounds for other online learning scenarios as well. Joint work with Pranjal Awasthi, Moses Charikar, and Andrej Risteski at Princeton.